DROPS

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}
}

Search Results

Documents authored by Hoppmann, Heide

Separation of Cycle Inequalities for the Periodic Timetabling Problem

Abstract

Cite as

A Configuration Model for the Line Planning Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message