Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

7-2023

Abstract

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.

Keywords

capacitated vehicle routing problem, Clockwise clustering, imitation learning, improvement learning, reinforcement learning

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Transportation

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS 2023): Prague, July 8-13

First Page

1

Last Page

9

Identifier

10.1609/icaps.v33i1.27236

Publisher

AAAI Press

City or Country

Palo Alto, CA

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1609/icaps.v33i1.27236

Download

Share

COinS