Algorithm

Engineering

Transport engineering

Ecology

Biology

Linear programming

Public transport

China

Flow network

Transfer station

Set (abstract data type)

Parallel computing

Beijing

Computer science

Mathematical optimization

Integer (computer science)

Decomposition

Integer programming

Transfer (computing)

Urban rail transit

Operations research

Mathematics

Political science

Rail network

Programming language

European Journal of Operational Research

With the expansion of urban rail networks and the increase of passengers demand, the coordination of strongly connected lines becomes more and more important, because passengers transfer several times during their trips and major transfer stations in the rail network often suffer from over-crowdedness, especially during peak-hours. In this paper, we study the optimization of coordinated train timetables for an urban rail network, which is a tactical timetabling problem and includes several operational constraints and time-dependent passenger-related data. We propose a mathematical formulation with the objective of minimizing the crowdedness of stations during peak hours to synchronously generate the optimal coordinated train timetables. By introducing several sets of passenger flow variables, the timetable coordination problem is formulated as a mixed-integer linear programming problem, that is possible to solve to optimum. To capture the train carrying capacity constraints, we explicitly incorporate the number of in-vehicle passengers in the modelling framework by considering the number of boarding and alighting passengers as passenger flow variables. To improve the computational efficiency of large-scale instances, we develop an Adaptive Large Neighborhood Search (ALNS) algorithm with a set of destroying and repairing operators and a decomposition-based ALNS algorithm. Real-world case studies based on the operational data of Beijing urban rail network are conducted to verify the effectiveness of timetable coordination. The computational results illustrate that the proposed approaches reduce the level of crowdedness of metro stations by around 8% in comparison with the current practical timetable of the investigated Beijing urban rail network.

Timetable coordination in a rail transit network with time-dependent passenger demand