TY - GEN
T1 - Unsplittable Euclidean Capacitated Vehicle Routing
T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
AU - Grandoni, Fabrizio
AU - Mathieu, Claire
AU - Zhou, Hang
N1 - Publisher Copyright:
© Fabrizio Grandoni, Claire Mathieu, and Hang Zhou; licensed under Creative Commons License CC-BY 4.0.
PY - 2023/1/1
Y1 - 2023/1/1
N2 - In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. Our main result is a polynomial-time (2 + ϵ)-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].
AB - In the unsplittable capacitated vehicle routing problem, we are given a metric space with a vertex called depot and a set of vertices called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the depot such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. Our main result is a polynomial-time (2 + ϵ)-approximation algorithm for this problem in the two-dimensional Euclidean plane, i.e., for the special case where the terminals and the depot are associated with points in the Euclidean plane and their distances are defined accordingly. This improves on recent work by Blauth, Traub, and Vygen [IPCO'21] and Friggstad, Mousavi, Rahgoshay, and Salavatipour [IPCO'22].
KW - Euclidean plane
KW - approximation algorithms
KW - capacitated vehicle routing
UR - https://www.scopus.com/pages/publications/85147549122
U2 - 10.4230/LIPIcs.ITCS.2023.63
DO - 10.4230/LIPIcs.ITCS.2023.63
M3 - Conference contribution
AN - SCOPUS:85147549122
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023
A2 - Kalai, Yael Tauman
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 10 January 2023 through 13 January 2023
ER -