Computationally efficient train timetable generation of metro networks with uncertain transfer walking time to reduce passenger waiting time: A generalized Benders decomposition-based method. (September 2022)

• Record Type: Journal Article
• Authors: Hu, Yuting; Li, Shukai; Dessouky, Maged M.; Yang, Lixing; Gao, Ziyou
• Is Part Of: Transportation research. Volume 163(2022)
• Page Start: 210
• Page End: 231
• Publication Date: 2022-09
• Subjects: Urban metro network -- Timetabling generation -- Uncertain transfer time -- Robust optimization -- Benders decomposition; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2022.07.007
• Languages: English
• ISSNs: 0191-2615

Abstract

Abstract: With more and more interchange stations in a large-scale metro network, passengers tend to transfer between different metro lines from origination to destination, sometimes even more than once. Passenger waiting time is one of the critical standards for measuring the quality of urban public transport services. To support high service quality, this paper proposes a mixed integer nonlinear programming (MINLP) model for the train timetable generation problem of a metro network that minimizes the transfer waiting times and access passenger waiting times. In the mathematical formulation of the model, the transfer walking times at the interchange stations between two connected lines are treated as uncertain parameters. The robust train timetable generation model is formulated to optimize timetables by adjusting arrival and departure times of each train in the metro network to reduce access and transfer passenger waiting times. A robust counterpart is further derived that transforms the formulated robust model into a deterministic one. Moreover, a generalized Benders decomposition technique based approach is developed to decompose the robust counterpart into a subproblem and a master problem. The subproblem is a convex quadratic programming problem that can be solved efficiently. Finally, two sets of numerical examples, consisting of a small case and a large-scale case based on a real-world portion of the Beijing metro network, are performed to demonstrate the validity and practicability of the proposed model and solution approach. Highlights: Train timetable coordination with uncertain transfer walking time is considered. A mixed integer nonlinear programming model is formulated for train timetable problem. A generalized Benders decomposition algorithm is designed. The proposed method reduces the passenger waiting times for metro networks.