文献类型：期刊文献

英文题名：Approximation and Polynomial Algorithms for Multi-depot Capacitated Arc Routing Problems

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

机构：[1] School of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2022

卷号：13148 LNCS

起止页码：93

外文期刊名：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

收录：EI(收录号：20221511942516)

语种：英文

外文关键词：Graph theory - Polynomial approximation - Routing algorithms - Vehicle routing - Vehicles

摘要：We study the multi-depot capacitated arc routing problem (MCARP), which generalizes the classical arc routing problem to the more realistic situation with multiple depots. We propose approximation and polynomial algorithms for different variants of the MCARP. First, we present the first constant-factor approximation algorithms for the MCARP and the nonfixed destination variant. Second, for a restricted case of the MCARP with infinite vehicle capacity, called the multi-depot rural postman problem, we devise a (2-12k+1) -approximation algorithm with k indicating the number of depots. Lastly, we show that the equal-demand MCARP defined on a line graph is polynomially solvable and develop a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a line. ? 2022, Springer Nature Switzerland AG.