Train Unit Scheduling with Unit Ordering under Platform-Feasible Operations

Abstract

In passenger railways where coupling and decoupling occur at platforms, a rolling-stock plan may be circulation-feasible but station-infeasible when the within-formation order of identified units causes blockage. We study the Train Unit Scheduling Problem under platform-feasible operations, where units cannot overtake or be resequenced without authorised shunting or resequencing. We formulate, to the best of our knowledge, the first single-stage unit-level integer linear programming model for this setting. It tracks identified units on a unit-indexed connection network and jointly determines the movements, coupling and decoupling decisions, and within-formation positions of train units, so every feasible integer solution provides a blockage-free schedule under the modelled restrictions. We further derive an exact fixed-assignment characterisation of orderability. Active coupling and decoupling requirements induce trip-wise precedence digraphs, while continuation arcs impose pairwise carry-over consistency. An assignment is orderable if and only if these digraphs admit a continuation-consistent family of topological orders. This yields a Train Unit Scheduler with Ordered Units (TUSOU), an exact branch-and-bound-and-cut train unit scheduler developed by us using ordering certification, lazy recovery of ordering constraints and activated cycle inequalities. Experiments on five real-world-derived TransPennine Express instances show that TUSOU produces certified blockage-free schedules, solves all instances to zero reported gap under solver tolerances, and outperforms direct full-model Gurobi baselines. Certification rejects 39 of 59 integer assignment-candidate encounters, showing that orderability should be embedded in optimisation rather than treated as post-processing.