关于《High-speed train timetable optimization based on space–time network model and quantum simulator》的报告

作者与发表信息

本文的研究成果由Hui-Zhang Xu、Jun-Hua Chen、Xing-Chen Zhang、Te-Er Lu、Tian-Ze Gao（均来自北京交通大学交通运输学院）和Kai Wen、Yin Ma（来自北京Qboson量子科技有限公司）共同完成，并发表在期刊《Quantum Information Processing》2023年第22卷（文章编号418）。文章于2023年11月22日在线发表，研究结合量子计算技术解决高速列车时刻表优化问题。

学术背景

本文研究围绕高速铁路时刻表优化问题展开，这是一类典型的组合优化问题，涉及复杂的约束条件，是计算机科学中NP-hard问题的代表之一。在传统计算环境下，解决此类问题通常需要漫长的计算时间，而且难以找到最优解。

近年来，随着量子计算技术的快速发展，研究者发现其在求解组合优化问题方面潜力巨大。量子力学相关的关键研究起步于1980年，物理学家Paul Benioff首次提出了基于量子哈密顿量的图灵机模型；随后Feynman和Shor分别提出量子电路和量子数因子分解算法，这些奠定了量子计算在优化问题中的理论基础。

在铁路优化领域，已有研究尝试应用量子退火算法、D-Wave量子计算机等工具，解决列车调度与冲突管理问题。例如，Domino等采用二次无约束二元优化模型（QUBO）处理波兰铁路网络的调度问题，并验证了量子退火在特定场景下的有效性。然而，由于铁路时刻问题约束复杂，现有方法在解决实际大规模问题时仍存在不少挑战。

为此，本文尝试将基于时空网络模型的高速列车时刻表优化问题与量子计算模拟器（Coherent Ising Machine, CIM）相结合，并提出了一套新颖的研究方法与优化模型，来克服传统算法的高复杂性。

研究目标

本文旨在运用量子计算技术优化高速列车的时空路径，提出适配量子模拟器的QUBO模型（Quadratic Unconstrained Binary Optimization），并测试其在不同规模问题下的计算表现。具体目标包括： 1. 构建简化的背包问题模型，测试量子计算的算力； 2. 提出适配量子模拟器环境的QUBO模型表述； 3. 运用多种算法（Simulated Annealing，CIM）测试所提方法在不同比例问题上的应用。

研究流程

研究总体分为以下几个步骤，每一步具体设计和实施方法如下：

1. 数学建模阶段：

   • 本文设计了四种数学模型来表述高速列车时刻表优化问题：

     • 模型ST：基于时空网络的整数规划模型。
     • 模型ST-QUBO：将ST模型转化为QUBO形式。
     • 模型KP：通过引入历史列车运行数据，将ST简化为背包问题（Knapsack Problem）的形式。
     • 模型KP-QUBO：对简化后的KP模型进行QUBO转化。

   • 时空网络模型（ST）以图论为基础，将列车运行状态离散化为节点（每分钟一个时间点，共1440个节点），建立列车运行状态在时间和空间维度中的表示框架。

   • KP模型进一步简化，固定列车进出站的时刻和停站时间，以实现计算的可操作性。

2. QUBO模型转化阶段：

   • 不同模型通过引入惩罚项（Penalty Term），转化为适用于量子计算的QUBO形式。惩罚项能够将约束条件（如列车间隔约束、安全约束等）转化为目标函数的一部分，形成无约束优化问题。

3. 算法选择与实验阶段：

   • 对于KP模型，使用经典的GUROBI求解器求解，作为对比基准。
   • 对于KP-QUBO模型，分别采用Simulated Annealing（模拟退火算法）和CIM模拟器（通过Kaiwu-SDK实现）求解。
   • 在四种问题规模（15、30、50、100列车）下，系统测试了算法的运行效率和最优解质量。

4. 实验结果分析阶段：

   • 确定量子模型的惩罚系数λ为100，通过调整模拟退火初始温度、下降速率等参数，优化求解性能；
   • 测试了CIM中不同泵浦率（Pump Rate）和噪声水平对结果质量的影响。

主要研究结果

1. 在小规模问题中的表现：

   • 在15列车的小规模问题上，模拟退火和CIM均能找到最优解（13列车），两种方法表现相近，计算时间平均耗时4.1秒。

2. 中等规模问题中的性能：

   • 在30列车场景中，理论最优解为25列车，CIM找到了解23列车解，优于SA的21列车解。
   • 在50列车问题中，理论最优解为41列车；CIM找到的35列车解质量优于SA的31列车解。

3. 大规模问题的挑战：

   • 在100列车的大规模场景中，理论最佳解为70列车解。但由于问题复杂性增高，CIM和SA算法结果分别为45列车和44列车。
   • 实验显示，CIM算法在中小规模问题上比模拟退火算法具有较好的质量表现，但在处理大规模问题时，其计算能力受到限制。

4. 对比分析：

   • 不同模型的性能显示，KP-QUBO模型在结构简化和有效性测度上更适合量子模拟器的求解，避免了模型ST中的复杂流平衡约束条件。

研究结论与意义

本文首次将基于时空网络的高速列车时刻表优化问题转化为量子适配模型，并集成CIM模拟器进行检验，验证了该方法在解决中小规模问题时的有效性，表现出量子计算技术在交通优化问题中的潜力。研究的主要意义包括： 1. 理论价值：提出了一种通用的约束优化问题转化为QUBO格式的流程，为其他组合优化问题提供参考。 2. 应用前景：该方法不仅适用于高速列车调度，还可在车辆路径规划（VRP）、自动引导车（AGV）调度等领域推广应用，同时为实际量子设备的设计提供测试依据。

研究亮点

1. 提出了优化列车运行路径的新范式，通过结合QUBO技术和时空网络理论解决了传统算法难以处理的复杂约束问题；
2. 转化中运用了多种创新性方法，如引入惩罚因子以兼顾计算精度与效率；
3. 初次在交通调度问题中验证了CIM模拟器的求解能力，表明其在中等规模问题上有明显优势。

展望

随着量子计算器件和算法的成熟，未来在交通运输等组合优化领域使用量子计算技术将可能带来更多革新。未来工作方向可能包括： 1. 提升CIM的规模处理能力； 2. 优化量子算法的参数选择，降低求解时间； 3. 探索在不同类型交通领域问题中的应用可能性。

以上报告框架可为同行研究者提供更清晰的视角，也为实际运输系统的优化提供潜在技术支撑。