文献类型：期刊文献

英文题名：Exact and Approximation Algorithms for the Multi-Depot Capacitated Arc Routing Problems

作者：Yu, Wei[1];Liao, Yujie[1];Yang, Yichen[2]

机构：[1]East China Univ Sci & Technol, Sch Math, Shanghai 200237, Peoples R China;[2]Sabre Inc, Sabre Lab Res Team, Southlake, TX 76092 USA

年份：2023

卷号：28

期号：5

起止页码：916

外文期刊名：TSINGHUA SCIENCE AND TECHNOLOGY

收录：;EI(收录号：20232314187232);WOS:【SCI-EXPANDED(收录号:WOS:001062465800003)】；

基金：The authors are grateful to the anonymous referees for their valuable and constructive comments. This research was supported by the National Natural Science Foundation of China (Nos. 11671135, 11871213, and 11901255), and the Natural Science Foundation of Shanghai (No. 19ZR1411800).

语种：英文

外文关键词：approximation algorithm; multi-depot; vehicle routing problem; arc routing problem; rural postman problem

摘要：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.