High-speed train timetable optimization based on space–time network model and quantum simulator
High-speed train timetable optimization based on space–time network model and quantum simulator
复制标题
DOI：
10.1007/s11128-023-04170-3
复制
发表时间：
2023-11
影响因子：
2.5
通讯作者：
Hui-Zhang Xu;Jun-Hua Chen;Xing-Chen Zhang;Te-Er Lu;Tian-Ze Gao;Kai Wen;Yin Ma
中科院分区：
文献类型：
--
作者：
Hui-Zhang Xu;Jun-Hua Chen;Xing-Chen Zhang;Te-Er Lu;Tian-Ze Gao;Kai Wen;Yin Ma
时间表调度是一个组合优化问题，对经典计算机提出了巨大的挑战。本文介绍了一种通过量子计算解决高速列车时刻表问题的开创性方法。最初，提出了一种基于时空网络的综合二进制整数规划模型（M1）。为了管理模型 M1 的复杂性，采用背包问题重新表述来建立简化的二进制整数规划模型 (M2)。 M1 和 M2 随后都转换为二次无约束二元优化 (QUBO) 模型，以利用量子计算的潜力。部署了多种技术，包括 Gurobi 求解器、模拟退火和相干伊辛机 (CIM) 量子模拟器，来解决四种复杂程度不同的不同场景的模型。研究结果表明，CIM 量子模拟器在解决中等规模问题的质量方面优于模拟退火方法。
Timetable scheduling is a combinatorial optimization problem that presents formidable challenges for classical computers. This paper introduces a pioneering methodology for addressing the high-speed train timetabling problem through quantum computing. Initially, a comprehensive binary integer programming model, grounded in the space–time network, is proposed (M1). To manage the intricacy of model M1, a knapsack problem reformulation is employed to establish a simplified binary integer programming model (M2). Both M1 and M2 are subsequently converted into quadratic unconstrained binary optimization (QUBO) models to harness the potential of quantum computing. Several techniques, including the Gurobi solver, simulated annealing, and the coherent Ising machine (CIM) quantum simulator, are deployed to solve the model across four distinct scenarios of varying complexity. The findings indicate that CIM quantum simulator outperforms the simulated annealing method in terms of solution quality for medium-scale problems.