Reducing the time needed to solve the global rescheduling problem for railway networks

摘要

In this paper a method is introduced to reduce the computation time needed to solve the global rescheduling problem for railway networks. The railway network is modeled as a switching max-plus-linear model. This model is used to determine the constraints of the rescheduling problem. The rescheduling problem is described as a Mixed Integer Linear Programming (MILP) problem. The dispatching actions in this implementation are limited to changing the order of the trains and breaking connections at stations. These dispatching actions are most effective for smaller delays. It is therefore assumed that the delays are less than some maximum value. The proposed reduction method determines which (combinations of) control inputs will never be used if the delays are below this maximum value and removes them, as well as the constraints associated to them, resulting in a smaller model. Using the reduced model in the MILP problem significantly decreases the time needed to solve the MILP problem while still yielding the optimal solution for the original MILP problem.