2025年IEEE TSMCS，基于模因计算优化的无人机—卡车协同配送系统

目录1.摘要2.问题定义与研究背景3.MATSP-D 模因算法4.实验研究5.结论6.参考文献7.算法辅导·应用定制·读者交流1.摘要无人机载重与续航有限卡车可同时承担配送并作为移动起降平台但两类路径相互耦合传统卡车路径算法难以直接处理。本文把系统建模为带无人机旅行商问题 TSP-D提出模因算法 MATSP-D。算法以显式双层结构联合表示卡车与无人机路线通过 PMX-D 交叉开展全局探索再用变邻域搜索改进协作关系。多组基准实验表明MATSP-D 在多数实例上优于先进算法且在规模较大、无人机较快、协作更复杂时优势更明显。2.问题定义与研究背景TSP-D 给定仓库和N NN个客户由一辆卡车与一架无人机以最短总时间完成服务。每个客户仅由其中一种载具访问无人机从卡车所在节点起飞每次服务一个客户并在后续节点与卡车汇合若二者到达时间不同先到者必须等待。一次协同操作o ⟨ v s , v e , v f , v t ⟩ o\langle v_s,v_e,v_f,v_t\rangleo⟨vs​,ve​,vf​,vt​⟩包含起点v s v_svs​、终点v e v_eve​、可选无人机客户v f v_fvf​和卡车访问序列v t v_tvt​。卡车与无人机并行执行因此操作成本取两条支路耗时较大值c ( o ) max ⁡ { c t r u c k ( v s , v t , v e ) , c d ( v s , v f ) c d ( v f , v e ) } c(o)\max\left\{c_{\mathrm{truck}}(v_s,v_t,v_e),\ c_d(v_s,v_f)c_d(v_f,v_e)\right\}c(o)max{ctruck​(vs​,vt​,ve​),cd​(vs​,vf​)cd​(vf​,ve​)}模型从所有可行操作集合O OO中选取连续闭合路线目标函数min ⁡ ∑ o ∈ O c o x o \min \sum_{o\in O}c_o x_omino∈O∑​co​xo​约束保证每个节点至少访问一次、操作前后流量守恒、路线从仓库出发并返回且不存在孤立子环。精确算法仅适合小规模实例现有启发式多先求卡车路线再分配无人机客户或分别优化两条路线难以发现复杂协作下的优质解。3.MATSP-D 模因算法MATSP-D 先初始化种群每代通过二元锦标赛选择父代以 PMX-D 生成子代并按概率执行局部搜索。与父代适应度重复的个体被过滤父代与新个体合并后保留成本最低者。算法采用双层个体表示S ( N S , S V ) , S V d ∈ { T , I , F } S(NS,SV),\qquad SV_d\in\{T,I,F\}S(NS,SV),SVd​∈{T,I,F}N S NSNS是包含首尾仓库的节点访问序列S V SVSV是等长状态向量。T TT表示卡车服务且无人机在车上可作为起降或汇合节点I II表示无人机飞行期间由卡车访问的内部节点F FF表示无人机服务节点。相邻两个T TT之间构成一次协同操作。初始化以优化器产生的高质量 TSP 路线作为一个种子其余个体随机生成并先令全部状态为T TT从可行的纯卡车方案开始。适应度评价依次扫描节点序列和状态向量识别各协同操作并累加其并行执行成本。PMX-D 在父代的节点序列和状态向量上使用同一交叉点。节点序列按部分映射交叉处理重复与缺失客户状态向量随后修复非法内部节点及同一操作内的多无人机客户使子代保持可行。该算子能同时改变卡车路线和无人机服务结构。局部开发采用 VNS 与 VND。传统 Insert、2-opt 和 Swap 调整访问顺序Drone-Move、Drone-Insert 和 Drone-Delete 直接改变无人机客户、起降点及无人机任务数量。算子定义的邻域为N o p ( S ) { S ′ ∣ S ′ o p ( S ) } N_{op}(S)\left\{S\mid Sop(S)\right\}Nop​(S){S′∣S′op(S)}VNS 在当前邻域随机扰动后调用 VND 搜索最佳改进若得到更优解便返回第一个邻域否则继续下一邻域。增量评价只重算受操作影响的路线连接降低局部搜索成本。4.实验研究实验包含三个数据集。小规模数据含 10–12 个客户并用 CPLEX 最优解验证精度第一组大规模数据含 270 个实例覆盖 50、75、100 个客户均匀、单中心、双中心分布及三种无人机相对速度第二组包含更复杂的协作实例。对比方法包括精确划分、贪心划分、TSP-MC、HGVNS 与 HGA。小规模实例中MATSP-D 在 30 个实例中的 22 个达到最优平均最优差距仅0.1 % 0.1\%0.1%运行时间始终少于 10 秒CPLEX 随规模增长可超过 2 小时。大规模实例采用相对成本差距G a p c o s t M A T S P − D − c o s t o t h e r c o s t o t h e r Gap\frac{cost_{\mathrm{MATSP-D}}-cost_{\mathrm{other}}}{cost_{\mathrm{other}}}Gapcostother​costMATSP−D​−costother​​MATSP-D 对各基线的平均差距均为负。相对表现第二的 TSP-EP当无人机与卡车等速、速度为两倍和三倍时平均差距分别为− 0.11 % -0.11\%−0.11%、− 1.64 % -1.64\%−1.64%和− 4.38 % -4.38\%−4.38%。无人机越快最优方案使用无人机越频繁路径耦合越强MATSP-D 的联合搜索优势越明显。5.结论MATSP-D 通过显式双层表示、PMX-D 交叉和六邻域局部搜索同时优化卡车路线、无人机客户及起降关系。实验验证其在协作复杂的大规模实例上具有稳定优势尤其适用于无人机速度至少为卡车两倍的场景。6.参考文献Zhai R, Mei Y, Guo T, Du W. A Collaborative Drone-Truck Delivery System With Memetic Computing Optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2024, 54(6): 3618-3628.7.算法辅导·应用定制·读者交流xx