Train timetabling in rail transit network under uncertain and dynamic demand using Advanced and Adaptive NSGA-II

It is critical to design an adaptable and stable train timetable for long-term use in rail transit network that not only meets the dynamicity of passenger demand in different hours within one day, but also meets the uncertainty of passenger demand in different days. In this study, a scenario-based train timetabling framework is constructed to classify the possibilities of passenger demand in multiple days into a set of scenarios based on profile and volume of passenger demand. On this basis, multi-scenario demand input method (MM) is introduced to deal with the uncertainty of passenger demand, which is different from one-scenario method (OM) and average-scenario method (AM). A MM-based mixed-integer linear programming model is formulated for the bi-objective train timetabling problem under uncertain and dynamic demand at acyclic network level, in which multi-scenario small-granularity passenger demand follows actual distribution processed from historical data. The two objectives are to minimize train service cost and penalized passenger waiting time from perspectives of enterprises and passengers. Advanced and Adaptive NSGA II (AANSGA-II) is proposed to cope with the high-complexity bi-objective problem, which applies advanced population sorting based on neighborhood distance, adaptive genetic operation based on scoring mechanism and improved population initialization based on boundary individuals. The model and algorithm are testified by a small-scale numerical experiment on a virtual line and a large-scale real-world instance in Shenyang Metro network. As a result, MM-based train timetables are generally better than AM-based and OM-based train timetables in reducing generalized cost and raising robustness. Besides, AANSGA-II is more applicable than NSGA-II and CPLEX in shortening computation time at the same time of improving computation result.