3 Search Results for "Hoppmann, Heide"

Document
DOI: 10.4230/OASIcs.ATMOS.2025.2
A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing

Authors: Fabian Löbel and Niels Lindner

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
We offer a geometric perspective on the problem of integrated periodic timetabling and passenger routing in public transport. Inside the space of periodic tensions, we single out those regions, where the same set of paths provides shortest passenger routes. This results in a polyhedral subdivision, which we combine with the known decomposition by polytropes. On each maximal region of the common refinement, the integrated problem is solvable in polynomial time. We transform these insights into a new geometry-driven primal heuristic, integrated tropical neighborhood search (ITNS). Computationally, we compare implementations of ITNS and the integrated (restricted) modulo network simplex algorithm on the TimPassLib benchmark set, and contribute better solutions in terms of total travel time for all but one of the twenty-five instances for which a proven optimal solution is not yet known.
Cite as

Fabian Löbel and Niels Lindner. A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lobel_et_al:OASIcs.ATMOS.2025.2,
  author =	{L\"{o}bel, Fabian and Lindner, Niels},
  title =	{{A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{2:1--2:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.2},
  URN =		{urn:nbn:de:0030-drops-247580},
  doi =		{10.4230/OASIcs.ATMOS.2025.2},
  annote =	{Keywords: Periodic Timetabling, Passenger Routing, Polyhedral Complexes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.21
Separation of Cycle Inequalities for the Periodic Timetabling Problem

Authors: Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

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.
Cite as

Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. Separation of Cycle Inequalities for the Periodic Timetabling Problem. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:LIPIcs.ESA.2016.21,
  author =	{Bornd\"{o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika},
  title =	{{Separation of Cycle Inequalities for the Periodic Timetabling Problem}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.21},
  URN =		{urn:nbn:de:0030-drops-63722},
  doi =		{10.4230/LIPIcs.ESA.2016.21},
  annote =	{Keywords: periodic timetabling, cycle inequalities, separation algorithm}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2013.68
A Configuration Model for the Line Planning Problem

Authors: Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

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.
Cite as

Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. A Configuration Model for the Line Planning Problem. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 68-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2013.68,
  author =	{Bornd\"{o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika},
  title =	{{A Configuration Model for the Line Planning Problem}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{68--79},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.68},
  URN =		{urn:nbn:de:0030-drops-42451},
  doi =		{10.4230/OASIcs.ATMOS.2013.68},
  annote =	{Keywords: Combinatorial optimization, polyhedral combinatorics, line planning}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2016
  • 1 2013

  • Refine by Author
  • 2 Borndörfer, Ralf
  • 2 Hoppmann, Heide
  • 2 Karbstein, Marika
  • 1 Lindner, Niels
  • 1 Löbel, Fabian

  • Refine by Series/Journal
  • 1 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Network optimization

  • Refine by Keyword
  • 1 Combinatorial optimization
  • 1 Passenger Routing
  • 1 Periodic Timetabling
  • 1 Polyhedral Complexes
  • 1 cycle inequalities
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact