×

Separation of cycle inequalities in periodic timetabling. (English) Zbl 1474.90136

Summary: Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem in public transport. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we contribute a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. Moreover, we provide several NP-completeness results, indicating that pseudo-polynomial time is best possible. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.

MSC:

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90B06 Transportation, logistics and supply chain management
90B20 Traffic problems in operations research

Software:

lop.gms; PESPLib
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Serafini, P.; Ukovich, W., A mathematical model for periodic scheduling problems, SIAM J. Discrete Math., 2, 4, 550-581 (1989) · Zbl 0676.90030
[2] Nachtigall, K., Periodic Network Optimization and Fixed Interval Timetables (1998), Universität Hildesheim, (Habilitation thesis)
[3] Lindner, T., Train Schedule Optimization in Public Rail Transport (2000), Technische Universität Braunschweig, (Ph.D. thesis) · Zbl 1048.90114
[4] Liebchen, C., Periodic Timetable Optimization in Public Transport (2006), Technische Universität Berlin, URL: http://www.dissertation.de · Zbl 1209.90095
[5] Schrijver, A., Routing and timetabling by topological search, Doc. Math., 1998, 1-9 (1998), Extra Volume ICM
[6] Nachtigall, K.; Opitz, J., Solving periodic timetable optimisation problems by modulo simplex calculations, (Fischetti, M.; Widmayer, P., ATMOS’08, Vol. 9 (2008)) · Zbl 1247.90160
[7] Liebchen, C.; Peeters, L., Integral cycle bases for cyclic timetabling, Discrete Optim., 6, 98-109 (2009) · Zbl 1160.90640
[8] Kümmling, M.; Großmann, P.; Nachtigall, K.; Opitz, J.; Weiß, R., A state-of-the-art realization of cyclic railway timetable computation, Public Transp., 7, 3, 281-293 (2015)
[9] Liebchen, C.; Swarat, E., The second chvatal closure can yield better railway timetables, (Fischetti, M.; Widmayer, P., 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’08). 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’08), OpenAccess Series in Informatics (OASIcs), vol. 9 (2008), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik Dagstuhl, Germany) · Zbl 1247.90056
[10] M.A. Odijk, Construction of periodic timetables, part 1: A cutting plane algorithm. Technical Report 94-61, TU Delft, 1994.
[11] Peeters, L. W.P., Cyclic Railway and Timetable Optimization (2003), Erasmus Universiteit Rotterdam, (Ph.D. thesis)
[12] Liebchen, C.; Möhring, R. H., The modeling power of the periodic event scheduling problem: Railway timetables – and beyond, (Geraets, F.; Kroon, L.; Schoebel, A.; Wagner, D.; Zaroliagis, C. D., Algorithmic Methods for Railway Optimization. Algorithmic Methods for Railway Optimization, Lecture Notes in Computer Science, vol. 4359 (2007), Springer: Springer Berlin Heidelberg), 3-40
[13] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W. H. Freeman and Company: W. H. Freeman and Company San Francisco · Zbl 0411.68039
[14] Liebchen, C., Optimierungsverfahren zur Erstellung von Taktfahrplänen (1998), Technische Universität Berlin, (Diploma thesis)
[15] M. Bussieck, GAMS - lop.gms: Line optimization. http://www.gams.com/modlib/libhtml/lop.htm.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.