High-Level Implicit Enumerations for Quadratic Periodic Train Timetabling with Prioritized Cross-Line Operations

Periodic train timetables provide passengers with easily accessible rail transport services. However, in networked railway operations, some long-distance cross-line trains have high operational priority and pose difficulties for scheduling local services. In this paper, we address the minimal-cycle-length periodic train timetabling problem with high-priority cross-line operations and complex local train types. We propose a special set of constraints to accommodate the prespecified operational times of cross-line operations with regard to system robustness. As the cycle length is regarded as a decision variable, the formulation is nonlinear. To solve the problem, we exploit the connection between cycle length and consumed capacity of periodic timetables and propose high-level cycle-capacity and binary search-guided iterative solution frameworks, which implicitly enumerate the periodic train timetabling problems. Using the real-world operational data of the Guangzhou–Zhuhai Intercity Rail Line, we explore the solution performance of the proposed solution approaches and the straight linearization of the problem, and we also compare the practices of fixing prespecified operational times and our proposed constraints for the cross-line services. The results demonstrate that our proposed method can efficiently achieve flexible while recoverable operational times for the cross-line services and the proposed implicit enumeration algorithms significantly outperform the direct linearization, which increases the search space significantly due to the considerable dimensionality of the periodic decision variables involved. Numerical computations also suggest that our proposed constraints provide a type of approach for balancing the operational convenience and stability margins available in the periodic timetable with the presence of cross-line operations.