<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>5379</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-03-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The S-Bahn Challenge in Berlin</title>
    <abstract language="eng">The S-Bahn Challenge in Berlin is a challenge in which one has to travel the entire S-Bahn network of Berlin in the shortest possible time.&#13;
&#13;
We explain how the problem can be modeled and solved mathematically. Furthermore, we report on our record attempt on January 10, 2015.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-53792</identifier>
    <identifier type="url">https://gor.uni-paderborn.de/index.php?id=362</identifier>
    <enrichment key="SourceTitle">Appeared in: OR News, 53 (March 2015). pp. 10-14</enrichment>
    <author>Isabel Beckenbach</author>
    <submitter>Isabel Beckenbach</submitter>
    <author>Ralf Borndörfer</author>
    <author>Loes Knoben</author>
    <author>David Kretz</author>
    <author>Marc Uetz</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-13</number>
    </series>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="beckenbach">Beckenbach, Isabel</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="projects" number="SCB">SCB</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5379/SBahnChallenge-2.pdf</file>
  </doc>
  <doc>
    <id>5850</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>2016-03-24</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations</title>
    <abstract language="eng">The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects&#13;
and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution,&#13;
and a fixed assignment of jobs to machines must be computed.&#13;
We propose a cutting-plane approach to solve the robust counterpart of this optimization problem.&#13;
To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities.&#13;
The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions.&#13;
We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which&#13;
only approximation approaches were known. Our model can&#13;
be extended to balance the load over several planning periods in a rolling horizon.&#13;
We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that:&#13;
(i) our approach performs well compared to a previous model that ignored the distribution of case durations; &#13;
(ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost;&#13;
(iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available.&#13;
Finally, we draw a number of managerial implications from these observations.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-58502</identifier>
    <identifier type="doi">10.1016/j.ejor.2018.05.022</identifier>
    <enrichment key="SourceTitle">Appeared in: European Journal of Operational Research 271(2):420-435</enrichment>
    <author>Guillaume Sagnol</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Christoph Barner</author>
    <author>Ralf Borndörfer</author>
    <author>Mickaël Grima</author>
    <author>Matthes Seeling</author>
    <author>Claudia Spies</author>
    <author>Klaus Wernecke</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-18</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>robust optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lognormal duration</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Hilbert's projective metric</value>
    </subject>
    <collection role="msc" number="90Cxx">Mathematical programming [See also 49Mxx, 65Kxx]</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="projects" number="Charité-OPOSSUM">Charité-OPOSSUM</collection>
    <collection role="projects" number="BMBF-IBOSS">BMBF-IBOSS</collection>
    <collection role="institutes" number="healthcare">Mathematics of Health Care</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5850/robust_alloc_lognorm_v1_zib.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/5850/robust_alloc_lognorm_v3_zib.pdf</file>
  </doc>
  <doc>
    <id>5849</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>2016-03-24</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Robust Allocation of Operating Rooms with Lognormal case Durations</title>
    <abstract language="eng">The problem of allocating operating rooms (OR) to surgical cases is a challenging task,&#13;
involving both combinatorial aspects and uncertainty handling. In this article,&#13;
we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution.&#13;
We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end, &#13;
we develop an algorithm based on fixed-point iterations to solve the subproblems that&#13;
identify worst-case scenarios and generate cut inequalities. The procedure is illustrated with numerical experiments based&#13;
on real data from a major hospital in Berlin.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-58497</identifier>
    <identifier type="url">http://www.pms2016.com/congreso/ficha.en.html</identifier>
    <enrichment key="SourceTitle">Proceedings of the 15th International Conference on Project Management and Scheduling (PMS 2016), pp.52-55</enrichment>
    <author>Guillaume Sagnol</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Ralf Borndörfer</author>
    <author>Mickaël Grima</author>
    <author>Matthes Seeling</author>
    <author>Claudia Spies</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-16</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>robust optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lognormal duration</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Hilbert's projective metric</value>
    </subject>
    <collection role="msc" number="90Cxx">Mathematical programming [See also 49Mxx, 65Kxx]</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="sagnol">Sagnol, Guillaume</collection>
    <collection role="projects" number="Charité-OPOSSUM">Charité-OPOSSUM</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisPublisher>Zuse Institute Berlin (ZIB)</thesisPublisher>
    <thesisGrantor>Freie Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/5849/PMS2016_zib.pdf</file>
  </doc>
  <doc>
    <id>420</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-09-17</completedDate>
    <publishedDate>1999-09-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Der Schnellste Weg zum Ziel</title>
    <abstract language="deu">Wir geben eine Einführung in die Mathematik von und mit Wegen. Nicht auf dem kürzesten, aber auf einem hoffentlich kurzweiligen Weg!</abstract>
    <identifier type="serial">SC-99-32</identifier>
    <identifier type="opus3-id">421</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-4209</identifier>
    <identifier type="doi">10.1007/978-3-322-96366-6_5</identifier>
    <enrichment key="SourceTitle">Appeared in: Aigner u. Behrends (Eds.) (2000), Alles Mathematik, Vieweg Verlag. S. 45-76</enrichment>
    <author>Ralf Borndörfer</author>
    <author>Martin Grötschel</author>
    <author>Andreas Löbel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-99-32</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Kürzeste Wege</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Kombinatorische Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Operations Research</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C10">Integer programming</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="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="loebel">Löbel, Andreas</collection>
    <collection role="projects" number="BMBF-DS">BMBF-DS</collection>
    <collection role="projects" number="MATHEON-B1">MATHEON-B1</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/420/SC-99-32.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/420/SC-99-32.pdf</file>
  </doc>
  <doc>
    <id>4713</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>2014-12-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Network Spot Checking Games: Theory and Application to Toll Enforcing in Transportation Networks</title>
    <abstract language="eng">We introduce the class of spot-checking games (SC games). These games model&#13;
problems where the goal is to distribute fare inspectors over a toll network.&#13;
In an SC game, the pure strategies of network users correspond to&#13;
paths in a graph, and the pure strategies of the inspectors &#13;
are subset of edges to be controlled.&#13;
Although SC games are not zero-sum, we show that a Nash equilibrium&#13;
can be computed by linear programming.&#13;
The computation of a strong Stackelberg equilibrium is&#13;
more relevant for this problem, but we show that this is NP-hard.&#13;
However, we give some bounds on the \emph{price of spite},&#13;
which measures how the&#13;
payoff of the inspector&#13;
degrades when committing to a Nash equilibrium. &#13;
Finally, we demonstrate the quality of these bounds for a real-world application,&#13;
namely the enforcement of a truck toll on German motorways.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-47139</identifier>
    <identifier type="doi">10.1002/net.21596</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Julia Buwaya</author>
    <author>Guillaume Sagnol</author>
    <author>Elmar Swarat</author>
    <series>
      <title>ZIB-Report</title>
      <number>14-07</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Game Theory</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Stackelberg Equilibrium</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Security Games</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Price of Anarchy</value>
    </subject>
    <collection role="msc" number="05-XX">COMBINATORICS (For finite fields, see 11Txx)</collection>
    <collection role="msc" number="91-XX">GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="persons" number="swarat">Swarat, Elmar</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/4713/zib_report_14_07.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/4713/14-07_v2.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/4713/networks_v4_zib.pdf</file>
  </doc>
  <doc>
    <id>6075</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>2016-01-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Graph Segmentation Problem</title>
    <abstract language="eng">We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-60750</identifier>
    <enrichment key="SourceTitle">INOC 2017 – 8th International Network Optimization Conference</enrichment>
    <author>Stephan Schwartz</author>
    <submitter>Stephan Schwartz</submitter>
    <author>Ralf Borndörfer</author>
    <author>Gerald Bartz</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-53</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>toll billing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>graph segmentation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</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="schwartz">Schwartz, Stephan</collection>
    <collection role="projects" number="no-project">no-project</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6075/ZR-16-53.pdf</file>
  </doc>
  <doc>
    <id>5929</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>2016-04-26</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Makespan and Tardiness in Activity Networks with Lognormal Activity Durations</title>
    <abstract language="eng">We propose an algorithm to approximate the distribution of the completion time (makespan)&#13;
and the tardiness costs of a project, when durations are lognormally distributed. This problem arises naturally for the optimization of surgery scheduling,&#13;
where it is very common to assume lognormal procedure times. We present an analogous of Clark's formulas to compute the moments of the maximum of a set of&#13;
lognormal variables. Then, we use moment matching formulas to approximate the earliest starting time of each activity of the project by a shifted lognormal variable.&#13;
This approach can be seen as a lognormal variant of a state-of-the-art method used for the statistical static timing analysis (SSTA) of digital circuits.&#13;
We carried out numerical experiments with instances based on real data from the application to surgery scheduling. We obtained very&#13;
promising results, especially for the approximation of the mean overtime in operating rooms, &#13;
for which our algorithm yields results of a similar quality to Monte-Carlo simulations&#13;
requiring an amount of computing time several orders of magnitude larger.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-59290</identifier>
    <author>Guillaume Sagnol</author>
    <submitter>Guillaume Sagnol</submitter>
    <author>Felix Balzer</author>
    <author>Ralf Borndörfer</author>
    <author>Claudia Spies</author>
    <author>Falk von Dincklage</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-23</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>activity network</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lognormal distribution</value>
    </subject>
    <collection role="msc" number="68M20">Performance evaluation; queueing; scheduling [See also 60K25, 90Bxx]</collection>
    <collection role="msc" number="90B36">Scheduling theory, stochastic [See also 68M20]</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="sagnol">Sagnol, Guillaume</collection>
    <collection role="projects" number="Charité-OPOSSUM">Charité-OPOSSUM</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5929/lognorm_sched_zib_v1.pdf</file>
  </doc>
  <doc>
    <id>6124</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>2016-11-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Shortest Path Problem with Crossing Costs</title>
    <abstract language="eng">We introduce the shortest path problem with crossing costs (SPPCC),  a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions. &#13;
The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs.&#13;
&#13;
In this paper, we provide a comprehensive analysis of the problem. In particular, &#13;
we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-61240</identifier>
    <author>Marco Blanco</author>
    <submitter>Nam-Dung Hoang</submitter>
    <author>Ralf Borndörfer</author>
    <author>Nam-Dung Hoang</author>
    <author>Anton Kaier</author>
    <author>Thomas Schlechte</author>
    <author>Swen Schlobach</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-70</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="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</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/6124/ZR-16-70.pdf</file>
  </doc>
  <doc>
    <id>6128</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>2016-01-12</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A novel partitioning of the set of non-dominated points</title>
    <abstract language="eng">We consider a novel partitioning of the set of non-dominated points for general multi-objective integer programs with $k$ objectives. The set of non-dominated points is partitioned into a set of non-dominated points whose efficient solutions are also efficient for some restricted subproblem with one less objective; the second partition comprises the non-dominated points whose efficient solutions are&#13;
inefficient for any of the restricted subproblems. We show that the first partition has the nice property that it yields finite rectangular boxes in which the points of the second partition are&#13;
located.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-61286</identifier>
    <author>Sebastian Schenker</author>
    <submitter>Sebastian Schenker</submitter>
    <author>Ralf Borndörfer</author>
    <author>Martin Skutella</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-55</number>
    </series>
    <collection role="ccs" number="G.2">DISCRETE MATHEMATICS</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C29">Multi-objective and goal programming</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="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="CRC1026">CRC1026</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/6128/report_16-55.pdf</file>
  </doc>
  <doc>
    <id>1074</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-05-07</completedDate>
    <publishedDate>2008-05-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Planung von öffentlichem Personenverkehr</title>
    <abstract language="deu">Millionen von Menschen werden allein in Deutschland täglich von Bussen, Bahnen und Flugzeugen transportiert. Der öffentliche Personenverkehr (ÖV) ist von großer Bedeutung für die Lebensqualität einzelner aber auch für die Leistungsfähigkeit ganzer Regionen. Qualität und Effizienz von ÖV-Systemen hängen ab von politischen Rahmenbedingungen (staatlich geplant, wettbewerblich organisiert) und der Eignung der Infrastruktur (Schienensysteme, Flughafenstandorte), vom vorhandenen Verkehrsangebot (Fahr- und Flugplan), von der Verwendung angemessener Technologien (Informations-, Kontroll- und Buchungssysteme) und dem bestmöglichen Einsatz der Betriebsmittel (Energie, Fahrzeuge und Personal). Die hierbei auftretenden Entscheidungs-, Planungs- und Optimierungsprobleme sind z.T. gigantisch und "schreien" aufgrund ihrer hohen Komplexität nach Unterstützung durch Mathematik. Dieser Artikel skizziert den Stand und die Bedeutung des Einsatzes von Mathematik bei der Planung und Durchführung von öffentlichem Personenverkehr, beschreibt die bestehenden Herausforderungen und regt zukunftsweisende Maßnahmen an.</abstract>
    <identifier type="serial">08-20</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1103</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10744</identifier>
    <enrichment key="SourceTitle">Ersch. in: Produktionsfaktor Mathematik - wie Mathematik Technik und Wirtschaft bewegt. Martin Grötschel u.a. (Hrsg.) 2008. ISBN 978-3-540-89434-6. S. 127-153</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Martin Grötschel</author>
    <author>Ulrich Jaeger</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-20</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Produktionsfaktor Mathematik</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Öffentlicher Personenverkehr</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Diskrete Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Operations Research</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1074/ZR_08_20.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1074/ZR_08_20.ps</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>1082</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-08-14</completedDate>
    <publishedDate>2008-08-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Line Connectivity Problem</title>
    <abstract language="eng">This paper introduces the "line connectivity problem", a generalization of the Steiner tree problem and a special case of the line planning problem. We study its complexity and give an IP formulation in terms of an exponential number of constraints associated with "line cut constraints". These inequalities can be separated in polynomial time. We also generalize the Steiner partition inequalities.</abstract>
    <identifier type="serial">08-31</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1117</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10820</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Reserach Proceedings 2008. Bernhard Fleischmann ... (eds.) Springer 2009, pp. 557-562</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Marika Neumann</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-31</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Steiner Tree Generalization</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1082/ZR_08_31.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1082/ZR_08_31.ps</file>
  </doc>
  <doc>
    <id>1070</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-03-25</completedDate>
    <publishedDate>2008-03-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Models for Fare Planning in Public Transport</title>
    <abstract language="eng">The optimization of fare systems in public transit allows to pursue objectives such as the maximization of demand, revenue, profit, or social welfare. We propose a non-linear optimization approach to fare planning that is based on a detailed discrete choice model of user behavior. The approach allows to analyze different fare structures, optimization objectives, and operational scenarios involving, e.g., subsidies. We use the resulting models to compute optimized fare systems for the city of Potsdam, Germany.</abstract>
    <identifier type="serial">08-16</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1099</identifier>
    <identifier type="doi">10.1016/j.dam.2012.02.027</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10708</identifier>
    <enrichment key="SourceTitle">A rev. vers. appeared in: Discrete Applied Mathematics Volume 160, Issue 18, December 2012, Pages 2591–2605</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Marika Neumann</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-16</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Preisplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Nachfragefunktion</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Nahverkehr</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</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="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1070/ZR_08_16.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1070/ZR_08_16_revised.pdf</file>
  </doc>
  <doc>
    <id>1055</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-01-15</completedDate>
    <publishedDate>2008-01-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Angebotsplanung im öffentlichen Nahverkehr</title>
    <title language="eng">Service Design in Public Transport</title>
    <abstract language="deu">Die Angebotsplanung im öffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen für die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenhänge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abhängigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.</abstract>
    <identifier type="serial">08-04</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1084</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10555</identifier>
    <enrichment key="SourceTitle">To appear in Heureka '08</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Marika Neumann</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-04</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Preisplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Linienplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierung</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="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="91B74">Models of real-world systems</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1055/ZR_08_04.pdf</file>
  </doc>
  <doc>
    <id>915</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation>DFG Reseach Center Matheon "Mathematics for Key Technologies"</creatingCorporation>
    <contributingCorporation>Technische Universität Berlin</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-11-01</completedDate>
    <publishedDate>2007-11-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">When Periodic Timetables are Suboptimal</title>
    <abstract language="eng">The timetable is the essence of the service offered by any provider of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the timetable has a major impact on both operating costs and on passenger comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two strategies with respect to vehicle operation costs. It turns out that for short time horizons, periodic timetabling can be suboptimal; for sufficiently long time horizons, however, periodic timetabling can always be done in an optimal way'.</abstract>
    <identifier type="serial">07-29</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1056</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9151</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2007. Jörg Kalcsics, Stefan Nickel (eds.) Springer 2008, pp. 449-454</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Christian Liebchen</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-29</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Taktfahrplan</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Fahrplan</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Nahverkehr</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>periodic timetable</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>trip timetable</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>public transport</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="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/915/ZR_07_29.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/915/ZR_07_29.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>854</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-03-23</completedDate>
    <publishedDate>2005-03-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Fare Planning for Public Transport</title>
    <abstract language="eng">In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments.</abstract>
    <identifier type="serial">05-20</identifier>
    <identifier type="opus3-id">854</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8541</identifier>
    <author>Ralf Borndörfer</author>
    <author>Marika Neumann</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-20</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>fare planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>demand function</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>discrete choice model</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</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="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MATHEON-B1">MATHEON-B1</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/854/ZR-05-20.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/854/ZR-05-20.ps</file>
  </doc>
  <doc>
    <id>6393</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2017-05-05</completedDate>
    <publishedDate>2017-05-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Propagation Approach to Acyclic Rolling Stock Rotation Optimization</title>
    <abstract language="eng">The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the&#13;
 timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-63930</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the IAROR conference RailLille 2017</enrichment>
    <author>Boris Grimm</author>
    <submitter>Boris Grimm</submitter>
    <author>Ralf Borndörfer</author>
    <author>Markus Reuther</author>
    <author>Stanley Schade</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-24</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</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="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6393/ZR-17-24.pdf</file>
  </doc>
  <doc>
    <id>1740</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-12-19</completedDate>
    <publishedDate>2012-12-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach</title>
    <abstract language="eng">We present a game-theoretic approach to optimize the strategies of toll enforcement&#13;
on a motorway network. In contrast to previous approaches,&#13;
we consider a network with an arbitrary&#13;
topology, and we handle the fact that&#13;
users may choose their Origin-Destination path; in particular they may take a detour to&#13;
avoid sections with a high control rate. We show that a Nash equilibrium can be&#13;
computed with an LP (although the game is not zero-sum), and we give a MIP for the computation&#13;
of a Stackelberg equilibrium. Experimental results based on an application to the&#13;
enforcement of a truck toll on German motorways are presented.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-17401</identifier>
    <identifier type="doi">/10.1016/j.endm.2013.05.100</identifier>
    <enrichment key="SourceTitle">Appeared in: Electronic Notes in Discrete Mathematics  Volume 41, 5 June 2013, Pages 253–260</enrichment>
    <submitter>Guillaume Sagnol</submitter>
    <author>Ralf Borndörfer</author>
    <author>Julia Buwaya</author>
    <author>Guillaume Sagnol</author>
    <author>Elmar Swarat</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-47</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Stackelberg Equilibrium</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Game Theory</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</value>
    </subject>
    <collection role="ccs" number="I.">Computing Methodologies</collection>
    <collection role="msc" number="91-XX">GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES</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="sagnol">Sagnol, Guillaume</collection>
    <collection role="persons" number="swarat">Swarat, Elmar</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1740/zib_report_12_47.pdf</file>
  </doc>
  <doc>
    <id>1429</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-11-21</completedDate>
    <publishedDate>2011-11-21</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An IP Approach to Toll Enforcement Optimization on German Motorways</title>
    <abstract language="eng">This paper proposes the first model for toll enforcement optimization&#13;
on German motorways. The enforcement is done by mobile control teams and our&#13;
goal is to produce a schedule achieving network-wide control, proportional to&#13;
spatial and time-dependent traffic distributions. Our model consists of two&#13;
parts. The first plans&#13;
control tours using a vehicle routing approach with profits and some side&#13;
constraints. The second plans feasible rosters for the control teams. Both&#13;
problems can be modeled as Multi-Commodity Flow Problems. Adding additional&#13;
coupling constraints produces a large-scale integrated integer programming&#13;
formulation. We show that this model can be solved to optimality for real&#13;
world instances associated with a control area in East Germany.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">11-42</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-14299</identifier>
    <identifier type="doi">10.1007/978-3-642-29210-1_51</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2011, Diethard Klatte et al. (eds.), 2012, pp. 317-322</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Elmar Swarat</submitter>
    <author>Guillaume Sagnol</author>
    <author>Elmar Swarat</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-42</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Toll Enforcement</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Vehicle Routing Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Duty Roster Planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Programming</value>
    </subject>
    <collection role="msc" number="90B06">Transportation, logistics</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="sagnol">Sagnol, Guillaume</collection>
    <collection role="persons" number="swarat">Swarat, Elmar</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1429/ZR-11-42.pdf</file>
  </doc>
  <doc>
    <id>5277</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>2014-10-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Price of Spite in Spot-checking games</title>
    <abstract language="eng">We introduce the class of spot-checking games (SC games). These games model&#13;
problems where the goal is to distribute fare inspectors over a toll network.&#13;
Although SC games are not zero-sum, we show that a Nash equilibrium&#13;
can be computed by linear programming.&#13;
The computation of a strong Stackelberg equilibrium is&#13;
more relevant for this problem, but we show that this is NP-hard.&#13;
However, we give some bounds on the \emph{price of spite},&#13;
which measures how the&#13;
payoff of the inspector&#13;
degrades when committing to a Nash equilibrium. &#13;
Finally, we demonstrate the quality of these bounds for a real-world application,&#13;
namely the enforcement of a truck toll on German motorways.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="doi">10.1007/978-3-662-44803-8</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-52775</identifier>
    <enrichment key="SourceTitle">Appeared in: 7th International Symposium on Algorithmic Game Theory (SAGT'2014), as a brief announcement</enrichment>
    <submitter>Guillaume Sagnol</submitter>
    <author>Guillaume Sagnol</author>
    <author>Ralf Borndörfer</author>
    <author>Thomas Schlechte</author>
    <author>Elmar Swarat</author>
    <series>
      <title>ZIB-Report</title>
      <number>14-38</number>
    </series>
    <collection role="msc" number="05-XX">COMBINATORICS (For finite fields, see 11Txx)</collection>
    <collection role="msc" number="91-XX">GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES</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="sagnol">Sagnol, Guillaume</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="swarat">Swarat, Elmar</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5277/sagt-one-page-zib.pdf</file>
  </doc>
  <doc>
    <id>6454</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>2017-07-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Demand-Driven Line Planning with Selfish Routing</title>
    <abstract language="eng">Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-64547</identifier>
    <identifier type="doi">10.1007/978-3-319-89920-6_91</identifier>
    <enrichment key="SourceTitle">appeared in: Operations Research Proceedings 2017</enrichment>
    <author>Malte Renken</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Amin Ahmadi</author>
    <author>Ralf Borndörfer</author>
    <author>Guvenc Sahin</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-38</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="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="ECMath-MI7">ECMath-MI7</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6454/ZR-17-38.pdf</file>
  </doc>
  <doc>
    <id>5347</id>
    <completedYear>2015</completedYear>
    <publishedYear>2015</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>2015-01-22</completedDate>
    <publishedDate>2015-01-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">G-RIPS 2014 RailLab - Towards robust rolling stock rotations</title>
    <abstract language="eng">The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an &#13;
opportunity for high-achieving graduate-level students to work in teams on a &#13;
real-world research project proposed by a sponsor from industry or the public &#13;
sector. Each G-RIPS team consists of four international students (two from &#13;
the US and two from European universities), an academic mentor, and an industrial sponsor. &#13;
&#13;
This is the report of the Rail-Lab project on the definition and integration of &#13;
robustness aspects into optimizing rolling stock schedules. In general, there is&#13;
a trade-off for complex systems between robustness and efficiency. The ambitious &#13;
goal was to explore this trade-off by implementing numerical simulations and &#13;
developing analytic models. &#13;
&#13;
In rolling stock planning a very large set of industrial railway requirements, &#13;
such as vehicle composition, maintenance constraints, infrastructure capacity, &#13;
and regularity aspects, have to be considered in an integrated model. General &#13;
hypergraphs provide the modeling power to tackle those requirements. &#13;
Furthermore, integer programming approaches are able to produce high quality &#13;
solutions for the deterministic problem.&#13;
&#13;
When stochastic time delays are considered, the mathematical programming problem &#13;
is much more complex and presents additional challenges. Thus, we started with a &#13;
basic variant of the deterministic case, i.e., we are only considering &#13;
hypergraphs representing vehicle composition and regularity.  &#13;
We transfered solution approaches for robust optimization&#13;
from the airline industry to the setting of railways and attained a &#13;
reasonable measure of robustness. Finally, we present and discuss different &#13;
methods to optimize this robustness measure.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-53475</identifier>
    <note>ZIB-Report 14-34</note>
    <author>Charles Brett</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Rebecca Hoberg</author>
    <author>Meritxell Pacheco</author>
    <author>Kyle Smith</author>
    <author>Ralf Borndörfer</author>
    <author>Ricardo Euler</author>
    <author>Gerwin Gamrath</author>
    <author>Boris Grimm</author>
    <author>Olga Heismann</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <author>Alexander Tesch</author>
    <series>
      <title>ZIB-Report</title>
      <number>14-34</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>robust optimization, rolling stock planning</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="tesch">Tesch, Alexander</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5347/ZR-14-34.pdf</file>
  </doc>
  <doc>
    <id>6031</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>2016-08-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Modulo Network Simplex with Integrated Passenger Routing</title>
    <abstract language="eng">Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-60319</identifier>
    <enrichment key="SourceTitle">To appear in: Operations Research Proceedings 2016</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Heide Hoppmann</submitter>
    <author>Heide Hoppmann</author>
    <author>Marika Karbstein</author>
    <author>Fabian Löbel</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-43</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>periodic timetabling, modulo network simplex, passenger routing</value>
    </subject>
    <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="hoppmann">Hoppmann, Heide</collection>
    <collection role="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="persons" number="fabian.loebel">Löbel, Fabian</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6031/ZR-16-43.pdf</file>
  </doc>
  <doc>
    <id>5372</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-02-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Recent Success Stories on Optimization of Railway Systems</title>
    <abstract language="eng">Planning and operating railway transportation systems is an extremely&#13;
hard task due to the combinatorial complexity of the underlying discrete&#13;
optimization problems, the technical intricacies, and the immense size of&#13;
the problem instances. Because of that, however, mathematical models&#13;
and optimization techniques can result in large gains for both railway cus-&#13;
tomers and operators, e.g., in terms of cost reductions or service quality&#13;
improvements. In the last years a large and growing group of researchers&#13;
in the OR community have devoted their attention to this domain devel-&#13;
oping mathematical models and optimization approaches to tackle many&#13;
of the relevant problems in the railway planning process. However, there&#13;
is still a gap to bridge between theory and practice, with&#13;
a few notable exceptions. In this paper we address three success stories,&#13;
namely, long-term freight train routing (part I), mid-term rolling stock&#13;
rotation planning (part II), and real-time train dispatching (part III). In&#13;
each case, we describe real-life, successful implementations. We will dis-&#13;
cuss the individual problem setting, survey the optimization literature,&#13;
and focus on particular aspects addressed by the mathematical models.&#13;
We demonstrate on concrete applications how mathematical optimization&#13;
can support railway planning and operations. This gives proof that math-&#13;
ematical optimization can support the planning of rolling stock resources.&#13;
Thus, mathematical models and optimization can lead to a greater effi-&#13;
ciency of railway operations and will serve as a powerful and innovative&#13;
tool to meet recent challenges of the railway industry.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-53726</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the IAROR conference RailTokyo</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Markus Reuther</submitter>
    <author>Torsten Klug</author>
    <author>Leonardo Lamorgese</author>
    <author>Carlo Mannino</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>14-47</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway operations</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>capacity optimization</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</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="klug">Klug, Torsten</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="KOSMOS">KOSMOS</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="ROTOR">ROTOR</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5372/ZR-14-47.pdf</file>
  </doc>
  <doc>
    <id>5350</id>
    <completedYear/>
    <publishedYear>2015</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-01-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Metric Inequalities for Routings on Direct Connections with Application in Line Planning</title>
    <abstract language="eng">We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct   connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows.&#13;
The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with  transfers.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="doi">10.1016/j.disopt.2015.07.004</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-53507</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete Optimization 18 (2015) 56-75</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Marika Karbstein</submitter>
    <author>Marika Karbstein</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-07</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>transfers</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>direct connection</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>metric inequalities</value>
    </subject>
    <collection role="msc" number="90B20">Traffic problems</collection>
    <collection role="msc" number="90C10">Integer programming</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="projects" number="ECMath-MI3">ECMath-MI3</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5350/ZR_15_07.pdf</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>963</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-08-02</completedDate>
    <publishedDate>2007-08-02</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Railway Track Allocation Problems</title>
    <abstract language="eng">The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.</abstract>
    <identifier type="serial">07-20</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">974</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9631</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2007. J. Kalcsics, S. Nickel (eds.)Springer 2008, pp. 117-122</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>07-20</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway track allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>timetabling</value>
    </subject>
    <subject>
      <language>eng</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="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/963/ZR_07_20.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/963/ZR_07_20.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>1448</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-01-18</completedDate>
    <publishedDate>2012-01-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Optimierung des Linienplans 2010 in Potsdam</title>
    <abstract language="deu">Im Zuge der Übernahme von 6 Linien der Havelbus Verkehrsgesellschaft&#13;
mbH durch die ViP Verkehr in Potsdam GmbH ergab sich 2009 die Notwendigkeit der&#13;
Entwicklung eines neuen Linien- und Taktplans für das Jahr 2010.&#13;
Das Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)&#13;
entwickelt in einem Projekt des DFG-Forschungszentrums Matheon ein Verfahren zur mathematischen Linienoptimierung. Dieses Tool wurde bei der Optimierung des ViP Linienplans 2010 in&#13;
einer projektbegleitenden Studie eingesetzt, um Alternativen bei&#13;
verschiedenen Planungs- und Zielvorgaben auszuloten.&#13;
In dem Artikel wird eine Auswertung der Ergebnisse mit dem Verkehrsanalysesystem Visum der PTV AG beschrieben. Die Auswertungen bestätigen, dass mit Hilfe von mathematischer Optimierung eine  weitere Verkürzung der Reisezeit um 1%, eine&#13;
als um 6% verkürzt empfundene Reisezeit, 10% weniger Fahrzeit im&#13;
Fahrzeug und eine gleichzeitige Kostenreduktion um 5% möglich sind.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">12-04</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-14486</identifier>
    <enrichment key="SourceTitle">Erschienen in: Der Nahverkehr 30/4 (2012) 34-39</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Karbstein Marika</submitter>
    <author>Isabel Friedow</author>
    <author>Marika Karbstein</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-04</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Fallstudie</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Linienplan</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierung</value>
    </subject>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90B20">Traffic problems</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1448/ZR-12-04.pdf</file>
  </doc>
  <doc>
    <id>1456</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-01-25</completedDate>
    <publishedDate>2012-01-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning</title>
    <abstract language="eng">Vehicle rotation planning is a fundamental problem in&#13;
  rail transport. It decides how the railcars, locomotives, and&#13;
  carriages are operated in order to implement the trips of the&#13;
  timetable.  One important planning requirement is operational&#13;
  regularity, i.e., using the rolling stock in the same way on every&#13;
  day of operation. We propose to take regularity into account by&#13;
  modeling the vehicle rotation planning problem as a minimum cost&#13;
  hyperassignment problem (HAP). Hyperassignments are generalizations&#13;
  of assignments from directed graphs to directed hypergraphs.&#13;
  Finding a minimum cost hyperassignment is&#13;
  NP-hard.&#13;
  Most instances arising from regular vehicle rotation planning, however, can&#13;
  be solved well in practice. We show that, in particular, clique&#13;
  inequalities strengthen the canonical LP relaxation substantially.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">11-46</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-14564</identifier>
    <identifier type="url">http://link.springer.com/chapter/10.1007%2F978-3-642-29210-1_10</identifier>
    <enrichment key="SourceTitle">Appeared in: Klatte, D., Lüthi, H.-J., and Schmedders, K., editors, Operations Research Proceedings 2011, pages 59–64</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Olga Heismann</submitter>
    <author>Olga Heismann</author>
    <series>
      <title>ZIB-Report</title>
      <number>11-46</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>hyperassignments</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle rotation planning</value>
    </subject>
    <collection role="msc" number="05C65">Hypergraphs</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C10">Integer programming</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="projects" number="MATHEON-B22">MATHEON-B22</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1456/ZR 11-46.pdf</file>
  </doc>
  <doc>
    <id>1447</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-01-18</completedDate>
    <publishedDate>2012-01-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Note on Menger's Theorem for Hypergraphs</title>
    <abstract language="eng">We prove the companion Theorem to Menger's Theorem for&#13;
  hypergraphs. This result gives rise to a new class of blocking pairs&#13;
  of ideal matrices, that generalize the incidence matrices of cuts&#13;
  and paths.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="serial">12-03</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-14471</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Marika Karbstein</submitter>
    <author>Marika Karbstein</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-03</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>ideal matrices</value>
    </subject>
    <collection role="msc" number="90C10">Integer programming</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1447/ZR-12-03.pdf</file>
  </doc>
  <doc>
    <id>1570</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-08-07</completedDate>
    <publishedDate>2012-08-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Global Manufacturing: How to Use Mathematical Optimisation Methods to Transform to Sustainable Value Creation</title>
    <abstract language="eng">It is clear that a transformation to sustainable value creation is needed, because business as usual is not an option for preserving competitive advantages of leading industries. What does that mean? This contribution proposes possible approaches for a shift in existing manufacturing paradigms. In a first step, sustainability aspects from the German Sustainability Strategy and from the tools of life cycle sustainability assessment are chosen to match areas of a value creation process. Within these aspects are indicators, which can be measured within a manufacturing process. Once these data are obtained they can be used to set up a mathematical linear pulse model of manufacturing in order to analyse the evolution of the system over time, that is the transition process, by using a system dynamics approach. An increase of technology development by a factor of 2 leads to an increase of manufacturing but also to an increase of climate change. Compensation measures need to be taken. This can be done by e.g. taking money from the GDP (as an indicator of the aspect ``macroeconomic performance''). The value of the arc from that building block towards climate change must then be increased by a factor of 10. The choice of independent and representative indicators or aspects shall be validated and double-checked for their significance with the help of multi-criteria mixed-integer programming optimisation methods.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-15703</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 10th Global Conference on Sustainable Manufacturing (GCSM2012), Günther Seliger, S. Engin Kilic (Hrsg.), pp. 538 - 545, 2012  ISBN-978-605-63463-1-6</enrichment>
    <author>Rene Scheumann</author>
    <submitter>Ralf Borndörfer</submitter>
    <author>Armin Fügenschuh</author>
    <author>Sebastian Schenker</author>
    <author>Ingmar Vierhaus</author>
    <author>Ralf Borndörfer</author>
    <author>Matthias Finkbeiner</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-28</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multi-Criteria Optimisation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Sustainability Indicator</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>System Dynamics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Value Creation Process</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="pacs" number="00.00.00">GENERAL</collection>
    <collection role="msc" number="90B30">Production models</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="fuegenschuh">Fügenschuh, Armin</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1570/ScheumannFuegenschuhSchenkerVierhausBorndoerferFinkbeiner2012__global_manufacturing.pdf</file>
  </doc>
  <doc>
    <id>1581</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>47</pageFirst>
    <pageLast>57</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>25</volume>
    <type>reportzib</type>
    <publisherName>Schloss Dagstuhl - Leibniz-Zentrum für Informatik</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2012-09-17</completedDate>
    <publishedDate>2012-09-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Direct Connection Approach to Integrated Line Planning and Passenger Routing</title>
    <abstract language="eng">The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of&#13;
extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.</abstract>
    <parentTitle language="eng">ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems</parentTitle>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-15812</identifier>
    <identifier type="doi">http://dx.doi.org/10.4230/OASIcs.ATMOS.2012.47</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. of the 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2012), D. Delling, L. Liberti (eds.) pp. 47-57.  Open Access Series in Informatics, vol. 25</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Marika Karbstein</submitter>
    <editor>Daniel Delling</editor>
    <author>Marika Karbstein</author>
    <editor>Leo Liberti</editor>
    <series>
      <title>ZIB-Report</title>
      <number>12-29</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>transfers</value>
    </subject>
    <collection role="msc" number="90B20">Traffic problems</collection>
    <collection role="msc" number="90C10">Integer programming</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1581/ZR_12_29.pdf</file>
  </doc>
  <doc>
    <id>1184</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-07-13</completedDate>
    <publishedDate>2010-07-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Quickest Path to the Goal</title>
    <abstract language="eng">We provide an introduction into the mathematics of and with paths. Not on the shortest, but hopefully on an entertaining path!</abstract>
    <identifier type="serial">10-21</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1245</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11840</identifier>
    <enrichment key="SourceTitle">Appeared in: Aigner,  Behrends (Eds.) Mathematics Everywhere, American Mathematical Society, 2010, pp. 27-51</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Martin Grötschel</author>
    <author>Andreas Löbel</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-21</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>shortest paths</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>operations research</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C10">Integer programming</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="loebel">Löbel, Andreas</collection>
    <collection role="projects" number="BMBF-DS">BMBF-DS</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="projects" number="SenWiFo-Telebus">SenWiFo-Telebus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1184/ZR_10_21.pdf</file>
  </doc>
  <doc>
    <id>1170</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation>Zuse-Institut Berlin</creatingCorporation>
    <contributingCorporation>Lufthansa Systems Berlin GmbH</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-05-31</completedDate>
    <publishedDate>2010-05-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Robust Tail Assignment</title>
    <abstract language="eng">We propose an efficient column generation method to minimize the probability of delay propagations along aircraft rotations. In this way, delay resistant schedules can be constructed. Computational results for large-scale real-world problems demonstrate substantial punctuality improvements. The method can be generalized to crew and integrated scheduling problems.</abstract>
    <identifier type="serial">10-08</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1231</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11707</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Ivan Dovica</author>
    <author>Ivo Nowak</author>
    <author>Thomas Schickinger</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-08</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Flugzeugumlaufplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>robuste Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Spaltenerzeugung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Tail Assignment</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Robust Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Column Generation</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90B15">Network models, stochastic</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="90C15">Stochastic programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-rxOPT-tail">LHS-rxOPT-tail</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1170/ZR_10_08.pdf</file>
  </doc>
  <doc>
    <id>1174</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>Matheon</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-06-14</completedDate>
    <publishedDate>2010-06-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Models for Line Planning with Transfers</title>
    <abstract language="eng">We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by “connection capacities” into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results.</abstract>
    <identifier type="serial">10-11</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1234</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11742</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Marika Neumann</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-11</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Linienplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Umsteigen</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Kombinatorische Optimierung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>transfers</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B20">Traffic problems</collection>
    <collection role="msc" number="90C10">Integer programming</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1174/ZR_10_11.pdf</file>
  </doc>
  <doc>
    <id>1183</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2010-07-13</completedDate>
    <publishedDate>2010-07-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Linienoptimierung - reif für die Praxis?</title>
    <abstract language="deu">Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege berücksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 für Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es möglich, durch Veränderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen über minimale Kosten und Fahrzeiten zu machen.</abstract>
    <identifier type="serial">10-20</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1244</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11832</identifier>
    <enrichment key="SourceTitle">App. in: HEUREKA '11, FGSV Verl. 2011. CD-ROM</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Marika Neumann</author>
    <series>
      <title>ZIB-Report</title>
      <number>10-20</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Linienplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierung</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="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="91B74">Models of real-world systems</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1183/ZR_10_20.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1183/ZR_10_20.ps</file>
  </doc>
  <doc>
    <id>6481</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>2017-08-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Cost Projection Methods for the Shortest Path Problem with Crossing Costs</title>
    <abstract language="eng">Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-64817</identifier>
    <enrichment key="FulltextUrl">Appeared in: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)</enrichment>
    <author>Marco Blanco</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Ralf Borndörfer</author>
    <author>Nam-Dung Hoang</author>
    <author>Anton Kaier</author>
    <author>Pedro Maristany de las Casas</author>
    <author>Thomas Schlechte</author>
    <author>Swen Schlobach</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-48</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="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6481/ZR-17-48.pdf</file>
  </doc>
  <doc>
    <id>5607</id>
    <completedYear/>
    <publishedYear>2015</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2015-07-09</completedDate>
    <publishedDate>2015-07-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue</title>
    <abstract language="eng">Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics&#13;
can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering  problems.  We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and&#13;
  airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-56070</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <author>Christof Schulz</author>
    <author>Elmar Swarat</author>
    <author>Steffen Weider</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-44</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="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="persons" number="schulz">Schulz, Christof</collection>
    <collection role="persons" number="swarat">Swarat, Elmar</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <collection role="projects" number="LHS-CS">LHS-CS</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/5607/ZR-15-44.pdf</file>
  </doc>
  <doc>
    <id>1549</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-05-31</completedDate>
    <publishedDate>2012-05-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Case Study on Optimizing Toll Enforcements on Motorways</title>
    <abstract language="eng">In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour&#13;
planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network&#13;
and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to&#13;
feasible rosters for one month. We present computational results in a&#13;
case-study on a German subnetwork which documents the practicability of our approach.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-15498</identifier>
    <identifier type="doi">10.4230/OASIcs.SCOR.2012.1</identifier>
    <enrichment key="SourceTitle">Appeared in: 3rd Student Conference on Operational Research. S. Ravizza, P. Holborn (eds.) Open Acess Series in Informatics 22 (2012) pp. 1-10</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Elmar Swarat</submitter>
    <author>Guillaume Sagnol</author>
    <author>Elmar Swarat</author>
    <series>
      <title>ZIB-Report</title>
      <number>12-21</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Vehicle Routing Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Duty Rostering</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Operations Research</value>
    </subject>
    <collection role="ccs" number="G.2.3">Applications (NEW)</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="sagnol">Sagnol, Guillaume</collection>
    <collection role="persons" number="swarat">Swarat, Elmar</collection>
    <collection role="projects" number="TOLLCONTROLOPT">TOLLCONTROLOPT</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1549/ZR-12-21.pdf</file>
  </doc>
  <doc>
    <id>6011</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>2016-09-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Line Planning on Path Networks with Application to the Istanbul Metrobüs</title>
    <abstract language="eng">Bus rapid transit systems in developing and newly&#13;
  industrialized countries often consist of a trunk with a path&#13;
  topology. On this trunk, several overlapping lines are operated&#13;
  which provide direct connections. The demand varies heavily over the&#13;
  day, with morning and afternoon peaks typically in reverse&#13;
  directions. We propose an integer programming&#13;
  model for this problem, derive a structural property of line plans&#13;
  in the static (or single period) ``unimodal demand'' case, and&#13;
  consider approaches to the solution of the multi-period version that&#13;
  rely on clustering the demand into peak and off-peak service&#13;
  periods. An application to the Metrobüs system of Istanbul is&#13;
  discussed.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-60119</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Oytun Arslan</author>
    <author>Ziena Elijazyfer</author>
    <author>Hakan Güler</author>
    <author>Malte Renken</author>
    <author>Güvenc Sahin</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>16-38</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>unimodal demand</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</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="ECMath-MI3">ECMath-MI3</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6011/ZR-16-38.pdf</file>
  </doc>
  <doc>
    <id>6594</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>2017-11-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Timetable Sparsification by Rolling Stock Rotation Optimization</title>
    <abstract language="eng">Rolling stock optimization is a task that naturally arises by operating a railway system.&#13;
It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike. &#13;
Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-65948</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>Boris Grimm</submitter>
    <author>Matthias Breuer</author>
    <author>Boris Grimm</author>
    <author>Markus Reuther</author>
    <author>Stanley Schade</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-63</number>
    </series>
    <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="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6594/ZR-17-63.pdf</file>
  </doc>
  <doc>
    <id>6339</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2017-11-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Pattern Detection For Large-Scale Railway Timetables</title>
    <abstract language="eng">We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-63390</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the IAROR conference RailLille 2017</enrichment>
    <author>Stanley Schade</author>
    <submitter>Stanley Schade</submitter>
    <author>Ralf Borndörfer</author>
    <author>Matthias Breuer</author>
    <author>Boris Grimm</author>
    <author>Markus Reuther</author>
    <author>Thomas Schlechte</author>
    <author>Patrick Siebeneicher</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-17</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>railway timetables</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>visualization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>pattern detection</value>
    </subject>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="grimm">Grimm, Boris</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="schade">Schade, Stanley</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="reuther">Reuther, Markus</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6339/ZR-17-17.pdf</file>
  </doc>
  <doc>
    <id>1125</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-04-14</completedDate>
    <publishedDate>2009-04-14</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Planning Problems in Public Transit</title>
    <abstract language="eng">Every day, millions of people are transported by buses, trains, and airplanes in Germany. Public transit (PT) is of major importance for the quality of life of individuals as well as the productivity of entire regions. Quality and efficiency of PT systems depend on the political framework (state-run, market oriented) and the suitability of the infrastructure (railway tracks, airport locations), the existing level of service (timetable, flight schedule), the use of adequate technologies (information, control, and booking systems), and the best possible deployment of equipment and resources (energy, vehicles, crews). The decision, planning, and optimization problems arising in this context are often gigantic and “scream” for mathematical support because of their complexity. This article sketches the state and the relevance of mathematics in planning and operating public transit, describes today’s challenges, and suggests a number of innovative actions. The current contribution of mathematics to public transit is — depending on the transportation mode — of varying depth. Air traffic is already well supported by mathematics. Bus traffic made significant advances in recent years, while rail traffic still bears significant opportunities for improvements. In all areas of public transit, the existing potentials are far from being exhausted. For some PT problems, such as vehicle and crew scheduling in bus and air traffic, excellent mathematical tools are not only available, but used in many places. In other areas, such as rolling stock rostering in rail traffic, the performance of the existing mathematical algorithms is not yet sufficient. Some topics are essentially untouched from a mathematical point of view; e.g., there are (except for air traffic) no network design or fare planning models of practical relevance. PT infrastructure construction is essentially devoid of mathematics, even though enormous capital investments are made in this area. These problems lead to questions that can only be tackled by engineers, economists, politicians, and mathematicians in a joint effort. Among other things, the authors propose to investigate two specific topics, which can be addressed at short notice, are of fundamental importance not only for the area of traffic planning, should lead to a significant improvement in the collaboration of all involved parties, and, if successful, will be of real value for companies and customers: • discrete optimal control: real-time re-planning of traffic systems in case of disruptions, • model integration: service design in bus and rail traffic. Work on these topics in interdisciplinary research projects could be funded by the German ministry of research and education (BMBF), the German ministry of economics (BMWi), or the German science foundation (DFG).</abstract>
    <identifier type="serial">09-13</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1174</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11252</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Martin Grötschel</author>
    <author>Ulrich Jaeger</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-13</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>öffentlicher Verkehr</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>diskrete Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>ganzzahlige Programmierung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>public transit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>discrete optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B06">Transportation, logistics</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1125/ZR_09_13.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1125/ZR_09_13.ps</file>
  </doc>
  <doc>
    <id>1132</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>CNPq (Sponsor)</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-06-03</completedDate>
    <publishedDate>2009-06-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Set Partitioning Approach to Shunting</title>
    <abstract language="eng">The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems.</abstract>
    <identifier type="serial">09-18</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1181</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11326</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Carlos Cardonha</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-18</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>set partitioning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial packing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle positioning</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C06">Large-scale problems</collection>
    <collection role="msc" number="90C10">Integer programming</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="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1132/ZR_09_18.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1132/ZR_09_18.ps</file>
  </doc>
  <doc>
    <id>1117</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-02-24</completedDate>
    <publishedDate>2009-02-24</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Steiner Connectivity Problem</title>
    <abstract language="eng">The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role.</abstract>
    <identifier type="serial">09-07</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1166</identifier>
    <identifier type="doi">10.1007/s10107-012-0564-5</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11171</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Marika Neumann</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-07</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Steiner Tree</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Partition Inequalities</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Paths</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Connectivity</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Generalization</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="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1117/ZR_09_07.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1117/ZR_09_07.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1117/ZR-09-07revised.pdf</file>
  </doc>
  <doc>
    <id>1107</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-12-18</completedDate>
    <publishedDate>2008-12-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System (Extended Abstract)</title>
    <abstract language="eng">Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.</abstract>
    <identifier type="serial">08-53</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1148</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11076</identifier>
    <enrichment key="SourceTitle">Appeared in: ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems. Matteo Fischetti and Peter Widmayer (eds.)Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, Dagstuhl, Germany, 2008. http://drops.dagstuhl.de/opus/volltexte/2008/1583</enrichment>
    <author>Luis Miguel Torres</author>
    <submitter>unknown unknown</submitter>
    <author>Ramiro Torres</author>
    <author>Ralf Borndörfer</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-53</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>computational complexity</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>public transport</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</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="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1107/ZR_08_53.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1107/ZR_08_53.ps</file>
  </doc>
  <doc>
    <id>1106</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-12-18</completedDate>
    <publishedDate>2008-12-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the Line Planning Problem in Tree Networks</title>
    <abstract language="eng">We introduce an optimization model for the line planning problem in a public transportation system that aims at minimizing operational costs while ensuring a given level of quality of service in terms of available transport capacity. We discuss the computational complexity of the model for tree network topologies and line structures that arise in a real-world application at the Trolebus Integrated System in Quito. Computational results for this system are reported.</abstract>
    <identifier type="serial">08-52</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1147</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11069</identifier>
    <author>Luis Miguel Torres</author>
    <submitter>unknown unknown</submitter>
    <author>Ramiro Torres</author>
    <author>Ralf Borndörfer</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-52</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>computational complexity</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>public transport optimization</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</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="projects" number="MATHEON-B1">MATHEON-B1</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1106/ZR_08_52.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1106/ZR_08_52.ps</file>
  </doc>
  <doc>
    <id>1120</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-02-25</completedDate>
    <publishedDate>2009-02-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Discrete Optimization in Public Transportation</title>
    <abstract language="eng">The mathematical treatment of planning problems in public transit has made significant advances in the last decade. Among others, the classical problems of vehicle and crew scheduling can nowadays be solved on a routine basis using combinatorial optimization methods. This is not yet the case for problems that pertain to the design of public transit networks, and for the problems of operations control that address the implementation of a schedule in the presence of disturbances. The article gives a sketch of the state and important developments in these areas, and it addresses important challenges. The vision is that mathematical tools of computer aided scheduling (CAS) will soon play a similar role in the design and operation of public transport systems as CAD systems in manufacturing.</abstract>
    <abstract language="deu">Die mathematische Behandlung von Planungsproblemen im öffentlichen Verkehr hat im letzten Jahrzehnt große Fortschritte gemacht. Klassische Probleme wie die Umlauf- und die Dienstplanung können heutzutage routinemäßig mit kombinatorischen Optimierungsmethoden gelöst werden. Die Behandlung von Problemen der Angebotsplanung und der Betriebssteuerung sind dagegen noch nicht ganz auf diesem Stand. Dieser Artikel gibt einen Überblick über den Stand der Forschung, über wichtige Entwicklungen und einige Herausforderungen in diesem Gebiet. Die Vision ist, dass mathematische Planungswerkzeuge im öffentlichen Verkehr (Computer Aided Scheduling, CAS) in Zukunft eine ähnliche Rolle spielen werden wie CAD-Systeme in der industriellen Fertigung.</abstract>
    <identifier type="serial">08-56</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1168</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11207</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>08-56</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Öffentlicher Verkehr</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Nahverkehr</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Public Transit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Optimization</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B20">Traffic problems</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1120/ZR_08_56.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1120/ZR_08_56.ps</file>
  </doc>
</export-example>
