TY - GEN
T1 - Exact and Approximation Algorithms for Routing a Convoy Through a Graph
AU - van Ee, Martijn
AU - Oosterwijk, Tim
AU - Sitters, René
AU - Wiese, Andreas
N1 - Publisher Copyright:
© Martijn van Ee, Tim Oosterwijk, René Sitters, and Andreas Wiese;
PY - 2023/8
Y1 - 2023/8
N2 - We study routing problems of a convoy in a graph, generalizing the shortest path problem (SPP), the travelling salesperson problem (TSP), and the Chinese postman problem (CPP) which are all well-studied in the classical (non-convoy) setting. We assume that each edge in the graph has a length and a speed at which it can be traversed and that our convoy has a given length. While the convoy moves through the graph, parts of it can be located on different edges. For safety requirements, at all time the whole convoy needs to travel at the same speed which is dictated by the slowest edge on which currently a part of the convoy is located. For Convoy-SPP, we give a strongly polynomial time exact algorithm. For Convoy-TSP, we provide an O(log n)-approximation algorithm and an O(1)-approximation algorithm for trees. Both results carry over to Convoy-CPP which – maybe surprisingly – we prove to be NP-hard in the convoy setting. This contrasts the non-convoy setting in which the problem is polynomial time solvable.
AB - We study routing problems of a convoy in a graph, generalizing the shortest path problem (SPP), the travelling salesperson problem (TSP), and the Chinese postman problem (CPP) which are all well-studied in the classical (non-convoy) setting. We assume that each edge in the graph has a length and a speed at which it can be traversed and that our convoy has a given length. While the convoy moves through the graph, parts of it can be located on different edges. For safety requirements, at all time the whole convoy needs to travel at the same speed which is dictated by the slowest edge on which currently a part of the convoy is located. For Convoy-SPP, we give a strongly polynomial time exact algorithm. For Convoy-TSP, we provide an O(log n)-approximation algorithm and an O(1)-approximation algorithm for trees. Both results carry over to Convoy-CPP which – maybe surprisingly – we prove to be NP-hard in the convoy setting. This contrasts the non-convoy setting in which the problem is polynomial time solvable.
KW - approximation algorithms
KW - convoy routing
KW - shortest path problem
KW - traveling salesperson problem
UR - http://www.scopus.com/inward/record.url?scp=85171484142&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2023.86
DO - 10.4230/LIPIcs.MFCS.2023.86
M3 - Conference contribution
AN - SCOPUS:85171484142
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
A2 - Leroux, Jerome
A2 - Lombardy, Sylvain
A2 - Peleg, David
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
Y2 - 28 August 2023 through 1 September 2023
ER -