动态交通网络中的配送创新：卡车-无人机混合调度及启发式研究

论文题目：Truck-drone hybrid routing problem with time-dependent road travel time

第一作者：王勇 重庆交通大学教授，博士生导师，2021/2022连续两年入选斯坦福大学发布的全球前2%顶尖科学家榜单，国家自然科学基金管理学部通讯评审专家，重庆市重点学科“管理科学与工程”一级学科博士点负责人。主要研究领域包括城市物流配送、物流与供应链管理、智能物流运输网络优化、城市应急物流即时配送与资源协同调度等。

E-mail：yongwx@cqjtu.edu.cn。

动态交通网络中的配送创新：卡车‑无人机混合调度及启发式研究

论文摘要

卡车与无人机协同配送被视为未来城市物流的重要模式，但在道路交通随时间变化的现实条件下，协同路径如何规划依然缺乏系统研究。本文提出卡车‑无人机混合路径问题，显式考虑道路拥堵引起的时间依赖旅行时间，寻求最小化总配送成本和满足客户时间窗的方案。研究建立了包含卡车与无人机固定成本、道路拥堵成本、协同成本的数理模型，并利用新扩展的流体排队模型描述时变道路旅行时间，证明其满足先进先出（FIFO）特性。为解决该 NP‑困难问题，作者设计了一种迭代局部搜索（ILS）算法：先通过时间窗预处理和贪心策略生成初始卡车‑无人机路径，再通过车‑机对内外部客户交换及2‑opt优化提升解质量，充分利用无人机规避拥堵的优势。仿真和重庆市实际数据案例表明，卡车‑无人机模式能显著减少运输距离与成本，平均服务时间较仅用卡车方案降低约16%。该研究为应对动态交通网络、提升城市配送效率提供了新框架。

一、研究背景与问题定义

1.1 城市配送的挑战与无人机优势

• 城市交通拥堵使传统卡车配送难以保障时效，特别在医疗物资等对时效要求高的场景。
• 无人机配送的优势在于不依赖道路基础设施、飞行速度高（约108–128 km/h）且能够规避地面干扰。
• 无人机受限于续航距离、载重和禁飞区，单独运作无法满足大规模城市配送需求。
• 结合卡车的载重与无人机的灵活性，可实现“高内聚、低耦合”的协同配送，成为城市智慧物流重要趋势。

1.2 时间依赖路况与混合路径问题

• 在动态路网中，卡车行驶时间与出发时刻相关，其旅行时间不再满足三角不等式，但满足FIFO特性。
• 研究采用扩展的流体排队模型近似道路排队过程，将拥堵期  划分为多个时段，并给出道路旅行时间函数  的近似表示，其中拥堵影响通过参数  调节。。
• 卡车‑无人机混合路径问题（TDHRP‑TDRTT）：每辆卡车携带一架无人机，从仓库出发在客户时间窗内完成配送，目标是最小化固定成本、道路拥堵成本及无人机协调成本。问题须决定无人机的起降节点与服务客户，兼顾车辆容量和无人机航程限制。

下图展示了重庆市不同时刻道路拥堵程度的变化，体现旅行时间的时间依赖性。

二、模型构建与基本假设

2.1 关键假设与变量

• 单车单机：每辆卡车最多携带一架无人机，车机需要在客户节点完成起降同步。
• 容量限制：卡车容量为 ，无人机容量为 ，部分客户因重量限制只能由卡车服务。
• 旅行时间函数：卡车在时段  行驶弧  的时间为 ，无人机采用欧氏距离  /飞行速度计算航行时间。
• 成本组成：包括卡车‑无人机对固定成本 、卡车单位行驶成本 、无人机单位行驶成本  以及卡车‑无人机在起降节点的协同成本 。

表 1定义了问题中的主要符号与含义。

2.2 成本最小化模型

模型以最小化总配送成本为目标，其简化的目标函数可表达为：

其中  表示卡车‑无人机对  在时段  选择弧 ， 表示无人机飞行路径的组合选择。约束条件要求车机容量满足、每个客户恰好被访问一次、特定客户仅由卡车服务、无人机起降点需由卡车访问、满足服务时间窗以及无人机航程限制等。

2.3 时变旅行时间与服务策略

• FIFO特性：若车辆在时间段较早出发，其到达时间不晚于晚出发车辆。
• 拥堵函数：拥堵期内的旅行时间  由多项式近似表示，与道路长度、拥堵比率及出发时刻相关。
• 无人机优势：无人机不受地面拥堵影响，可用于服务远离主路或道路严重拥堵的客户，在混合调度中发挥成本节约作用。

三、迭代局部搜索算法设计

3.1 总体流程

为求解上述模型，作者提出迭代局部搜索（ILS）。算法流程如图 2 所示，核心包含三个模块：时间窗预处理、初始解生成及局部搜索。

1. 时间窗预处理：删除不满足  的弧，构建初始可行弧集。
2. 生成初始车‑机路线：使用贪心算法基于时间依赖旅行时间构建仅卡车方案，然后通过两个策略将部分客户分配给无人机。
3. 局部搜索与2‑opt优化：通过在车机对内（intra‑pair）和车机对间（inter‑pair）执行节点移动与交换，不断改进路线；若一定迭代后无改进，则应用2‑opt算法对卡车路线进行连接优化。

3.2 初始解生成策略

• 策略 1 （节省式选择无人机节点）：在某条卡车路径  中，计算每个候选节点由卡车服务与由无人机服务的成本比 ，选取  最小的节点作为无人机服务对象，从而最大化节约成本。
• 策略 2 （贪婪选择降落点）：给定无人机起点  与服务客户 ，从可行降落点集合  中选择使“卡车行驶成本+无人机飞行成本”最小的节点作为降落点。
• 若两策略均无法找到可行降落点，则放弃当前节点，更新路径继续搜索。

3.3 局部搜索算子

3.3.1 Intra‑pair 局部搜索

图 3 展示了在同一车‑机对内的三种操作：随机移动一个节点、交换两车节点、以及交换车节点与无人机节点。这些操作可以调节车机分工，减小拥堵影响。

3.3.2 Inter‑pair 局部搜索

针对不同车‑机对之间随机选择两个父路径，交换各自的两个客户节点，若产生不可行解则通过重新选择降落点或调整载荷解决。此外通过交换某个路径中的无人机节点与另一路径的卡车节点并重新应用策略 1 和 2，可进一步增加解空间多样性。

3.3.3 2‑opt 优化

当局部搜索陷入停滞时，对卡车路线进行2‑opt操作：随机选择卡车路径中的四个节点，交换并重新连接，用最短路代替原有连接，去除低效“回路”，提升整体解质量。

四、实验设计与案例分析

4.1 算法性能评估

• 采用经典算例（如 C101、R101）调节算法参数，通过测试不同迭代次数及无改进循环阈值，发现设定最大迭代1000次即可在保证解质量的同时控制计算时间。
• 与 CPLEX、适应性大邻域搜索、混合遗传‑扫描算法和变邻域搜索等算法相比，本文 ILS 在小规模及基准实例上表现出更优的成本与计算效率，说明所提策略有效。

4.2 重庆市案例设定

• 使用百度地图获取重庆市实时路网的四类拥堵状态（畅通、缓慢、拥堵、严重拥堵），并随机生成 50 个客户的位置。各客户经纬度、需求及时间窗见论文表格。
• 卡车容量为300 件，无人机容量为30 件，最大飞行距离10 km，卡车最高速度50 km/h，无人机60 km/h。

下图示意了仓库与客户的空间分布：

4.3 路线与成本分析

图 5 显示了仅卡车方案（TDVRP）与卡车‑无人机方案（TDHRP‑TDRTT）的最优路线对比：三辆卡车分别服务 19、14 和 17 个客户，而在混合方案中有 13 个客户由无人机完成，减少了卡车行驶距离和拥堵暴露。

关键发现包括：

• 混合方案总成本为 ¥683，较仅卡车方案减少 ¥17；无人机相关成本占总成本的34.99%。
• 平均总服务时间缩短约16.1%，一些车‑机对可节省10–15 分钟。
• 随着道路拥堵加重，选择由无人机服务的客户数量由 15 增长至 20；无人机主要用于替代道路拥堵严重或与主路线偏离较大的客户。
• 在极端拥堵情形下，无人机仍需依赖卡车到达某些可起降节点后才能继续服务，反映出航程限制对调度的约束。

五、结论与研究贡献

1. 问题创新：本文提出在时变路网中考虑无人机与卡车协同的混合路径问题，建立了含时间依赖旅行时间的成本最小化模型，并证明了旅行时间函数的 FIFO 性质。
2. 算法贡献：设计了面向动态路网的迭代局部搜索框架，通过节省式与贪婪式策略生成初始混合路径，并结合车‑机对内外部局部搜索和2‑opt 优化，实现了高效求解。
3. 实证价值：在基准算例和重庆市实际路况测试中，卡车‑无人机方案明显降低了物流成本和服务时间。
4. 管理启示：当城市道路拥堵程度加重时，应增加无人机使用频率以规避拥堵；但应充分考虑无人机航程限制，合理设置起降节点及协同策略。

综上，本文为城市智慧物流提供了一种应对动态交通环境的新思路，未来可以进一步考虑多无人机协同、充电/换电策略以及实时交通信息更新对调度的影响。

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