View in EDS HTML Full Text PDF Full Text

The Tropical and Zonotopal Geometry of Periodic Timetables.

Saved in:
Bibliographic Details
Title: The Tropical and Zonotopal Geometry of Periodic Timetables.
Authors: Bortoletto, Enrico1,2 (AUTHOR) bortoletto@zib.de, Lindner, Niels1 (AUTHOR) lindner@zib.de, Masing, Berenike1,2 (AUTHOR) masing@zib.de
Source: Discrete & Computational Geometry. Apr2025, Vol. 73 Issue 3, p719-763. 45p.
Subjects: Discrete geometry, Supply chain management, Mathematical optimization, Linear programming, Public transit
Abstract: The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetables in public transport. A solution to a PESP instance consists of three parts: a periodic timetable, a periodic tension, and integer offset values. While the space of periodic tensions has received much attention in the past, we explore geometric properties of the other two components. The general aim of this paper is to establish novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables as a disjoint union of polytropes. These are 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 neighbourhood relations of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope, and then study its zonotopal tilings. These are related to the hyperrectangle of fractional periodic tensions, as well as the polytropes of the periodic timetable space, and we detail their interplay. To conclude, we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis. [ABSTRACT FROM AUTHOR]
Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: egs
DbLabel: Engineering Source
An: 183753295
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: The Tropical and Zonotopal Geometry of Periodic Timetables.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bortoletto%2C+Enrico%22">Bortoletto, Enrico</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> bortoletto@zib.de</i><br /><searchLink fieldCode="AR" term="%22Lindner%2C+Niels%22">Lindner, Niels</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> lindner@zib.de</i><br /><searchLink fieldCode="AR" term="%22Masing%2C+Berenike%22">Masing, Berenike</searchLink><relatesTo>1,2</relatesTo> (AUTHOR)<i> masing@zib.de</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+%26+Computational+Geometry%22">Discrete & Computational Geometry</searchLink>. Apr2025, Vol. 73 Issue 3, p719-763. 45p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Discrete+geometry%22">Discrete geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Supply+chain+management%22">Supply chain management</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+optimization%22">Mathematical optimization</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+programming%22">Linear programming</searchLink><br /><searchLink fieldCode="DE" term="%22Public+transit%22">Public transit</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetables in public transport. A solution to a PESP instance consists of three parts: a periodic timetable, a periodic tension, and integer offset values. While the space of periodic tensions has received much attention in the past, we explore geometric properties of the other two components. The general aim of this paper is to establish novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables as a disjoint union of polytropes. These are 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 neighbourhood relations of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope, and then study its zonotopal tilings. These are related to the hyperrectangle of fractional periodic tensions, as well as the polytropes of the periodic timetable space, and we detail their interplay. To conclude, we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=183753295
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1007/s00454-024-00686-2
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 45
        StartPage: 719
    Subjects:
      – SubjectFull: Discrete geometry
        Type: general
      – SubjectFull: Supply chain management
        Type: general
      – SubjectFull: Mathematical optimization
        Type: general
      – SubjectFull: Linear programming
        Type: general
      – SubjectFull: Public transit
        Type: general
    Titles:
      – TitleFull: The Tropical and Zonotopal Geometry of Periodic Timetables.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bortoletto, Enrico
      – PersonEntity:
          Name:
            NameFull: Lindner, Niels
      – PersonEntity:
          Name:
            NameFull: Masing, Berenike
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 04
              Text: Apr2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 01795376
          Numbering:
            – Type: volume
              Value: 73
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: Discrete & Computational Geometry
              Type: main
ResultId 1