<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1363</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2011-07-27</completedDate>
    <publishedDate>2011-07-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Railway Track Allocation - Simulation and Optimization</title>
    <abstract language="eng">Today the railway timetabling process and the track allocation &#13;
is one of the most challenging problems to solve by a railway infrastructure provider.&#13;
Especially due to the deregulation of the transport market in the recent years several&#13;
suppliers of railway traffic have entered the market. This leads to an increase of slot requests&#13;
and then it is natural that conflicts occur among them.&#13;
Furthermore, railway infrastructure networks consist of very expensive assets, even more&#13;
they are rigid due to the long-term upgrade process. &#13;
&#13;
In order to make best use of these valuable infrastructure and to ensure economic operation, &#13;
efficient planning of the railway operation is indispensable. &#13;
Mathematical optimization models and algorithmic methodology can help&#13;
to automatize and tackle these challenges.&#13;
Our contribution in this paper is to present a renewed planning process &#13;
due to the liberalization in Europe and a general framework to &#13;
support the integration of simulation and optimization for &#13;
railway capacity allocation.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">11-32</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-13632</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of 4th International Seminar on Railway Operations Modelling and Analysis (IAROR), I.A. Hansen et al. (eds.) 2011, vol. 4,</enrichment>
    <author>Thomas Schlechte</author>
    <submitter>Thomas Schlechte</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>11-32</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway models</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway capacity</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>track allocation framework</value>
    </subject>
    <collection role="ccs" number="D.">Software</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1363/ZR-11-32.pdf</file>
  </doc>
  <doc>
    <id>1640</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-11-05</completedDate>
    <publishedDate>2012-11-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Railway Track  Allocation</title>
    <abstract language="eng">This article gives an overview of the results of the author's PhD thesis. The thesis deals with the&#13;
 mathematical optimization for the efficient use of&#13;
 railway infrastructure. We address the optimal allocation of the available&#13;
 railway track capacity - the track allocation problem. This track allocation&#13;
 problem is a major challenge for a railway company, independent of whether&#13;
 a free market, a private monopoly, or a public monopoly is given. Planning&#13;
 and operating railway transportation systems is extremely hard due to the&#13;
 combinatorial complexity of the underlying discrete optimization problems,&#13;
 the technical intricacies, and the immense sizes of the problem instances.&#13;
 Mathematical models and optimization techniques can result in huge gains&#13;
 for both railway customers and operators, e.g., in terms of cost reductions or&#13;
 service quality improvements. We tackle this challenge by developing novel&#13;
 mathematical models and associated innovative algorithmic solution methods&#13;
 for large scale instances. We made considerable progress on solving track &#13;
 allocation problems by two main features - a novel modeling approach for the &#13;
 macroscopic track allocation problem and algorithmic improvements based on the&#13;
 utilization of the bundle method. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-16402</identifier>
    <submitter>Thomas Schlechte</submitter>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-38</number>
    </series>
    <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>configuration models</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="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1640/ZR-12-38.pdf</file>
  </doc>
  <doc>
    <id>1188</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation>Zuse Institut Berlin</creatingCorporation>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-11-01</completedDate>
    <publishedDate>2010-11-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Aggregation Methods for Railway Networks</title>
    <abstract language="eng">In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run.</abstract>
    <identifier type="serial">10-23</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1251</identifier>
    <identifier type="url">http://www.sciencedirect.com/science/article/pii/S2210970611000047</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11881</identifier>
    <enrichment key="SourceTitle">A rev. vers. appeared in: Journal of Rail Transport Planning &amp; Management 1(2011) 38-48</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Berkan Erol</author>
    <author>Thomas Graffagnino</author>
    <author>Thomas Schlechte</author>
    <author>Elmar Swarat</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-23</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>makroskopische Bahnmodellierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Netzwerkaggregation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>macroscopic railway modeling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>network aggregation</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90B20">Traffic problems</collection>
    <collection role="msc" number="91B74">Models of real-world systems</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="swarat">Swarat, Elmar</collection>
    <collection role="projects" number="MATHEON-B22">MATHEON-B22</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1188/ZR-10-23.pdf</file>
  </doc>
  <doc>
    <id>1186</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation>Zuse Institut Berlin</creatingCorporation>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-08-24</completedDate>
    <publishedDate>2010-08-24</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Railway Track Allocation by Rapid Branching</title>
    <abstract language="eng">The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.</abstract>
    <identifier type="serial">10-22</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1247</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11864</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Thomas Schlechte</author>
    <author>Steffen Weider</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-22</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Trassenallokationsproblem</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Rapid-Branching-Heuristik</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Proximale Bündelmethode</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Railway Track Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bundle Method</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Rapid Branching</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="projects" number="MATHEON-B22">MATHEON-B22</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1186/ZR_10_22.pdf</file>
  </doc>
  <doc>
    <id>4271</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2013-10-15</completedDate>
    <publishedDate>2013-10-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Analysis of Micro-Macro Transformations of Railway Networks</title>
    <abstract language="eng">A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value.</abstract>
    <identifier type="urn">urn:nbn:de:0297-zib-42710</identifier>
    <author>Marco Blanco</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>13-65</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="KOSMOS">KOSMOS</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/4271/ZR-13-65.pdf</file>
  </doc>
  <doc>
    <id>1076</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation>ZIB</creatingCorporation>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-05-16</completedDate>
    <publishedDate>2008-05-16</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Balancing Efficiency and Robustness – A Bi-criteria Optimization Approach to Railway Track Allocation</title>
    <abstract language="eng">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. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are 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 be propagated causing delays of 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 more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional $\epsilon$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network.</abstract>
    <identifier type="serial">08-22</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1105</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10763</identifier>
    <enrichment key="SourceTitle">To appear in: MCDM for Sustainable Energy and Transportation Systems, Lecture Notes in Economics and Mathematical Systems, 2009</enrichment>
    <author>Thomas Schlechte</author>
    <submitter>unknown unknown</submitter>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-22</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Train Timetabling Problem</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Bicriteria Optimization</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Column Generation</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1076/ZR_08_22.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1076/ZR_08_22_revised.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1076/ZR_08_22_revised.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1076/ZR_08_22.ps</file>
  </doc>
  <doc>
    <id>878</id>
    <completedYear>2005</completedYear>
    <publishedYear>2005</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-11-04</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Auctioning Approach to Railway Slot Allocation</title>
    <abstract language="eng">We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.</abstract>
    <identifier type="serial">05-45</identifier>
    <identifier type="opus3-id">878</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8786</identifier>
    <enrichment key="SourceTitle">Appeared in: Competition and Regulation in Network Industries 1 (2006) 163-196</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-8786</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Sascha Lukac</author>
    <author>Kay Mitusch</author>
    <author>Thomas Schlechte</author>
    <author>Sören Schultz</author>
    <author>Andreas Tanner</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-45</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Railway Slot Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Train Dispatching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Combinatorial Auctions</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/878/ZR-05-45.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/878/ZR-05-45.ps</file>
  </doc>
  <doc>
    <id>945</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>This work was funded by the Federal Ministry of Economics and Technology (BMWi), project Trassenbörse, grant 19M4031A</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-01-08</completedDate>
    <publishedDate>2007-01-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Models for Railway Track Allocation</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">07-02</identifier>
    <identifier type="opus3-id">945</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9451</identifier>
    <enrichment key="SourceTitle">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</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-02</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Railway Slot Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Train Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Combinatorial Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Linear and Integer Programming</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/945/ZR_07_02.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/945/ZR_07_02.ps</file>
  </doc>
  <doc>
    <id>1403</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2011-09-22</completedDate>
    <publishedDate>2011-09-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Railway Track Allocation - Simulation, Aggregation, and Optimization</title>
    <abstract language="eng">Today the railway timetabling process and the track allocation &#13;
is one of the most challenging problems to solve by a railway company.&#13;
Especially due to the deregulation of the transport market in the recent years several&#13;
suppliers of railway traffic have entered the market in Europe. This leads to more &#13;
potential conflicts between trains caused by an increasing demand of train paths.&#13;
&#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 size of the problem instances.&#13;
In order to make best use of the infrastructure and to ensure economic operation, &#13;
efficient planning of the railway operation is indispensable. &#13;
&#13;
Mathematical optimization models and algorithms can help&#13;
to automatize and tackle these challenges.&#13;
Our contribution in this paper is to present a renewed planning process &#13;
due to the liberalization in Europe and an associated concept for track allocation, that consists &#13;
of three important parts, simulation, aggregation, and optimization. &#13;
Furthermore, we present results of our general framework for real world data.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">11-35</identifier>
    <identifier type="doi">10.1007/978-3-642-27963-8</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-14031</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. 1st International Workshop on High-speed and Intercity Railways (IWHIR 2011), Yi-Qing Ni and Xiao-Wei Ye (eds.) 2012, pp. 53-70,</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Thomas Schlechte</author>
    <author>Elmar Swarat</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-35</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway models, railway capacity, track allocation framework</value>
    </subject>
    <collection role="msc" number="90C08">Special problems of linear programming (transportation, multi-index, etc.)</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="swarat">Swarat, Elmar</collection>
    <collection role="projects" number="MATHEON-B22">MATHEON-B22</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1403/ZR-11-35.pdf</file>
  </doc>
  <doc>
    <id>1172</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-06-14</completedDate>
    <publishedDate>2010-06-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Railway capacity auctions with dual prices</title>
    <abstract language="eng">Railway scheduling is based on the principle of the construction of a conflict-free timetable. This leads to a strict definition of capacity: in contrast with road transportation, it can be said in advance whether a given railway infrastructure can accommodate - at least in theory - a certain set of train requests. Consequently, auctions for railway capacity are modeled as auctions of discrete goods -- the train slots. We present estimates for the efficiency gain that may be generated by slot auctioning in comparison with list price allocation. We introduce a new class of allocation and auction problems, the feasible assignment problem, that is a proper generalization of the well-known combinatorial auction problem. The feasible assignment class was designed to cover the needs for an auction mechanism for railway slot auctions, but is of interest in its own right. As a practical instance to state and solve the railway slot allocation problem, we present an integer programming formulation, briefly the ACP, which turns out to be an instance of the feasible assignment problem and whose dual problem yields prices that can be applied to define a useful activity rule for the linearized version of the Ausubel Milgrom Proxy auction. We perform a simulation aiming to measure the impact on efficiency and convergence rate.</abstract>
    <identifier type="serial">10-10</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1233</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11729</identifier>
    <author>Thomas Schlechte</author>
    <submitter>unknown unknown</submitter>
    <author>Andreas Tanner</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-10</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Combinatorial Auction Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Railway Track Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Ausubel Milgrom Proxy Auction Mechanism</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="91B26">Market models (auctions, bargaining, bidding, selling, etc.)</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1172/ZR_10_10.pdf</file>
  </doc>
  <doc>
    <id>5606</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2015-04-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Comparing two dual relaxations of large scale train timetabling problems</title>
    <abstract language="eng">Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-56068</identifier>
    <author>Frank Fischer</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-43</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="Trassenbörse">Trassenbörse</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5606/ZR-15-43.pdf</file>
  </doc>
</export-example>
