Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation

Fischer, Frank; Helmberg, Christoph; Janßen, Jürgen; Krostitz, Boris

doi:10.4230/OASIcs.ATMOS.2008.1585

Document

Towards Solving Very Large Scale Train Timetabling Problems by Lagrangian Relaxation

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

Part of: Volume: 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (ATMOS 2008)
Part of: Series: Open Access Series in Informatics (OASIcs)
Part of: Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2008-09-24

PDF

File

OASIcs.ATMOS.2008.1585.pdf

Filesize: 182 kB
12 pages

Document Identifiers

DOI: 10.4230/OASIcs.ATMOS.2008.1585
URN: urn:nbn:de:0030-drops-15850

Author Details

Frank Fischer

Christoph Helmberg

Jürgen Janßen

Boris Krostitz

Cite AsGet BibTex

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)
https://doi.org/10.4230/OASIcs.ATMOS.2008.1585

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.

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail