Optimizing Vehicle Routing in the Dial-a-Ride Problem Using Deep Q-Networks

Authors

Ayari M., Nasri S., Bouziri H., Aggoune-Mtalaa W.

Reference

Communications in Computer and Information Science, vol. 2482 CCIS, pp. 281-300, 2026

Description

In this paper, we propose an enhanced approach to the Deep Q-Network (DQN) for solving the Dial-a-Ride Problem (DARP), a challenging vehicle routing problem. We introduce a hybrid method that combines an insertion heuristic with reinforcement learning to generate initial solutions, which are formulated into a Markov Decision Process (MDP). Our enhanced DQN framework involves past experiences to iteratively improve decision quality and optimize vehicle routes. By integrating problem-specific heuristics and reinforcement learning, our method achieves superior performance compared to the insertion heuristic. Experimental results show that the proposed approach significantly improves vehicle route optimization, providing better overall efficiency for the tested DARP instances. The key advantage of IBRL-DARP lies in its ability to adapt and learn from the problem environment, making intelligent decisions that improve over time. IBRL-DARP demonstrates superior performance in most instances, as evidenced by the lower total travel cost values. This improvement is particularly notable in larger problem instances where heuristic methods tend to underperform due to their reliance on predefined rules. Its robustness across a range of DARP instances highlights its potential as a practical solution for real-world transport-on-demand applications.

Link

doi:10.1007/978-3-031-93601-2_18