EMU circulation planning for Silesian Railways: case study and a quantum approach

This paper presents a case study on daily electric multiple unit (EMU) circulation planning for Silesian Railways, comparing a high-quality classical mixed-integer linear programming solution against quantum and quantum-inspired approaches to demonstrate the current limitations and potential of QUBO-based methods for real-world railway optimization.

The Gist

Imagine you are the conductor of a massive, busy orchestra, but instead of violins and drums, your instruments are electric trains. Your job is to make sure every single train has a driver, enough seats for passengers, and enough space for their bicycles, all while making sure the trains end up back in their "garages" (depots) ready for the next day.

This paper is a case study about solving this puzzle for Silesian Railways in Poland. The researchers tried two different ways to solve it: the old-school, reliable way (Classical Math) and the futuristic, experimental way (Quantum Computing).

Here is the breakdown of their journey:

1. The Problem: The Train Puzzle

The railway operator needs to plan the daily schedule for hundreds of trains. It's not just about picking a train for a route; it's a complex game of Tetris with extra rules:

• Coupling: Sometimes, two identical trains can be hooked together (like train cars) to make a bigger train for crowded routes.
• Bicycles: They have to make sure there is enough space for passengers' bikes.
• Drivers: They can't assign more trains than they have drivers available at a specific time.
• Garage Balance: Every day, a certain number of trains must start and end in specific depots.

2. The "Old-School" Solution: The Master Chef (ILP)

First, the team built a Classical Mathematical Model (called an Integer Linear Program or ILP).

• The Analogy: Think of this as a super-smart, hyper-organized chef who has a recipe book for every possible way to arrange the trains. The chef checks every single possibility against the rules (drivers, bikes, coupling) to find the perfect, cheapest schedule.
• The Result: This method worked flawlessly. Even with 404 train trips and 11 different types of trains, the computer solved the whole day's schedule in under 40 minutes. It found the best possible plan every time.

3. The "Futuristic" Solution: The Quantum Dice Roll (QUBO)

Next, the team tried to translate this problem into a format that Quantum Computers (specifically D-Wave machines) and "Quantum-Inspired" software could understand. They turned the train rules into a QUBO (Quadratic Unconstrained Binary Optimization) problem.

• The Analogy: Imagine instead of a chef checking recipes one by one, you have a magical dice roller that tries to find the best arrangement by "feeling" the energy of the system. If the arrangement is bad (e.g., not enough bike space), it feels "hot" (high energy). If it's good, it feels "cold" (low energy). The goal is to find the coldest state.
• The Catch: To make the quantum computer understand the rules, the researchers had to add "penalty" weights. This made the problem explode in size.
  • The "Explosion": While the classical model had a manageable number of variables, the quantum version had to account for millions of interactions between them. It was like trying to fit a whole ocean into a teacup.

4. The Showdown: Who Won?

The researchers tested both methods on real data from the railway.

• The Classical Chef (ILP): Won easily. It handled the big, messy, real-world schedules quickly and found the perfect answer.
• The Quantum Dice (D-Wave): Could only solve the tiny versions of the problem (like a toy example with just 3 trains). When they tried to feed it a medium-sized schedule, the computer's "memory" (qubits) wasn't big enough to hold the puzzle. It was like trying to solve a 1,000-piece puzzle with only 10 puzzle pieces.
• The Quantum-Inspired Solver (VeloxQ): This is a classical computer pretending to be quantum. It did better than the real quantum computer and could solve slightly larger problems, but it still hit a wall when the problem got too big. It couldn't generate the "map" of the problem fast enough.

5. The Bottom Line

The paper concludes that for today's railway planning:

• Stick to the Classical Chef: The traditional math method is fast, reliable, and ready for real-world use.
• Quantum is still a "Toy": Current quantum computers are too small and the math required to translate the problem is too heavy. They can only solve tiny, simplified versions of the puzzle.

The Future Idea:
The authors suggest a Hybrid Approach for the future. Imagine using the Classical Chef to plan the whole day, but then using the Quantum Dice to quickly check a few specific, tricky spots (like a busy station where trains need to couple and uncouple) to see if there's a slightly better way to arrange just those few trains.

In short: The researchers proved that while quantum computing is exciting, for planning train schedules right now, the old-fashioned super-computer math is still the king. The quantum approach is a promising sidekick, but it's not ready to take the lead yet.

Technical Summary

Technical Summary: EMU Circulation Planning for Silesian Railways

Problem Definition

The paper addresses the daily rolling stock circulation planning problem for electric multiple units (EMUs) on the regional passenger network of Silesian Railways (Koleje Śląskie) in Poland. The objective is to assign available EMUs to a fixed timetable of train trips while satisfying a complex set of operational constraints.

Key characteristics of the problem include:

• Flexible Compositions: EMUs of the same type may be coupled in pairs on a predefined subset of trips to increase capacity, while other trips must be served by single units.
• Demand-Driven Capacity: The model explicitly incorporates constraints for both passenger seat capacity and bicycle storage capacity, ensuring that shortages do not exceed admissible limits.
• Depot Balance: The plan must respect lower and upper bounds on the number of EMUs of each type starting and ending the day at specific depots, maintaining operational reserves.
• Crew Availability: Aggregate constraints limit the number of simultaneously operated EMUs based on the availability of suitable drivers at specific depots and times.
• Acyclic Horizon: The planning horizon is a single day, resulting in an acyclic circulation structure, distinct from cyclic weekly planning models.

Methodology

The authors propose a dual-methodology approach, comparing a classical Integer Linear Programming (ILP) formulation against a Quadratic Unconstrained Binary Optimization (QUBO) reformulation.

1. Graph/Hyper-Graph Representation

The problem is modeled using a time-expanded graph where:

• Nodes represent train trips and auxiliary depot service events.
• Arcs represent feasible transitions of a single EMU between trips.
• Hyper-arcs represent transitions involving coupled EMUs (coupling, coupled transfer, and decoupling).
  This hyper-graph formulation naturally captures the combinatorial complexity of flexible train compositions.

2. Classical ILP Approach

The problem is encoded as a Mixed-Integer Linear Program (MILP) and solved using the SCIP solver.

• Objective: Minimizes a weighted sum of operational costs (fixed and distance-dependent) and the number of dispatched EMUs (to preserve reserve fleets).
• Constraints: Includes coverage (every trip served exactly once), flow balance (continuity of rolling stock), depot balance, capacity limits (seats/bikes), and crew availability.
• Scaling: The number of binary variables scales roughly with $|T| \cdot |T|^2 \cdot |R|$ in the worst case, where $|T|$ is the number of trips and $|R|$ is the number of EMU types, though practical constraints significantly reduce this.

3. Quantum and Quantum-Inspired Approach (QUBO)

The ILP is reformulated into a QUBO problem to utilize quantum annealing and physics-inspired heuristics.

• Transformation: Constraints are converted into penalty terms added to the objective function. Slack variables are introduced to handle inequality constraints (e.g., depot limits, crew availability).
• Solvers:
  • Quantum Annealing: Executed on D-Wave Advantage systems (both Pegasus and Zephyr topologies).
  • Quantum-Inspired: Executed using VeloxQ, a classical solver based on physics-inspired heuristics (simulated bifurcation/energy minimization) that does not require quantum hardware.
• Scaling: The QUBO formulation introduces a significant overhead in the number of quadratic terms, scaling as $|T|^5$ in the worst case, which creates a bottleneck for model generation and storage even before solving.

Key Contributions

1. Practical ILP Model: Development of a flexible, directly solvable ILP model that integrates specific operator requirements: pairwise coupling restricted to predefined trips, explicit bicycle capacity constraints, and aggregate crew limits.
2. QUBO Mapping: A specific reformulation of the rolling stock circulation problem into QUBO, including an analysis of the scaling of variables and terms, highlighting the rapid growth of quadratic interactions.
3. Empirical Benchmarking: A comparative study on real-world data from Silesian Railways (up to 404 trips and 11 EMU types) evaluating:
   • Classical ILP (SCIP).
   • Quantum Annealing (D-Wave hardware).
   • Quantum-Inspired Heuristics (VeloxQ).
4. Feasibility Analysis: Identification of the current practical frontier for QUBO-based methods in railway planning, specifically regarding the trade-off between model expressiveness and computational tractability.

Experimental Results

Classical ILP Performance

• Scalability: The SCIP solver successfully solved all instances, including the largest with ~404 trips and ~380,000 binary variables.
• Runtime: Optimal or high-quality solutions were obtained within seconds for medium instances and up to approximately 40 minutes for the largest instances.
• Quality: The model produced feasible, practical circulation plans that respected all constraints, including complex coupling scenarios and capacity limits.

Quantum and Quantum-Inspired Performance

• Hardware Limitations: D-Wave quantum annealers were restricted to the smallest instances (up to ~50 trips) due to embedding limitations and the number of available qubits. The newer Advantage2 system (Zephyr topology) solved slightly larger sub-instances than the older Pegasus-based system but could not handle instances beyond size 2a.
• QUBO Construction Bottleneck: The primary barrier was not the solving time but the generation of the QUBO matrix. For medium-sized instances (e.g., 78 trips), the number of quadratic terms reached ~1.8 million, and for larger instances, it exceeded $10^8$, making model construction infeasible within available RAM (62 GB).
• Solver Comparison:
  • VeloxQ: Outperformed D-Wave on small instances, finding optimal solutions quickly. However, it faced the same limitation regarding the generation of the QUBO model for larger instances.
  • Feasibility: Both quantum and quantum-inspired solvers required post-processing to filter out solutions that violated soft constraints (slack variables), as the penalty method does not guarantee feasibility by construction.

Significance and Claims

The paper claims that for the specific problem of daily EMU circulation with the described constraints:

• Classical ILP is currently superior: The classical approach (SCIP) is the only method capable of handling the full scale of real-world regional railway instances (hundreds of trips) within practical timeframes while guaranteeing feasibility.
• Current State of Quantum Methods: QUBO-based approaches (both quantum and quantum-inspired) are currently limited to small sub-problems or highly restricted instances due to the quadratic expansion of terms and embedding overheads. They do not yet outperform classical solvers for end-to-end daily planning.
• Future Direction: The results suggest a hybrid classical-quantum architecture as the most viable near-term path. In this framework, the classical solver would handle the global problem, while QUBO-based methods could be applied to localized, high-complexity subproblems (e.g., specific coupling "hotspots" or short-term rescheduling windows) where the problem size is reduced.
• Practical Utility: The study demonstrates that restricting the transfer time window ($\Delta$) serves as an effective heuristic to reduce model complexity for classical solvers without significantly degrading solution quality, a feature that could also aid in sparsifying QUBO formulations.

The authors conclude that while quantum methods show promise for sampling low-energy states and providing alternative feasible solutions, their application to large-scale railway circulation planning remains constrained by hardware limitations and the mathematical overhead of the QUBO reformulation.