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

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.