2026-07-23T16:36:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14875 2024-03-06T10:31:35Z ddc:004 open_access

A Phase I Simplex Method for Finding Feasible Periodic Timetables Goerigk, Marc Schöbel, Anita Spühler, Felix train timetable optimization periodic event scheduling problem modulo simplex 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marc Goerigk and Anita Schöbel and Felix Spühler 2021 Is Part Of OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2021.6 urn:nbn:de:0030-drops-148753 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.6 eng https://creativecommons.org/licenses/by/4.0/legalcode