Evolutionary Multi-Objective Optimization for High-Speed Railway Train Timetable Rescheduling with Optimal/Suboptimal Solutions into Initial Population*

In this paper, the high-speed railway train timetable rescheduling (TTR) problem with disturbances of trains running in sections and stations is analyzed. It is formulated as a multi-objective optimization problem that minimizes the total train delays and the frequency of adjusting train arrival/departure time. In order to solve the problem, a novel nondominated sorting genetic algorithm-II (NSGA-II) is proposed for TTR. A multi-permutation encoding method is developed to decide the departure orders of the trains at different stations. A rule-based decoding method determines the trains’ feasible schedule according to the departure orders. The constraints to model the train operation are handled through encoding and decoding. To improve the quality of the initial population, one or more Pareto optimal and suboptimal (near Pareto optimal) solutions are included into the initial population, which achieves the utilization of the information and knowledge of TTR in problem-solving. We investigate the effectiveness of the proposed NSGA-II with multi-permutation encoding and the effects of including one or more Pareto optimal solution(s) in the initial population. The experiment results show that including optimal solutions significantly improves the performance of NSGA-II.