盖世汽车讯 车辆路径问题是物流和供应链管理中的一项关键挑战，随着配送地点数量的增加，其计算量往往会变得难以处理，从而阻碍了高效配送网络的构建。据外媒报道，来自量子科学与技术中心（Center for Quantum Science and Technology）的Shreetam Dash、埃克塞特大学（University of Exeter）的Siksha 'O' Anusandhan和Shreya Banerjee以及Prasanta K. Panigrahi及其同事，展示了一种量子方法，该方法显著扩展了可解决的车辆路径问题的规模。

图片来源：ArXiv

该方法结合了标准量子算法和多角度量子算法，巧妙地将一个包含13个地点的车辆路径问题分解成更小、更易于管理的集群。这项创新技术不仅能够以惊人的精度识别每个集群内的最优路径，达到与经典优化方法相当的水平，而且在集群间路径规划方面也取得了优异的性能，从而突破了量子优化在实际物流挑战中的应用极限，并将解决方案的能力扩展到以往仅限于少数地点的局限。

本研究致力于开发一种分层量子优化（HQO）算法，该算法在多角度配置下利用了量子近似优化算法（QAOA）。该方法克服了现有量子算法在处理多点问题（常见于现实世界的车辆路径规划场景）时的局限性。该方法的核心在于一种聚类分解技术，该技术基于地理位置的接近性，将整体问题分解为更小、更易于处理的子问题。

这种分层结构使该算法能够处理多达100个地点的问题，相比传统的QAOA实现有了显著改进。具体来说，该团队提出了一种在QAOA框架内构建成本函数的新方法，该方法针对车辆路径问题的约束条件进行了优化。该成本函数包含了行驶距离、车辆容量和配送时间窗口等因素。多角度QAOA配置与聚类分解相结合，显著增强了算法在复杂车辆路径实例中寻找近似最优解的能力。研究人员者探索了一种混合量子-经典方法来优化配送路线，旨在利用近期量子计算机的潜力将其应用于实际物流应用。其核心挑战在于为一组客户找到最有效的车队路线，以最小化总行驶距离或成本。这是一个计算难题，随着客户和车辆数量的增加，其复杂性也会显著提高。

本研究着重于利用变分量子算法QAOA求解VRP的近似解。QAOA与经典优化技术相结合，采用混合方法。VRP被建模为二次无约束二元优化（QUBO）问题，适用于在量子退火器或QAOA电路上实现。QAOA的性能取决于其参数的优化，研究人员采用经典优化算法来寻找QAOA电路的最佳参数设置。本研究包括在经典计算机上模拟QAOA算法以评估其性能，最终目标是在近期实际量子硬件上运行这些算法。

Spall算法是一种无需计算导数的优化方法，用于调整QAOA电路的参数。研究表明，随着量子硬件的不断改进，QAOA和混合量子-经典算法在解决车辆路径问题（VRP）方面可能比经典算法更具优势。研究人员强调了对近期量子器件的关注，并证明即使在当前硬件限制下也能获得有意义的结果。量子算法和经典算法的结合对于实现良好的性能至关重要，其中量子部分负责组合优化，而经典部分则负责参数优化以及可能的后处理。

该团队通过分层分解方法实现了这一进展，利用K均值聚类将问题分解为更小的子问题，使用标准量子近似优化算法（QAOA）进行簇内路由，并使用多角度QAOA优化簇间连接。结果表明，标准QAOA能够始终如一地找到簇内路由任务的最优解，其性能与经典优化算法的性能完全一致。在各种测试实例中，准确率达到29%。这表明，即使当前量子硬件存在固有噪声，量子方法仍具有应对复杂后勤挑战的潜力。

研究人员承认，多角度量子自适应光学阵列（QAOA）的性能依赖于对大量参数的有效优化，而所选的优化技术已被证明非常适合这项任务。