Network planning and routing problems over time: Models, complexity and algorithms

Glomb L, Hoch B, Liers F, Rösel F (2021)

Publication Type: Conference contribution

Publication year: 2021

Journal

Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Book Volume: 204

Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs

Event location: Lisbon

ISBN: 9783959772044

DOI: 10.4230/LIPIcs.ESA.2021.1

Abstract

In this invited contribution for ESA 2021, we will study the complexity of and algorithms for network optimization tasks with a timing component. They occur, for example, in planning or routing problems that need to be solved repeatedly over time. Typically, already simplified versions of such problems are NP-hard. In addition, the instances typically are too large to be solved straight-forwardly on a time-expanded graph. After an introduction into the area, we state the problem of determining best possible non-stop trajectories in a network that are not allowed to cross at any point in time. For simplified settings, polynomial-time solution approaches are presented whereas already for restricted settings the problems are shown to be NP-hard. When moving to more complex and more realistic settings as they occur, for example, in determining non-stop disjoint trajectories for a set of aircraft, we present heuristic algorithms that adaptively refine coarse disjoint trajectories in the timing dimension. In order to be able to solve the non-stop disjoint trajectories problem over time, the method is integrated in a rolling-horizon algorithm. We present computational results for realistic settings. Motivated by the fact that rolling-horizon approaches are often applied in practice without knowledge on the quality of the obtained solutions, we study this problem from an abstract point of view. In fact, we more abstractly analyze the solution quality of general rolling-horizon algorithms for optimization tasks that show a timing component. We apply it to different planning problems. We end by pointing out some challenges and possibilities for future research.

Authors with CRIS profile

How to cite

APA:

Glomb, L., Hoch, B., Liers, F., & Rösel, F. (2021). Network planning and routing problems over time: Models, complexity and algorithms. In Petra Mutzel, Rasmus Pagh, Grzegorz Herman (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Lisbon, PT: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.

MLA:

Glomb, Lukas, et al. "Network planning and routing problems over time: Models, complexity and algorithms." Proceedings of the 29th Annual European Symposium on Algorithms, ESA 2021, Lisbon Ed. Petra Mutzel, Rasmus Pagh, Grzegorz Herman, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021.

BibTeX: Download