Direction-aware deep policy learning for efficient capacitated arc routing

Line coverage of urban-scale routes by multiple vehicles can be formulated as the Capacitated Arc Routing Problem (CARP). Early solutions, including constructive heuristics, meta-heuristics, and exact algorithms, struggle to achieve efficient runtimes. Recently, neural network (NN)-based methods have emerged as promising alternatives for efficiently solving CARP; however, their solution quality significantly lags behind non-NN approaches. This significant gap mainly results from the inappropriate modeling and learning of non-Euclidean graphs, traversal direction and capacity constraints. In this paper, we introduce an NN-based solver tailored for these complexities, which significantly narrows the gap with advanced meta-heuristics while achieving much shorter runtimes. First, we propose the direction-aware attention model (DaAM) to incorporate directionality into the embedding process, facilitating more effective one-stage decision-making. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy for subsequent reinforcement fine-tuning. It proves particularly valuable for solving CARP that has a higher complexity than the node routing problems (NRPs). Finally, a path optimization method is introduced to adjust the depot return positions within the path generated by DaAM. Experiments show that DaAM surpasses constructive heuristics and achieves decision quality comparable to state-of-the-art meta-heuristics for the first time while maintaining superior efficiency, even in large-scale CARP instances. The code and datasets are provided in the link and will be released on GitHub.

Authors

• Feng Xue
• Runze Guo
• Anlong Ming Beijing University of Posts and Telecommunications
• Nicu Sebe Department of Information Engineering and Computer Science, University of Trento, Italy

Keywords

• Capacitated Arc Routing Problem
• Direction-aware attention model
• Supervised reinforcement learning
• Multi-vehicle routing
• Urban road coverage