Lower and upper bound algorithms for the real-time train scheduling and routing problem in a railway network

This paper focuses on the development of new algorithms for the real-time train scheduling and routing problem in a complex and busy railway network. Since this is a strongly NP-hard problem and practical size instances are complex, simple heuristics are typically adopted in practice to compute feasible but low quality schedules in a short computation time. In order to compute good quality solutions, we consider a mixed-integer linear programming formulation of the problem and solve it with a commercial solver. However, the resolution of this formulation by a commercial solver often takes a too long computation time. Therefore, a new methodology based on the relaxation of some train routing constraints in the formulation is proposed for the quick computation of a good quality lower bound. The lower bound solution is then transformed via a constructive metaheuristic into a feasible schedule, representing a good quality upper bound to the problem. Computational experiments are performed on several disturbed traffic situations for two practical case studies from the Dutch and British railways. The results show that the new lower and upper bounds are computed in a few seconds and are often of similar quality to the ones computed by the commercial solver in hours of computation.