Modeling and solving the last-shift period train scheduling problem in subway networks

Train arrivals and departures should be scheduled over a certain period when talking about train timetabling problems. For the midnight train operations, passengers significantly concern about the network transfer issue. Currently, some existing studies address the last train timetabling problem by only optimizing the timetable for the last train on a single subway line whereas this study takes into consideration the complete last-shift period. We first put forward a last-shift train scheduling model aiming to minimize the transfer waiting time and maximize the network connectivity. Two genetic-based algorithms, an integer-coded genetic algorithm (ICGA) and a binary-coded genetic algorithm (BCGA) are developed. The relevance and applicability of the algorithms have been demonstrated by several testing networks and real-world implementation. The ICGA and the branch-and-bound approaches show high efficiency in obtaining the optimal solutions for a small network, while the BCGA approach that bases on an integer-programming model shows low efficiency in addressing problems of sparse solution spaces. However, the branch-and-bound approach has limited ability in solving medium-sized networks. On the contrary, the ICGA generates satisfactory results in solution quality and computational efficiency when applied to large-sized networks.