TY - GEN
T1 - Capacitated Vehicle Routing in Graphic Metrics
AU - Mömke, Tobias
AU - Zhou, Hang
N1 - Publisher Copyright:
Copyright © 2023 by SIAM.
PY - 2023/1/1
Y1 - 2023/1/1
N2 - We study the capacitated vehicle routing problem in graphic metrics (graphic CVRP). Our main contribution is a new lower bound on the cost of an optimal solution. For graphic metrics, this lower bound is tight and significantly stronger than the well-known bound for general metrics. The proof of the new lower bound is simple and combinatorial. Using this lower bound, we analyze the approximation ratio of the classical iterated tour partitioning algorithm combined with the TSP algorithms for graphic metrics of Christofides [1976], of Mömke-Svensson [JACM 2016], and of Sebő-Vygen [Combinatorica 2014]. In particular, we obtain a 1.95-approximation for the graphic CVRP.
AB - We study the capacitated vehicle routing problem in graphic metrics (graphic CVRP). Our main contribution is a new lower bound on the cost of an optimal solution. For graphic metrics, this lower bound is tight and significantly stronger than the well-known bound for general metrics. The proof of the new lower bound is simple and combinatorial. Using this lower bound, we analyze the approximation ratio of the classical iterated tour partitioning algorithm combined with the TSP algorithms for graphic metrics of Christofides [1976], of Mömke-Svensson [JACM 2016], and of Sebő-Vygen [Combinatorica 2014]. In particular, we obtain a 1.95-approximation for the graphic CVRP.
M3 - Conference contribution
AN - SCOPUS:85193352058
T3 - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
SP - 114
EP - 123
BT - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
A2 - Kavitha, Telikepalli
A2 - Mehlhorn, Kurt
PB - Society for Industrial and Applied Mathematics Publications
T2 - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
Y2 - 23 January 2023 through 25 January 2023
ER -