城市区域多物流无人机协同任务分配

doi:10.12305/j.issn.1001-506X.2021.12.22

Abstract

Abstract:

To solve the problem of multiple unmanned aerial vehicle (UAV) collaborative logistics task allocation in urban areas, a collaborative logistics task allocation model for multiple UAVs is constructed with the objective function of minimizing economic cost, time penalty and safety risk by comprehensively considering the factors of different UAVs'performance, logistics timeliness and flight reliability. Because of the large scale and high complexity of task allocation, an improved quantum particle swarm optimization algorithm is designed to solve the problem. Firstly, in order to enhance the ergodicity and diversity of particles, particle initialization is carried out by homogenization cascade Logistic mapping. Then, in order to improve the search ability of particles and speed up the running efficiency of the algorithm, particle mutation method based on Gaussian distribution is introduced. Finally, in order to improve the efficiency of the algorithm, adaptive inertia weight method is used to assign different values to each particle. Simulation results show that the constructed model can achieve multi-objective optimization of task allocation. It is close to the reality of UAV logistics distribution in urban areas. Compared with the traditional quantum particle swarm optimization algorithm and the genetic algorithm, the task allocation cost of the improved algorithm is reduced by 5.9% and 6.3% respectively. Furthermore, the parameter weight setting is also analyzed in this paper. When the weight coefficients of the three sub objective functions are 0.225, 0.275 and 0.500 respectively and the population size is 150, the task allocation scheme planned by this algorithm is optimal.

Key words: logistics unmanned aerial vehicle (UAV), task allocation, improved quantum particle swarm optimization algorithm, Gaussian distribution, adaptive inertia weight

CLC Number:

V279.3

Han LI, Honghai ZHANG, Liandong ZHANG, Hao LIU. Multiple logistics unmanned aerial vehicle collaborative task allocation in urban areas[J]. Systems Engineering and Electronics, 2021, 43(12): 3594-3602.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Table 1

Fig.5

Table 2

Table 3

Table 4

Table 5

Fig.6

Table 6

Fig.7

Table 7

Fig.8

References 31

1	SHE R F , OUYANG Y F . Efficiency of UAV-based last-mile delivery under congestion in low-altitude air[J]. Transportation Research Part C: Emerging Technologies, 2021, 122, 102878. doi: 10.1016/j.trc.2020.102878
2	KURU K , ANSELL D , KHAN W , et al. Analysis and optimization of unmanned aerial vehicle swarms in logistics: an intelligent delivery platform[J]. IEEE Access, 2019, 7, 15804- 15831. doi: 10.1109/ACCESS.2019.2892716
3	KIM M H , BAIK H , LEE S . Response threshold model based UAV search planning and task allocation[J]. Journal of Intelligent & Robotic Systems, 2014, 75 (3, 4): 625- 640.
4	ZHANG L , ZHU Y A , SHI X C . A hierarchical decision-making method with a fuzzy ant colony algorithm for mission planning of multiple UAVS[J]. Information, 2020, 11 (4): 226. doi: 10.3390/info11040226
5	HUANG T Y, WANG Y, CAO X W, et al. Multi-UAV mission planning method[C]//Proc. of the 3rd International Conference on Unmanned Systems, 2020: 325-330.
6	LIU X F , PENG Z R , CHANG Y T , et al. Multi-objective evolutionary approach for UAV cruise route planning to collect traffic information[J]. Journal of Central South University, 2012, 19 (12): 3614- 3621. doi: 10.1007/s11771-012-1449-8
7	赵雪森, 王社伟, 邵校. 基于改进量子粒子群优化算法的多UCAV协同任务分配研究[J]. 兵器装备工程学报, 2015, 36 (10): 120- 124. doi: 10.11809/scbgxb2015.10.030
	ZHAO X S , WANG S W , SHAO X . Cooperative task allocation for multiple UCAV based on improved quantum-behaved particle swarm optimization algorithm[J]. Journal of Ordnance Equipment Engineering, 2015, 36 (10): 120- 124. doi: 10.11809/scbgxb2015.10.030
8	ZHANG Y Z, HU B, LI J W, et al. Heterogeneous multi-UAVs cooperative task assignment based on GSA-GA[C]//Proc. of the IEEE/CSAA International Conference on Aircraft Utility Systems, 2016: 423-426.
9	FU Z J , MAO Y H , HE D J , et al. Secure multi-UAV collaborative task allocation[J]. IEEE Access, 2019, 7, 35579- 35587. doi: 10.1109/ACCESS.2019.2902221
10	蒋硕, 袁小平. 改进PSO算法在多无人机协同任务分配中的应用[J]. 计算机应用研究, 2019, 36 (11): 3344- 3347, 3360.
	JIANG S , YUAN X P . Application of improved PSO algorithm in multi UAV cooperative task allocation[J]. Application Research of Computers, 2019, 36 (11): 3344- 3347, 3360.
11	林君灿, 贾高伟, 侯中喜. 异构UAV编队反雷达作战中任务分配方法[J]. 系统工程与电子技术, 2018, 40 (9): 1986- 1992.
	LIN J C , JIA G W , HOU Z X . Research on task assignment of heterogeneous UAV formation in the anti-radar combat[J]. Systems Engineering and Electronics, 2018, 40 (9): 1986- 1992.
12	ZHU S R, ZHANG Y Z, GAO Y, et al. A cooperative task assignment method of multi-UAV based on self organizing map[C]// Proc. of the International Conference on Cyber-Enabled Distri-buted Computing and Knowledge Discovery, 2018: 437-442.
13	YAO W R , QI N M , WAN N , et al. An iterative strategy for task assignment and path planning of distributed multiple unmanned aerial vehicles[J]. Aerospace Science and Technology, 2019, 86, 455- 464. doi: 10.1016/j.ast.2019.01.061
14	SONG B D , PARK K , KIM J . Persistent UAV delivery logistics: MILP formulation and efficient heuristic[J]. Computers & Industrial Engineering, 2018, 120, 418- 428.
15	JIANG X W, ZHOU Q, YE Y. Method of task assignment for UAV based on particle swarm optimization in logistics[C]//Proc. of the International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, 2017: 113-117.
16	SHIRANI B , NAJAFI M , IZADI I . Cooperative load transportation using multiple UAVs[J]. Aerospace Science and Technology, 2019, 84, 158- 169. doi: 10.1016/j.ast.2018.10.027
17	FU X W, PAN J, GAO X G, et al. Task allocation method for multi-UAV teams with limited communication bandwidth[C]//Proc. of the 15th International Conference on Control, Automation, Robotics and Vision, 2018: 1874-1878.
18	SAMIEI A, ISMAIL S, SUN L. Cluster-based hungarian approach to task allocation for unmanned aerial vehicles[C]//Proc. of the IEEE National Aerospace and Electronics Conference, 2019: 148-154.
19	林君灿, 贾高伟, 侯中喜. 异构UAV编队反雷达作战中任务分配方法[J]. 系统工程与电子技术, 2018, 40 (9): 1986- 1992.
	LIN J C , JIA G W , HOU Z X . Research on task assignment of heterogeneous UAV formation in the anti-radar combat[J]. Systems Engineering and Electronics, 2018, 40 (9): 1986- 1992.
20	YE F , CHEN J , TIAN Y , et al. Cooperative multiple task assignment of heterogeneous UAVs using a modified genetic algorithm with multi-type-gene chromosome encoding strategy[J]. Journal of Intelligent & Robotic Systems, 2020, 100 (2): 615- 627.
21	NI J J , TANG M , CHEN Y N , et al. An improved cooperative control method for hybrid unmanned aerial-ground system in multitasks[J]. International Journal of Aerospace Engineering, 2020, 2020, 9429108.
22	AMJAAD A , HEBA K , KAMAL Y . Fish-inspired task allocation algorithm for multiple unmanned aerial vehicles in search and rescue missions[J]. Remote Sensing, 2020, 13 (27): 27.
23	CHEN C , BAO W D , MEN T , et al. NECTAR—an agent-based dynamic task allocation algorithm in the UAV swarm[J]. Complexity, 2020, 6747985.
24	LIU W H , ZHENG X . Three-dimensional multi-mission planning of UAV using improved ant colony optimization algorithm based on the finite-time constraints[J]. International Journal of Computational Intelligence Systems, 2021, 14 (1): 79- 87.
25	CHEN X , LIU Y T , YIN L Y , et al. Cooperative task assignment and track planning for multi-UAV attack mobile targets[J]. Journal of Intelligent & Robotic Systems, 2020, 100 (3): 1383- 1400. doi: 10.1007/s10846-020-01241-w
26	SUN J, FENG B, XU W B. Particle swarm optimization with particles having quantum behavior[C]//Proc. of the Congress on Evolutionary Computation, 2004.
27	MASDARI M , SALEHI F , JALALI M , et al. A survey of PSO-based scheduling algorithms in cloud computing[J]. Journal of Network ＆ Systems Managenment, 2017, 25 (1): 122- 158. doi: 10.1007/s10922-016-9385-9
28	XU C F , DUAN H B , LIU F . Chaotic artificial bee colony approach to uninhabited combat air vehicle (UCAV) path plan- ning[J]. Aerospace Science and Technology, 2010, 14 (8): 535- 541. doi: 10.1016/j.ast.2010.04.008
29	ZHANG Z X , YANG R N , LI H Y , et al. Antlion optimizer algorithm based on chaos search and its application[J]. Journal of Systems Engineering and Electronics, 2019, 30 (2): 352- 365. doi: 10.21629/JSEE.2019.02.14
30	张庆. 基于改进型混沌映射的粒子群算法及其在天线参数优化中的应用[D]. 昆明: 云南大学, 2018.
	ZHANG Q. Based on improved chaos mapping particle swarm optimization algorithm and its application on optimization of antenna parameter[D]. Kunming: Yunnan University, 2018.
31	李继松. 自适应参数调整量子粒子群算法研究及应用[D]. 长沙: 中南大学, 2014.
	LI J S. Research and application on adaptive parameter adjusting quantum-behaved particle swarm optimization[D]. Changsha: Central South University, 2014.

无人机编号	c_{f_i}/(元/分钟)	η_i/(元/千米)	v_i/(m·s^-1)	L_i(max)/m	q_i(max)/ kg
U₁	0.30	0.25	10	6 000	4.5
U₂	0.30	0.30	12	4 500	5.0
U₃	0.30	0.20	12	4 000	3.5
U₄	0.30	0.22	15	4 200	5.0
U₅	0.30	0.26	14	4 500	4.0
U₆	0.30	0.24	13	4 700	6.0
U₇	0.30	0.20	11	5 000	4.5
U₈	0.30	0.27	15	4 300	5.5

任务编号	时间窗/s	坐标点/m	卸货时间/s	需货量/kg
T₁	[0, 100]	[75,475,50]	30	0.5
T₂	[0, 180]	[225,400,50]	60	1.0
T₃	[0, 200]	[1 000, 750, 60]	60	1.0
T₄	[0, 190]	[600,300,25]	96	1.6
T₅	[0, 300]	[800,275,25]	60	1.0
T₆	[0, 350]	[750,200,50]	90	1.5
T₇	[0, 220]	[1 100, 225, 50]	72	1.2
T₈	[0, 450]	[450, 750, 60]	108	1.8
T₉	[0, 400]	[1 200, 800, 25]	36	0.6
T₁₀	[0, 500]	[1 340, 800, 50]	90	1.5
T₁₁	[0, 370]	[300, 800, 50]	108	1.8
T₁₂	[0, 550]	[900, 600, 50]	96	1.6
T₁₃	[0, 420]	[275, 200, 30]	84	1.4
T₁₄	[0, 520]	[1 050, 125, 20]	72	1.2
T₁₅	[0, 600]	[500, 225, 40]	90	1.5
T₁₆	[0, 530]	[175,825,60]	102	1.7
T₁₇	[0.560]	[270,600,60]	54	0.9
T₁₈	[0, 230]	[900,400,10]	48	0.8
T₁₉	[0, 460]	[1 200, 550, 40]	72	1.2
T₂₀	[0, 570]	[1 075, 425, 30]	66	1.1

参数	数值	参数	数值
时间损失系数λ	10	经济成本α₁	0.3
延迟惩罚α₂	0.3	安全风险α₃	0.4
配送中心坐标	[125, 100, 25]	出发时间t₀	0
种群规模Q	50	迭代次数t_max	200
惯性权重上界β_max	1.0	惯性权重下界β_min	0.5
Logistic参数μ	4	高斯分布预设参数ε	1.0

算法名称	目标函数值	经济成本	延迟惩罚	安全风险
QPSO	0.145 5	0.222 5	0.104 0	0.118 9
IQPSO	0.136 9	0.220 9	0.082 5	0.114 8
遗传算法	0.146 1	0.199 6	0.020 1	0.200 4

编号	配送顺序	航程/m	飞行时长/s	载货量/kg
U₁	0－T₃－T₁₉－T₁₈－T₁₇－0	2 896	524	3.9
U₂	0－T₁₃－T₁₅－T₄－0	1 048	357	4.5
U₃	0－T₂－T₁－T₁₆－0	1 577	323	3.2
U₄	0－T₁₂－T₁₀－T₉－T₁₄－0	3 165	505	4.9
U₅	0－T₅－T₆－0	1 424	252	2.5
U₆	0－T₁₁－T₈－0	1 608	340	3.6
U₈	0－T₇－T₂₀－0	2 190	284	2.3

Multiple logistics unmanned aerial vehicle collaborative task allocation in urban areas

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 31

Related Articles 14

Recommended Articles

Metrics

Comments

序号	α₁权重	α₂权重	α₃权重	经济成本	延迟惩罚	安全风险	算法时长/s
1	0.000	0.500	0.500	0.276 1	0.053 5	0.122 9	12.81
2	0.025	0.475	0.500	0.285 1	0.054 1	0.124 4	13.67
3	0.050	0.450	0.500	0.281 3	0.051 2	0.122 3	13.86
4	0.075	0.425	0.500	0.260 5	0.063 0	0.113 8	13.83
5	0.100	0.400	0.500	0.267 3	0.057 0	0.117 3	13.78
6	0.125	0.375	0.500	0.260 1	0.069 8	0.111 6	13.62
7	0.150	0.350	0.500	0.242 0	0.098 1	0.114 7	13.22
8	0.175	0.325	0.500	0.252 2	0.076 7	0.103 1	13.90
9	0.200	0.300	0.500	0.239 8	0.093 1	0.110 5	13.76
10	0.225	0.275	0.500	0.232 7	0.087 4	0.106 2	13.79
11	0.250	0.250	0.500	0.250 2	0.103 4	0.110 5	13.89
12	0.275	0.225	0.500	0.234 1	0.114 5	0.110 9	13.72
13	0.300	0.200	0.500	0.222 4	0.124 6	0.102 8	14.00
14	0.325	0.175	0.500	0.221 3	0.114 3	0.101 4	13.87
15	0.350	0.150	0.500	0.220 0	0.149 2	0.089 7	13.64
16	0.375	0.125	0.500	0.213 2	0.150 8	0.099 7	13.85
17	0.400	0.100	0.500	0.203 9	0.159 7	0.096 1	13.95
18	0.425	0.075	0.500	0.201 6	0.170 3	0.089 0	13.81
19	0.450	0.050	0.500	0.204 3	0.180 9	0.103 9	13.65
20	0.475	0.025	0.500	0.201 5	0.224 4	0.102 0	13.98
21	0.500	0.000	0.500	0.195 3	0.156 8	0.087 4	13.53

实验序号	种群规模Q	经济成本	延迟惩罚	安全风险	算法时长/s
1	25	0.292 7	0.112 1	0.168 9	1.74
2	50	0.270 1	0.098 4	0.132 6	5.18
3	75	0.245 2	0.100 3	0.124 2	9.01
4	100	0.209 5	0.114 7	0.105 9	13.34
5	125	0.226 5	0.082 6	0.105 1	17.43
6	150	0.202 8	0.097 0	0.084 6	21.45
7	175	0.217 6	0.084 2	0.087 7	25.47
8	200	0.211 9	0.076 5	0.093 8	29.13
9	225	0.230 4	0.083 3	0.094 9	32.59
10	250	0.203 5	0.086 1	0.093 5	37.08
11	275	0.196 7	0.086 9	0.096 2	40.81
12	300	0.206 2	0.083 2	0.087 9	44.79

[1]	Jialei LIU, Jiazhi MA, Longfei SHI. DOA estimation algorithm based on fourth-order cumulant using virtual beam forming [J]. Systems Engineering and Electronics, 2022, 44(7): 2134-2142.
[2]	Andi TANG, Tong HAN, Dengwu XU, Huan ZHOU, lei XIE. An improved salp swarm algorithm using Gaussian distribution estimation strategy [J]. Systems Engineering and Electronics, 2022, 44(7): 2229-2240.
[3]	Chengfei YUE, Zhenghua XUE, Weiran YAO, Xibin CAO. Cooperative combat task allocation of multiple aerial vehicles based on the characteristic relation [J]. Systems Engineering and Electronics, 2022, 44(6): 1897-1906.
[4]	Ruiyang LI, Weibo HUO, Wei MA, Ziyang CHENG. Covariance matrix estimation method based on inverse Gaussian texture distribution [J]. Systems Engineering and Electronics, 2021, 43(9): 2470-2475.
[5]	Xiaoyun SHEN, Xianhua LIAO, Weitian SUN, Yabo XIA, Lei YANG. Sparse SAR imaging based on varying prior Bayes learning [J]. Systems Engineering and Electronics, 2021, 43(7): 1781-1790.
[6]	Jing ZHOU, Xiaozhe ZHAO, Zhen XU, Zhong LIN, Xiaopan ZHANG. Many-objective task allocation method based on D-NSGA-Ⅲ algorithm for multi-UAVs [J]. Systems Engineering and Electronics, 2021, 43(5): 1240-1247.
[7]	WANG Jianhao, ZHANG Liang, SHI Chao, CHE Fei, ZHANG Pengtao. Task allocation modeling and solving algorithm for equipment support using DLS-BCIWBA [J]. Systems Engineering and Electronics, 2018, 40(9): 1979-1985.
[8]	CUI Ya-ni, REN Jia, DU Wen-cai. Time-sensitive task dynamic allocation algorithm for multi-UAVs in battlefield environments [J]. Systems Engineering and Electronics, 2016, 38(4): 828-835.
[9]	YAO Peiyang1， WAN Lujun1,2， SUN Peng1， ZHOU Xiangxiang3. Dynamic task allocation in multiple agent groups based on RHPIVFSA [J]. Systems Engineering and Electronics, 2014, 36(7): 1309-1319.
[10]	SUN Tian-yu, SHI Yi-min, WEI Wei. Reliability analysis for B-S components under progressive hybrid Type I censoring test [J]. Systems Engineering and Electronics, 2014, 36(11): 2326-2331.
[11]	WAN Lu-jun， YAO Pei-yang， SUN Peng. Distributed task allocation method of manned/unmanned combat Agents [J]. Journal of Systems Engineering and Electronics, 2013, 35(2): 310-316.
[12]	LIANG Xiao-long，HU Jun-hua，JING Xian-yong，LIU An，FENG Jin-fu. Multi-stage optimization model and algorithm for near space multi-weapon platform attacking ground targets [J]. Journal of Systems Engineering and Electronics, 2010, 32(12): 2618-2622.
[13]	TANG Suyan，ZHU Yifan，LI Qun，LEI Yonglin. Survey of task allocation in multi Agent systems [J]. Journal of Systems Engineering and Electronics, 2010, 32(10): 2155-2161.
[14]	LI Wei-xiang, ZHANG Guang-ming, LI Bang-yi. Research on multi-attributes task allocation mechanism in MAS [J]. Journal of Systems Engineering and Electronics, 2009, 31(5): 1113-1116.