Learning-based model predictive control for passenger-oriented train rescheduling with flexible train composition

Technical Summary: Learning-based Model Predictive Control for Passenger-Oriented Train Rescheduling with Flexible Train Composition

Problem Statement
Urban rail transit systems face significant challenges in real-time scheduling due to rapidly expanding networks, time-varying passenger demands, and the need to balance operational costs with service quality. While existing research addresses passenger-oriented scheduling, many approaches are limited to fixed train compositions or fixed departure frequencies. Furthermore, incorporating flexible train composition (adjusting the number of train units per service) and rolling stock circulation (managing train units across depots) introduces a large number of integer decision variables. This transforms the rescheduling problem into a complex Mixed-Integer Nonlinear Programming (MINLP) or Mixed-Integer Linear Programming (MILP) problem. The primary bottleneck for real-time application is the high online computational burden required to solve these problems within the tight time constraints of Model Predictive Control (MPC).

Methodology
The paper proposes a Learning-based Model Predictive Control (MPC) framework that integrates deep learning with optimization to address the computational complexity of real-time train rescheduling. The approach is structured as follows:

1. Mathematical Formulation: The authors extend a passenger-oriented rescheduling model to include time-varying sectional passenger demands, flexible train composition, and rolling stock circulation. The objective is to minimize total passenger waiting time and operational costs (energy and composition change costs). The problem is initially formulated as an MINLP, where integer variables represent train compositions, train ordering, and rolling stock circulation, while continuous variables represent departure and arrival times.
2. Presolve Techniques: To reduce the dimensionality of the optimization problem, four presolve techniques are developed. These techniques prune subsets of integer decision variables by determining their values based on predetermined constraints and coupled variables (e.g., fixing train ordering based on predetermined timetables or fixing composition for trains that have already departed).
3. Hybrid Learning-Optimization Approach:
   • Offline Training: Long Short-Term Memory (LSTM) networks are trained to predict the optimal values of the remaining integer variables. The training process uses an ensemble of LSTM networks to maximize the feasibility rate. The networks are trained on data generated by solving the full MINLP problem, with the loss function minimizing the squared error between the network's predicted objective values and the optimal values.
   • Online Execution: In the real-time MPC loop, the trained LSTM networks generate the integer variables (train compositions and orders) based on the current system state (passenger counts, demands, and available rolling stock). These variables are then fixed.
   • Continuous Optimization: With the integer variables fixed, the original MINLP problem is reduced to a continuous Nonlinear Programming (NLP) problem (or a Linear Programming (LP) problem if the objective function is further approximated). This reduced problem is solved efficiently to determine the detailed timetable (departure and arrival times).
4. Feasibility Guarantee: To ensure recursive feasibility, a heuristic fallback mechanism (based on Lemma 1) is employed. If the LSTM network fails to generate a feasible set of integer variables, the heuristic constructs a feasible solution, ensuring the MPC loop can always proceed.

Key Contributions
The paper lists three main contributions:

1. Extended Model: The passenger-oriented rescheduling model is extended to jointly optimize time-varying passenger demands, flexible train composition, and rolling stock circulation, approximating demands as piecewise constant functions.
2. Presolve and Dimensionality Reduction: Four presolve techniques are developed to prune integer decision variables, significantly reducing the search space for the learning algorithm.
3. Learning-based MPC Framework: A novel deep-learning-based MPC approach is developed where pre-trained LSTM networks determine integer variables, and constrained optimization determines continuous variables. This combines the constraint satisfaction guarantees of optimization with the computational speed of learning.

Results
The approach was evaluated using real-life data from a three-line network in the Beijing urban rail transit system. Simulations compared the proposed learning-based MPC (both NLP and LP variants) against a Benchmark (MINLP with warm-start and extended time), a standard Warm-start MINLP, and a MILP approach.

• Computational Efficiency: The learning-based approaches demonstrated a dramatic reduction in solution time. The Learning + LP approach achieved an average solution time of 0.13 seconds (maximum 0.31s), compared to 96.71 seconds (average) for the Warm-start MINLP and 51.36 seconds for the MILP in closed-loop tests.
• Optimality: The learning-based methods achieved comparable performance to the optimization-based benchmarks with an acceptable trade-off. In closed-loop tests, the Learning + NLP approach showed an average optimality gap of 4.92%, and Learning + LP showed 5.50%, compared to the benchmark.
• Feasibility: The initial feasibility rate of the raw LSTM output was approximately 98.5–98.9%. However, with the application of the heuristic fallback mechanism, the final feasibility rate reached 100% for all learning-based approaches in closed-loop simulations.
• Timetable Quality: Visual analysis of generated timetables indicated that the learning-based approaches successfully adapted train compositions to passenger flows (e.g., using longer trains during peak hours), though slight variations in strategy compared to the benchmark led to minor differences in objective function values.

Significance and Claims
The paper claims that the proposed framework effectively addresses the scalability and computational burden challenges inherent in real-time train rescheduling with flexible composition. By decoupling the integer decision-making (handled by learning) from the continuous optimization (handled by solvers), the method enables the generation of optimized timetables in real-time (under 1 second for the LP variant), which is critical for operational control centers. The authors assert that this approach balances the need for high-quality, constraint-satisfying solutions with the strict time requirements of real-time urban rail operations, offering a viable alternative to computationally expensive exact methods for large-scale networks. The work suggests that future research could explore reinforcement learning and multi-agent systems to further enhance adaptability and scalability.