@inproceedings{ba367f049b7c4b8993f05c8cd9ba9094,
title = "Complexity of Fixed Order Routing",
abstract = "We consider the classic Vehicle Routing Problem with the additional property that all requests are ordered and the subtour of each server (or vehicle) must obey the fixed order. A scheduling version of this problem was introduced by Bosman et al. (2019). We study several metric spaces and objective functions and our results show that in some settings such a fixed order simplifies the problem, while in others it makes an easy problem become NP-hard. For general metrics, we show that c-capacitated VRP remains APX-hard in the fixed order setting for c=3 and show that the well-known iterated tour partitioning algorithm yields a (2-1/c)-approximation. When all points are on the line, we show that the fixed order restriction makes VRP NP-hard to solve for minimizing total completion time or maximum completion time, in contrast to standard VRP. We also sketch how to obtain a PTAS in these settings for general metrics.",
keywords = "Approximation Algorithms, Complexity, Routing",
author = "Steven Miltenburg and Tim Oosterwijk and Ren{\'e} Sitters",
note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 22nd International Workshop on Approximation and Online Algorithms, WAOA 2024 ; Conference date: 05-09-2024 Through 06-09-2024",
year = "2025",
doi = "10.1007/978-3-031-81396-2_13",
language = "English",
isbn = "9783031813955",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "183--197",
editor = "Marcin Bie{\'n}kowski and Matthias Englert",
booktitle = "Approximation and Online Algorithms",
}