TY - GEN
T1 - An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees
AU - Dufay, Marc
AU - Mathieu, Claire
AU - Zhou, Hang
N1 - Publisher Copyright:
© Marc Dufay, Claire Mathieu, and Hang Zhou.
PY - 2023/3/1
Y1 - 2023/3/1
N2 - In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of n terminals, and a distance constraint D. The goal is to find a minimum number of tours starting and ending at the depot such that those tours together cover all the terminals and the length of each tour is at most D. The DVRP on trees is of independent interest, because it is equivalent to the “virtual machine packing” problem on trees studied by Sindelar et al. [SPAA’11]. We design a simple and natural approximation algorithm for the tree DVRP, parameterized by ε > 0. We show that its approximation ratio is α + ε, where α ≈ 1.691, and in addition, that our analysis is essentially tight. The running time is polynomial in n and D. The approximation ratio improves on the ratio of 2 due to Nagarajan and Ravi [Networks’12]. The main novelty of this paper lies in the analysis of the algorithm. It relies on a reduction from the tree DVRP to the bounded space online bin packing problem via a new notion of “reduced length”.
AB - In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of n terminals, and a distance constraint D. The goal is to find a minimum number of tours starting and ending at the depot such that those tours together cover all the terminals and the length of each tour is at most D. The DVRP on trees is of independent interest, because it is equivalent to the “virtual machine packing” problem on trees studied by Sindelar et al. [SPAA’11]. We design a simple and natural approximation algorithm for the tree DVRP, parameterized by ε > 0. We show that its approximation ratio is α + ε, where α ≈ 1.691, and in addition, that our analysis is essentially tight. The running time is polynomial in n and D. The approximation ratio improves on the ratio of 2 due to Nagarajan and Ravi [Networks’12]. The main novelty of this paper lies in the analysis of the algorithm. It relies on a reduction from the tree DVRP to the bounded space online bin packing problem via a new notion of “reduced length”.
KW - approximation algorithms
KW - distance constraint
KW - trees
KW - vehicle routing
U2 - 10.4230/LIPIcs.STACS.2023.27
DO - 10.4230/LIPIcs.STACS.2023.27
M3 - Conference contribution
AN - SCOPUS:85149821756
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
A2 - Berenbrink, Petra
A2 - Bouyer, Patricia
A2 - Dawar, Anuj
A2 - Kante, Mamadou Moustapha
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023
Y2 - 7 March 2023 through 9 March 2023
ER -