无人机协同卡车配送：基于连续近似的效率分析

论文题目：Coordinated Logistics with a Truck and a Drone

第一/通讯作者：John Gunnar Carlsson 美国南加州大学（USC）工业与系统工程系副教授，研究方向：连续选址与几何优化算法，重点研究具有空间结构的物流与路径规划问题，包括无人机–卡车协同配送等模型。

E-mail：jcarlsso@usc.edu

无人机协同卡车配送：基于连续近似的效率分析

论文摘要

近年来，无人机（UAV）在物流领域备受关注，亚马逊、谷歌和多家物流企业都探索用无人机实现“最后一公里”配送。传统卡车配送具有经济规模优势却成本高，而无人机配送成本低、速度快但受限于载重和续航。因此，作者提出一种卡车与无人机协同配送系统，无人机从移动中的卡车出发为客户送货，再返回卡车接收下一件包裹。为了分析这种混合系统的效率提升，论文将问题抽象为一般化的旅行商问题——马蠅路径问题（Horsefly Routing），这是一个 NP 难问题，需要同时优化卡车行驶路径和无人机起飞/降落点。

作者采用连续近似方法将离散的客户位置视为概率密度函数，以几何分析替代复杂的组合优化。论文首先给出了马蠅路径问题的形式化定义和基本符号；然后推导了卡车路径长度与客户平均距离的上下界，证明最优效率提升与卡车和无人机速度比的平方根成正比。在此基础上，提出了基于“之”字形/螺旋巡回的Heron 启发式，并通过模拟验证理论预测。最后，作者在均匀分布和城市道路网络两种情况下进行实验，结果表明理论模型能够合理预测实际性能，卡车–无人机协同系统相比单纯卡车配送可实现显著的时间节约。

一、问题背景与数学建模

1.1 物流场景与研究动机

• 快递需求增长与无人机应用：电子商务的兴起导致末端配送需求激增，现有卡车配送成本高且效率有限，而无人机具有低成本、高速度的优势，但存在载重小、续航短等缺点。
• 混合配送方案的提出：为兼顾两种载具的优劣，文中提出让无人机从移动的卡车上起飞送货，并在完成投递后于前进路线中与卡车再次汇合。
• 研究核心问题：如何设计卡车行程、无人机起降点和服务顺序，使整体完成时间最短？由于这是旅行商问题的推广，称为马蠅路径问题，求解难度极高。

下图比较了三种配送模式的路线结构，展示了单卡车、单无人机和卡车+无人机方案在拓扑上的差异，这构成了研究的直观背景。

1.2 变量及符号约定

论文采用以下符号描述模型：

•  ：客户数量。
•  ：平面上第  个客户的位置。
• 、 ：卡车与无人机的速度，满足 。
•  ：卡车路线，视为闭合曲线（loop）。
•  ：点  到路线  的最短距离。
•  ：配送顺序的排列。
•  ：卡车上无人机第  次起飞的地点。

1.3 马蠅路径问题的数学模型

在上述符号下，马蠅路径问题可表述为：在给定客户集合 ，求解卡车起飞点  和访问顺序 ，最小化所有相邻服务阶段中最大单段完成时间：

式中第一项代表卡车从一个起飞点驶向下一个起飞点的时间，第二项代表无人机从卡车起飞服务客户并回到卡车的时间。显然，当  时，该模型退化为欧几里得旅行商问题，因此是 NP 难的。

二、连续近似分析与理论结果

2.1 平均距离与下界分析

为避免直接求解组合优化，作者将客户视为在区域  内按照概率密度  分布，研究卡车路线长度  与客户平均距离之间的关系。设

则当  很大时有渐近公式：

该结果指出：平均距离的下界与路线长度  成反比，与概率密度的平方根积分相关。当  为均匀分布时，作者通过几何分析给出了严格的下界表达式。

为了达到该下界，卡车路线应呈 “之”字形或螺旋形 穿过区域，使区域中每一点到路线的距离保持尽可能均匀。下图展示了在均匀和非均匀密度下的最优路径示意：

2.2 上界分析与 Heron 启发式

在下界的基础上，作者推导了期望服务时间的上界。通过将实际最大值优化简化为相加形式，连续近似问题可转换为最小化

从而得出最优路线长度 ，相应的下界和上界差异非常小。进一步的精确上界通过引入函数  得到：

其中  为由三重积分定义的函数，且对所有  满足 。因此，总体完成时间与客户数量  的平方根成正比，且与速度比的平方根成反比，这揭示了混合系统的效率提升主要来自无人机速度的提升。

为了实现这一上界，作者提出了Heron 启发式算法。算法采用之字/螺旋路线  并通过以下步骤为每个客户分配起飞点：

1. 令路线  长度满足 。
2. 对于每个客户 ，找到其在路线上的投影点 。
3. 按  在路线上的顺序确定服务顺序。
4. 对相邻客户  和 ，在路径  与  之间选择一个起飞点 ，使  最小。

下图展示了 Heron 启发式的示意，左图为之字形路线及客户投影，右图为选择起飞点的几何关系：

该策略利用了类似海龙（Heron）定理的几何性质，使无人机路径和卡车路径协调一致，近似达到理论上界。

三、计算实验与实际评估

3.1 欧氏平面实验

作者首先在单位正方形内均匀采样  个客户，设卡车速度 ，无人机速度 。采用旅行商顺序作为初始排列，并通过 2-OPT 与 3-OPT 交换及凸优化确定起飞点。结果表明：

• 系数  接近 1：在不同速度比下，对应的效率系数  的平均值约为 1.0~1.05。这说明服务时间≈ 倍于传统卡车路径的长度。
• 影响因素：实验进一步考虑了无人机电池容量（最大飞行时间），得到的函数  随电池比例增加而上升，说明电池限制会减弱效率提升。

3.2 城市道路网络实验

第二个实验选取美国加州帕萨迪纳市的 1734 个城区街区中心点，从中随机抽取  个目的地。作者利用 Google Maps Directions API 计算道路网络上的旅行商路径，并将其与通过两阶段启发式计算得到的马蠅路径进行比较。下图为  时传统 TSP 路径与马蠅路径对比。

主要观察结果包括：

• 预测公式的验证：实际服务时间与理论预测  的比值大约在 0.9–1.1 之间，误差较小。
• 样本规模影响较小：即便 ，连续近似模型仍能提供合理的估计。
• 卡车访问客户时的改进：若允许卡车直接访问部分客户，误差进一步降低，特别是在无人机续航受限情况下。

实验结果证明理论模型在实际道路网络中仍具有较高适用性。

四、研究结论与创新点

• 提出马蠅路径问题并建立连续近似框架。文章将卡车–无人机协同配送抽象为一般化 TSP，并通过将客户分布视为概率密度来研究极限行为。
• 上下界分析揭示效率提升规律。理论证明平均服务时间与客户数量  的平方根、速度比  的平方根以及区域密度的平方根积分相关。这一规律意味着无人机速度越快，效率提升越显著。
• Heron 启发式设计。为了接近理论上界，提出通过“之”字形或螺旋巡回路径选择起飞点的算法，并证明其合理性。
• 结合仿真验证连续近似模型。通过欧氏平面模拟和实际城市道路数据，验证了预测公式的准确性，并分析了电池约束等实际因素的影响。
• 学术贡献与应用前景。该研究为未来无人机辅助配送提供了可操作的理论基准，尤其适用于多客户、密集区域的配送规划。其连续近似与几何方法也为解决其他多模式物流问题提供了参考。

通过以上分析可以看出，卡车–无人机协同配送在理论和实践中都展现出明显优势。尤其是在无人机速度大大高于卡车时，混合系统的总服务时间几乎与传统卡车模式相比缩短到  倍。这为未来城市物流布局和相关算法设计提供了重要启示。

原文链接见文末，或扫下方交流群二维码。群内实时更新推文及原文 pdf，方便专家学者随时获取（若二维码失效，请翻阅扫描最新文章的二维码）。