Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Tropical Neighbourhood Search: A New Heuristic for Periodic Timetabling

Please always quote using this URN: urn:nbn:de:0297-zib-87385
  • 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 [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 available in the solver. Finally, we provide better primal bounds for five PESPlib instances.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Enrico BortolettoORCiD, Niels LindnerORCiD, Berenike MasingORCiD
Document Type:ZIB-Report
Tag:Mixed-Integer Programming; Neighbourhood Search; Periodic Timetabling; Tropical Geometry
MSC-Classification:14-XX ALGEBRAIC GEOMETRY / 14Txx Tropical geometry [See also 12K10, 14M25, 14N10, 52B20] / 14T05 Tropical geometry [See also 12K10, 14M25, 14N10, 52B20]
51-XX GEOMETRY (For algebraic geometry, see 14-XX) / 51Mxx Real and complex geometry / 51M20 Polyhedra and polytopes; regular figures, division of spaces [See also 51F15]
52-XX CONVEX AND DISCRETE GEOMETRY / 52Bxx Polytopes and polyhedra / 52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
Date of first Publication:2022/07/19
Series (Serial Number):ZIB-Report (22-13)
Published in:appeared in 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.