车辆路径问题的量子启发式方法

《Mathematics》：Quantum Heuristic Approach to Vehicle Routing Problem Jun Suk Kim, Donghyeon Lee and Chang Wook Ahn

　　

量子优化作为噪声中等规模量子（Noisy Intermediate-Scale Quantum, NISQ）计算的潜在应用之一，近来备受关注。然而，当将组合优化问题转化为量子电路时，量子比特需求问题仍然是一个主要瓶颈。在使用量子近似优化算法（Quantum Approximate Optimization Algorithm, QAOA）解决有容量约束的车辆路径问题（Capacitated Vehicle Routing Problem, CVRP）时，这一问题变得尤为关键，因为所需量子比特的数量随节点数呈多项式增长。本研究探讨了启发式分治策略是否能适应量子环境，从而在合理程度上保持优化能力的同时，提高量子比特效率。所提出的方法通过基于扫描的聚类方法将单个CVRP分解为多个旅行商问题（Traveling Salesman Problem, TSP），利用格罗弗搜索算法（Grover's Search Algorithm）寻找具有最小角度和的扇区配置，然后借助引力搜索算法（Gravitational Search Algorithm, GSA）辅助的量子近似优化算法（QAOA）解决每个扇区内的旅行商问题。在五个基准数据集上的实验表明，在主测试集上，所提出的方法获得的可行解与强化学习基线的差距在3.4%至12.7%之间。这些结果表明，所提出的方法为约束路由优化提供了一个可行的量子启发式框架，其优势在于通过将原始问题分解为更小的子问题来减轻量子比特负担。

### **论文解读：量子启发式方法求解车辆路径问题**

**一、 研究背景与动机**

量子计算作为信息技术领域最受瞩目的研究和投资方向之一，其解决特定问题的潜力，尤其是在化学模拟、量子机器学习等领域，已引起广泛关注。尽管完全实用的量子计算机尚未到来，但量子算法的实用性已在部分领域得到初步验证。量子计算的核心优势在于其理论上能够以远超经典计算机的效率处理某些极其庞大和复杂的问题，例如著名的组合优化问题。然而，量子算法设计本身充满挑战，一个主要障碍是量子比特资源有限。在噪声中等规模量子（NISQ）时代，量子比特的数量和质量是制约算法实际应用的关键因素。

有容量约束的车辆路径问题（CVRP）是组合优化领域一个经典且关键的原型问题，它是旅行商问题（TSP）的扩展，涉及多辆具有容量约束（如载重）的车辆，需要为所有车辆寻找最优路径。直接使用量子算法（如量子近似优化算法，QAOA）解决CVRP时，所需的量子比特数量会随着节点数目的增加而急剧增长（通常为节点数的平方级），这成为当前量子硬件难以承受的负担。因此，如何在有限的量子比特资源下，有效求解此类复杂优化问题，是量子计算应用面临的核心挑战之一。

目前的研究存在一定的局限性。许多现有工作要么专注于在预定义聚类后解决路由问题，要么依赖于量子退火而非基于电路的量子方法。特别是，关于如何通过启发式分解将单个CVRP分解为更小的子问题，以在合理保持优化能力的前提下显著减少量子比特负担，并构建一个统一的、基于电路的量子框架来同时处理分解和路由步骤，这方面的研究尚不充分。本研究的目的是填补这一空白，提出一种量子分治框架。

**二、 主要研究方法**

研究人员提出了一种量子启发式框架，核心思想是将一个大规模的CVRP分解为多个更小的、独立的TSP子问题，然后分别用量子算法求解。该方法主要包含三个关键技术步骤：

1. **基于扫描的聚类分解**：首先，将CVRP问题建模为一个以仓库为中心的二维空间。根据每个客户节点相对于仓库的极角，采用“扫描”方法将整个区域划分为若干个扇区。划分过程需确保每个扇区内所有客户节点的总需求不超过单辆车的容量上限，从而将原始的CVRP转化为多个独立的TSP。
2. **基于格罗弗算法的扇区配置选择**：由于扫描的起始点不同，会产生多种不同的扇区划分方案。研究人员利用格罗弗搜索算法，在所有这些可能的划分方案中，快速搜索出“扇区角度和”最小的那一种配置。这一步利用了格罗弗算法在无序数据中搜索目标的平方加速优势。
3. **基于QAOA和GSA的扇区内TSP求解**：对于每个确定的扇区（即一个TSP子问题），研究人员使用量子近似优化算法（QAOA）来寻找最短哈密顿回路。QAOA是一种变分量子算法，需要经典优化器来调整其量子电路中的参数（旋转角）。本研究选用引力搜索算法（GSA）作为经典优化器，通过模拟粒子间引力相互作用来迭代优化QAOA的参数，最终求得每个TSP的近似最优解。最后，将所有扇区内的TSP路径简单连接，形成完整的CVRP解。

**三、 研究结果与分析**

研究人员在五个不同规模的基准CVRP数据集上进行了实验，使用IBM的QISKIT量子模拟框架进行实现。由于模拟环境限制（最多支持32个量子比特），实验中设定每个扇区内的节点数上限为5个（包含仓库）。主要结果如下：

* **优化性能**：与一个基于强化学习（Reinforcement Learning, RL）的经典CVRP求解器相比，所提出的量子启发式方法（标记为QVRP）在所有测试集上都得到了可行的路径解。QVRP所得路径的总长度与RL基线结果存在差距，具体在3.4%到12.7%之间。这表明该框架在现有模拟限制下，能够产生具有合理优化质量的解。
* **额外扇区划分的有效性**：对于节点数更多、导致初始扇区过大的问题，研究人员引入了额外的扇区再划分步骤。实验表明（在VRP 6和VRP 8数据集上），这种进一步分解不仅没有严重恶化优化结果，在VRP 6上甚至取得了比RL基线更好的结果（提升约6.1%），在VRP 8上结果略差（差距约5.7%）。这证明了该框架通过分解控制问题规模的鲁棒性。
* **量子比特需求分析**：理论分析表明，整个算法所需的量子比特总数主要取决于解决各个扇区TSP的部分。通过分解，将需要O(n²)个量子比特的直接求解问题，转化为处理多个规模为n_c的子问题，其总量子比特需求为Θ(n)，其中n是总节点数，n_c是扇区内节点数。这显著降低了对量子硬件规模的要求。
* **时间复杂度分析**：在考虑量子电路深度的前提下，分析指出算法的总时间复杂度为O(n²)，与问题规模呈平方关系。考虑到CVRP本身的NP难性质，这是一个可接受的复杂度水平。

**四、 讨论与结论总结**

**讨论部分**指出，本研究的核心贡献不在于直接提升QAOA等量子路由子程序本身的性能，而在于提出了一种能够在QAOA阶段之前，通过分解策略有效减小问题规模的量子启发式框架。与直接应用QAOA解决路由问题的研究，或基于量子退火范式的研究相比，本工作的侧重点和比较基准不同。其实验意义更多在于验证所提出的、节省量子比特的分治框架的可行性，而非追求在绝对路由距离上的优越性。

研究也承认了若干**局限性**：实验在简化的CVRP设定下进行（未考虑时间窗、假设车辆同质等）；受Qiskit模拟器32量子比特上限的限制，扇区规模被严格控制；实验比较的规模有限；路由质量受到当前QAOA参数优化配置的影响。

**研究结论**（翻译自原文）：
> 本文介绍了一种用于解决CVRP的量子启发式框架，其方法是将单个问题分解为多个扇区层面的TSP，并借助格罗弗搜索算法、QAOA和GSA进行求解。本研究的主要发现是，分治结构有助于提供一种合理的方式来减小量子路由子程序处理的有效问题规模，从而在合理程度上保持优化性能的同时，减轻量子比特使用的负担。在选定基准数据集上的实验结果表明，在所给的模拟环境下，所提出的方法能够生成有效的路由解，其优化结果与参考基线具有可比性。此外，额外的扇区划分步骤表明，当扇区内的节点数超过实际可管理范围时，进一步分解可以维持并在某些情况下改进优化结果。所提出框架的主要优点在于其在基于电路的量子计算范式下实现了节省量子比特的问题分解。与仅关注路由阶段的方法不同，它试图在一个统一的量子导向结构中同时处理扇区选择和扇区内路由优化两个阶段。理论分析进一步表明，该分解策略在量子比特需求和实现复杂度方面都具有优势。