Balancing Efficiency and Robustness – A Bi-criteria Optimization Approach to Railway Track Allocation

Thomas Schlechte () and Ralf Borndörfer
Additional contact information
Thomas Schlechte: Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)

A chapter in Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems, 2010, pp 105-116 from Springer

Abstract: Abstract Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company, also known as the train timetabling problem (TTP). This article focuses on a robust extension of the TTP, which typically consists in finding a conflict free set of train routes of maximum value for a given railway network. Timetables are, however, not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to propagate and cause delays to subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand, we want to maximize the profit of a schedule, that is the number of routed trains. On the other hand, if two trains are scheduled with a minimum gap the delay of the first one will affect the subsequent train. We present extensions of the standard integer programming formulation for solving the TTP. These models incorporate both aspects with additional track configuration variables. We discuss how these variables reflect a certain robustness measure. These models can be solved by column generation techniques. We propose scalarization techniques to determine efficient, i.e., the decisions Pareto optimal, solutions. We prove that the LP-relaxation of the TTP including an additional ε-constraint remains solvable in polynomial time. Finally, we present some preliminary computational results on macroscopic real-world data of a part of the German long distance railway network.

Keywords: Train timetabling; Bi-criteria optimization; Integer programming (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnechp:978-3-642-04045-0_9

Ordering information: This item can be ordered from
http://www.springer.com/9783642040450

DOI: 10.1007/978-3-642-04045-0_9

Access Statistics for this chapter

More chapters in Lecture Notes in Economics and Mathematical Systems from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().