混合蛙跳算法求解车辆无人机协同配送问题

doi:10.3785/j.issn.1008-973X.2024.11.007

浙江大学学报(工学版)

2024, Vol. 58

Issue (11): 2258-2269 DOI: 10.3785/j.issn.1008-973X.2024.11.007

计算机技术、控制工程

混合蛙跳算法求解车辆无人机协同配送问题

段浩浩(

),李晓玲*(

),路庆昌,林杉

长安大学电子与控制工程学院，陕西西安 710064

Hybrid shuffled frog leaping algorithm for solving vehicle-dronecooperative delivery problem

Haohao DUAN(

),Xiaoling LI*(

),Qingchang LU,Shan LIN

School of Electronics and Control Engineering, Chang’an University, Xi’an 710064, China

全文: PDF(928 KB) HTML

摘要：

为了充分发挥无人机与车辆各自的优势，研究无人机起飞后可服务多个客户的车辆-无人机协同配送问题，其中考虑了车辆因区域限制、无人机因载重和续航限制导致2类运输工具配送范围均受到限制的约束. 针对这类运输工具配送受限的车辆-多投递无人机协同配送问题(MDVCP-DR)，以最小化总配送时间为优化目标，建立对应的数学模型，提出混合蛙跳算法(HSFLA)进行求解. 提出新的编码与预调整解码方法，得到满足各种约束的可行解. 建立基于4种交叉算子和精英表的个体生成方法，更新种群中的个体. 设计自适应局部搜索策略来增强算法的局部开发能力，通过种群多样性检测策略来保证个体的多样性. 通过仿真实验，验证了建立的数学模型的正确性和HSFLA的有效性.

关键词： 车辆-无人机; 协同配送; 配送限制; 蛙跳算法; 路径优化

Abstract:

The vehicle-drone cooperative delivery problem was analyzed where a drone could service multiple customers after takeoff in order to fully utilize the respective advantages of drones and vehicles. The considered constraints include regional restrictions for vehicles and delivery range limitations due to the loading and endurance capabilities of the drone. A mathematical model of the problem was established to minimize the total delivery time, and a hybrid shuffled frog leaping algorithm (HSFLA) was proposed to solve it aiming at the multi-drop vehicle-drone cooperative problem with delivery restrictions (MDVCP-DR). A novel encoding and pre-adjusted decoding method was proposed to obtain feasible solutions so that the constraints involved in the problem can be satisfied. Then an individual generation method was developed to update individuals in the population based on four crossover operators and an elite list. An adaptive local search strategy was imbedded into the algorithm in order to enhance the local exploitation ability of HSFLA. A population diversity detection strategy was used to ensure the diversity of individuals in the population. Simulation experiments demonstrated the accuracy of the established mathematical model and the effectiveness of HSFLA.

Key words: vehicle-drone cooperative delivery delivery restriction shuffled frog leaping algorithm routing optimization

收稿日期: 2023-10-08 出版日期: 2024-10-23

CLC:

TP 18

基金资助: 国家自然科学基金资助项目（62103062, 71971029）；长安大学中央高校基本科研业务费专项资金资助项目（300102322101）.

通讯作者: 李晓玲 E-mail: 2022132066@chd.edu.cn;xiaolingli@chd.edu.cn

作者简介: 段浩浩（1999—），男，硕士生，从事车辆路径优化的研究. orcid.org/0009-0009-5535-0503. E-mail：2022132066@chd.edu.cn

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	作者相关文章
	段浩浩
	李晓玲
	路庆昌
	林杉

引用本文:

段浩浩,李晓玲,路庆昌,林杉. 混合蛙跳算法求解车辆无人机协同配送问题[J]. 浙江大学学报(工学版), 2024, 58(11): 2258-2269.

Haohao DUAN,Xiaoling LI,Qingchang LU,Shan LIN. Hybrid shuffled frog leaping algorithm for solving vehicle-dronecooperative delivery problem. Journal of ZheJiang University (Engineering Science), 2024, 58(11): 2258-2269.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2024.11.007 或 https://www.zjujournals.com/eng/CN/Y2024/V58/I11/2258

图 1 车辆-无人机协同配送的示意图

图 2 η和θ类路径的示意图

输入: 待解码个体X = {x₁, x₂, …, x_n}输出: 可行解B = (ID, NA)

1: 初始化: i = 0, k = 1, td = 0, td′ = 0, seq = ?, seq_u = ?, seq_t = ?, N_temp = ?, flag = 0, flag_UF = 0, flag_Nu = 0;令ID = {id₀, id₁

$, \cdots , $

id_n+1} = {0, x₁, x₂

$, \cdots , $

x_n, 0}.2: while(i < |ID|){/*|ID|表示ID中元素个数*/3:　if(id_i∈N_u){将id_i插入seq的末端, i = i+1, flag_Nu = 1, N_temp = ?;} 4:　else{5:　　将id_i插入seq的末端, i = i+1; 6:　　if(|seq| = 2){seq_u := seq, seq_t := seq, C_k^t:= seq, td = abs (t_k^u?t_k^t);}/*|seq|表示seq中的元素个数, abs表示绝对值*/7:　　if(|seq| > 2){ 8:　　　if(flag_UF = 0){/*执行无人机优先配送原则*/9:　　　　seq_u := seq, seq_t := seq; 保留seq_t中第一个和最后一个元素, 其余置?1; seq_u中的配送序列满足无人机载重和续航约束，则flag =0, 否则flag = 1; td′ = abs (t_k^u?t_k^t); /*?1表示无客户*/10:　　　if(flag = 0){11:　　　　C_k^t:= seq_t, C_k^u:= seq_u, td = abs (t_k^u?t_k^t);12:　　　　if(flag_Nu = 1){N_temp := N_temp∪{id_i};}13:　　　　if(|N_temp| ≥ 2){flag_Nu = 0;}/*seq_u中最后一个n_u∈N_u之后分配了2个以上满足n_a∈N₁的客户*/14:　　　else{15:　　　　if(flag_Nu = 1){保存C_k^t和C_k^u, k = k+1; flag_Nu = 0; 在ID中找到C_k^t和C_k^u中最后一个元素的位置, 记作i′; i := i′; seq := {id_i};}/*出现了必须由无人机服务的客户, 则当前子配送路径划分结束*/16:　　　　else{/*flag = 1且flag_Nu = 0, 尝试将无人机最后配送的客户分配给车辆*/17:　　　　　seq_t中倒数第2个点与seq_u中倒数第2个点交换; 若seq_u中的配送序列满足无人机载重和续航约束则flag = 0, 否则flag = 1; td′ = abs(t_k^u?t_k^t);18:　　　　　if(flag = 0 & (td′< td)){C_k^t:= seq_t, C_k^u:= seq_u; flag_UF = 1; td = td′;}/*通过将客户分配给车辆得到满足约束的路径, 则中止无人机优先配送的规则*/19:　　　　　else{保存C_k^t和C_k^u, k = k+1; 在ID中找到C_k^t和C_k^u中最后一个元素的位置, 记作i′; i := i′; seq :={id_i};}}20:　　　}/*end if-else(flag = 0)*/ }21:　　else{/*flag_UF = 1, 基于子配送路径中车辆与无人机路径耗时尽可能相近的原则，更改无人机的降落点并增加车辆服务的客户*/22:　　　if(flag_Nu = 1){保存C_k^t和C_k^u, k = k+1; flag_Nu = 0, flag_UF = 0; 在ID中找到C_k^t和C_k^u中最后一个元素的位置, 记作i′; i := i′; seq:= {id_i};} 23:　　　else{24:　　　　seq_u最后一个元素置?1, 将seq最后一个元素分别添加到seq_u和seq_t末端; 若seq_u中的配送序列满足无人机载重和续航约束，则flag = 0, 否则flag = 1; td′ = abs (t_k^u?t_k^t); 25:　　　　if(flag = 0 & td′< td){C_k^t:= seq_t, C_k^u:= seq_u; td = td′;}26:　　　　else{保存C_k^t和C_k^u, k = k+1; 在ID中找到C_k^t和C_k^u中最后一个元素的位置, 记作i′; i:= i′; seq:={id_i}; flag_UF = 0;}}27:　　}/*end if-else(flag_UF = 0)*/28:　}/*end if(|seq| > 2)*/29:}}/*end while*/30: 根据C_k^t和C_k^u(k∈K)可得ID对应的配送属性序列NA, 其中当id_i为共同访问点时na_i = 0, id_i由车辆配送时na_i = 1, id_i由无人机配送时na_i = 2.End

图 3 不同的OX操作

图 4 不同的邻域结构

图 5 HSFLA算法的流程图

表 1 客户、车辆和无人机的参数设置

表 2 HSFLA算法的参数设置

表 3 正交表L9(34)

表 4 Gurobi和HSFLA算法的仿真结果

表 5 消融实验的仿真结果

表 6 对比算法的参数设置

表 7 当Lm = 5 kg, Ltime = 0.5 h时不同算法的仿真结果

表 8 不同无人机参数下算法在算例FP08上的结果

图 6 不同算法的对比

1	MURRAY C C, CHU A G The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery[J]. Transportation Research Part C: Emerging Technologies, 2015, 54: 86- 109 doi: 10.1016/j.trc.2015.03.005
2	GRIFFITH E F, SCHURER J M, MAWINDO B, et al The use of drones to deliver rift valley fever vaccines in rwanda: perceptions and recommendations[J]. Vaccines, 2023, 11 (3): 605 doi: 10.3390/vaccines11030605
3	WEN X P, WU G H Heterogeneous multi-drone routing problem for parcel delivery[J]. Transportation Research Part C: Emerging Technologies, 2022, 141: 103763 doi: 10.1016/j.trc.2022.103763
4	AGATZ N, BOUMAN P, SCHMIDT M Optimization approaches for the traveling salesman problem with drone[J]. Transportation Science, 2018, 52 (4): 965- 981 doi: 10.1287/trsc.2017.0791
5	GONZALEZ-R P L, CANCA D, ANDRADE-PINEDA J L, et al Truck-drone team logistics: a heuristic approach to multi-drop route planning[J]. Transportation Research Part C: Emerging Technologies, 2020, 114: 657- 680 doi: 10.1016/j.trc.2020.02.030
6	柳伍生, 李旺, 周清, 等 “无人机-车辆”配送路径优化模型与算法[J]. 交通运输系统工程与信息, 2021, 21 (6): 176- 186 LIU Wusheng, LI Wang, ZHOU Qing, et al “Drone-Vehicle” distribution routing optimization model[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21 (6): 176- 186
7	LUO Z H, POON M, ZHANG Z Z, et al The multi-visit traveling salesman problem with multi-drones[J]. Transportation Research Part C: Emerging Technologies, 2021, 128: 103172 doi: 10.1016/j.trc.2021.103172
8	伍国华, 毛妮, 徐彬杰, 等基于自适应大规模邻域搜索算法的多车辆与多无人机协同配送方法[J]. 控制与决策, 2023, 38 (1): 201- 210 WU Guohua, MAO Ni, XU Binjie, et al The cooperative delivery of multiple vehicles and multiple drones based on adaptive large neighborhood search[J]. Control and Decision, 2023, 38 (1): 201- 210
9	GU R X, POON M, LUO Z H, et al A hierarchical solution evaluation method and a hybrid algorithm for the vehicle routing problem with drones and multiple visits[J]. Transportation Research Part C: Emerging Technologies, 2022, 141: 103733 doi: 10.1016/j.trc.2022.103733
10	MARA S T W, RIFAI A P, SOPHA B M An adaptive large neighborhood search heuristic for the flying sidekick traveling salesman problem with multiple drops[J]. Expert Systems with Applications, 2022, 205: 117647 doi: 10.1016/j.eswa.2022.117647
11	杜茂康, 罗娟, 李博文基于多车场的车载无人机协同配送路径优化[J]. 系统工程, 2021, 39 (6): 90- 98 DU Maokang, LUO Juan, LI Bowen Research on cooperative delivery route optimization of vehicle-carried drones based on multi-depot[J]. Systems Engineering, 2021, 39 (6): 90- 98
12	范厚明, 张跃光, 田攀俊时变路网下多中心电动车-无人机协同配送路径优化[J]. 管理工程学报, 2023, 37 (2): 131- 142 FAN Houming, ZHANG Yueguang, TIAN Panjun Multi-depot electric vehicle routing problem with drones under time-dependent networks[J]. Journal of Industrial Engineering and Engineering Management, 2023, 37 (2): 131- 142
13	吴廷映, 陶新月, 孟婷 “卡车+无人机”模式下带时间窗的取送货车辆路径问题[J]. 计算机集成制造系统, 2023, 29 (7): 2440- 2448 WU Tingying, TAO Xinyue, MENG Ting Pickup and delivery problem with time windows in mode of “truck +drone”[J]. Computer Integrated Manufacturing Systems, 2023, 29 (7): 2440- 2448
14	DAS D N, SEWANI R, WANG J W, et al Synchronized truck and drone routing in package delivery logistics[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 22 (9): 5772- 5782
15	KUO R J, LU S H, LAI P Y, et al Vehicle routing problem with drones considering time windows[J]. Expert Systems with Applications, 2022, 191: 116264 doi: 10.1016/j.eswa.2021.116264
16	LUO Q Z, WU G H, JI B, et al Hybrid multi-objective optimization approach with pareto local search for collaborative truck-drone routing problems considering flexible time windows[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 23 (8): 13011- 13025
17	彭勇, 黎元钧考虑疫情影响的卡车无人机协同配送路径优化[J]. 中国公路学报, 2020, 33 (11): 73- 82 PENG Yong, LI Yuanjun Optimization of truck-drone collaborative distribution route considering impact of epidemic[J]. China Journal of Highway and Transport, 2020, 33 (11): 73- 82
18	颜瑞, 陈立双, 朱晓宁, 等考虑区域限制的卡车搭载无人机车辆路径问题研究[J]. 中国管理科学, 2022, 30 (5): 144- 155 YAN Rui, CHEN Lishuang, ZHU Xiaoning, et al Research on vehicle routing problem with truck and drone considering regional restriction[J]. Chinese Journal of Management Science, 2022, 30 (5): 144- 155
19	EUSUFF M, LANSEY K, PASHA F Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization[J]. Engineering Optimization, 2006, 38 (2): 129- 154 doi: 10.1080/03052150500384759

[1]	鲁建厦,翟文倩,李嘉丰,易文超,汤洪涛. 基于改进混合蛙跳算法的多约束车辆路径优化[J]. 浙江大学学报(工学版), 2021, 55(2): 259-270.
[2]	艾小祥,俞慈君,方强,陈磊,方伟,沈立恒. 基于遗传算法的机翼壁板扫描路径优化[J]. 浙江大学学报(工学版), 2015, 49(3): 448-456.
[3]	张维泽林剑波吴洪森童若锋董金祥. 基于改进蚁群算法的物流配送路径优化[J]. J4, 2008, 42(4): 574-578.
[4]	俞武嘉傅建中陈子辰. 基于遗传算法的刀具路径优化排布方法[J]. J4, 2006, 40(12): 2117-2121.

Viewed

Full text

Abstract

Cited

Shared

Discussed