License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2022.3
URN: urn:nbn:de:0030-drops-171075
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17107/
Go to the corresponding OASIcs Volume Portal

Bortoletto, Enrico ; Lindner, Niels ; Masing, Berenike

Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling

pdf-format:
OASIcs-ATMOS-2022-3.pdf (1.0 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bortoletto_et_al:OASIcs.ATMOS.2022.3,
  author =	{Bortoletto, Enrico and Lindner, Niels and Masing, Berenike},
  title =	{{Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{3:1--3:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17107},
  URN =		{urn:nbn:de:0030-drops-171075},
  doi =		{10.4230/OASIcs.ATMOS.2022.3},
  annote =	{Keywords: Periodic Timetabling, Tropical Geometry, Neighborhood Search, Mixed-Integer Programming}
}

Keywords: Periodic Timetabling, Tropical Geometry, Neighborhood Search, Mixed-Integer Programming
Collection: 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)
Issue Date: 2022
Date of publication: 06.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI