Coordinated optimization of departure sequencing and section-track allocation in railway short-term concentrated departure scenarios based on qubo and hybrid quantum algorithms

This study proposes a QUBO-based modeling framework combined with simulation-based evaluation to optimize railway departure sequencing and track allocation, demonstrating that hybrid quantum algorithms like QPSO-QAOA significantly reduce operational costs and delays compared to conventional methods in concentrated departure scenarios.

The Gist

Imagine a busy train station during rush hour. Instead of just one or two trains leaving, you have a whole fleet of five trains all ready to go at almost the exact same time. They all need to leave, but they have to share a limited number of tracks and sections of the railway line ahead. If you send them out in the wrong order or assign them to the wrong tracks, they might get stuck waiting, cause delays for each other, or even block the entire line.

This paper is about finding the perfect "dance routine" for these trains so they can leave efficiently without tripping over each other.

Here is a simple breakdown of how the authors solved this problem:

1. The Two-Step Strategy: The "Blueprint" and the "Rehearsal"

The authors realized that you can't just look at a static list of who leaves first; you have to see how that list plays out in real time. So, they built a two-layer system:

• Layer 1: The Blueprint (The QUBO Model)
  Think of this as a giant puzzle. The goal is to figure out two things for every train:

  1. Who goes first? (Departure sequence)
  2. Which track do they take? (Section-track allocation)

  They turned this puzzle into a math problem called QUBO (Quadratic Unconstrained Binary Optimization). In plain English, this is just a way of writing the puzzle using only "Yes" (1) or "No" (0) answers. It's like a giant checklist where the computer tries to find the combination of "Yes/No" answers that creates the least amount of conflict.

• Layer 2: The Rehearsal (The Simulation)
  A blueprint is just paper until you build the house. Similarly, a list of "Yes/No" answers is just a theory until you see if it works in real life.
  The authors took the "Yes/No" solutions from the Blueprint and ran them through a computer simulation. This simulation acts like a video game where they watch the trains actually move. They check:

  • Did a train get stuck waiting at a station?
  • Did the tracks get too crowded?
  • Did a small delay in the beginning cause a huge traffic jam later?

  This step is crucial because a mathematically "perfect" puzzle solution might fail in the real world if it doesn't account for how long trains actually take to stop and start.

2. The "Quantum" Twist

The paper tests different ways to solve the "Blueprint" puzzle.

• The Old Ways: They used standard computer tricks (like Genetic Algorithms or Simulated Annealing), which are like trying to solve a maze by walking through it randomly or by following a set of rules.
• The New Ways: They also tested Quantum-Inspired and Hybrid methods.
  • Analogy: Imagine trying to find the best route through a city. The old methods might check one street at a time. The "Quantum" methods are like having a magical map that can look at many different routes simultaneously to find the shortest one faster.
  • Specifically, they used a method called QAOA (Quantum Approximate Optimization Algorithm) to refine the answers.

3. What They Found

The authors ran their system in two different "worlds":

• The "Perfect Day" (Normal Scenario): Everything runs smoothly.
  • Result: The Hybrid Quantum method (QPSO-QAOA) was the champion. It created the smoothest schedule with the least amount of waiting time and cost. It was better than the standard computer methods.
• The "Chaotic Day" (Dynamic Scenario): They introduced random delays (like a train running 20% slower than usual) to see how the schedules held up.
  • Result: The Quantum and Hybrid methods were much more resilient. When things went wrong, the schedules made by the standard methods fell apart and caused huge delays. The Quantum methods kept the trains moving much better, reducing total delays by about 4% to 24% compared to the old methods.

4. The "Stress Test"

They also tested what happens when the problem gets bigger (more trains) or the chaos gets worse (more delays).

• The Finding: As the number of trains increased, the standard methods started to struggle and get expensive (in terms of time and delays). The Quantum-inspired methods handled the complexity much better, keeping the system stable even when the "traffic" got heavy.

The Bottom Line

The paper doesn't claim that quantum computers are already running train stations today. Instead, it says: "We built a new way to plan train departures using a math model (QUBO) and a simulation. When we tested it, the new 'Quantum-style' algorithms found better, more robust schedules than the old standard methods, especially when things get chaotic or the number of trains gets large."

It's like proving that a new type of navigation app is better at finding routes during a traffic storm than the old map you've been using for years.

Technical Summary

Technical Summary: Coordinated Optimization of Departure Sequencing and Section-Track Allocation in Railway Short-Term Concentrated Departure Scenarios

Problem Definition

The study addresses the short-term concentrated departure scenario in railway operations, a situation where multiple trains become ready for departure within a narrow time window. Unlike conventional timetable planning, this scenario is characterized by high operational sensitivity, tight local infrastructure constraints, and the immediate coupling of departure priority, section capacity, and downstream station resources.

The core challenge is that a dispatching decision at the departure stage rapidly propagates through the network, affecting section release, intermediate-station occupancy, track conflicts, and delay propagation. Existing literature often treats timetable adjustment, routing, and platforming as separate subproblems. This paper argues that short-term concentrated departure organization must be treated as a coupled dispatching problem requiring the coordinated optimization of departure sequencing and section-track allocation within a unified decision framework.

Methodology

The authors propose a layered optimization framework consisting of two distinct stages: a combinatorial decision layer and a simulation-based evaluation layer.

1. QUBO-Based Combinatorial Decision Layer
The core decision problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) model. This approach encodes discrete scheduling decisions into a unified binary framework:

• Variables: The model uses binary variables to represent two key decisions:
  • $x_{i,p}$: Whether train $i$ departs from position $p$.
  • $y_{i,\tau,l}$: Whether train $i$ uses track $l$ in section $\tau$.
• Constraints & Penalties: Hard constraints (e.g., each train assigned to exactly one position, each track used by at most one train) and soft operational preferences are embedded into the objective function via penalty terms:
  • $H_{seq}$: Departure-sequence uniqueness.
  • $H_{track}$: Section-track selection uniqueness.
  • $H_{switch}$: Penalty for frequent track switching between adjacent sections.
  • $H_{cong}$: Penalty for congestion (multiple trains on the same departure-section track).
• Objective: Minimize $E_{QUBO}(z) = z^T Q z$, where $z$ is the binary decision vector and $Q$ is the coefficient matrix.

2. Simulation-Based Evaluation Layer
Recognizing that static combinatorial feasibility does not guarantee operational viability, a simulation layer evaluates the decoded QUBO solutions. This layer simulates the actual train movement, accounting for:

• Dynamic Interactions: Section release times, intermediate-station dwell rules, and platform capacity constraints.
• Cost Metrics: The simulation calculates a comprehensive cost ($E_{sim}$) comprising:
  • Delay Cost: Total departure and intermediate-station delays.
  • Track Switching Cost: Number of track transitions.
  • Section Fluctuation Cost: Deviation of actual running times from baseline.
  • Platform Capacity Cost: Penalties for exceeding station dwelling thresholds.

3. Algorithmic Comparison
The framework serves as a common testbed to compare various search mechanisms solving the same QUBO problem:

• Conventional Heuristics: Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Simulated Annealing (SA).
• Quantum-Inspired Methods: Quantum GA (QGA), Quantum PSO (QPSO), Quantum SA (QSA).
• Hybrid Algorithms: Combinations of the above with QAOA (Quantum Approximate Optimization Algorithm) for local refinement (e.g., QPSO-QAOA).

Key Contributions

1. Unified QUBO Formulation: The study establishes a single QUBO model that jointly encodes departure sequencing and section-track allocation, allowing heterogeneous constraints to be handled within a consistent binary objective.
2. Layered Evaluation Mechanism: It introduces a simulation-based evaluation mechanism that assesses decoded schemes for temporal feasibility and operational performance, addressing the gap between static combinatorial solutions and time-dependent dispatching dynamics.
3. Common Comparison Framework: The paper provides a standardized environment to compare conventional, quantum-inspired, and hybrid algorithms under identical modeling and evaluation conditions, rather than comparing different problem reformulations.
4. Empirical Validation: Numerical experiments are conducted under normal, dynamic (disturbed), robustness, and scale-expansion settings to analyze algorithmic behavior.

Results

The study was tested on an abstract network with 5 stations, 4 sections, and 5 trains per direction (2 tracks per section).

• Normal Scenario: Under deterministic conditions, QPSO-QAOA achieved the best performance with a total cost of 50 and total delay of 50 minutes. Quantum-inspired and hybrid methods generally outperformed conventional baselines (GA, PSO, SA).
• Dynamic Scenario: When section running times fluctuated by 20%, the structural quality of solutions diverged. Quantum-enhanced methods reduced comprehensive costs by 4.28%–26.26% and total delays by 4.37%–24.25% on average compared to their conventional counterparts. QGA-QAOA performed best in this scenario.
• Robustness: As perturbation rates increased, schemes generated by quantum-inspired methods maintained lower costs and fewer platform occupancy penalties compared to conventional methods, indicating better structural stability against delay propagation.
• Scalability: As the number of trains increased, the performance gap between methods widened. Quantum-inspired and hybrid methods showed more moderate cost growth in medium-to-large scale scenarios compared to the rapid cost escalation seen in some conventional methods.

Significance and Claims

The paper claims that integrating QUBO-based modeling with simulation-based evaluation provides a useful methodological framework for railway short-term concentrated departure scheduling.

The authors explicitly state that the objective is not to claim the immediate operational deployment of quantum computing in railway dispatching. Instead, the study aims to evaluate whether QUBO-based modeling, combined with quantum-related and hybrid solution strategies, offers a useful methodological direction for this class of scheduling problems. The findings suggest that these methods can generate feasible candidate schemes that, when evaluated dynamically, demonstrate superior adaptability to operational uncertainty and resource constraints compared to traditional heuristics.

The study acknowledges limitations, noting that the current validation relies on constructed test scenarios rather than real-world operational data, station layouts, or original train diagrams. Future work is proposed to extend the framework to actual railway corridors and more complex network settings.