Filtern
Erscheinungsjahr
- 2020 (1) (entfernen)
Dokumenttyp
- Artikel (1)
Sprache
- Englisch (1)
Volltext vorhanden
- nein (1)
Gehört zur Bibliographie
- nein (1)
Institut
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.