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

Hong，Wenjing1,2; Liu，Tonglin3

2022

10.1109/ACCESS.2022.3140783

IEEE Access   影响因子和分区

2169-3536

2169-3536

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.

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

SCI ; EI

英语

第一 ; 通讯

WOS:000744485900001

20220311480242

Deep neural networks ; Heuristic methods ; Iterative methods ; Job analysis ; Learning algorithms ; Optimization ; Program processors

Ergonomics and Human Factors Engineering:461.4 ; Computer Programming:723.1 ; Machine Learning:723.4.2 ; Optimization Techniques:921.5 ; Numerical Methods:921.6

2-s2.0-85122887614

Scopus

1.Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China
2.Guangdong-Hong Kong-Macao Greater Bay Area,Center for Brain Science and Brain-Inspired Intelligence,Guangzhou,510515,China
3.Science and Technology on Complex System Control and Intelligent Agent Cooperation Laboratory,Beijing Electro-Mechanical Engineering Institute,Beijing,100074,China

Hong，Wenjing,Liu，Tonglin. Faster Capacitated Arc Routing: A Sequence-to-Sequence Approach[J]. IEEE Access,2022,10:4777-4785.

Hong，Wenjing,&Liu，Tonglin.(2022).Faster Capacitated Arc Routing: A Sequence-to-Sequence Approach.IEEE Access,10,4777-4785.

Hong，Wenjing,et al."Faster Capacitated Arc Routing: A Sequence-to-Sequence Approach".IEEE Access 10(2022):4777-4785.