<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>9906</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>14</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2025-08-28</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm</title>
    <abstract language="eng">Given a public transportation network, which and how many passenger routes can potentially be shortest paths, when all possible timetables are taken into account? &#13;
This question leads to shortest path problems on graphs with interval costs on their arcs and is closely linked to multi-objective optimization.&#13;
We introduce a Dijkstra algorithm based on polynomials over the tropical semiring that computes complete or minimal sets of efficient paths.&#13;
We demonstrate that this approach is computationally feasible by employing it on the public transport network of the city of Wuppertal and instances of the benchmarking set TimPassLib, and we evaluate the resulting sets of passenger routes.</abstract>
    <parentTitle language="eng">EURO Journal on Transportation and Logistics</parentTitle>
    <identifier type="arxiv">2412.14654</identifier>
    <identifier type="doi">10.1016/j.ejtl.2025.100163</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Berenike Masing</author>
    <submitter>Berenike Masing</submitter>
    <author>Niels Lindner</author>
    <author>Enrico Bortoletto</author>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="persons" number="bortoletto">Bortoletto, Enrico</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>
  </doc>
  <doc>
    <id>9231</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">Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times</title>
    <abstract language="eng">The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-92315</identifier>
    <identifier type="doi">10.1007/978-3-031-58405-3_51</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="SubmissionStatus">accepted for publication</enrichment>
    <enrichment key="AcceptedDate">2023-11-02</enrichment>
    <enrichment key="SourceTitle">appeared in Operations Research Proceedings 2023</enrichment>
    <author>Enrico Bortoletto</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <series>
      <title>ZIB-Report</title>
      <number>23-23</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="persons" number="bortoletto">Bortoletto, Enrico</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/9231/ZR-23-23.pdf</file>
  </doc>
  <doc>
    <id>9775</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>4:1</pageFirst>
    <pageLast>4:18</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>123</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Periodic Event Scheduling with Flexible Infrastructure Assignment</title>
    <abstract language="eng">We present novel extensions of the Periodic Event Scheduling Problem (PESP) that integrate the assignment of activities to infrastructure elements. An application of this is railway timetabling, as station and platform capacities are limited and need to be taken into account. We show that an assignment of activities to platforms can always be made periodic, and that it can be beneficial to allow larger periods for the assignment than for the timetable. We present mixed-integer programming formulations for the general problem, as well as for the practically relevant case when multiple platforms can be considered equivalent, for which we present a bipartite matching approach. We finally test and compare these models on real-world instances.</abstract>
    <parentTitle language="eng">24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2024.4</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Enrico Bortoletto</author>
    <submitter>Enrico Bortoletto</submitter>
    <author>Rolf Nelson van Lieshout</author>
    <author>Berenike Masing</author>
    <author>Niels Lindner</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="persons" number="bortoletto">Bortoletto, Enrico</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-PaA3">Mathplus-PaA3</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8410</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>masterthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The tropical tiling of periodic timetable space and a dual modulo network simplex algorithm</title>
    <abstract language="eng">We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic&#13;
ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem.</abstract>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <advisor>Ralf Borndörfer</advisor>
    <author>Enrico Bortoletto</author>
    <submitter>Niels Lindner</submitter>
    <advisor>Niels Lindner</advisor>
    <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="bortoletto">Bortoletto, Enrico</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <thesisGrantor>Freie Universität Berlin</thesisGrantor>
  </doc>
  <doc>
    <id>8670</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-05-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Tropical and Zonotopal Geometry of Periodic Timetables</title>
    <abstract language="eng">The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetabling problems in public transport. A solution to PESP consists of three parts: a periodic timetable, a periodic tension, and integer periodic offset values. While the space of periodic tension has received much attention in the past, we explore geometric properties of the other two components, establishing novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables, and decompose it into polytropes, i.e., polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on the tropical neighbourhood of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope. We relate its zonotopal tilings back to the hyperrectangle of fractional periodic tensions and to the tropical neighbourhood of the periodic timetable space. To conclude we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="arxiv">2204.13501</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-86708</identifier>
    <identifier type="doi">https://doi.org/10.1007/s00454-024-00686-2</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="SourceTitle">Appeared in Discrete &amp; Computational Geometry</enrichment>
    <author>Enrico Bortoletto</author>
    <submitter>Enrico Bortoletto</submitter>
    <author>Niels Lindner</author>
    <author>Berenike Masing</author>
    <series>
      <title>ZIB-Report</title>
      <number>22-09</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>periodic event scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>tropical geometry</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>zonotopal tilings</value>
    </subject>
    <collection role="msc" number="14T05">Tropical geometry [See also 12K10, 14M25, 14N10, 52B20]</collection>
    <collection role="msc" number="51M20">Polyhedra and polytopes; regular figures, division of spaces [See also 51F15]</collection>
    <collection role="msc" number="52B12">Special polytopes (linear programming, centrally symmetric, etc.)</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="persons" number="bortoletto">Bortoletto, Enrico</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>
    <collection role="projects" number="Mathplus-PaA3">Mathplus-PaA3</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8670/zibrep.pdf</file>
  </doc>
  <doc>
    <id>8738</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-07-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling</title>
    <abstract language="eng">Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The&#13;
most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [3]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [4]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods&#13;
available in the solver. Finally, we provide better primal bounds for five PESPlib instances.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-87385</identifier>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2022.3</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="SourceTitle">appeared in 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)</enrichment>
    <author>Enrico Bortoletto</author>
    <submitter>Enrico Bortoletto</submitter>
    <author>Niels Lindner</author>
    <author>Berenike Masing</author>
    <series>
      <title>ZIB-Report</title>
      <number>22-13</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Periodic Timetabling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Tropical Geometry</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Neighbourhood Search</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mixed-Integer Programming</value>
    </subject>
    <collection role="msc" number="14T05">Tropical geometry [See also 12K10, 14M25, 14N10, 52B20]</collection>
    <collection role="msc" number="51M20">Polyhedra and polytopes; regular figures, division of spaces [See also 51F15]</collection>
    <collection role="msc" number="52B12">Special polytopes (linear programming, centrally symmetric, etc.)</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="persons" number="bortoletto">Bortoletto, Enrico</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/8738/report.pdf</file>
  </doc>
  <doc>
    <id>8810</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>3:1</pageFirst>
    <pageLast>3:19</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>106</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling</title>
    <abstract language="eng">Periodic timetabling is a central aspect of both the long-term organization and the day-to-day operations of a public transportation system. The Periodic Event Scheduling Problem (PESP), the combinatorial optimization problem that forms the mathematical basis of periodic timetabling, is an extremely hard problem, for which optimal solutions are hardly ever found in practice. The most prominent solving strategies today are based on mixed-integer programming, and there is a concurrent PESP solver employing a wide range of heuristics [Borndörfer et al., 2020]. We present tropical neighborhood search (tns), a novel PESP heuristic. The method is based on the relations between periodic timetabling and tropical geometry [Bortoletto et al., 2022]. We implement tns into the concurrent solver, and test it on instances of the benchmarking library PESPlib. The inclusion of tns turns out to be quite beneficial to the solver: tns is able to escape local optima for the modulo network simplex algorithm, and the overall share of improvement coming from tns is substantial compared to the other methods available in the solver. Finally, we provide better primal bounds for five PESPlib instances.</abstract>
    <parentTitle language="eng">22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2022.3</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-87385</enrichment>
    <author>Enrico Bortoletto</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <author>Berenike Masing</author>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="persons" number="bortoletto">Bortoletto, Enrico</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>
    <collection role="projects" number="Mathplus-PaA3">Mathplus-PaA3</collection>
  </doc>
  <doc>
    <id>9209</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>7:1</pageFirst>
    <pageLast>7:18</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">Periodic Timetabling with Cyclic Order Constraints</title>
    <abstract language="eng">Periodic timetabling for highly utilized railway networks is a demanding challenge. We formulate an infrastructure-aware extension of the Periodic Event Scheduling Problem (PESP) by requiring that not only events, but also activities using the same infrastructure must be separated by a minimum headway time. This extended problem can be modeled as a mixed-integer program by adding constraints on the sum of periodic tensions along certain cycles, so that it shares some structural properties with standard PESP. We further refine this problem by fixing cyclic orders at each infrastructure element. Although the computational complexity remains unchanged, the mixed-integer programming model then becomes much smaller. Furthermore, we also discuss how to find a minimal subset of infrastructure elements whose cyclic order already prescribes the order for the remaining parts of the network, and how cyclic order information can be modeled in a mixed-integer programming context. In practice, we evaluate the impact of cyclic orders on a real-world instance on the S-Bahn Berlin network, which turns out to be computationally fruitful.</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.7</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Enrico Bortoletto</author>
    <submitter>Niels Lindner</submitter>
    <author>Niels Lindner</author>
    <author>Berenike Masing</author>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="persons" number="bortoletto">Bortoletto, Enrico</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>
    <collection role="projects" number="Mathplus-PaA3">Mathplus-PaA3</collection>
  </doc>
  <doc>
    <id>10188</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>397</pageFirst>
    <pageLast>402</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times</title>
    <abstract language="eng">The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.</abstract>
    <parentTitle language="eng">Operations Research Proceedings 2023</parentTitle>
    <identifier type="doi">10.1007/978-3-031-58405-3_51</identifier>
    <enrichment key="Series">Lecture Notes in Operations Research</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-92315</enrichment>
    <enrichment key="AcceptedDate">2023-11-02</enrichment>
    <author>Enrico Bortoletto</author>
    <submitter>Niels Lindner</submitter>
    <editor>Guido Voigt</editor>
    <author>Niels Lindner</author>
    <editor>Malte Fliedner</editor>
    <editor>Knut Haase</editor>
    <editor>Wolfgang Brüggemann</editor>
    <editor>Kai Hoberg</editor>
    <editor>Jörn Meissner</editor>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="persons" number="bortoletto">Bortoletto, Enrico</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="Mathplus-PaA3">Mathplus-PaA3</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
</export-example>
