盖世汽车讯 据外媒报道，由Yuan-Zheng Lei领导的马里兰大学（University of Maryland）科学家团队开发出新的框架，旨在增强量子近似优化算法（Quantum Approximate Optimisation Algorithm，QAOA），以应对复杂的物流挑战，特别是车辆路径问题。这项研究解决了标准QAOA的一个根本局限性：难以在庞大的搜索空间中高效地识别有效解。

图片来源：ArXiv

该团队的方法结合了目标初始状态（该初始状态基于问题固有的局部约束）和一种新型混合器，该混合器旨在既保留现有的部分解结构，又能促进对新潜在路径的探索。通过仿真进行的评估（包括考虑当前量子硬件实际限制的仿真）始终表明，与传统的QAOA实现相比，该方法在解的成本和可行性方面均表现出更优的性能，这表明随着量子技术的成熟，为更高效的车辆路径量子解决方案提供了一条可行的途径。

约束感知QAOA显著扩展车辆路径问题的可行解空间

与标准QAOA相比，新框架取得了显著改进，可行解的占比提升至99.7%。标准QAOA在应用于车辆路径问题时，通常只能在搜索空间的极小一部分范围内找到可行解。可行路径对于物流应用至关重要，而以往，即使找到一个可行解也往往计算量巨大，尤其是在规模较大的实例中。袁正雷及其同事开发了约束感知QAOA，该算法采用轻量级初始化策略和混合XY-X混合器，性能始终优于传统方法。车辆路径问题本身涉及确定车队服务一组客户的最佳路径集合，同时考虑车辆容量、配送时间窗口和行驶距离等约束条件。这是一个非确定性多项式难（NP难）问题，这意味着找到最优解所需的计算量会随着顾客和车辆数量的增加呈指数级增长。

在所有测试条件下，平均能量水平始终较低，表明算法能够更高效地搜索最优解。在QAOA算法中，能量水平对应于解的成本；能量越低，意味着路径越好、成本越低。通过关注关键的局部约束，例如确保每个客户只被访问一次以及遵守车辆容量限制，轻量级初始化策略缩小了初始计算空间，有效地引导算法找到可行的路径。这与标准QAOA算法采用的随机起始点形成鲜明对比，后者通常需要对不可行区域进行大量探索才能找到有效解。在优化过程中，通过混合XY-X混合器可以保持重要的约束结构。XY-X混合器是一种特殊的量子电路，用于在QAOA优化过程中演化量子态。“X”组件负责对解空间进行必要的探索，而“XY”组件则通过最大限度地减少对已满足约束的干扰来帮助保持部分解的结构。这种探索与利用之间的微妙平衡对于提高算法性能至关重要。该框架为解决复杂的物流问题迈出了重要一步，有可能大幅节省成本并提高运输网络的效率。

然而，目前的研究成果仅限于模拟和相对较小的实例，这意味着将其扩展到包含数百辆车辆和配送点的真实物流挑战仍然是一个巨大的障碍。模拟中使用的实例最多只有20个地点，远低于许多真实配送网络的复杂程度。这凸显了算法结构与量子硬件实际情况之间的微妙矛盾，尽管约束感知QAOA框架带来了改进。虽然该算法在接近理想条件下展现出更优的性能，但随着实际量子噪声的引入，其优势会逐渐减弱。量子噪声源于量子比特控制和测量的缺陷，它会在计算中引入误差，阻碍算法收敛到最优解。即使噪声限制了短期收益，这仍然代表着在将量子算法应用于真实物流挑战方面取得的重要进展，并且随着技术的进步，有望带来显著的性能提升。未来的工作需要着重开发误差缓解技术，并探索更稳健的量子硬件，以充分发挥该方法的潜力。

结构化QAOA混合器展现出良好的应用前景，但仍受限于当前的量子噪声水平

物流公司正越来越多地探索利用量子计算来优化复杂的车辆路径规划，这对于降低成本和缩短配送时间至关重要。考虑到现代物流运营的规模，即使路径效率的微小提升也能带来巨大的潜在收益。模拟真实量子硬件（包括量子比特门操作和读出保真度的限制）的仿真结果表明，与标准QAOA相比，结构化QAOA的性能有所提升，尽管在噪声环境下性能差距有所缩小。量子比特门保真度指的是量子操作的精度，而读出保真度则反映了测量最终量子态的可靠性。较低的保真度会引入误差，从而降低算法的性能。

正如这些结果所示，随着量子硬件的成熟和错误率的降低，像本研究中使用的混合XY-X混合器这样结构化的算法方法可能会变得越来越有价值。该方法在各种仿真条件下都能始终如一地识别出比标准方法成本更低、更可行的路径，证明了其在解决车辆路径问题（物流优化中的一个关键挑战）方面的有效性。使用混合混合器，巧妙地平衡探索和利用，似乎是一种很有前景的策略，可以减轻噪声的影响，并提高QAOA在实际应用中的鲁棒性。还需要进一步研究该方法的可扩展性，并探索其与其他量子算法和经典优化技术集成的潜力。