EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

353. Exact and approximation algorithms for routing a convoy through a graph

Invited abstract in session MA-25: Discrete, continuous or stochastic optimization and control in networks, transportation and design I , stream Combinatorial Optimization.

Monday, 8:30-10:00
Room: 011 (building: 208)

Authors (first author is the speaker)

1. Martijn van Ee
Faculty of Military Sciences, Netherlands Defence Academy
2. Tim Oosterwijk
Operations Analytics, Vrije Universiteit Amsterdam
3. René Sitters
Vrije Universiteit Amsterdam and CWI
4. Andreas Wiese
Mathematics, Technical University of Munich

Abstract

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 using dynamic programming. 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.

Keywords

Status: accepted

Back to the list of papers