An Improved Algorithm for the Periodic Timetabling Problem

  • We consider the computation of periodic timetables, which is a key task in the service design process of public transportation companies. We propose a new approach for solving the periodic timetable optimisation problem. It consists of a (partially) heuristic network aggregation to reduce the problem size and make it accessible to standard mixed-integer programming (MIP) solvers. We alternate the invocation of a MIP solver with the well-known problem specific modulo network simplex heuristic (ModSim). This iterative approach helps the ModSim-method to overcome local minima efficiently, and provides the MIP solver with better initial solutions. Our computational experiments are based on the 16 railway instances of the PESPlib, which is the only currently available collection of periodic event scheduling problem instances. For each of these instances, we are able to reduce the objective values of previously best known solutions by at least 10.0%, and up to 22.8% with our iterative combined method.

Download full text files

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author:Goerigk Marc, Christian LiebchenORCiDGND
URN:urn:nbn:de:kobv:526-opus4-9899
DOI (Version of Record):https://doi.org/10.4230/OASIcs.ATMOS.2017.12
ISBN:978-3-95977-042-2
Parent Title (English):17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Publisher:Schloss Dagstuhl / Leibniz-Zentrum für Informatik
Place of publication:Dagstuhl
Editor:Gianlorenzo D'Angelo, Twan Dollevoet
Document Type:Part of a Book
Language:English
Year of Publication:2017
Publishing Institution:Technische Hochschule Wildau
Release Date:2017/09/14
Tag:modulo network simplex; periodic event scheduling problem; periodic timetabling; railway optimisation
First Page:12:1
Last Page:12:14
Source:Goerigk, M., & Liebchen, C. (2017). An Improved Algorithm for the Periodic Timetabling Problem. In Gianlorenzo D’Angelo, & Twan Dollevoet (Eds.), 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). (pp. 12:1-12:14). Dagstuhl, Germany: Schloss Dagstuhl / Leibniz-Zentrum für Informatik.
Faculties an central facilities:Fachbereich Ingenieur- und Naturwissenschaften
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 005 Computerprogrammierung, Programme, Daten
3 Sozialwissenschaften / 38 Handel, Kommunikation, Verkehr / 385 Schienenverkehr
Licence (German):Creative Commons - CC BY 3.0 - Namensnennung 3.0 Unported
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.