Search Results

Documents authored by Fischer, Frank

Document
DOI: 10.4230/OASIcs.ATMOS.2017.11
Strong Relaxations for the Train Timetabling Problem Using Connected Configurations

Authors: Frank Fischer and Thomas Schlechte

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral.
Cite as

Frank Fischer and Thomas Schlechte. Strong Relaxations for the Train Timetabling Problem Using Connected Configurations. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fischer_et_al:OASIcs.ATMOS.2017.11,
  author =	{Fischer, Frank and Schlechte, Thomas},
  title =	{{Strong Relaxations for the Train Timetabling Problem Using Connected Configurations}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{11:1--11:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.11},
  URN =		{urn:nbn:de:0030-drops-79021},
  doi =		{10.4230/OASIcs.ATMOS.2017.11},
  annote =	{Keywords: combinatorial optimization, train timetabling, Lagrangian relaxation, connected configurations}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2015.97
Ordering Constraints in Time Expanded Networks for Train Timetabling Problems

Authors: Frank Fischer

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
The task of the train timetabling problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. This kind of problem has proven to be very challenging and numerous solution approaches have been proposed. One of the most successful approaches is based on time discretized network models. However, one of the major weaknesses of these models is that fractional solutions tend to change the order of trains along some track, which is not allowed for integer solutions, leading to poor relaxations. In this paper, we present an extension for these kind of models, which aims at overcoming these problems. By exploiting a configuration based formulation, we propose to extend the model with additional ordering constraints. These constraints enforce compatibility of orderings along a sequence of tracks and greatly improve the quality of the relaxations. We show in some promising preliminary computational experiments that our approach indeed helps to resolve many of the invalid overtaking problems of relaxations for the standard models.
Cite as

Frank Fischer. Ordering Constraints in Time Expanded Networks for Train Timetabling Problems. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 97-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{fischer:OASIcs.ATMOS.2015.97,
  author =	{Fischer, Frank},
  title =	{{Ordering Constraints in Time Expanded Networks for Train Timetabling Problems}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{97--110},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. 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.2015.97},
  URN =		{urn:nbn:de:0030-drops-54524},
  doi =		{10.4230/OASIcs.ATMOS.2015.97},
  annote =	{Keywords: combinatorial optimization, train timetabling, Lagrangian relaxation, ordering constraints}
}
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/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