基于QUBO与混合量子算法的铁路短期集中发车场景下出发顺序与区段轨道分配协同优化

# 基于QUBO与混合量子算法的铁路短时集中发车场景下发车排序与区间-轨道协调优化 来源: https://arxiv.org/html/2606.06543

肖彬·李\*  
交通运输工程学院  
华东交通大学  
中国江西南昌 330000  
yuncifor@outlook\.com  

&颜斌·高  
交通运输工程学院  
华东交通大学  
中国江西南昌 330000  
specoale296@outlook\.com  

&伟光·王  
交通运输工程学院  
华东交通大学  
中国江西南昌 330000  
Wang0422paper@outlook\.com  

&雪晨·梁  
交通运输工程学院  
华东交通大学  
中国江西南昌 330000  
david\.i\.ubosi@my\.occc\.edu  

###### 摘要  
本研究探讨了铁路短时集中发车场景下发车排序与区间-轨道分配的协调优化问题。构建了一个二次无约束二元优化（QUBO）模型，在统一的二元框架内表述发车位置分配与区间-轨道选择。由于调度方案的质量取决于随时间变化的运行交互作用，而静态组合模型无法完全捕获这些交互作用，因此引入了一个基于仿真的评估层，用于评估区间占用、中间站等待、站台能力压力、运行时间波动以及延误传播。在此分层框架内，在相同的决策结构上比较了传统启发式算法、量子启发式算法和混合算法。结果表明，QUBO模型在解码后能够生成可行的候选方案，而仿真层则能清晰区分各比较算法在正常和干扰条件下的运行性能。在所测试的场景中，QPSO-QAOA在正常条件下表现最佳；在动态条件下，相对于传统方法，量子增强方法平均降低综合成本4.28%–26.26%，总延误平均降低4.37%–24.25%。这些发现表明，基于QUBO的建模与基于仿真的评估相结合，为铁路短时集中发车调度提供了一种有用的方法学框架，尽管仍需利用实际运行数据进行验证。实现代码可在https://github.com/yuncifor/Railway-Short-Term-Based-on-QUBO-and-Hybrid-Quantum-Algorithms 获取。

*关键词* QUBO⋅铁路调度⋅混合量子算法⋅短时集中发车

## 1 引言

在铁路运营中，当多列列车在较窄的时间窗口内准备发车，并且必须同时竞争发车优先级、区间能力和下游车站资源时，便会出现短时集中发车场景。与传统的时刻表规划问题相比，该场景更具操作性、时间敏感度更高，且受当地基础设施约束更严格。在发车阶段做出的调度决策会迅速影响区间释放、中间站占用、轨道冲突以及后续的延误传播。因此，短时集中发车组织不应仅被视为排序问题，而应被视为涉及发车优先级、轨道分配和运行可行性的耦合调度问题。

现有关于铁路调度、列车重新排班、站台分配和轨道分配的研究为分析此类问题提供了重要基础。关于列车路径选择与时刻表的研究表明，铁路运营决策受到高度约束且耦合紧密，尤其是在饱和和受干扰条件下[7 (https://arxiv.org/html/2606.06543#bib.bib1),20 (https://arxiv.org/html/2606.06543#bib.bib2),4 (https://arxiv.org/html/2606.06543#bib.bib3),26 (https://arxiv.org/html/2606.06543#bib.bib4)]。关于车站路径、站台分配和冲突管理的研究进一步证明，局部基础设施约束会显著影响网络层面的运营性能[30 (https://arxiv.org/html/2606.06543#bib.bib5),5 (https://arxiv.org/html/2606.06543#bib.bib6),9 (https://arxiv.org/html/2606.06543#bib.bib7),27 (https://arxiv.org/html/2606.06543#bib.bib8)]。此外，关于实时重新排班和鲁棒性的研究强调，调度方案的评估不仅应考虑名义效率，还应考虑其在不确定性下缓解连锁延误和保持稳定性的能力[11 (https://arxiv.org/html/2606.06543#bib.bib9),17 (https://arxiv.org/html/2606.06543#bib.bib10),10 (https://arxiv.org/html/2606.06543#bib.bib11),8 (https://arxiv.org/html/2606.06543#bib.bib12)]。然而，现有大多数研究将时刻表调整、径路选择、站台分配或重新排班作为独立的子问题处理，而短时集中发车问题需要在统一决策框架内协调处理发车排序和区间-轨道分配。

从建模角度来看，短时集中发车组织所涉及的关键决策本质上是离散的。每列列车必须被分配到一个精确的发车位置，每个区间必须匹配一个可行的轨道或径路选项，同时受资源冲突和运行惩罚的约束。这种结构天然适合二元组合优化。近年来，二次无约束二元优化（QUBO）作为一种统一建模框架，用于编码离散决策变量及其成对耦合，引起了越来越多的关注[19 (https://arxiv.org/html/2606.06543#bib.bib13),15 (https://arxiv.org/html/2606.06543#bib.bib14)]。QUBO的一大优势在于，异构的运行约束和协调关系可以通过惩罚项嵌入到单一的二元目标函数中，从而使排序选择、轨道选择决策和冲突避免要求能够以数学上一致的方式表示。这一特性对于铁路短时集中发车调度尤为重要。在此背景下，发车顺序和区间-轨道分配无法独立优化：一旦考虑下游轨道使用情况，理想的发车序列可能变得不可行；而一个局部可行的轨道分配模式与不合适的发车顺序相结合时，可能导致过度等待或冲突累积。因此，基于QUBO的表示提供了一种自然的方式，将这些耦合的组合决策编码到统一模型中。更重要的是，它建立了一个共同的解空间，使得传统启发式、量子启发式以及混合量子-经典算法可以在相同的决策结构上进行对比，而不是基于问题的不同重新表述。

随着量子优化的发展，基于QUBO的方法已逐步在铁路和交通应用中得到探索。先前的研究已考察了用于一般组合问题的Ising或QUBO公式[19 (https://arxiv.org/html/2606.06543#bib.bib13),15 (https://arxiv.org/html/2606.06543#bib.bib14),16 (https://arxiv.org/html/2606.06543#bib.bib15)]，用于量子计算的铁路重新排班[13 (https://arxiv.org/html/2606.06543#bib.bib16)]，以及使用量子导向求解方法的高铁时刻表优化[29 (https://arxiv.org/html/2606.06543#bib.bib17)]。这些研究表明，量子算法和混合方法可能为大规模离散铁路决策空间提供有前景的搜索机制。尽管如此，当前研究在直接解决短时集中发车组织方面仍然有限，更少有研究将基于QUBO的组合建模与显式的运行评估过程相结合，以检验候选二元解在随时间变化的调度动态、区间占用交互、车站容量约束和延误传播效应下是否仍然有效。

受此研究空白驱动，本研究开发了一个用于铁路短时集中发车调度的分层框架，其中基于QUBO的决策层生成候选组合方案，而基于仿真的评估层检查其运行后果。该框架解决了一个核心方法论问题：方案质量不能仅凭静态的组合可行性判断，因为下游区间占用、中间站等待、能力压力和延误传播都依赖于基于时间的运行交互。本研究的主要贡献如下：首先，建立了一个统一的QUBO公式，以联合编码短时集中发车场景下的发车排序和区间-轨道分配。其次，引入了一种基于仿真的评估机制，用于在时间可行性和运行性能方面评估解码方案，超越QUBO目标本身。第三，为传统启发式、量子启发式和混合算法提供了在相同建模和评估条件下的共同比较框架。第四，在正常、动态、鲁棒性和规模扩展设置下进行了数值实验，以检验不同算法在建议框架内的行为。目标并非声称量子计算在铁路调度中的立即运营部署，而是评估基于QUBO的建模，结合量子相关和混合求解策略，是否为这类调度问题提供有用的方法论方向。

## 2 预备知识

### 2.1 二次无约束二元优化

QUBO是一种广泛使用的离散组合优化表述形式，因为它可以在单个二次目标函数中表达二元决策变量及其成对耦合。这种建模形式已应用于多种优化场景，包括投资组合优化[18 (https://arxiv.org/html/2606.06543#bib.bib21),25 (https://arxiv.org/html/2606.06543#bib.bib22),1 (https://arxiv.org/html/2606.06543#bib.bib23)]、交通规划与路径选择[12 (https://arxiv.org/html/2606.06543#bib.bib24),6 (https://arxiv.org/html/2606.06543#bib.bib25),23 (https://arxiv.org/html/2606.06543#bib.bib26)]以及物流优化[28 (https://arxiv.org/html/2606.06543#bib.bib27),21 (https://arxiv.org/html/2606.06543#bib.bib28),22 (https://arxiv.org/html/2606.06543#bib.bib29)]。在本研究中，QUBO的主要吸引力在于它能够将多个耦合的调度决策（例如发车位置分配和区间-轨道选择）编码到统一的二元框架中。标准QUBO目标函数写作：  
min_{x∈{0,1}^n} E(x) = ∑_{i=1}^n a_i x_i + ∑_{1≤i<j≤n} b_{ij} x_i x_j (1)  
其中 a_i 是线性系数，b_{ij} 是二次耦合系数，x_i 是二元决策变量。该形式可以紧凑地表示为矩阵形式 E(x)=x^T Q x，其中 Q 是包含系数的上三角矩阵。

### 2.2 量子近似优化算法 (QAOA)

QAOA [3] 是一种变分量子算法，旨在解决组合优化问题。它通过交替应用问题哈密顿量 H_C 和混合哈密顿量 H_B 来制备参数化量子态：  
|ψ(γ,β)⟩ = e^{-iβ_p H_B} e^{-iγ_p H_C} ... e^{-iβ_1 H_B} e^{-iγ_1 H_C} |s⟩ (2)  
其中 p 是层数，γ 和 β 是变分参数，|s⟩ 是初始均匀叠加态。测量该态并迭代更新参数以最小化期望值 ⟨ψ(γ,β)|H_C|ψ(γ,β)⟩。对于 QUBO 问题，H_C 直接由 QUBO 目标函数构造。

### 2.3 量子粒子群优化 (QPSO)

QPSO [24] 是一种基于量子行为粒子群模型的群体智能算法。与经典 PSO 不同，QPSO 通过概率密度函数更新粒子位置，无需速度，从而增强全局搜索能力。粒子位置更新公式为：  
mbest = (1/N) ∑_{i=1}^N pbest_i (3)  
p = φ·pbest_i + (1-φ)·gbest (4)  
x_i(t+1) = p ± β·|mbest - x_i(t)|·ln(1/u) (5)  
其中 mbest 是平均最好位置，pbest_i 是粒子 i 的个体最好位置，gbest 是全局最好位置，φ 和 u 是 [0,1] 上的随机数，β 是收缩-扩张系数。本研究中，QPSO 用于优化 QAOA 的变分参数，形成 QPSO-QAOA 混合算法。

## 3 问题建模

### 3.1 问题描述

考虑一个从起点站到终点站的单线铁路走廊，包含若干中间站。在某个计划时刻，一批列车准备从起点站发车，形成短时集中发车场景。每列列车具有预定的基本运行时间、中间站停站方案和终点站到达时间窗口。决策包括：确定列车的发车顺序，为每个区间分配轨道（若存在多条轨道），以及处理中间站的轨道切换。目标是在满足安全间隔和站线能力约束的前提下，最小化总延误和轨道切换成本，同时保持运行稳定性。

### 3.2 二元变量定义

定义以下二元变量：
- z_i 表示列车 i 的发车顺序（通过排序变量编码）。
- y_{i,τ,l} 表示列车 i 在区间 τ 选择轨道 l（l∈L，L 为每个区间的可用轨道集）。
- 其他辅助变量用于约束编码。

### 3.3 发车顺序约束

采用基于 QUBO 的排序惩罚来确保每列列车被分配唯一发车位置且顺序一致：
H_seq = λ_1 ∑_{i∈I} (∑_{t∈T} t·x_{i,t} - pos_i)^2 + λ_2 ∑_{t∈T} (∑_{i∈I} x_{i,t} - 1)^2 (6)
其中 x_{i,t} 表示列车 i 被分配至发车时隙 t，pos_i 是列车 i 的排序位置，λ 为惩罚系数。

### 3.4 区间-轨道选择约束

每列列车在每个区间必须选择恰好一条轨道：
∑_{l∈L} y_{i,τ,l} = 1, ∀i∈I, ∀τ∈Γ (7)
若两条列车在同一区间选择相同轨道，则需满足安全间隔，这通过惩罚项实现：
H_track = λ_3 ∑_{i∈I} ∑_{i'>i} ∑_{τ∈Γ} ∑_{l∈L} y_{i,τ,l} y_{i',τ,l} · penalty_{i,i',τ} (8)

### 3.5 相邻区间轨道切换惩罚

H_switch = λ_4 ∑_{i∈I} ∑_{τ=1}^{|Γ|-1} (1 - ∑_{l∈L} y_{i,τ,l} y_{i,τ+1,l}) (9)

### 3.6 发车区间同轨道拥堵惩罚

H_cong = λ_5 ∑_{i∈I} ∑_{i'>i} ∑_{l∈L} y_{i,τ0,l} y_{i',τ0,l} (10)
其中 τ0 表示发车区间，λ_5 设为 12。

### 3.7 QUBO 矩阵形式

决策层的目标函数统一写作标准 QUBO 形式：
E_QUBO(z) = H_seq + H_track + H_switch + H_cong = z^T Q z (11)
其中 z 是组合决策向量，Q 是系数矩阵。

### 3.8 目标函数与评估指标

为区分组合搜索与运行评估，本研究分别定义 QUBO 层的目标函数和仿真层的综合评估函数。前者刻画发车排序与区间-轨道分配的静态组合结构，后者评估解码方案在发车池推进、区间释放和中间站停留过程中的运行性能。

QUBO 目标：
min E_QUBO(z) = min (H_seq + H_track + H_switch + H_cong) = min z^T Q z (12)

仿真层综合成本包含四部分：延误成本、换轨成本、区间波动惩罚和站台能力惩罚。它从延误控制、换轨组织、区间运行波动和车站停靠资源占用等方面表征方案质量。较低值表示方案更有利于减少发车等待、抑制延误传播和缓解车站资源压力。

仿真层目标：
min E_sim = E_delay + E_change + E_fluct + E_platform (13)

#### 3.8.1 延误成本

延误项用于最小化列车总延误，包括发车站延误和中间站停留延误：
E_delay = ∑_{i∈I} (d_i^{origin} + d_i^{mid}) (14)
其中 d_i^{origin} 表示列车 i 的发车站延误，d_i^{mid} 表示其在中间站的累积延误。

#### 3.8.2 换轨成本

换轨项用于减少相邻区间之间的轨道转换次数，从而降低调度复杂度和运营成本：
E_change = ∑_{i∈I} ∑_{τ=1}^{|Γ|-1} (1 - ∑_{l∈L} y_{i,τ,l} y_{i,τ+1,l}) (15)

#### 3.8.3 区间波动成本

列车在区间的运行时间基于预设值，但实际运行时间并非固定。列车在特定条件下可能适当加速或减速，因此实际运行时间在一个合理范围内波动。区间波动项表示为：
E_fluct = ∑_{i∈I} ∑_{τ∈Γ} |t_{i,τ}^{actual} - t_{i,τ}^{base}| (16)
该项表征运行时间波动对综合评价的影响。实际运行时间与基本运行时间偏差越大，波动惩罚越大，表示该组合方案...