Modeling the first train timetabling problem with minimal missed trains and synchronization time differences in subway networks

- Provide a new formulation to precisely describe the first train transfer problem in mathematical terms.
- The non-linear constraints of the model are linearized.
- A heuristic algorithm is developed to solve the Beijing subway case with a local search method.
- We observe that departure time constraints can be relaxed for the first train timetabling problem.

Urban railway transportation organization is a systematic activity that is usually composed of several stages, including network design, line planning, timetabling, rolling stock and staffing. In this paper, we study the optimization of first train timetables for an urban railway network that focuses on designing convenient and smooth timetables for morning passengers. We propose a mixed integer programming (MIP) model for minimizing train arrival time differences and the number of missed trains, i.e., the number of trains without transfers within a reasonable time at interchange stations as an alternative to minimize passenger transfer waiting times. This is interesting from the operator's point of view, and we show that both criteria are equivalent. Starting from an intuitive model for the first train transfer problem, we then linearize the non-linear constraints by utilizing problem specific knowledge. In addition, a local search algorithm is developed to solve the timetabling problem. Through computational experiments involving the Beijing subway system, we demonstrate the computational efficiency of the exact model and the heuristic approach. Finally, three practical suggestions are proposed for the operation and management of the urban railway transit system.