Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations

8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Karl Nachtigall ; Jens Opitz

Others  :  http://drops.dagstuhl.de/opus/volltexte/2008/1588/pdf/08002.Nachtigall.1588.pdf
PID  :  6945

来源: CEUR

【 摘 要 】

In the last 15 years periodic timetable problems have found much interest in the combinatorial optimization community. We will focus on the optimisation task to minimise a weighted sum of undesirable slack times. This problem can be formulated as a mixed integer linear problem, which for real world instances is hard to solve. This is mainly caused by the integer variables, the so-called modulo parameter. At first we will discuss some results on the polyhedral structure of the periodic timetable problem. These ideas allow to define a modulo simplex basic solution by calculating the basic variables from modulo equations. This leads to a modulo network simplex method, which iteratively improves the solution by changing the simplex basis.