Train Unit Scheduling Optimization with Station Level Resolution

The train unit scheduling optimization (TUSO) problem aims at seeking a conflict-free operational plan for a set of train units to serve all trips defined in a fixed timetable with minimum operational costs. TUSO is addressed at two levels: the network level and the station level. The network level focuses on determining the serving sequence of trips for each train unit, where the stations are simplified as single points. The station level deals with the issues left in a network-level solution with detailed infrastructure restored. Prior to this research, TUSO at the network level, specific on the UK railway operating system, has been tackled as a multi-commodity network flow problem. Whereas train unit flows are balanced and optimised over the service network, potential operational conflicts due to layouts in individual train station have been ignored. This research mainly concerns resolving such operational conflicts at the station level. However, this research has also made contributions in improving the network flow model. This research follows the two-phase approach to tackle TUSO at these two levels. TUSO is first solved at the network level in Phase I, where two solvers have been developed, namely RS-Opt and SLIM. Given a solution from the network level, two operational aspects are left undetermined: coupling order issues and linkage feasibility. To finalize these two aspects, an adaptive approach expanding Phase I to Phase II is proposed. Phase II takes a further step of station-level resolution and attempts to complete a fully operable schedule. The logistics of coupling/decoupling activities and tentative linkages are determined in detail to prevent conflicts where possible, particularly focusing on developing an operable schedule without conflicts of coupling order or crossing linkages in train stations. If the unresolvable station-level conflicts still exist at Phase II, the process loops back to Phase I with added constraints to avoid the identified conflicts. Through these two phases, a global optimal solution that is also operable considering station-level layouts will be secured. Moreover, the observation on the network-level experimental results from the existing RS-Opt and SLIM has inspired the research on improving the network flow model from the perspective of considering additional terms in the objective function such as the slack time and the number of cars. It is extended as a new methodology to evaluate the effectiveness of alternative objective function designs.