在无人机配送装箱问题上测试量子退火与模拟退火

无人机配送的装箱问题（drone delivery packing problem，DDPP）来自物流场景中的一个现实压力：配送需求上升，同时又要减少人工介入。这类问题通常被写成组合优化问题——在电池约束、固定地点和能量预算下，用尽量少的无人机完成时间上连贯的配送。这份资料要回答的问题是：把 DDPP 写成 quadratic unconstrained binary optimization（QUBO）之后，量子退火（quantum annealing，QA）和模拟退火（simulated annealing，SA）以及经典全局优化工具相比，究竟表现如何。值得现在看的原因在于，它不是停留在「量子优化或许有优势」的泛论，而是拿一个具体的、有工程背景的优化问题做横向实测，并把优势和局限都摆出来。

覆盖范围上，工作提出两种 DDPP 的 QUBO 形式：一种沿用通用的标准做法，另一种针对 DDPP 本身定制。技术路线上，先把带约束的二次优化问题通过引入松弛变量转成整数线性规划问题（ILPP），再用二次罚项转成 QUBO——罚项对可行解取零、对不可行解取正值。作者指出，这种标准流程如果直接实现，会导致变量数过多，进而在嵌入量子硬件后需要过多量子比特，因此才提出松弛版本。实验部分使用模拟退火与量子退火采样器，量子端采用 D-Wave 的 Advantage system 4.1，并与经典模拟退火以及确定性的全局优化商业工具对比；评价维度包括问题规模、链强度（chain strength）、求解时间、内存开销和解的质量。

第一个关键结论关于形式化本身：定制的 QUBO 形式所需的松弛变量显著少于通用做法。这不是单纯的工程技巧，因为松弛变量数直接决定嵌入后的量子比特需求，而在量子退火上，量子比特数与连接度约束恰恰是把问题写进硬件的实质障碍。换句话说，问题能不能上机、能上多大的机，很大程度上取决于形式化写得好不好，而不只是硬件规模。作者把这一点列为贡献之一，也说明两种形式的对比是整篇工作的基础。

第二个关键结论关于硬件与对比结果。材料给出的具体数字是：上一代 D-Wave 2000Q 具备 5627 个量子比特、每比特 15 个耦合器、共 35,000 个耦合器；而 Advantage 量子处理单元平均可承载的输入规模约为前者的近三倍。作者据此做了较广泛的实验，报告了在问题规模与链强度方面的性能统计，以及相对于模拟退火和确定性基线在求解时间、内存成本和解质量上的表现，并明确称实验展示了量子退火器在这个优化问题上的优势与局限。需要注意的是，材料只给出了上述硬件规格数字，并未在可见正文中列出具体的解质量差距或时间加速倍数。

这些结论意味着什么？从作者自述的目标看，这项工作是把 DDPP 当作一类复杂组合优化问题的原型，用来识别现代量子退火硬件在寻找可靠解上的长处与短板，以及它在多大程度上能成为模拟退火和确定性方法的现实替代。一个更具体的落点是量子—经典混合思路：在中等至小规模测试问题上考察可扩展性，对混合方法尤其重要，因为量子部件可以被当作专用子处理器，用来改进更大经典算法内部的子问题。这也解释了为什么作者要花力气压缩松弛变量——在混合范式下，量子端能装下多大的子问题直接决定它有没有用。

读这份资料的人应当是关注组合优化落地、量子退火实测或物流调度建模的同行；可拿走的东西有三样：一个带电池与时间约束的无人机配送装箱问题的明确表述，两套可直接对照的 QUBO 形式化方案（含「定制形式显著更省松弛变量」这一可复用经验），以及一份把量子退火与模拟退火、确定性商业求解器放在同一问题上的评测框架与统计口径。边界也要说清楚：材料中的硬件数字只到 D-Wave 2000Q 的规格与 Advantage 承载规模约为其三倍这一层，正文可见部分没有给出具体的加速比或解质量数值，因此不能据此推断量子退火已在 DDPP 上取得实际优势；作者的结论本身也是「优势与局限并存」，而非单方面的胜出。

arXiv:2406.08430v1 [math.CO] 12 Jun 2024 Testing Quantum and Simulated Annealers on the Drone Delive ry Packing Problem Sara T arquini1 Daniele Dragoni 2 3 Matteo V andelli2 Francesco T udisco1 4 Abstract Using drones to perform human-related tasks can play a key role in various fields, such as de- fense, disaster response, agriculture, healthcare, and many others. The drone delivery packing problem (DDPP) arises in the context of logistics in response to an increasing demand in the deliv- ery process along with the necessity of lowering human intervention. The DDPP is usually formu- lated as a combinatorial optimization problem, aiming to minimize drone usage with specific bat- tery constraints while ensuring timely consistent deliveries with fixed locations and energy budget. In this work, we propose two alternative formu- lations of the DDPP as a quadratic unconstrained