Search Results

Documents authored by Helmberg, Christoph

Document
DOI: 10.4230/OASIcs.ATMOS.2010.45
Dynamic Graph Generation and Dynamic Rolling Horizon Techniques in Large Scale Train Timetabling

Authors: Frank Fischer and Christoph Helmberg

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
The aim of the train timetabling problem is to find a conflict free timetable for a set of passenger and freight trains along their routes in an infrastructure network. Several constraints like station capacities and train dependent running and headway times have to be satisfied. In this work we deal with large scale instances of the aperiodic train timetabling problem for the German railway network. The problem is modelled in a classical way via time discretised networks, its Lagrange-dual is solved by a bundle method. In order to handle the enormous number of variables and constraints dynamic graph generation and dynamic rolling horizon techniques are employed.
Cite as

Frank Fischer and Christoph Helmberg. Dynamic Graph Generation and Dynamic Rolling Horizon Techniques in Large Scale Train Timetabling. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 45-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:OASIcs.ATMOS.2010.45,
  author =	{Fischer, Frank and Helmberg, Christoph},
  title =	{{Dynamic Graph Generation and Dynamic Rolling Horizon Techniques in Large Scale Train Timetabling}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{45--60},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.45},
  URN =		{urn:nbn:de:0030-drops-27492},
  doi =		{10.4230/OASIcs.ATMOS.2010.45},
  annote =	{Keywords: combinatorial optimization, train-timetabling}
}
Document
DOI: 10.4230/DagSemProc.09261.17
Network Models with Convex Cost Structure like Bundle Methods

Authors: Christoph Helmberg

Published in: Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

Abstract
For three rather diverse applications (truck scheduling for inter warehouse logistics, university-course timetabling, operational train timetabling) that contain integer multi-commodity flow as a major modeling element we present a computational comparison between a bundle and a full linear programming (LP) approach for solving the basic relaxations. In all three cases computing the optimal solutions with LP standard solvers is computationally very time consuming if not impractical due to high memory consumption while bundle methods produce solutions of sufficient but low accuracy in acceptable time. The rounding heuristics generate comparable results for the exact and the approximate solutions, so this entails no loss in quality of the final solution. Furthermore, bundle methods facilitate the use of nonlinear convex cost functions. In practice this not only improves the quality of the relaxation but even seems to speed up convergence of the method.
Cite as

Christoph Helmberg. Network Models with Convex Cost Structure like Bundle Methods. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{helmberg:DagSemProc.09261.17,
  author =	{Helmberg, Christoph},
  title =	{{Network Models with Convex Cost Structure like Bundle Methods}},
  booktitle =	{Models and Algorithms for Optimization in Logistics},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9261},
  editor =	{Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.17},
  URN =		{urn:nbn:de:0030-drops-21905},
  doi =		{10.4230/DagSemProc.09261.17},
  annote =	{Keywords: Lagrangian decomposition, large scale convex optimization, bundle methods, integer multi-commodity flow}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2008.1585
Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation

Authors: Frank Fischer, Christoph Helmberg, Jürgen Janßen, and Boris Krostitz

Published in: OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Abstract
The train timetabling problem considered is to find conflict free routes for a set of trains in a given railway network so that cer- tain time window conditions are satisfied. We deal with the very large scale problem of constructing such timetables for the German railway network. A number of restrictions on different train types like freight trains or passenger trains have to be observed, e.g., sequence dependent headway times, station capacities, and stopping times. In order to handle the enormous number of variables and constraints we employ Lagrangian relaxation of the conflict constraints combined with a cutting plane approach. The model is solved by a bundle method; its primal aggregate is used for separation and as starting point for rounding heuristics. We present some promising results towards handling a test instance com- prising ten percent of the entire network.
Cite as

Frank Fischer, Christoph Helmberg, Jürgen Janßen, and Boris Krostitz. Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:OASIcs.ATMOS.2008.1585,
  author =	{Fischer, Frank and Helmberg, Christoph and Jan{\ss}en, J\"{u}rgen and Krostitz, Boris},
  title =	{{Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation}},
  booktitle =	{8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)},
  pages =	{1--12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-07-1},
  ISSN =	{2190-6807},
  year =	{2008},
  volume =	{9},
  editor =	{Fischetti, Matteo and Widmayer, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1585},
  URN =		{urn:nbn:de:0030-drops-15850},
  doi =		{10.4230/OASIcs.ATMOS.2008.1585},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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