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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Mariem Ayari,
  • Sonia Nasri,
  • Hend Bouziri,
  • Wassila Aggoune-Mtalaa

摘要

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.