A Timetable Rescheduling Approach for Railway based on Monte Carlo Tree Search

Abstract

This paper concentrates on a timetable rescheduling problem on a railway line when trains encounter uncertain emergencies. As for this problem, a novel approach based on Monte Carlo tree search (MCTS) is presented to reduce train delay. More significantly, deep learning is used to improve the computational speed by reducing the depth and breadth of the search tree. A mathematical model about timetable rescheduling under train operation time constraints is formulated to establish the reinforcement learning environment based on which the state, action and reward function are designed. After resolving conflicts in block sections and stations, the agent determines an optimal departure sequence for trains by transversing branches and nodes of the Monte Carlo tree and generating rollout policies with the purpose of minimizing the average total delay along the railway line. To verify the effectiveness of the presented approach, numerical experiments are carried out from a timetable on a railway line. Simulation results demonstrate that the proposed approach can bring about a rescheduling strategy of a less average total delay within a faster computational speed, which is superior to the conventional method.