末端配送的"空地协同"方案：时空约束下多趟次无人机参与的配送网络
多趟次空地协同要怎么优化？
清晨六点，生鲜商店的货品刚刚到达履约中心，客户却希望在九点前收到新鲜面包；医院急需的紧急药品正在包装，却还没被释放出库。无人机可以快速穿梭城市上空，却无法承受过多重量；无人车能一次送达多户，却又要在交通拥堵中缓慢前行。如何在 时间紧迫、需求多样 的城市配送中协调无人机与无人车，让每一件包裹既早发又准时到达？这种 “速度与容量” 的矛盾构成了当前生鲜与应急物资配送的最大瓶颈。
如果让无人机负责履约中心到中转节点的第一阶段，用无人车完成最后一公里，是否能够兼顾效率和可持续性？当 包裹的释放时间各不相同 ，多行程调度、充电/准备时间和车辆数量如何决策？
论文摘要
该研究针对一类新颖的空地协同配送网络，提出了多行程无人机–无人车（UAV‑UGV）位置‑路径联合优化模型。每个包裹从履约中心释放出来具有独特的释放时间和要求的送达时间，需先由无人机送往若干可选对接点（docking hubs），再由无人车完成最终配送。文章的目标是同时确定对接点的位置、无人机/无人车的队列规模、各自多行程的路径和出发时间，以最小化总投资和运营成本。为此作者建立了一个紧凑的混合整数线性规划（MILP）模型，并设计了基于适应性大邻域搜索（ALNS）的启发式算法，以求解这个 NP‑难问题。论文通过小规模实例比较验证模型的精确性，通过香港九龙区的大规模案例展示算法在实际场景中的适用性。敏感性分析揭示，增加无人机载重可显著降低成本，而缩短包裹释放‑截止时间则会显著提高成本。
一、问题背景与研究综述
1.1 背景与现实挑战
双层配送模式：研究场景中存在一个履约中心、一组候选对接点与若干顾客。无人机负责将包裹从履约中心运送至对接点；无人车从对接点出发服务顾客，完成“最后一公里”配送。 包裹释放与时限：每个包裹在其释放时间之后才可装载，无人车必须在顾客的送达截止时间前送达。释放时间各不相同，形成复杂的时间协调问题。 资源约束：无人机与无人车均具有载重和续航限制，并且需要在每次行程之间进行充电或准备。 研究空白：已有两层车辆路由问题（2E‑LRP）的研究多集中于时间窗口或容量约束，但鲜有同时考虑包裹释放时间、无人机‑无人车协同和多行程调度的工作。
1.2 相关研究概述
两层位置‑路径问题（2E‑LRP）是物流学中的重要模型，早期研究多采用禁忌搜索、分支定价等方法解决传统路网下的货物配送。随着城市即时配送需求增长，学者开始加入时间窗约束（2E‑LRPTW）、多产品运输等复杂因素。本论文在此基础上，首次将包裹释放时间与多行程无人机‑无人车协同纳入统一框架，构建了全新的两层配送网络优化模型。
二、模型与方法
2.1 网络描述与决策变量
研究对象是一张有向图 ，包含履约中心、候选对接点集合 与顾客集合 。决策变量主要包括：
：对接点 是否被启用； 、：分别表示无人机 、无人车 是否分配至对接点 ； ：无人机 的第 趟行程是否飞往对接点 ； ：包裹 是否由无人机 的第 趟行程运送至对接点 ； 、 等变量表示各行程的出发和到达时间。
图 1 展示了该双层网络的示意图：无人机从履约中心出发执行多行程，将包裹放置在对接点，再由无人车多行程服务顾客，行程之间还需留出准备时间。
2.2 优化目标与约束
目标是最小化总系统成本，包括对接点启用成本 、无人机和无人车的投资成本 、 以及行驶成本。简化表达的目标函数为：
其中 、 分别为无人机和无人车各行程的旅行时间。
主要约束包括：
无人机约束：每个包裹必须由一趟无人机行程运输；行程载重不超过无人机容量；出发时间不得早于包裹释放时间且满足起飞‑飞行‑降落顺序；同一无人机多行程之间需留出充电/准备时间。 无人车约束：每个顾客由一趟无人车行程服务；行程载重不超过无人车容量；对接点到顾客顺序要保证路径连贯；多行程之间满足准备时间与电池限制；必须在顾客截止时间前完成服务。 连结约束：如果包裹由某趟无人机行程送至对接点，则对应无人车行程必须从该对接点出发；无人车出发时间不得早于所有所载包裹到达该对接点的时间。
2.3 时间序列优化策略
由于包裹释放时间及多行程调度使时间安排复杂，论文提出了决定无人车与无人机出发时间的局部搜索策略（见图2）。核心思想是：
无人车行程（Gtrip）：设某无人车行程服务客户集合 并从对接点 出发返回，则其最早出发时间为
即所载客户包裹到达该对接点的最大释放时间；其最晚出发时间为
其中第二项为从对接点到客户 的累计旅行时间。若 则行程可行，并且选择尽可能晚出发可以增加可连接的无人机行程数量。
无人车路线（Groute）：若一辆无人车执行多趟行程 ，采用递归调度，先将最后一趟行程的出发时间设为其 ，前一趟出发时间则为
无人机行程（Atrip）：类似地，服务客户集合 的无人机行程最早出发时间为该集合中包裹的最大释放时间
最晚出发时间为携带客户到达履约中心允许的最早截止时间
行程可行时选取尽可能早出发以便包裹早到对接点，增加后续无人车行程连接的机会。
无人机路线（Aroute）：多行程无人机采取前向递推；第一趟行程在其最早时间出发，后续行程的出发时间为
确保每趟行程至少等待前一行程完成加准备时间。
这种策略实质上将全局复杂的时间调度分解为局部可解的子问题，显著简化了后续搜索。
2.4 初始化方法与模型复杂性
完整的 MILP 模型包含大量连续和整数变量以及复杂的连结约束。例如在一个拥有5名客户、2个候选对接点、每种车辆最多5趟行程的小网络中，模型就有225个连续变量、1345个二进制变量和6835条线性约束，其中 4375 条是连接无人机与无人车的约束。为了获得可行的初始解，作者提出了四阶段贪心算法：
生成无人车行程：激活一个对接点，根据电池里程和时间窗口筛选可达顾客，逐一插入形成最短路径。 生成无人车路线：将所有行程按最早返程时间排序，递归插入保证时间可行性。 生成无人机行程：针对每个对接点按顾客的到达履约中心截止时间排序，形成无人机行程并插入已有行程。 生成无人机路线：按最早返程时间将行程分配给多辆无人机，并调整出发时间。
这套初始化方案既考虑了时间窗口和载重约束，又能为后续启发式优化提供高质量起点。
三、定制适应性大邻域搜索 (ALNS)
3.1 算法框架与思想
由于 MILP 模型的 NP‑难性质，对接点决策、车辆数量、行程组合及时间同步相互耦合，商业求解器在大规模实例上难以快速求解。因此作者提出将问题拆分为主问题（决定对接点、车辆配置和路径）与若干时间序列子问题，并采用适应性大邻域搜索（ALNS）来迭代改良。
ALNS 核心采用“破坏‑修复”机制：在当前解中随机或基于某种策略移除一部分行程（破坏），再用不同的插入策略将待服务顾客重新安置（修复），从而跳出局部最优并探索大的邻域。算法自适应调整各操作的选择概率，并使用 Metropolis 准则接受劣解以增加多样性。
3.2 破坏与修复操作设计
论文设计了9种破坏操作与2种修复操作。关键破坏操作包括：
随机移除：随机选择一部分顾客从当前解决方案中删除； k‑随机移除：一次移除 k 个随机顾客； Gtrip移除 / Atrip移除：直接移除一趟无人车（或无人机）行程，使其顾客重新安排； 区域移除：从某个地理区域中移除一定比例的顾客； 最差成本移除：选择当前方案中增成本最高的顾客或行程删除； 对接点移除：关闭某个对接点并移除其相关行程； Shaw移除：根据顾客之间的相似度（地理位置、释放时间）移除一簇顾客，参数调节如表中所示。
修复阶段包含贪心插入与带噪声贪心插入：分别按最小成本插入未服务顾客，或在成本上加入随机扰动以增加多样性。
3.3 自适应机制与接受准则
自适应选择：每个破坏与修复操作初始概率相等。算法每隔 代更新一次操作得分：若新解优于当前最优解，则操作得 分；若优于当前解但非最优，得 分；若被 Metropolis 准则接受则得 分。得分越高，下一阶段被选中概率越大。
Metropolis 接受准则：对于新解 与当前解 ，若 则直接接受；否则以概率
接受新解，其中 为“温度”，逐渐按冷却率 下降。
算法流程：算法1概述了整个 ALNS 流程，包括初始化、选择操作、更新解、更新温度及概率等步骤。下图展示了论文中给出的 ALNS框架示意。
3.4 时序关系图示
论文还提供了无人机与无人车行程的关键时间关系图（见图4），用于帮助理解释放时间、准备时间、出发时间和到达时间之间的逻辑关系。该图形象展示了Atrip与Gtrip之间的时间联动，对算法设计有重要指导意义。
四、实验与分析
4.1 小规模实例比较
研究首先在一系列包含 5–20 个顾客、2–7 个候选对接点的小规模实例上比较 ALNS 与 Gurobi 的表现。结果显示，Gurobi 仅在部分实例中能在 24 小时内找到并证明最优解，而 ALNS 在所有实例上都能稳定给出质量可比的解，且部分解甚至优于 Gurobi。随着问题规模增大，Gurobi 的求解时间迅速增长，部分实例无法在时限内获得可行解；相比之下，ALNS 始终可在约 70 秒内获得高质量解，体现了启发式方法在该类两层配送问题上的效率优势。
4.2 大规模香港案例
论文进一步以香港九龙区为场景开展大规模案例研究。该案例包含1个履约中心、20个候选对接点（SF快递的业务站点）和200个客户。包裹释放时间均匀分布在 6:00–22:00 之间，各客户有60–90分钟的送达时间窗。在24小时时限内 Gurobi 未能提供任何可行解；采用 ALNS 则多次运行均得到成本约 2.68×10^4 的解，平均计算时间约 2,794 秒。一份典型方案如图5所示：共激活4个对接点，使用6架无人机执行83个航程，11辆无人车执行多行程服务所有200名顾客。
对接点选择：位于荔枝角、旺角、九龙城和观塘的四个对接点被启用，每个对接点配备1–6辆无人车。 资源配置：共需要6架无人机和11辆无人车；无人机主要负责及时将包裹送达对接点，无人车则集中完成最后一公里配送。 运行效率：该集成方案确保所有顾客在其时间窗内收到包裹，且比传统模式大幅缩短了配送时间。
4.3 敏感性分析：无人机载重
为了评估无人机载重对系统效率的影响，作者在大规模实例中将单架无人机的载重量从5 kg提高到20 kg。结果显示，当载重从5 kg提升到20 kg时，所需无人机数量从8架降至4架，行程数量减少，网络成本下降约30%。然而当载重超过20 kg 后，由于包裹释放时间分散，行程组合依然受时间窗限制，成本不再继续下降。该分析揭示了监管放宽无人机重量限制可能带来的成本节约机会。
4.4 敏感性分析：包裹释放时间
论文还考察了缩短包裹释放-截止时间间隔的影响。将时间窗从原来的 60–90 分钟压缩到 30–60 分钟时，网络所需无人车数量平均从 12.33 辆增加到 20 辆，导致行程增多、整体成本上升超过 60%。其原因在于释放-截止时间变短会显著削弱调度灵活性，使 UAV 与 UGV 的协同空间缩小，从而需要更多车辆来满足时限要求。此外，适度提前释放包裹可提升路径规划效率，但超过一定阈值后成本下降趋于平稳，表明过早释放带来的边际收益有限。因此快递企业在制定服务时效时，应平衡快速配送带来的非线性成本增长，并对“超快速”服务设置合理溢价。
4.5 初始化方法与算法性能
作者比较了两种构造初始解的方法：先生成无人车行程 (INI) 与先生成无人机行程 (SEQ)。在35个小实例和一个大实例中，INI方法平均能产生更好的初始方案，比SEQ低 2.99%，并在随后的 ALNS 迭代中平均改进14.11%。不过更优的初始解并不总能加快收敛速度，显示出 ALNS 框架具有一定的鲁棒性和自适应性。
五、结论与展望
本文针对具有包裹释放时间、时间窗和多行程约束的空地协同配送提出了全新的模型与算法。论文的主要贡献可归纳为：
问题创新：首次在两层位置‑路径优化框架中整合无人机与无人车的多行程调度、对接点选址和包裹释放时间，将理论模型与现实城市配送相结合。 模型设计：构建了紧凑的 MILP 模型，通过连结约束精确描述无人机与无人车之间的关联，考虑了容量、时间窗、准备时间等多重限制。 时间序列策略：提出局部递推的出发时间优化策略，确定无人机/无人车行程的最早、最晚出发时刻，降低了调度复杂度。 算法贡献：设计了定制化 ALNS 算法，包括多种破坏/修复操作与自适应选择机制，可快速求解大规模实例，并通过实际案例验证效果优于商业求解器。 实证与洞见：在香港九龙区案例中，算法成功选择4个对接点、6架无人机和11辆无人车完成200个包裹的配送；敏感性分析表明提高无人机载重可大幅降低成本，而缩短释放‑截止时间将显著增加成本。
未来研究方向：首先，可考虑不确定性因素，如天气、交通和需求波动，构建稳健或随机优化模型。其次，应探索与传统车辆和人工配送相结合的混合模式，引入多运输方式决策层。此外，随着无人系统具备多功能能力，未来可将配送与数据采集、监测等任务结合，进一步提升网络效用。
通过深入剖析该论文，我们可以看到，在面对城市即时配送的时间约束与成本压力时，充分利用无人机和无人车的互补优势，并设计合适的时间调度策略与启发式算法，是实现高效、低碳物流网络的关键。
文章须知
推文编辑：单子叶
责任编辑：张仁义
原文链接：https://doi.org/10.1016/j.trc.2025.105389
