<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1489</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber>239</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName>Südwestdeutscher Verlag für Hochschulschriften</publisherName>
    <publisherPlace>Saarbrücken, Germany</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-03-21</completedDate>
    <publishedDate>2012-03-21</publishedDate>
    <thesisDateAccepted>2012-02-15</thesisDateAccepted>
    <title language="eng">Railway Track Allocation: Models and Algorithms</title>
    <abstract language="eng">This thesis is about mathematical optimization for the efficient use of railway infrastructure. We address the &#13;
optimal allocation of the available railway track capacity - the track allocation problem.&#13;
This track allocation problem is a major challenge for a railway company, independent of &#13;
whether a free market, a private monopoly, or a public monopoly is given.&#13;
Planning and operating railway transportation systems is extremely hard due &#13;
to the combinatorial complexity of the underlying discrete optimization problems, &#13;
the technical intricacies, and the immense sizes of the problem instances. Mathematical models and optimization&#13;
techniques can result in huge gains for both railway customers and operators, e.g., &#13;
in terms of cost reductions or service quality improvements. &#13;
We tackle this challenge by developing novel mathematical models and associated innovative algorithmic &#13;
solution methods for large scale instances. This allows us to produce for the first time reliable &#13;
solutions for a real world instance, i.e., the Simplon corridor in Switzerland.&#13;
The opening chapter gives a comprehensive overview on railway planning problems.&#13;
This provides insights into the regulatory and technical framework, &#13;
it discusses the interaction of several planning steps, and identifies optimization potentials in &#13;
railway transportation. The remainder of the thesis is comprised of two major parts. &#13;
&#13;
&#13;
The first part is concerned with modeling railway systems to allow for resource and capacity analysis.&#13;
Railway capacity has basically two dimensions, a space dimension which are the physical &#13;
infrastructure elements as well as a time dimension that refers to the train movements, i.e., &#13;
occupation or blocking times, on the physical infrastructure. Railway safety systems operate &#13;
on the same principle all over the world. A train has to reserve infrastructure blocks for some time to pass through. &#13;
Two trains reserving the same block of the infrastructure within the same point in time is called block conflict.  &#13;
Therefore, models for railway capacity involve the definition &#13;
and calculation of reasonable running and associated reservation and &#13;
blocking times to allow for a conflict free allocation.&#13;
&#13;
In the second and main part of the thesis, the optimal track &#13;
allocation problem for macroscopic models of the railway system is considered.&#13;
The literature for related problems is surveyed. &#13;
A graph-theoretic model for the track allocation problem is &#13;
developed. In that model optimal track allocations correspond to &#13;
conflict-free paths in special time-expanded graphs.&#13;
Furthermore, we made considerable progress on solving track allocation problems by two &#13;
main features - a novel modeling approach for the macroscopic track &#13;
allocation problem and algorithmic improvements based on the&#13;
utilization of the bundle method.   &#13;
&#13;
Finally, we go back to practice and present in the last chapter several case &#13;
studies using the tools netcast and tsopt.&#13;
We provide a computational comparison of &#13;
our new models and standard packing models used in the literature. &#13;
Our computational experience indicates that our approach, i.e.,&#13;
``configuration models'', outperforms other models. Moreover, the rapid branching &#13;
heuristic and the bundle method enable us to produce high quality solutions for very large scale&#13;
instances, which has not been possible before. &#13;
In addition, we present results for a theoretical and rather visionary auction framework &#13;
for track allocation. We discuss several auction design questions and analyze experiments of &#13;
various auction simulations. &#13;
&#13;
The highlights are results for the Simplon corridor in Switzerland. &#13;
We optimized the train traffic through this tunnel using our models and &#13;
software tools.&#13;
To the best knowledge of the author and confirmed by several railway &#13;
practitioners this was the first time that fully automatically produced &#13;
track allocations on a macroscopic scale fulfill the requirements &#13;
of the originating microscopic model, withstand the evaluation in the &#13;
microscopic simulation tool OpenTrack, and exploit the infrastructure capacity.&#13;
This documents the success of our approach in practice and the usefulness &#13;
and applicability of mathematical optimization to railway track allocation.</abstract>
    <identifier type="isbn">978-3-8381-3222-8</identifier>
    <identifier type="url">http://opus.kobv.de/tuberlin/volltexte/2012/3427/pdf/schlechte_thomas.pdf</identifier>
    <identifier type="urn">urn:nbn:de:kobv:83-opus-34272</identifier>
    <advisor>Martin Grötschel</advisor>
    <author>Thomas Schlechte</author>
    <submitter>Thomas Schlechte</submitter>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway track allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>large-scale integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>network aggregation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>rapid branching</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisPublisher>Technische Universität Berlin</thesisPublisher>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1489/thesisFinal.pdf</file>
  </doc>
</export-example>
