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

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

摘要/Abstract

摘要：

针对城市区域多无人机协同物流任务分配问题, 综合考虑不同无人机性能、物流时效性、飞行可靠性等影响因素, 以经济成本、时间损失和安全风险最小为目标函数, 构建多无人机协同物流任务分配模型。因问题规模大、求解复杂度高, 设计改进的量子粒子群算法进行求解。首先，为增强粒子遍历性和多样性, 采用均匀化级联Logistic映射进行粒子初始化; 其次，为避免算法陷入局部最优解, 引入基于高斯分布的粒子变异方式; 最后，为提高算法运行效率, 运用自适应惯性权重方法对粒子赋值。仿真实验结果表明，所构建的模型能够实现任务分配多目标优化, 贴近城市区域无人机物流配送实际; 所提算法与传统量子粒子群算法和遗传算法相比, 任务分配代价分别下降了5.9%和6.3%;并进一步对参数权重设置进行分析, 当3个子目标函数权重系数分别为0.225、0.275和0.500, 种群规模为150时, 算法规划的结果最优。

关键词: 物流无人机, 任务分配, 改进量子粒子群算法, 高斯分布, 自适应惯性权重

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

中图分类号:

V279.3

李翰, 张洪海, 张连东, 刘皞. 城市区域多物流无人机协同任务分配[J]. 系统工程与电子技术, 2021, 43(12): 3594-3602.

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.

图/表 15

图1

图2

图3

图4

表1

图5

表2

表3

表4

表5

图6

表6

图7

表7

图8

参考文献 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