Scheduling local and express trains in suburban rail transit lines: Mixed–integer nonlinear programming and adaptive genetic algorithm. (November 2021)

• Record Type: Journal Article
• Authors: Tang, Lianhua; D'Ariano, Andrea; Xu, Xingfang; Li, Yantong; Ding, Xiaobing; Samà, Marcella
• Is Part Of: Computers & operations research. Volume 135(2021)
• Publication Date: 2021-11
• Subjects: Suburban rail transit (SRT) -- Train timetabling -- Traditional (all) stopping mode (TSM) -- Express/local stopping mode (ELM) -- Passenger travel time (PTT) -- Train overtaking -- Adaptive genetic algorithm (A–GA) -- Mixed–integer nonlinear programming (MINLP); Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105436
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We investigate the train timetabling problem in suburban rail transit lines by considering (1) the traditional stopping mode (TSM), in which all trains stop at each station, and (2) the express/local stopping mode (ELM), in which express trains can skip certain low–demand stations. We first propose two mixed–integer linear programming models for the train timetabling problem under the TSM with and without capacity constraints. Next, we develop two mixed–integer nonlinear programming models under the ELM with and without "overtaking"; thus, a total of four optimization models are proposed. The objective is to minimize the passenger travel time (PTT). Owing to the NP–hardness of the studied problem, we propose an adaptive genetic algorithm (A–GA) that can efficiently solve the four proposed models. The A–GA is customized to solve the train timetabling problem with train capacity, overtaking, and other operational constraints, reducing the PTT. To evaluate the performance of the proposed algorithm, we conduct numerical experiments on 60 randomly generated realistic instances and a real–world case study based on Shanghai Metro Line 16. The computational results for the realistic instances indicate that our A–GA can obtain near–optimal solutions with significantly less computation time than an established commercial solver. The computational results from the real-world case study quantify the benefits of considering the combination of the ELM and overtaking strategies in train timetabling. Furthermore, we perform a sensitivity analysis on key parameters of our mathematical formulations. The results provide insights to railway managers on how to set key parameters when applying the proposed formulations and solution methodology in practice. Highlights: We propose mixed–integer programming formulations for train timetabling in suburban transit lines. We consider passengers being left behind under limited train capacity and express/local stopping mode. We accurately calculate passenger waiting times under oversaturated traffic conditions. We present an adaptive genetic algorithm for optimizing train timetables with overtaking possibility. The proposed algorithm yields good quality solutions in a short computation time.