<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <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>
</export-example>
