A phase i simplex method for finding Feasible periodic timetables

Goerigk M, Schöbel A, Spühler F (2021)

Publication Type: Conference contribution

Publication year: 2021

Journal

OASIcs : OpenAccess Series in Informatics Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

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

Book Volume: 96

Conference Proceedings Title: OpenAccess Series in Informatics

Event location: Virtual, Lisbon, PRT

ISBN: 9783959772136

DOI: 10.4230/OASIcs.ATMOS.2021.6

Abstract

The periodic event scheduling problem (PESP) with various applications in timetabling or traffic light scheduling is known to be challenging to solve. In general, it is already NP-hard to find a feasible solution. However, depending on the structure of the underlying network and the values of lower and upper bounds on activities, this might also be an easy task. In this paper we make use of this property and suggest phase I approaches (similar to the well-known phase I of the simplex algorithm) to find a feasible solution to PESP. Given an instance of PESP, we define an auxiliary instance for which a feasible solution can easily be constructed, and whose solution determines a feasible solution of the original instance or proves that the original instance is not feasible. We investigate different possibilities on how such an auxiliary instance can be defined theoretically and experimentally. Furthermore, in our experiments we compare different solution approaches for PESP and their behavior in the phase I approach. The results show that this approach can be especially helpful if the instance admits a feasible solution, while it is generally outperformed by classic mixed-integer programming formulations when the instance is infeasible.

Involved external institutions

Universität Siegen DE Germany (DE) Technische Universität Kaiserslautern DE Germany (DE) Technische Universität Braunschweig DE Germany (DE)

How to cite

APA:

Goerigk, M., Schöbel, A., & Spühler, F. (2021). A phase i simplex method for finding Feasible periodic timetables. In Matthias Muller-Hannemann, Federico Perea (Eds.), OpenAccess Series in Informatics. Virtual, Lisbon, PRT: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.

MLA:

Goerigk, Marc, Anita Schöbel, and Felix Spühler. "A phase i simplex method for finding Feasible periodic timetables." Proceedings of the 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2021, Virtual, Lisbon, PRT Ed. Matthias Muller-Hannemann, Federico Perea, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021.

BibTeX: Download