CANCELLED: News on Periodic Event Scheduling

Niels Lindner (Zuse Institute Berlin)
Start date

Friday, 27 Mar 2020, 12:00

End date

Friday, 27 Mar 2020, 13:00

Polak 2-16
Polak Building
Campus Woudestein
Spoken Language

Creating and optimizing periodic timetables is a key task in public transportation.

The underlying mathematical framework is the Periodic Event Scheduling Problem (PESP) in combinatorial optimization. The talk gives an overview of recent developments on PESP: We present our concurrent solver that computed the currently best known primal and dual bounds for all hard instances of the benchmarking library PESPlib. Moreover, we give a graph partitioning view on PESP, leading to a maximum cut heuristic and balanced separator approaches. On the theoretical side, we investigate the parameterized complexity of PESP in terms of treewidth and several other graph parameters. In the end, we outline our current research direction on connecting integrated periodic timetablin and passenger routing  with tropical geometry.


More information

Secretariat Econometrics

Office: ET-21/ET-22
Phone: 010-408 1259/1264