Urban rail train timetabling for the end-of-service period with passenger accessibility and operation cost: An advanced benders decomposition algorithm

Train timetable during the end-of-service period is crucial for passenger accessibility and operation cost in urban rail transit networks. Existing studies have investigated the last train timetabling problem for improving passenger accessibility. This study investigates a train timetabling problem for the end-of-service period, which concentrates on the coordination of the service ending time on different lines and the last several train timetables. A mixed-integer linear programming model based on a space–time network is proposed to determine the number of train services provided in the end-of-service period while coordinating the timetables of both last and non-last trains, of which the objective function minimizes the number of inaccessible passengers and operation costs. To address the computational challenges, a Benders decomposition algorithm is developed and enhanced with dedicated acceleration strategies. A dual solution algorithm is proposed to efficiently generate the optimal dual solution of the subproblems. A reformulation and update strategy is proposed for the Benders cuts, and a relax-and-fix heuristic is developed to improve solving efficiency of the master problem. Small-scale numerical experiments demonstrate the optimality and efficiency of the proposed Benders decomposition algorithm. Large-scale experiments in the Wuhan network show that the proposed model and algorithm can improve passenger accessibility by 6.8% without additional operation cost, and by 38.7% with a 28.4% increment in operation cost.