文献类型：期刊文献

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

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

机构：[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

年份：2023

卷号：28

期号：5

起止页码：916

中文期刊名：Tsinghua Science and Technology

外文期刊名：清华大学学报（自然科学版（英文版）

收录：CSTPCD;;Scopus;CSCD:【CSCD2023_2024】；PubMed;

基金：supported by the National Natural Science Foundation of China(Nos.11671135,11871213,11901255);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.