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

Document Type

Journal Article

Publication Date

2024

Subject Area

mode - rail, place - asia, place - urban, operations - scheduling, operations - coordination, economics - operating costs

Keywords

Urban rail, last train timetabling

Abstract

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.

Rights

Permission to publish the abstract has been given by Elsevier, copyright remains with them.

Comments

Transportation Research Part B Home Page:

http://www.sciencedirect.com/science/journal/01912615

Link to Full Text

Share

COinS