量子退火
二次无约束二元优化
计算机科学
背包问题
模拟退火
解算器
整数规划
量子计算机
调度(生产过程)
数学优化
量子
组合优化
二进制数
作业车间调度
模拟
算法
数学
地铁列车时刻表
物理
算术
量子力学
程序设计语言
操作系统
作者
H. Y. Xu,Junhua Chen,Xingchen Zhang,Tianlan Lu,Tianze Gao,Kai Wen,Ming Yin
标识
DOI:10.1007/s11128-023-04170-3
摘要
Abstract 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.
科研通智能强力驱动
Strongly Powered by AbleSci AI