<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>9230</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>2023-09-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Incremental Heuristics for Periodic Timetabling</title>
    <abstract language="eng">We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-92309</identifier>
    <identifier type="doi">10.1007/978-3-031-58405-3_59</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="AcceptedDate">2023-11-02</enrichment>
    <enrichment key="SourceTitle">appeared in Operations Research Proceedings 2023</enrichment>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <author>Niels Lindner</author>
    <submitter>Niels Lindner</submitter>
    <author>Christian Liebchen</author>
    <series>
      <title>ZIB-Report</title>
      <number>23-22</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed-Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Public Transport</value>
    </subject>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="MathPlus-AA3-8">MathPlus-AA3-8</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/9230/ZR-23-22.pdf</file>
  </doc>
  <doc>
    <id>8275</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>2021-07-03</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Forward Cycle Bases and Periodic Timetabling</title>
    <abstract language="eng">Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance \texttt{R1L1} of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-82756</identifier>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2021.2</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="AcceptedDate">30.07.2021</enrichment>
    <enrichment key="SourceTitle">appeared in 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)</enrichment>
    <author>Niels Lindner</author>
    <submitter>Niels Lindner</submitter>
    <author>Christian Liebchen</author>
    <author>Berenike Masing</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-18</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cycle Bases</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed Integer Programming</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="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="persons" number="masing">Masing, Berenike</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="MathPlus-AA3-8">MathPlus-AA3-8</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8275/ZR-21-18.pdf</file>
  </doc>
  <doc>
    <id>8862</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>2022-12-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Periodic Timetabling with Integrated Track Choice for Railway Construction Sites</title>
    <abstract language="eng">We propose a mixed-integer linear programming model to generate and optimize periodic timetables with integrated track choice in the context of railway construction sites. When a section of a railway network becomes unavailable, the nearby areas are typically operated close to their capacity limits, and hence carefully modeling headways and allowing flexible routings becomes vital. We therefore discuss first how to integrate headway constraints into the Periodic Event Scheduling Problem (PESP) that do not only prevent overtaking, but also guarantee conflict-free timetables in general and particularly inside stations. Secondly, we introduce a turn-sensitive event-activity network, which is able to integrate routing alternatives for turnarounds at stations, e.g., turning at a platform vs. at a pocket track for metro-like systems. We propose several model formulations to include track choice, and finally evaluate them on six real construction site scenarios on the S-Bahn Berlin network.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-88626</identifier>
    <identifier type="doi">10.1016/j.jrtpm.2023.100416</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <author>Berenike Masing</author>
    <submitter>Berenike Masing</submitter>
    <author>Niels Lindner</author>
    <author>Christian Liebchen</author>
    <series>
      <title>ZIB-Report</title>
      <number>22-26</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Railway Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Event Scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Train Routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Turnarounds</value>
    </subject>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="persons" number="masing">Masing, Berenike</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="MathPlus-AA3-8">MathPlus-AA3-8</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8862/zib_report.pdf</file>
  </doc>
  <doc>
    <id>9210</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>5:1</pageFirst>
    <pageLast>5:15</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>115</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice</title>
    <abstract language="eng">We consider maintenance sites for urban rail systems, where unavailable tracks typically require changes to the regular timetable, and often even to the line plan. In this paper, we present an integrated mixed-integer linear optimization model to compute an optimal line plan that makes best use of the available tracks, together with a periodic timetable, including its detailed routing on the tracks within the stations. The key component is a flexible, turn-sensitive event-activity network that allows to integrate line planning and train routing using a track choice extension of the Periodic Event Scheduling Problem (PESP). Major goals are to maintain as much of the regular service as possible, and to keep the necessary changes rather local. Moreover, we present computational results on real construction site scenarios on the S-Bahn Berlin network. We demonstrate that this integrated problem is indeed solvable on practically relevant instances.</abstract>
    <parentTitle language="eng">23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2023.5</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Berenike Masing</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <author>Christian Liebchen</author>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="persons" number="masing">Masing, Berenike</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="MathPlus-AA3-8">MathPlus-AA3-8</collection>
  </doc>
  <doc>
    <id>9248</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>100416</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>28</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Periodic timetabling with integrated track choice for railway construction sites</title>
    <abstract language="eng">We propose a mixed-integer linear programming model to generate and optimize periodic timetables with integrated track choice in the context of railway construction sites. When a section of a railway network becomes unavailable, the nearby areas are typically operated close to their capacity limits, and hence carefully modeling headways and allowing flexible routings becomes vital. We therefore discuss first how to integrate headway constraints into the Periodic Event Scheduling Problem (PESP) that do not only prevent overtaking, but also guarantee conflict-free timetables in general and particularly inside stations. Secondly, we introduce a turn-sensitive event-activity network, which is able to integrate routing alternatives for turnarounds at stations, e.g., turning at a platform vs. at a pocket track for metro-like systems. We propose several model formulations to include track choice, and finally evaluate them on six real construction site scenarios on the S-Bahn Berlin network.</abstract>
    <parentTitle language="eng">Journal of Rail Transport Planning &amp; Management</parentTitle>
    <identifier type="doi">10.1016/j.jrtpm.2023.100416</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-88626</enrichment>
    <author>Berenike Masing</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <author>Christian Liebchen</author>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="persons" number="masing">Masing, Berenike</collection>
    <collection role="projects" number="MathPlus-AA3-8">MathPlus-AA3-8</collection>
    <collection role="projects" number="Mathplus-PaA3">Mathplus-PaA3</collection>
  </doc>
  <doc>
    <id>8663</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>100081</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>11</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Timetable merging for the Periodic Event Scheduling Problem</title>
    <abstract language="eng">We propose a new mixed integer programming based heuristic for computing new benchmark primal solutions for instances of the PESPlib. The PESPlib is a collection of instances for the Periodic Event Scheduling Problem (PESP), comprising periodic timetabling problems inspired by real-world railway timetabling settings, and attracting several international research teams during the last years. We describe two strategies to merge a set of good periodic timetables. These make use of the instance structure and minimum weight cycle bases, finally leading to restricted mixed integer programming formulations with tighter variable bounds. Implementing this timetable merging approach in a concurrent solver, we improve the objective values of the best known solutions for the smallest and largest PESPlib instances by 1.7 and 4.3 percent, respectively.</abstract>
    <parentTitle language="eng">EURO Journal on Transportation and Logistics</parentTitle>
    <identifier type="doi">10.1016/j.ejtl.2022.100081</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-81587</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">false</enrichment>
    <author>Niels Lindner</author>
    <submitter>Niels Lindner</submitter>
    <author>Christian Liebchen</author>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MathPlus-AA3-8">MathPlus-AA3-8</collection>
  </doc>
</export-example>
