Exact and Approximation Algorithms for the Multi-Depot Capacitated Arc Routing Problems  

作　　者：Wei Yu Yujie Liao Yichen Yang 

机构地区：[1]School of Mathematics,East China University of Science and Technology,Shanghai 200237,China [2]Sabre Lab Research Team,Sabre Inc.,Southlake,TX 76092,USA

出　　处：《Tsinghua Science and Technology》2023年第5期916-928,共13页清华大学学报（自然科学版（英文版）

基　　金：supported by the National Natural Science Foundation of China(Nos.11671135,11871213,11901255);the Natural Science Foundation of Shanghai(No.19ZR1411800)。

摘　　要：In this work,we investigate a generalization of the classical capacitated arc routing problem,called the Multi-depot Capacitated Arc Routing Problem(MCARP).We give exact and approximation algorithms for different variants of the MCARP.First,we obtain the first constant-ratio approximation algorithms for the MCARP and its nonfixed destination version.Second,for the multi-depot rural postman problem,i.e.,a special case of the MCARP where the vehicles have infinite capacity,we develop a(2-1/2k+1)-approximation algorithm(k denotes the number of depots).Third,we show the polynomial solvability of the equal-demand MCARP on a line and devise a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line.Lastly,we conduct extensive numerical experiments on the algorithms for the multi-depot rural postman problem to show their effectiveness.

关 键 词：approximation algorithm MULTI-DEPOT vehicle routing problem arc routing problem rural postman problem 

分 类 号：TN9[电子电信—信息与通信工程]