最后一公里物流中能量受限无人机配送装箱问题的近似

这份资料讨论的是无人机与卡车协同的最后一公里配送中，如何用尽可能少的无人机把一批包裹全部送完。每个包裹带有配送时间区间和成本，系统由一组同型号无人机和沿卡车路线布置的电池站组成，无人机可以更换耗尽电池或充电。与已有的“固定机队、最大化利润”的无人机调度问题不同，这里反过来要求不遗漏任何包裹，目标是最小化所需无人机数量，同时受电池预算和单架无人机任务兼容性的约束。这个角度更贴近配送企业按区域分配运力的实际决策，因此值得关注。

材料覆盖三类问题变体：没有电池服务站的 DDP-NS、配送区间不冲突的 DDP-NC，以及既有电池站又可能出现区间冲突的 DDP-SC。作者说明三类问题都是 NP-hard，并为每一类提出近似算法，使用绝对近似比和渐近近似比两个指标衡量。方法上属于组合优化与近似算法分析，最后还在不同实例上把算法表现与最优解进行比较。换句话说，材料提供的是理论界与实例验证，而不是实地车队试验数据。

关键数字集中在近似比上。无电池站时，摘要给出的无人机数量上界是 min{(11/9)OPT_NC+24/9，(3/2)OPT_NC+3/2}，其中 OPT_NC 是最优解规模；正文贡献部分又把同类情形概括为至多 (2+ψ)OPT_NS。区间不冲突时，作者设计的是 (2+ψ)-近似算法。这里的 ψ=(ϵmax−ϵmin)/(1−ϵmax)，ϵmin 与 ϵmax 由单次配送成本与无人机电池预算 B 的比值决定，ϵmax 还被限制为不超过 1/2。

当电池站存在且配送区间可能冲突时，材料给出 (4+ψ)-近似算法；如果电池服务站同时充当换电站，算法可改进为 (3+ψ)-近似。这个变化说明，换电能力不只是工程细节，它直接改变了近似比中的常数项。结合三类问题均为 NP-hard 的结论，这意味着作者并不追求精确最优解，而是用可证明的近似界来控制无人机数量。

这些结论对实践的含义是：按区域压缩所需无人机数量，可以让仓库里的同一批无人机服务更多区域，因为配送公司通常按区域派出卡车，无人机需要在这些卡车之间分配。电池站允许充电或换电，会显著降低完成全部配送所需的无人机数量；而时间区间冲突和“同一时刻最多送一个包裹”的兼容性约束，则决定了一架无人机能否接上下一单。解读来看，ψ 把配送成本和电池预算纳入了近似比，说明电池预算越紧或成本差异越大，算法相对最优解的余量就越需要被认真评估。

这份资料适合做最后一公里物流、无人机调度和近似算法研究的读者阅读，能拿走的是问题形式化、三类变体的划分、各自的近似比，以及用电池预算和成本构造 ψ 的参数化思路。边界也需要说明：材料中的验证是“在不同实例上与最优解比较”，没有给出真实城市路网、空域管制或大规模车队部署的数据。另外，无电池站情形的上界在摘要中写成 min 形式的常数界，在正文贡献部分又写成 (2+ψ)OPT_NS，两处表述并不完全一致，实际使用时需要回到原文核对定义与适用条件。

Approximation Algorithm on Drone Delivery Packing Problem with Battery Stations Saswata Jana and Partha Sarathi Mandal ∗ † ‡ April 28, 2026 Abstract Collaboration between drones and trucks in a last-mile delivery system offers numer- ous benefits and reduces many challenges of the traditional delivery system. Here, we introduceDrone-Delivery Packing Problem, where a set of parcels, associated with deliv- ery intervals and cost, should be delivered to customer locations. The system comprises a set of identical drones and battery stations along truck’s route, where drones swap de- pleted batteries or recharge them. The objective is to find assignment for all parcels by using the minimum number of drones, subject to the battery budget and compatibility of each drone’s assignment. We consider three variants of the problem, based on conflicting