@misc{Hoppmann, type = {Master Thesis}, author = {Hoppmann, Heide}, title = {A Configuration Model for the Line Planning Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51610}, pages = {108}, abstract = {In this thesis we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations are combinatorial building blocks of primal solutions; they rule out the "capacity numerics" and make the problem purely combinatorial. The concept of configurations can also be adapted to other capacitated network design problems. The configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, multicover, and MIR inequalities. These theoretical findings can be confirmed in computations, however, the enormous number of configurations can blow up the formulation for large instances. We propose a mixed model that enriches the standard model by a judiciously chosen subset of configurations that provide a good compromise between model strength and size. Computational results for large-scale line planning problems are presented.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {A Configuration Model for the Line Planning Problem}, series = {ATMOS 2013 - 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, volume = {33}, booktitle = {ATMOS 2013 - 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Frigioni, Daniele and Stiller, Sebastian}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/OASIcs.ATMOS.2013.68}, pages = {68 -- 79}, language = {en} } @article{Hoppmann, author = {Hoppmann, Heide}, title = {Linienplanung und Minimale Konfigurationen}, series = {OR News}, volume = {55}, journal = {OR News}, pages = {22 -- 23}, language = {de} } @misc{Hoppmann, author = {Hoppmann, Heide}, title = {An Extended Formulation for the Line Planning Problem}, issn = {1438-0064}, doi = {10.1007/978-3-319-42902-1_2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57467}, abstract = {In this paper we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.}, language = {en} } @article{BorndoerferHoppmannKarbstein, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Passenger routing for periodic timetable optimization}, series = {Public Transport}, journal = {Public Transport}, publisher = {Springer-Verlag Berlin Heidelberg}, doi = {10.1007/s12469-016-0132-0}, abstract = {The task of periodic timetabling is to determine trip arrival and departure times in a public transport system such that travel and transfer times are minimized. This paper investigates periodic timetabling models with integrated passenger routing. We show that different routing models can have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems by integrating passenger routing.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Separation of Cycle Inequalities for the Periodic Timetabling Problem}, series = {24th Annual European Symposium on Algorithms (ESA 2016)}, volume = {57}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, doi = {10.4230/LIPIcs.ESA.2016.21}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.}, language = {en} } @inproceedings{Hoppmann, author = {Hoppmann, Heide}, title = {An Extended Formulation for the Line Planning Problem}, series = {Operations Research Proceedings 2015}, booktitle = {Operations Research Proceedings 2015}, doi = {10.1007/978-3-319-42902-1_2}, pages = {11 -- 17}, abstract = {In this paper we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.}, language = {en} } @misc{BorndoerferHoppmannKarbsteinetal., author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and L{\"o}bel, Fabian}, title = {The Modulo Network Simplex with Integrated Passenger Routing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60319}, abstract = {Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Umsteigen ohne Warten}, series = {HEUREKA 2017}, booktitle = {HEUREKA 2017}, abstract = {Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrpl{\"a}nen vor, bei dem die Umsteigezeiten unter Ber{\"u}cksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Bef{\"o}rderungsqualit{\"a}t.}, language = {de} } @misc{BorndoerferHoppmannKarbstein, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Umsteigen ohne Warten}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62006}, abstract = {Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrpl{\"a}nen vor, bei dem die Umsteigezeiten unter Ber{\"u}cksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Bef{\"o}rderungsqualit{\"a}t.}, language = {de} } @misc{BorndoerferHoppmannKarbstein, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {A Configuration Model for the Line Planning Problem}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2013.68}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-41903}, abstract = {We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model.}, language = {en} } @misc{BorndoerferHoppmannKarbstein, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Passenger Routing for Periodic Timetable Optimization}, issn = {1438-0064}, doi = {10.1007/s12469-016-0132-0}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56739}, abstract = {The task of periodic timetabling is to schedule the trips in a public transport system by determining arrival and departure times at every station such that travel and transfer times are minimized. To date, the optimization literature generally assumes that passengers do not respond to changes in the timetable, i.e., the passenger routes are fixed. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We show that different routing models have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. to different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Timetabling and Passenger Routing in Public Transport}, series = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, year = {2015}, abstract = {The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.}, language = {en} } @misc{BorndoerferHoppmannKarbstein, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Timetabling and Passenger Routing in Public Transport}, series = {Appeard in: Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, journal = {Appeard in: Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55305}, abstract = {The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.}, language = {en} } @article{BorndoerferHoppmannKarbsteinetal., author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and Lindner, Niels}, title = {Separation of cycle inequalities in periodic timetabling}, series = {Discrete Optimization}, journal = {Discrete Optimization}, number = {35}, doi = {10.1016/j.disopt.2019.100552}, pages = {100552}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbsteinetal., author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and L{\"o}bel, Fabian}, title = {The Modulo Network Simplex with Integrated Passenger Routing}, series = {Operations Research Proceedings 2016}, booktitle = {Operations Research Proceedings 2016}, abstract = {Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.}, language = {en} } @misc{BorndoerferHoppmannKarbsteinetal., author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and Lindner, Niels}, title = {Separation of Cycle Inequalities in Periodic Timetabling}, issn = {1438-0064}, doi = {https://doi.org/10.1016/j.disopt.2019.100552}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69746}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algo- rithm for cycle inequalities, and we give 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.}, language = {en} }