<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>6974</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>2018-07-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Separation of Cycle Inequalities in Periodic Timetabling</title>
    <abstract language="eng">Cycle inequalities play an important role in the polyhedral study of the periodic&#13;
timetabling problem. We give the first pseudo-polynomial time separation algo-&#13;
rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial&#13;
time separability of the change-cycle inequalities. Moreover, we provide several&#13;
NP-completeness results, indicating that pseudo-polynomial time is best possible.&#13;
The efficiency of these cutting planes is demonstrated on real-world instances of the&#13;
periodic timetabling problem.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-69746</identifier>
    <identifier type="doi">https://doi.org/10.1016/j.disopt.2019.100552</identifier>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="AcceptedDate">2019/08/13</enrichment>
    <enrichment key="SourceTitle">Discrete Optimization</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Heide Hoppmann</author>
    <author>Marika Karbstein</author>
    <author>Niels Lindner</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-16</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cycle inequality</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Change-cycle inequality</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <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="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</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/6974/sepa_cycle.pdf</file>
  </doc>
  <doc>
    <id>6968</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>2018-07-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable</title>
    <abstract language="eng">We consider the following planning problem in public transportation: Given a&#13;
periodic timetable, how many vehicles are required to operate it?&#13;
In [9], for this sequential approach, it is proposed to first expand the periodic&#13;
timetable over time, and then answer the above question by solving a flow-based&#13;
aperiodic optimization problem.&#13;
In this contribution we propose to keep the compact periodic representation of&#13;
the timetable and simply solve a particular perfect matching problem. For practical&#13;
networks, it is very much likely that the matching problem decomposes into several&#13;
connected components. Our key observation is that there is no need to change any&#13;
turnaround decision for the vehicles of a line during the day, as long as the timetable&#13;
stays exactly the same.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-69688</identifier>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2018.16</identifier>
    <enrichment key="SourceTitle">appeared in: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Niels Lindner</submitter>
    <author>Marika Karbstein</author>
    <author>Christian Liebchen</author>
    <author>Niels Lindner</author>
    <series>
      <title>ZIB-Report</title>
      <number>18-38</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Vehicle scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bipartite matching</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <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="lindner">Lindner, Niels</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/6968/PeriodicVehicleScheduling.pdf</file>
  </doc>
  <doc>
    <id>5673</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-12-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Passenger Routing for Periodic Timetable Optimization</title>
    <abstract language="eng">The task of periodic timetabling is to schedule the trips in a public transport system by determining arrival and departure times at every station such that travel and transfer times are minimized. To date, the optimization literature generally assumes that passengers do not respond to changes in the timetable, i.e., the passenger routes are fixed. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We show that different routing models have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. to different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-56739</identifier>
    <identifier type="doi">10.1007/s12469-016-0132-0</identifier>
    <enrichment key="SourceTitle">Public Transport, 2016</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter> Hoppmann</submitter>
    <author>Heide Hoppmann</author>
    <author>Marika Karbstein</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-55</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Passenger routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Public transport</value>
    </subject>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C11">Mixed 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="persons" number="hoppmann">Hoppmann, Heide</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/5673/borndoerferHoppmannKarbstein_publicTransport_ZTP.pdf</file>
  </doc>
  <doc>
    <id>5653</id>
    <completedYear>2015</completedYear>
    <publishedYear>2015</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2015-07-23</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Timetabling and Passenger Routing in Public Transport</title>
    <abstract language="eng">The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.</abstract>
    <parentTitle language="eng">Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-55305</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Heide Hoppmann</submitter>
    <author>Heide Hoppmann</author>
    <author>Marika Karbstein</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Passenger routing</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Periodic timetabling</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Public transport</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="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>5530</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-06-04</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Timetabling and Passenger Routing in Public Transport</title>
    <abstract language="eng">The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.</abstract>
    <parentTitle language="eng">Appeard in: Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)</parentTitle>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-55305</identifier>
    <enrichment key="SourceTitle">Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>Heide Hoppmann</submitter>
    <author>Heide Hoppmann</author>
    <author>Marika Karbstein</author>
    <series>
      <title>ZIB-Report</title>
      <number>15-31</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Passenger routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Public transport</value>
    </subject>
    <collection role="msc" number="90B06">Transportation, logistics</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="persons" number="hoppmann">Hoppmann, Heide</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/5530/ZR-15-31.pdf</file>
  </doc>
</export-example>
