文献类型：期刊文献

英文题名：Distance Constrained Vehicle Routing Problem to Minimize the Total Cost

作者：Yu, Wei[1]; Liu, Zhaohui[1]; Bao, Xiaoguang[2]

机构：[1] Department of Mathematics, East China University of Science and Technology, Shanghai, 200237, China; [2] College of Information Technology, Shanghai Ocean University, Shanghai, 201306, China

年份：2019

卷号：11653 LNCS

起止页码：639

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

收录：EI(收录号：20193207287478)

基金：Acknowledgements. This research is supported by the National Natural Science Foundation of China under grants numbers 11671135, 11701363, the Natural Science Foundation of Shanghai under grant number 19ZR1411800 and the Fundamental Research Fund for the Central Universities under grant number 22220184028.

语种：英文

外文关键词：Routing algorithms - Undirected graphs - Approximation algorithms - Trees (mathematics) - Vehicles

摘要：Given (Formula Presented), an undirected complete graph G = (V,E) with nonnegative edge-weight function obeying the triangle inequality and a depot vertex (Formula Presented), a set (Formula Presented) of cycles is called a λ-bounded r-cycle cover if (Formula Presented) and each cycle Ci contains r and has a length of at most λ. The Distance Constrained Vehicle Routing Problem with the objective of minimizing the total cost (DVRP-TC) aims to find a λ-bounded r-cycle cover (Formula Presented) such that the sum of the total length of the cycles and γk is minimized, where γ is an input indicating the assignment cost of a single cycle. For DVRP-TC on tree metric, we show a 2-approximation algorithm that is implied by the existing results and give an LP relaxation whose integrality gap has an upper bound of 5/2. In particular, when γ=0 we prove that this bound can be improved to 2. For the unrooted version of DVRP-TC, we devise a 5-approximation algorithm and show that a natural set-covering LP relaxation has a constant integrality gap of 25 using the rounding procedure given by Nagarajan and Ravi (2008). ? Springer Nature Switzerland AG 2019.