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

Models for Railway Track Allocation

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-9451
  • This article is about the optimal track allocation problem (OPTRA) to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations: a standard formulation that models block conflicts in terms of packing constraints, and a new extended formulation that is based on additional configuration' variables. We show that the packing constraints in the standard formulation stem from an interval graph, and that they can be separated in polynomial time. It follows that the LP relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the extended formulation produces the same LP bound, and that it can also be computed with this model in polynomial time. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view, because it features a constant number of rows and is therefore amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hannover-Fulda-Kassel region of the German long distance railway network are reported.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Ralf BorndörferORCiD, Thomas Schlechte
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Combinatorial Optimization; Linear and Integer Programming; Railway Slot Allocation; Train Timetabling
MSC-Klassifikation:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Beteiligte Körperschaft:This work was funded by the Federal Ministry of Economics and Technology (BMWi), project Trassenbörse, grant 19M4031A
Datum der Erstveröffentlichung:08.01.2007
Schriftenreihe (Bandnummer):ZIB-Report (07-02)
ZIB-Reportnummer:07-02
Verlagspublikation:Appeared in: Proceeding of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS 2007) (C. Liebchen, R. K. Ahuja und J. A. Mesa, Hg.), Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 2007
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.