Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 36 von 119
Zurück zur Trefferliste

Strong Relaxations for the Train Timetabling Problem using Connected Configurations

  • 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.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Frank Fischer, Thomas Schlechte
Herausgeber:in:Gianlorenzo D'Angelo, Twan Dollevoet
Dokumentart:Konferenzbeitrag
Titel des übergeordneten Werkes (Deutsch):17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Band:59
Volltext-Url:http://drops.dagstuhl.de/opus/volltexte/2017/7902/
Jahr der Erstveröffentlichung:2017
Preprint:urn:nbn:de:0297-zib-64743
DOI:https://doi.org/10.4230/OASIcs.ATMOS.2017.11
Lizenz (Deutsch):License LogoCreative Commons - CC BY - Namensnennung 4.0 International
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.