多访问时变无人机﹣卡车协同优化：智慧城市末端配送

论文题目：Resilient Last-Mile Logistics in Smart Cities Through Multi-Visit and Time-Dependent Drone–Truck Collaboration

第一作者：肖钦心四川师范大学商学院讲师，主要研究领域为调度优化、智能算法、智慧物流。E-mail：xiaoqinxin2017@163.com

多访问时变无人机﹣卡车协同优化：智慧城市末端配送

论文摘要

针对智慧城市末端物流中车辆拥堵与资源不足并存的矛盾，文章提出一种 多访问且时间依赖的无人机‑卡车协作路径优化问题（MTTRP‑PD）。传统无人机‑卡车协同研究多假设每架无人机每次只送达一位客户，未考虑城市交通的时变性与逆向取件需求。本文构建了一个同时考虑多客户访问、时间依赖行驶速度、同步 配送与取件 的混合整数规划模型，并基于时段分段的卡车速度函数与无人机能耗模型建立总成本目标函数，通过限制任务分配、时间同步与载重约束，确保决策可行。为求解该 NP‑hard 模型，作者设计了一套两阶段启发式算法：先用扫描插入启发式生成初始卡车‑无人机路线，再通过改进模拟退火优化方案，设置 移位、交换、移除‑再插入 等领域算子，并利用区域划分加速搜索。仿真和实际案例表明，与仅依赖卡车或单访问协同相比，该方法能够显著降低总成本和行驶距离，并提高系统的韧性和服务能力。

一、研究背景与问题描述

1.1 城市末端配送挑战

• 智慧城市的增长使末端配送需求激增，受道路拥堵、停车难等限制，传统卡车配送效率低且排放高。
• 无人机因具有高机动性和直线飞行优势，是未来绿色配送的重要补充，但续航与载重有限，必须与卡车协作。
• 现有无人机‑卡车协同多假设单次访问和固定速度，忽略了在复杂交通下无人机可承载多件任务且卡车速度随时间变化。

1.2 问题定义

目标是针对带有时变行驶速度和同步取送需求的客户集合，确定一辆卡车与无人机协同执行配送/取件任务的最佳路线，使得系统总成本（时间成本、油耗/电耗成本、车辆折旧等）最小，并满足所有约束。主要特征包括：

• 时间依赖性：卡车行驶速度  由时间段函数描述，例如以正弦函数模拟拥堵高峰。
• 多访问巡航：每架无人机可在一次飞行中连续服务多位客户，只需按顺序起降于卡车路径。
• 同步配送与取件：顾客可能同时需要送货和取件，决定了无人机的载重与剩余电量计算方式。

下面的示意图直观呈现该问题的典型场景：无人机从卡车出发，依次服务两个客户并返回卡车，卡车继续前往下一个区域。

二、模型构建与方法框架

2.1 关键假设与符号

• 车队由若干同构卡车-无人机组合组成，其索引集合为 ，客户集用  表示。

• 配送与取件需求：客户  具有配送需求  和取件需求 。

• 载重与能量约束：卡车容量 ，无人机容量 ；无人机最大续航时间为 ，飞行能耗与载荷比例相关。

• 起降操作时间：无人机起飞与回收需要额外时间  与 。

• 时变速度函数：卡车在不同时段的速度  按道路类型定义，常用函数如下， 为时间索引：

该式模拟了早晚高峰速度下降的现象。

2.2 目标函数与约束

总体目标是最小化总运营成本 ，包括卡车行驶成本 、无人机飞行成本 、车辆固定成本  、无人机固定成本  ，可表示为：

其中  为卡车路径选择变量， 为无人机路径变量。约束主要包括：

• 车辆路径完整性：卡车和无人机必须从仓库出发并最终返回，服务完所有客户。
• 时序约束：无人机的起降时间受卡车位置限制，卡车行驶时间由  决定，保证无人机返航前卡车仍在起飞点。
• 载重与能量约束：无人机在一次巡航中货物重量及消耗能量不能超过  与电池容量；卡车负载不超过 ；无人机多次访问时累计货物重量动态调整。
• 时间窗口约束：客户服务时刻必须位于规定区间 ；违约将产生惩罚成本。

2.3 算法框架：扫描插入 + 改进模拟退火

由于该模型属于 NP‑hard 问题，难以用精确算法求解大规模实例，作者提出名为 Scanning Heuristic – Enhanced Simulated Annealing（SH‑ESA） 的两阶段算法。

• 阶段一：扫描插入启发式

• 使用类似扫描法的规则为卡车构建初始路径，并根据客户角度和距离顺序逐步插入无人机任务。
• 通过检查卡车候选节点与无人机可用时间窗，确保插入后的时间可行性。

• 阶段二：增强型模拟退火 (ESA)

• 移位 (Relocation) ：将一个或一段任务从原位置移至新位置，调整卡车与无人机同步。例如，下图示意将无人机排序转移到新的卡车节点。
• 交换 (Exchange) ：互换两个任务段的位置，打破局部最优；
• 移除‑再插入 (Remove–Reinsert) ：删除一段子路径并重新插入到另一区域，提高多访问任务的可组合性；

• 领域算子：设计三类操作改善路径：

• 区域加速策略：根据卡车路径划分若干区域，局部搜索只在同一区域内移动任务，减少计算时间。

• 接受准则：采用降温函数和 Metropolis 标准接受较差解，逐步收敛到高质量解。

下面是一张示意图，展示了“移除‑再插入”操作在无人机‑卡车路径中的作用。

三、实验与案例分析

3.1 小规模实例验证

作者将 SH‑ESA 与商业求解器 CPLEX 在 20 个以内客户规模上进行比较。结果显示，该启发式在保证计算效率的同时，求解质量接近最优解，平均相对误差不足 5%。

3.2 大规模实例与算法优势

在 50～100 个客户的实例上，与传统模拟退火方法比较，SH‑ESA 的总成本平均降低约 10.53% 。算法优势主要体现在：

• 多访问：多访问无人机可以在一次飞行中连续服务多位客户，显著降低卡车行驶距离和等待时间。
• 区域加速：将搜索空间限定于局部区域，减少无效尝试，提升收敛速度。

3.3 多访问与同时取送的效益

论文通过对比单访问与多访问、纯配送与同步取送的不同模式，发现：

• 多访问 vs. 单访问：多访问模式使卡车行驶距离下降 45%，总成本下降 19.76%，平均每架无人机每次飞行服务客户数由 1 提升至约 1.8。
• 同步取送 vs. 仅配送：允许无人机回收货物可以提升载具利用率，服务容量增加 55%，总成本降低 40%。

这些结果表明，为无人机设计合理的多访问序列和同步取送策略是提升系统效率的关键。

3.4 敏感性分析

作者进一步研究了交通波动、无人机电池续航和载重等参数的影响：

• 交通时变性：忽略高峰期交通波动将低估总成本约 20%，高峰期速度下降时无人机承担更多任务，有助于缓解拥堵。
• 无人机续航：当电池续航大于 60 分钟时，成本下降趋于平缓，表明续航时间并不是无限延长越好，载重限制才是瓶颈。
• 载重能力：提高无人机载重可显著减少卡车行驶距离，但受制于法规和机体尺寸，需要平衡。

3.5 城市案例：长沙智慧配送

作者以中国长沙某电商平台 30 个客户的城区配送为案例，构建有 禁飞区 与 时间依赖速度 的实际路网。结果表明：

• 采用 MTTRP‑PD 模型的无人机‑卡车协作方案总成本比仅卡车方案下降 19.58%，总行驶时间减少 21.79%。
• 原需 4 辆卡车才能完成的任务经协作后只需 3 辆卡车和 3 架无人机，其中无人机完成了 36% 的配送任务。
• 多访问使得无人机平均每次飞行服务 1.4 位客户，提高了电池利用率。

四、结论与创新点

1. 提出全新的 MTTRP‑PD 模型：首次将多访问、时间依赖速度与同步取送三种特征融入无人机‑卡车协同中，为城市末端配送提供更真实的数学描述。
2. 建立多层次决策框架：综合考虑车辆调度、无人机路线、能耗与时间窗约束，构建混合整数规划并给出工程化的求解框架。
3. 设计高效启发式算法：通过扫描插入启发式和增强型模拟退火组合，巧妙利用移位、交换、移除‑再插入等操作，提高了大规模实例求解效率。
4. 系统性实验验证：详尽的对比实验、敏感性分析及真实城市案例证明了模型与算法的优越性，为政策制定者和企业提供了量化依据。
5. 揭示关键管理启示：强调多访问与同步取送的重要性，指出应合理配置无人机载重与电池续航，并结合交通实时信息调度卡车以提高系统韧性。

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