Imitation improvement learning for large-scale capacitated vehicle routing problems

• Main Authors: BUI, The Viet, MAI, Tien
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: capacitated vehicle routing problem; Clockwise clustering; imitation learning; improvement learning; reinforcement learning; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering; Transportation
• Online Access: https://ink.library.smu.edu.sg/sis_research/8025; https://ink.library.smu.edu.sg/context/sis_research/article/9028/viewcontent/main__2_.pdf
• Institution: Singapore Management University

Recent works using deep reinforcement learning (RL) to solve routing problems such as the capacitated vehicle routing problem (CVRP) have focused on improvement learning-based methods, which involve improving a given solution until it becomes near-optimal. Although adequate solutions can be achieved for small problem instances, their efficiency degrades for large-scale ones. In this work, we propose a newimprovement learning-based framework based on imitation learning where classical heuristics serve as experts to encourage the policy model to mimic and produce similar or better solutions. Moreover, to improve scalability, we propose Clockwise Clustering, a novel augmented framework for decomposing large-scale CVRP into subproblems by clustering sequentially nodes in clockwise order, and then learningto solve them simultaneously. Our approaches enhance state-of-the-art CVRP solvers while attaining competitive solution quality on several well-known datasets, including real-world instances with sizes up to 30,000 nodes. Our best methods are able to achieve new state-of-the-art results for several largeinstances and generalize to a wide range of CVRP variants and solvers. We also contribute new datasets and results to test the generalizability of our deep RL algorithms.