Faster Capacitated Arc Routing: A Sequence-to-Sequence Approach

Abstract

The Capacitated Arc Routing Problem (CARP) is an NP-hard optimization problem that has been investigated for decades. Heuristic search methods are commonly used to solve it. However, given a CARP instance, most heuristic search algorithms require plenty of time to iteratively search for the solution from scratch, and hence may be impractical for emerging applications that need a solution to be obtained in a very short time period. In this work, a novel approach to efficiently solve CARP is presented. The proposed approach replaces the heuristic search process with the inference phase of a trained Deep Neural Network (DNN), which is trained to take a CARP instance as the input and outputs a solution to the instance. In this way, CARP could be solved by a direct mapping rather than by iterative search, and hence could be more efficient and more easily accelerated by the use of GPUs. Empirical study shows that the DNN-based solver can achieve significant speed-up with minor performance loss, and up to hundreds of times acceleration in extreme cases.

Keywords

• Capacitated arc routing problem
• sequence-to-sequence
• deep neural network