A double-track train rescheduling for incident conditions: optimisation model and decomposition method

This paper studies a double-track train rescheduling problem, when an un-foreseen incident over a specific time horizon occurs. We solve the problem by utilising a rescheduling technique named bi-operational approach. An incident-based mixed-integer rescheduling model is proposed which is solved using CPLEX software which automatically generates optimal solutions. To reduce the computation time, an innovative method is proposed which decomposes the main problem to five smaller sub-problems, each of which is solved by branch-and-bound algorithm. Moreover, a novel heuristic is proposed which divides the available computation time between sub-problems proportionately depending on their sizes. An experimental analysis, on two double-track railways of Iranian network, indicates that the decomposition method provides near-optimal solutions with much shorter computation times compared with CPLEX. The analysis also provides evidence for effectiveness of the proposed heuristic in tackling large-scale problems; so that good feasible solutions are achievable in limited times compatible with real-time use.