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

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

Journal of ZheJiang University (Engineering Science)

2024, Vol. 58

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

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

Download:

HTML

PDF(928KB) HTML
Export: BibTeX | EndNote (RIS)

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

Received: 08 October 2023 Published: 23 October 2024

CLC:	TP 18
	U 15

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

Corresponding Authors: Xiaoling LI E-mail: 2022132066@chd.edu.cn;xiaolingli@chd.edu.cn

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Haohao DUAN
	Xiaoling LI
	Qingchang LU
	Shan LIN

Cite this article:

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.

URL:

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

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

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

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

Fig.1 Diagram of vehicle-drone cooperative distribution

Fig.2 Illustration of η and θ paths

输入: 待解码个体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

Fig.3 Different OX operations

Fig.4 Different neighborhood structure

Fig.5 Flowchart of HSFLA

Tab.1 Parameter setting of customer, vehicle and drone

Tab.2 Parameter settings of HSFLA

Tab.3 Orthogonal table L₉(3⁴)

Tab.4 Simulation results of Gurobi and HSFLA

Tab.5 Simulation result of ablation study

Tab.6 Parameter setting of comparison algorithm

Tab.7 Simulation result of different algorithm with L_m = 5 kg, L_time = 0.5 h

Tab.8 Result of different algorithm on FP08 under different drone parameter

Fig.6 Comparison of different algorithm


[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]	Jian-sha LU,Wen-qian ZHAI,Jia-feng LI,Wen-chao YI,Hong-tao TANG. Multi-constrained vehicle routing optimization based on improved hybrid shuffled frog leaping algorithm[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(2): 259-270.

Viewed

Full text

Abstract

Cited

Shared

Discussed