一种基于量子比特优化（QUBO）的模拟退火算法方法，用于解决城市交通网络中最短路径问题 作者：Isaac Oliva-González 和 Hugo Jiménez-Hernández

《Algorithms》：A QUBO-Driven Simulated Annealing Methodology for Solving the Shortest Path Problem in Urban Transportation Networks Isaac Oliva-González and Hugo Jiménez-Hernández

　　**摘要**
最短路径问题在图优化领域面临着巨大挑战，尤其是在密集或大规模网络中，传统算法存在严重的可扩展性限制。本文提出了一种基于二次无约束二进制优化（QUBO）的模拟退火（QUBO-SA）方法，该方法能够有效结合路径成本和结构约束进行编码。我们在具有可控连接性的合成图上对该方法进行了严格评估，这些合成图的节点数从??=10增加到??=40，并在墨西哥克雷塔罗的一个实际城市交通网络上进行了测试，该网络包含??=443个节点。我们通过一系列严谨的概率可靠性指标来评估性能，主要包括成功率??success、解决时间以及相对于Dijkstra算法的运行时间比率???(??target)。在小型合成图中（??=10），QUBO-SA方法的成功率非常高（??success≥0.97），且运行时间与确定性基线方法相当（???.??≈1）。然而，随着问题规模的增加，成功率会降低，计算开销也随之上升，其中???.??的值从大约0.85大幅降至0.65。在真实城市网络中，根据指定的路径长度，我们的求解器的成功率介于0.75到0.85之间，运行时间范围也在相应的区间内。值得注意的是，将目标置信水平从0.9降低到0.85可以在所有配置中将运行开销减少约50%。尽管QUBO公式在某些方面表现出良好的可扩展性，这可能限制了其在密集图中的应用，但现实世界道路网络的稀疏结构使得该方法在中等规模问题中仍能保持竞争力。这些发现明确指出了解决方案可靠性和计算效率之间的权衡，并指出了特定问题类型，在这些类型中基于QUBO的优化方法不仅可行，而且对于路径优化任务来说具有显著优势。