A simulated annealing algorithm for first train transfer problem in urban railway networks

Passengers often have to transfer between different subway lines to reach their destinations. Time coordination of first trains between feeder and connecting lines plays an important role in reducing passenger transfer waiting time. This paper addresses the first train synchronization problem, and proposes a first train coordination model which aims at minimizing total passenger transfer waiting time. Taking into account the specification of the first train problem, we use mixed-integer variables to enable the correct calculation of the waiting time for the “first available” train at each transfer station. In addition, we develop a simulated annealing algorithm to deal with a case study of the Beijing subway network. Results indicate that the proposed approach reduces the passenger waiting time from 705.1 min of the original first train timetable to 567.42 min of the scheduled one.