Location
Hilton Waikoloa Village, Hawaii
Event Website
https://hicss.hawaii.edu/
Start Date
7-1-2025 12:00 AM
End Date
10-1-2025 12:00 AM
Description
The Multi-Vehicle Dial-a-Ride Problem (MVDARP) consists of routing a fixed number of capacitated vehicles from their initial positions to multiple pick-up locations and, subsequently, to the delivery depots, while minimising the overall costs of the transportation. In this paper, we propose an extended version of the MVDARP which considers multiple consecutive routes: the Multi-Route Multi-Vehicle Dial-a-Ride Problem (MRMVDARP). In this case, a scalarized multi-objective MIP formulation, addressing at the same time the costs of the routing and the duration of the job, is examined together with a Markov Decision Process (MDP) conceptualisation. Thus, the results found using an exact solver applied to the former problem are compared to the solutions of the MDP achieved by Q-learning. The computational experiments tested in small grid-world environments show that the performance of the Reinforcement Learning algorithm outperforms the exact solver in the larger maps tested. This preliminary evaluation indicates a promising research direction that could be explored in the future.
Recommended Citation
Triebold, Philipp; Milani, Rudy; and Pickl, Stefan, "Multi-Route Multi-Vehicle Dial-a-Ride Problem: A Comparison Study" (2025). Hawaii International Conference on System Sciences 2025 (HICSS-58). 2.
https://aisel.aisnet.org/hicss-58/da/supply_chain/2
Multi-Route Multi-Vehicle Dial-a-Ride Problem: A Comparison Study
Hilton Waikoloa Village, Hawaii
The Multi-Vehicle Dial-a-Ride Problem (MVDARP) consists of routing a fixed number of capacitated vehicles from their initial positions to multiple pick-up locations and, subsequently, to the delivery depots, while minimising the overall costs of the transportation. In this paper, we propose an extended version of the MVDARP which considers multiple consecutive routes: the Multi-Route Multi-Vehicle Dial-a-Ride Problem (MRMVDARP). In this case, a scalarized multi-objective MIP formulation, addressing at the same time the costs of the routing and the duration of the job, is examined together with a Markov Decision Process (MDP) conceptualisation. Thus, the results found using an exact solver applied to the former problem are compared to the solutions of the MDP achieved by Q-learning. The computational experiments tested in small grid-world environments show that the performance of the Reinforcement Learning algorithm outperforms the exact solver in the larger maps tested. This preliminary evaluation indicates a promising research direction that could be explored in the future.
https://aisel.aisnet.org/hicss-58/da/supply_chain/2