Multi-Route Multi-Vehicle Dial-a-Ride Problem: A Comparison Study

Abstract

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.