摘要详情

ID / 提交时间

138 / 2023-09-20 23:05:11

标题

Learning to Optimize Vehicle Routes Problem: A Two-Stage Hybrid Reinforcement Learning

关键字

vehicle routing problem,imitation learning,deep reinforcement learning

主题及专题

Special Sessions > SS04 - Application of Computational Intelligence in Manufacturing and Logistics

状态

终稿

作者

Wenqiang Zhang / Henan University of Technology

Xiaomeng Wang / Henan University of Technology

摘要

The Vehicle Routing Problem (VRP) is a typical combinatorial optimization problem, aiming to determine the optimal customer visit routes while minimizing the total cost under certain constraints. However, for solving large-scale VRP instances, traditional heuristic optimization algorithms could hardly meet the demands of both solution accuracy and computational efficiency. Thus learning-based methods have recently garnered more attention. Some work attempts to solve the problems by reinforcement learning methods, which suffer from slow convergence issues during training and are still not accurate enough regarding the solutions. To that end, this paper proposes a two-stage hybrid algorithm based on imitation learning and reinforcement learning for solving the vehicle routing problem. Firstly, we introduce a novel imitation learning framework, where classical heuristic methods are treated as experts to encourage policy models to mimic and generate similar or better solutions. which accelerates the convergence more stably and accurately. Secondly, by employing deep reinforcement learning methods, we further train neural networks to improve their performance in generating superior solutions. Experimental results demonstrate that our approach exhibits significant performance improvements on multiple instances of vehicle routing problems, outperforming a wide range of baselines and getting results close to highly optimized and specialized algorithms. Additionally, our method possesses a degree of generalization capability, allowing it to adapt to vehicle routing problems of varying scales.