2024年IEEE TITS SCI2区TOP，考虑无人机能耗与时间窗的卡车–无人机协同路径规划，深度解析+性能实测-深圳市維司達科技有限公司

1.摘要

在考虑客户时间窗的条件下，本文研究多卡车–多次访问无人机协同配送问题，综合建模无人机能耗及载重变化对能耗率的影响。通过MILP模型刻画问题，引入Segment概念强化卡车与无人机协同，并设计同步构建卡车与无人机路径的启发式算法，结合变邻域搜索与模拟退火提升解的质量，最终通过Solomon算例与实际案例验证算法有效性。

2.问题描述

本文对带时间窗的卡车–多次访问无人机协同路径问题（VRPTW-MD）进行建模，在有向图上刻画卡车与无人机协同配送过程。卡车与无人机均可服务客户且每个客户仅被访问一次，需满足时间窗、载重及无人机续航与能耗约束。模型明确了无人机起降、回收与等待规则，并在车辆同构、卡车续航不受限等假设下，系统描述了协同配送的运行机制。

在满足约束的前提下同时最小化配送总时长、最大单车配送时长及启用的协同配送系统数量：
min ⁡ λ 1 × ∑ k ∈ K ( t k R − t k L ) + λ 2 × max ⁡ k ∈ K { ( t k R − t k L ) } + λ 3 × ∑ k ∈ K ∑ j ∈ N y 0 j k \begin{aligned}\min\lambda_{1}\times\sum_{k\in K}(t_{k}^{R}-t_{k}^{L})+\lambda_{2}\times\max_{k\in K}\{(t_{k}^{R}-t_{k}^{L})\}+\lambda_{3}\times\sum_{k\in K}\sum_{j\in N}y_{0jk}\end{aligned}minλ1×k∈K∑(tkR−tkL)+λ2×k∈Kmax{(tkR−tkL)}+λ3×k∈K∑j∈N∑y0jk

其中，λ 1 \lambda_1λ1用于衡量总配送时间的权重，λ 2 \lambda_2λ2表示卡车之间工作负载均衡的重要性，λ 3 \lambda_3λ3表示协同
配送系统的使用成本。

3.提出的算法

分段定义

针对传统两阶段启发式在时间窗约束下协同效果不足的问题，本文提出基于 Segment 概念的构造型启发式方法，并结合变邻域搜索与模拟退火提升解的质量。
其中，Segment 以无人机起降/回收节点为划分点，将协同路径拆分为两类：包含完整无人机航程的协同段和仅由卡车行驶的纯卡车段，从而将复杂的卡车–无人机协同路径转化为多个 Segment 的线性组合，便于高效构建与优化。

基于分段的启发式算法

基于 Segment 的启发式算法（HBS）在仍存在未服务客户时持续生成新路线，并优先构建卡车与无人机同步服务的协同段。算法通过四个核心步骤实现：首先在不考虑回收的情况下构造无人机路径，使无人机尽可能多地服务客户；随后在满足无人机续航与时间窗约束的前提下，寻找合适的回收节点并同步生成对应的卡车路径，形成协同段；若协同失败，则构造仅由卡车运输并携带无人机的纯卡车段；最后对各段及整条路线的出发时间进行调整，以减少等待并缩短总配送时间。

模拟退火的可变邻域搜索

为进一步提升 HBS 初始解的质量，本文提出融合模拟退火的变邻域搜索算法，并设计了三类针对 VRPTW-MD 特性的邻域算子，所有新解均通过快速可行性检验以确保满足时间窗与协同约束。1）Segment 拆分算子：针对初始解中部分路线时长过长的问题，对长路线或随机路线进行拆分，通过调整协同段与纯卡车段的起点与服务方式，生成更均衡的多条路线。2）交换算子：根据节点类型（卡车/无人机）及所属 Segment 的不同，设计多种交换方式，在保证可行性的前提下减少段内时间消耗并扩大搜索范围。
3）删除–插入算子：随机移除节点以增强解的多样性，并通过多种插入策略（卡车、无人机或新增车辆）重新安置客户，选择时间成本最小的方案。

4.结果展示

5.参考文献

[1] Liu Y, Shi J, Luo Z, et al. Cooperated truck-drone routing with drone energy consumption and time windows[J]. IEEE Transactions on Intelligent Transportation Systems, 2024.