使用混合量子-经典方法解决异构城市铁路网络的重新调度问题
Solving rescheduling problems in heterogeneous urban railway networks using hybrid quantum-classical approach
摘要 Abstract
本文探讨了混合量子-经典启发式算法在实际铁路重新调度管理问题中的适用性。我们构建了一个整数线性规划模型,并使用D-Wave的量子-经典混合求解器(CQM)以及CPLEX进行求解以作对比。该方法在波兰一个包含单轨和多轨段的真实异构城市网络中得到验证。模型包含了网络运营商提出的全部要求。计算结果表明了在现实铁路场景中应用量子-经典混合求解器的可行性和优势:它们能够在关键的重新调度时间内提供可接受的解决方案。特别是,CQM作为一种概率性启发式求解器,为调度员提供了多个可行且接近最优的解决方案供其选择。
We address the applicability of a hybrid quantum-classical heuristics for practical railway rescheduling management problems. We build an integer linear programming model and solve it with D-Wave's quantum-classical hybrid solver (CQM) as well as with CPLEX, for comparison. The proposed approach is demonstrated on a real-life heterogeneous urban network in Poland, including both single- and multi-track segments. All the requirements posed by the operator of the network are included in the model. The computational results demonstrate the readiness for application and the benefits of quantum-classical hybrid solvers in a realistic railway scenario: they yield acceptable solutions on time, which is a critical requirement in a rescheduling situation. In particular, CQM as a probabilistic heuristic solver provides a number of feasible, close-to-optimal solutions the dispatcher can choose from.