How to improve transportation capacity of oversaturated metro lines? A flexible operation approach with extra-long train compositions

Under regular metro operation conditions, one critical bottleneck to improving metro transportation capacity is fixed-length train compositions. These fixed-length compositions are mandated to not exceed station platform lengths, thereby limiting the potential for increasing capacity to effectively accommodate oversaturated passenger demand. To this end, we focus on a flexible metro operating system equipped with extra-long train compositions, which allows trains to protrude beyond both ends of the station platforms for additional capacity. Driven by oversaturated and time-dependent passenger demand, we develop a compact integer linear programming model to determine train composition lengths and train-platform alignment relationships. When using commercial solvers to directly handle this model, complexity analyses and computational practice show that it is less efficient for large-scale experiments. We thus reformulate it as a column-based optimization model, while employing a column generation algorithm to solve its linear relaxation version and customizing a dynamic programming method to generate promising column variables. To achieve high-quality integer solutions, we carefully embed the column generation into a branch-and-bound procedure and elaborate some accelerating strategies through theoretical analyses. The approach is applied to several test instances defined by using hypothetical and real-world lines. The computational results demonstrate that the proposed approach can significantly reduce passenger waiting times and effectively handle large-scale problems.