CANCELED: News on Periodic Event Scheduling

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.