Joint optimization of train scheduling and maintenance planning in a railway network: A heuristic algorithm using Lagrangian relaxation

Train scheduling and maintenance planning compete for the resources in a railway network. A commonly used way is dealing with maintenance planning first and then train scheduling, or vice versa. In this paper, we propose a joint optimization model for the two problems in a railway network with double-track, where the upstream and downstream trains are independent and a maintenance task on a section cannot be split or disrupted. In order to solve the model, a heuristic algorithm using Lagrangian relaxation is developed. Due to the large number of constraints, we use a dynamic constraint-generation technique in the iterations of the sub-gradient optimization procedure. We apply the model and algorithm to a practical problem in the Chinese railway network, in which some additional trains are inserted into a fixed existing timetable and the maintenance plan on the involved high-speed railway sections is adjusted. The computational results illustrate the effectiveness and efficiency of the proposed model and algorithm.