Weapon configuration, allocation and route planning with time windows for multiple unmanned combat air vehicles

doi:10.21629/JSEE.2018.05.08

Journal of Systems Engineering and Electronics ›› 2018, Vol. 29 ›› Issue (5): 953-968.doi: 10.21629/JSEE.2018.05.08

收稿日期:2017-03-13 出版日期:2018-10-26 发布日期:2018-11-14

Weapon configuration, allocation and route planning with time windows for multiple unmanned combat air vehicles

Jiaming ZHANG*(), Zhong LIU(), Jianmai SHI(), Chao CHEN()

Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China

Received:2017-03-13 Online:2018-10-26 Published:2018-11-14
Contact: Jiaming ZHANG E-mail:zjm08091018@163.com;phillipliu@263.net;jianmaishi@gmail.com
About author:ZHANG Jiaming was born in 1982. He received his B.S. degree in communication command from National University of Defense Technology, Changsha, Hunan, China, in 2004. From 2004 to 2008, he was a commanding officer in combat troops. He received his M.S. degree in military training from National University of Defense Technology, in 2010. He is currently pursuing his Ph.D. degree in management science and engineering at National University of Defense Technology. His current research interests include task assignment, mission planning and supply chain management. E-mail: zjm08091018@163.com|LIU Zhong is a professor of the National University of Defense Technology, Changsha, Hunan, China, and the deputy director of Science and Technology on Information Systems Engineering Laboratory as well as a senior advisor of the Research Center for Computational Experiments and Parallel Systems at National University of Defense Technology. He received his M.S. and Ph.D. degrees from National University of Defense Technology, Changsha, China, in 1997 and 2000, respectively. His main research interests include planning systems, computational organization and intelligent systems. E-mail: phillipliu@263.net|SHI Jianmai is an associate research fellow of the National University of Defense Technology, Changsha, Hunan, China, and a researcher of Science and Technology on Information Systems Engineering Laboratory. His main research interests include task assignment, mission planning and supply chain management. E-mail: jianmaishi@gmail.com|CHEN Chao was born in 1977. He received his M.S. and Ph.D. degrees from National University of Defense Technology in 2003 and 2007 respectively. He is now an associate research fellow in National University of Defense Technology. His research interests include complexity of war systems, battle modeling and simulation, and automatization in command and control system. E-mail: jianmaishi@gmail.com
Supported by:
the National Natural Science Foundation of China(71471175);the National Natural Science Foundation of China(71471174);This work was supported by the National Natural Science Foundation of China (71471175; 71471174)

摘要/Abstract

Abstract:

Unmanned combat air vehicles (UCAVs) mission planning is a fairly complicated global optimum problem. Military attack missions often employ a fleet of UCAVs equipped with weapons to attack a set of known targets. A UCAV can carry different weapons to accomplish different combat missions. Choice of different weapons will have different effects on the final combat effectiveness. This work presents a mixed integer programming model for simultaneous weapon configuration and route planning of UCAVs, which solves the problem optimally using the IBM ILOG CPLEX optimizer for simple missions. This paper develops a heuristic algorithm to handle the medium-scale and large-scale problems. The experiments demonstrate the performance of the heuristic algorithm in solving the medium scale and large scale problems. Moreover, we give suggestions on how to select the most appropriate algorithm to solve different scale problems.

Key words: unmanned combat air vehicles (UCAVs), mission planning, route planning, weapon configuration, time windows

. [J]. Journal of Systems Engineering and Electronics, 2018, 29(5): 953-968.

Jiaming ZHANG, Zhong LIU, Jianmai SHI, Chao CHEN. Weapon configuration, allocation and route planning with time windows for multiple unmanned combat air vehicles[J]. Journal of Systems Engineering and Electronics, 2018, 29(5): 953-968.

图/表 26

Number of instances	Number of hanging points	Weight of bomb load/kg	CPLEX result			Heuristic optimization methods result (before adding optimization strategy)			Heuristic optimization methods result (after adding optimization strategy)
Number of instances	Number of hanging points	Weight of bomb load/kg	Number of UCAVs used	Objective value	Computation time/s	Number of UCAVs used	Objective value	Computation time/s	Number of UCAVs used	Objective value	Computation time/s
1	4	600	3	308.41	1 528.62	4	397.01	5.64	3	396.05	4.17
	6	900	2	279.40	1 818.49	3	298.07	6.50	3	289.06	3.52
	8	1 200	2	244.95	2 178.99	2	269.94	4.75	2	265.17	5.02
2	4	600	3	327.98	1 559.41	4	354.61	5.03	4	309.17	5.37
	6	900	2	315.53	1 762.04	3	288.59	7.76	3	247.77	4.37
	8	1 200	2	212.41	2 100.98	2	267.88	4.91	2	249.27	5.13
3	4	600	3	327.70	1 565.23	4	433.97	5.63	3	423.90	3.15
	6	900	2	305.30	1 797.92	3	307.26	6.94	2	270.25	5.56
	8	1 200	2	266.72	2 035.51	2	270.59	3.48	2	256.35	3.16
4	4	600	3	320.43	1 545.68	4	416.76	4.47	3	413.57	5.61
	6	900	2	283.89	1 820.99	3	304.52	6.99	3	299.16	5.04
	8	1 200	2	251.63	2 036.52	2	286.43	4.58	2	231.08	3.45
5	4	600	3	310.30	1 588.34	4	389.30	5.77	4	343.51	3.15
	6	900	2	293.98	1 826.54	3	304.15	6.41	3	255.31	3.67
	8	1 200	2	263.50	2 010.42	2	308.78	7.01	2	272.33	3.79
6	4	600	3	323.11	1 571.59	4	406.91	6.71	3	351.19	4.51
	6	900	2	297.26	1 792.01	3	271.29	4.74	2	263.60	3.86
	8	1 200	2	235.56	2 045.99	2	282.55	4.71	2	278.42	5.51
7	4	600	3	331.15	1 738.78	4	463.52	7.24	4	439.97	3.06
	6	900	2	289.88	1 768.12	3	361.89	5.19	3	302.14	3.31
	8	1 200	2	274.67	2 008.25	2	304.19	6.97	2	290.32	4.95
8	4	600	3	357.66	1 782.41	4	400.19	6.66	4	320.95	4.44
	6	900	2	304.60	1 800.62	3	323.21	4.29	2	275.63	3.52
	8	1 200	2	211.37	2 034.13	2	283.22	5.58	2	282.48	5.07
9	4	600	3	370.25	1 706.42	5	448.21	5.65	4	399.08	5.73
	6	900	2	279.99	1 849.68	3	317.75	3.29	3	309.50	3.44
	8	1 200	2	265.34	2 090.53	2	254.60	3.68	3	247.79	5.99
10	4	600	3	333.53	1 586.89	5	473.34	5.43	4	398.82	3.29
	6	900	2	306.63	1 766.78	4	384.81	7.75	3	337.03	3.85
	8	1 200	2	253.85	2 141.24	2	232.33	7.93	2	193.33	5.21

参考文献 35

1	SHETTY V K, SUDIT M, NAGI R. Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles. Computers & Operations Research, 2008, 35 (6): 1813- 1828.
2	EVERS L, BARROS A I, MONSUUR H, et al. UAV mission planning: from robust to agile. ZEIMPEKIS V, KAIMAKAMIS G, DARAS N J, ed. Military logistics: research advances and future trends. Switzerland: Springer, 2015: 1- 17.
3	SHI Z, HUANG X, HUA Y, et al. Statistical physics method for multi-base multi-UAV cooperative reconnaissance mission planning. Proc. of the IEEE Advanced Information Technology, Electronic and Automation Control Conference, 2015: 64-68.
4	LIU Z, LUO Q, DING W, et al. A task assignment algorithm for multiple aerial vehicles to attack targets with dynamic values. IEEE Trans. on Intelligent Transportation Systems, 2013, 14 (1): 236- 248.
5	KOPEIKIN A N, PONDA S S, JOHNSON L B, et al. Dynamic mission planning for communication control in multiple unmanned aircraft teams. Unmanned Systems, 2013, 1 (1): 41- 58.
6	WANG X, WU J, HUANG H, et al. Multiple tasks scheduling algorithm for UAV attacking in uncertain environment. Proc. of the IEEE International Conference on Systems and Informatics, 2012: 735-739.
7	GRECU D L, GONSALVES P G. Agent-based simulation environment for UCAV mission planning and execution. Proc. of the AIAA Guidance, Navigation, and Control Conference and Exhibit, 2000: AIAA-2000-4481.
8	TIAN J, SHEN L C, ZHENG Y X. Genetic algorithm based approach for multi-UAV cooperative reconnaissance mission planning problem. Lecture Notes in Computer Science, 2006, 4203, 101- 110.
9	LAMONT G B, LAMONT G B. UAV swarm mission planning development using evolutionary algorithms and parallel simulation-part II SCI-195. OMB No. 0704-0188. New York: American National Standards Institute, 2008.
10	POHL A J, LAMONT G B. Multi-objective UAV mission planning using evolutionary computation. Proc. of the Conference on Winter Simulation, 2008: 1268-1279.
11	KARAMAN S, FRAZZOLI E. Linear temporal logic vehicle routing with applications to multi-UAV mission planning. International Journal of Robust & Nonlinear Control, 2011, 21 (12): 1372- 1395.
12	ZENG J, YANG X, YANG L, et al. Modeling for UAV resource scheduling under mission synchronization. Journal of Systems Engineering and Electronics, 2010, 21 (5): 821- 826. doi: 10.3969/j.issn.1004-4132.2010.05.016
13	KIM J, SONG B D, MORRISON J R. On the scheduling of systems of uavs and fuel service stations for long-term mission fulfillment. Journal of Intelligent & Robotic Systems, 2013, 70 (1-4): 347- 359.
14	JR CRUZ J B, CHEN G, LI D, et al. Particle swarm optimization for resource allocation in UAV cooperative control. Proc. of the AIAA Guidance, Navigation, and Control Conference and Exhibit, 2004: 1-11.
15	TAO J, TIAN Y, MENG X. Cooperative task allocation for unmanned combat aerial vehicles using improved ant colony algorithm. Proc. of the IEEE Conference on Cybernetics and Intelligent Systems, 2008: 1220-1225.
16	BELLINGHAM J, TILLERSON M, RICHARD A S, et al. Multi-task allocation and path planning for cooperating UAVs. Proc. of the Cooperative Control: Models, Applications and Algorithms, 2003: 23-41.
17	CHEN G, JR CRUZ J B. Genetic algorithm for task allocation in UAV cooperative control. Proc. of the AIAA Guidance, Navigation, and Control Conference and Exhibit, 2003: AIAA-2003-5582.
18	JIN Y, MINAI A A, POLYCARPOU M M. Cooperative realtime search and task allocation in UAV teams. Proc. of the IEEE Conference on Decision and Control, 2003: 7-12.
19	SUJIT P B, SINHA A, GHOSE D. Multiple UAV task allocation using negotiation. Proc. of the International Joint Conference on Autonomous Agents & Multiagent Systems, 2006: 471-478.
20	LI S M, BOSKOVIC J D, SEEREERAM S, et al. Autonomous hierarchical control of multiple unmanned combat air vehicles. Proc. of the IEEE American Control Conference, 2002: 274-279.
21	NIKOLOS I K, VALAVANIS K P, TSOURVELOUDIS N C, et al. Evolutionary algorithm based offline/online path planner for UAV navigation. IEEE Trans. on Systems, Man, and Cybernetics, Part B (Cybernetics), 2003, 33 (6): 898- 912. doi: 10.1109/TSMCB.2002.804370
22	ZHENG C, LI L, XU F. Evolutionary route planner for unmanned air vehicles. IEEE Trans. on Robotics, 2005, 21 (4): 609- 620.
23	ALLAIRE F C J, TARBOUCHI M, LABONT G, et al. FPGA implementation of genetic algorithm for UAV real-time path planning. Journal of Intelligent & Robotic Systems, 2009, 54 (1-3): 495- 510.
24	SONMEZOCAK E, KURT S. Optimum route planning and scheduling for unmanned aerial vehicles. Monterey, California: Naval Postgraduate School, 2008.
25	XU C, DUAN H, LIU F. Chaotic artificial bee colony approach to uninhabited combat air vehicle path planning. Aerospace Science and Technology, 2010, 14 (8): 535- 541. doi: 10.1016/j.ast.2010.04.008
26	LI S, SUN X, XU Y. Particle swarm optimization for route planning of unmanned aerial vehicles. Proc. of the IEEE International Conference on Information Acquisition, 2006: 1213-1218.
27	MADDULA T, MINAI A A, POLYCARPOU M M. Multitarget assignment and path planning for groups of UAVs. BUTENKO S, MURPHEY R, PARDALOS P M, ed. Recent developments in cooperative control and optimization. Boston: Springer, 2004: 261- 272.
28	EDISON E, SHIMA T. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms. Computers & Operations Research, 2011, 38 (1): 340- 356.
29	EVERS L, DOLLEVOET T, BARROS A I, et al. Robust UAV mission planning. Annals of Operations Research, 2014, 222 (1): 293- 315.
30	GAO C, ZHEN Z, GONG H. A self-organized search and attack algorithm for multiple unmanned aerial vehicles. Aerospace Science and Technology, 2016, 54 (1): 229- 240.
31	OH H, KIM S, TSOURDOS A, et al. Coordinated roadnetwork search route planning by a team of UAVs. International Journal of Systems Science, 2014, 45 (5): 825- 840. doi: 10.1080/00207721.2012.737116
32	PHAN C, LIU H H. A cooperative UAV/UGV platform for wildfire detection and fighting. Proc. of the 7th International Conference on System Simulation and Scientific Computing, 2008: 494-498.
33	SCHANZ M V. The reaper harvest. Air Force Magazine, 2011, 94 (4): 36- 39.
34	EVERS L, BARROS A I, MONSUUR H. Online stochastic UAV mission planning with time windows and time-sensitive targets. European Journal of Operational Research, 2014, 238 (1): 348- 362.
35	ZHANG S, ZHOU Y Q, LI Z M, et al. Grey wolf optimizer for unmanned combat aerial vehicle path planning. Advances in Engineering Software, 2016, 99, 121- 136. doi: 10.1016/j.advengsoft.2016.05.015

Tgt^a	Dam^b	Des^c	Win^d/h	Pos^e
T1	0.85	Bridge	[2.14, 2.95]	(245.26, 240.39)
T2	0.81	Military camp	[3.07, 3.84]	(231.89, 291.20)
T3	0.85	Bunker	[4.37, 6.86]	(141.50, 200.05)
T4	0.84	Arsenal	[3.30, 4.59]	(356.32, 209.34)
T5	0.55	Airbase	[3.83, 4.62]	(315.56, 252.39)

Index	Parameter value
Cost/$ million	10
Payload capacity/kg	1 200
Full-loaded endurance/h	15
Cruise speed/(km/h)	180
Hanging points	8
Types of weapons	W1, W2 and W3

Weapon	Description	Weight/kg	Cost/$ thousand
W1	Small smart bombs	75	68
W2	Small precision guided bombs	165	84
W3	Laser-guided bombs	240	22

Weapon	T1	T2	T3	T4	T5
W1	0.82	0.84	0.43	0.34	0.02
W2	0.86	0.88	0.54	0.67	0.35
W3	0.93	0.95	0.85	0.75	0.56

Feature		Index	Parameter value
UCAV		Payload capacity of the UCAV/kg	600, 900, 1 200
		Number of hanging points	4, 6, 8
		Type of weapons	W1, W2 and W3
		Cruise speed /(km/h)	180
Weapons	W1	Weight/kg	75
	W1	Cost /$ thousand	68
	W2	Weight/kg	165
	W2	Cost /$ thousand	84
	W3	Weight/kg	240
	W3	Cost /$ thousand	22

Weapon configuration, allocation and route planning with time windows for multiple unmanned combat air vehicles

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 26

参考文献 35

相关文章 0

编辑推荐

Metrics

本文评价

Number of instances	Number of hanging points	Weight of bomb load/kg	Heuristic optimization methods result (before adding optimization strategy)			Heuristic optimization methods result (after adding optimization strategy)
Number of instances	Number of hanging points	Weight of bomb load/kg	Number of UCAVs used	Objective value	Computation time/s	Number of UCAVs used	Objective value	Computation time/s
11	4	600	10	974.73	13.87	9	670.34	13.56
	6	900	6	720.32	13.04	6	688.95	13.03
	8	1 200	3	481.06	14.78	4	479.81	12.16
12	4	600	8	850.96	14.50	9	606.09	12.20
	6	900	6	664.56	15.28	6	468.31	14.81
	8	1 200	4	625.95	12.15	3	361.68	10.26
13	4	600	9	956.22	12.66	11	783.47	12.60
	6	900	6	745.49	11.49	6	412.36	9.76
	8	1 200	4	563.98	13.61	4	410.71	12.76
14	4	600	10	950.95	15.88	9	805.08	13.19
	6	900	5	638.65	13.88	6	506.17	13.01
	8	1 200	3	479.81	11.83	4	548.63	10.85
15	4	600	9	853.74	11.84	8	551.77	9.71
	6	900	6	667.08	11.83	6	477.80	10.29
	8	1 200	4	582.77	12.01	4	480.80	10.93
16	4	600	7	718.97	12.77	7	497.88	11.62
	6	900	6	667.34	12.48	6	428.88	11.20
	8	1 200	3	447.61	13.37	3	404.05	13.12
17	4	600	9	840.24	10.88	8	643.66	9.93
	6	900	6	675.44	10.98	6	484.96	9.59
	8	1 200	4	568.92	13.26	4	422.01	10.79
18	4	600	8	847.41	13.90	8	525.47	11.72
	6	900	6	660.60	15.31	6	454.85	13.59
	8	1 200	3	518.98	12.89	3	345.91	11.65
19	4	600	7	764.53	14.10	8	679.74	13.12
	6	900	5	603.78	20.73	5	392.81	20.14
	8	1 200	3	529.89	11.44	3	429.58	9.97
20	4	600	8	813.40	12.38	8	762.84	10.83
	6	900	5	581.59	14.12	5	459.30	12.91
	8	1 200	3	494.18	13.72	3	319.86	12.39

Number of instances	Number of hanging points	Weight of bomb load/kg	Heuristic optimization methods result (before adding optimization strategy)			Heuristic optimization methods result (after adding optimization strategy)
Number of instances	Number of hanging points	Weight of bomb load/kg	Number of UCAVs used	Objective value	Computation time/s	Number of UCAVs used	Objective value	Computation time/s
21	4	600	20	3 118.83	20.89	16	1 794.39	13.73
	6	900	15	2 409.37	22.10	10	1 218.02	10.61
	8	1 200	10	2 264.81	21.67	6	1 649.30	11.39
22	4	600	20	3 189.04	22.16	16	1 560.80	41.19
	6	900	13	2 220.32	22.02	8	1 518.78	18.40
	8	1 200	11	2 416.54	22.82	7	1 197.14	16.40
23	4	600	19	3 096.02	21.67	14	2 251.81	11.86
	6	900	15	2 388.66	21.69	9	1 542.54	20.90
	8	1 200	11	2 404.01	22.06	7	1 631.10	13.75
24	4	600	19	3 136.23	22.18	14	2 472.81	10.30
	6	900	15	2 471.75	22.21	9	1 436.20	16.86
	8	1 200	11	2 472.17	21.39	7	1 101.81	21.84
25	4	600	18	2 766.77	22.18	12	1 676.03	31.51
	6	900	15	2 097.54	21.40	10	1 499.16	26.55
	8	1 200	10	2 258.25	21.66	7	1 297.40	10.92
26	4	600	19	3 081.02	21.41	13	1 779.37	16.22
	6	900	15	2 543.91	22.25	10	1 433.83	15.15
	8	1 200	9	2 110.61	22.32	7	1 850.77	10.45
27	4	600	20	3 170.16	22.32	15	1 876.65	11.56
	6	900	14	2 392.31	21.48	9	1 613.56	17.49
	8	1 200	9	2 159.92	22.13	7	1 241.95	11.86
28	4	600	22	3 440.64	22.13	18	2 311.71	24.28
	6	900	14	2 381.41	22.22	10	1 250.07	13.28
	8	1 200	10	2 400.32	21.71	8	1 102.32	16.40
29	4	600	19	3 067.64	21.19	14	1 943.43	12.17
	6	900	15	2 444.17	21.87	10	1 458.42	15.62
	8	1 200	9	2 159.54	22.33	8	1 665.02	19.83
30	4	600	19	2 968.83	20.62	14	1 794.73	19.17
	6	900	13	2 288.42	22.02	8	1 723.92	18.58
	8	1 200	10	2 280.96	22.32	7	1 795.97	18.89

Number of instances	Number of hanging points	Weight of bomb load/kg	Heuristic optimization methods result (before adding optimization strategy)			Heuristic optimization methods result (after adding optimization strategy)
Number of instances	Number of hanging points	Weight of bomb load/kg	Number of UCAVs used	Objective value	Computation time/s	Number of UCAVs used	Objective value	Computation time/s
31	4	600	67	11 373.55	41.44	56	7 797.37	21.11
	6	900	54	9 701.86	43.46	41	5 810.26	27.30
	8	1 200	34	7 442.35	42.02	20	3 458.04	57.86
32	4	600	69	11 949.95	42.43	57	6 434.11	22.15
	6	900	54	10 287.85	41.46	46	5 400.13	15.60
	8	1 200	32	6 934.83	42.71	25	4 993.74	18.23
33	4	600	64	10 784.83	40.28	49	6 173.95	22.28
	6	900	54	9 580.61	42.67	36	4 977.12	27.61
	8	1 200	33	6 999.56	41.32	18	3 995.80	32.60
34	4	600	61	10 449.04	40.15	54	7 062.17	47.60
	6	900	45	8 258.14	42.67	41	5 068.17	28.24
	8	1 200	33	6 967.72	41.33	23	3 867.36	37.28
35	4	600	59	10 108.06	42.73	53	5 661.16	49.45
	6	900	50	9 240.44	43.26	42	4 852.35	62.38
	8	1 200	29	6 377.50	40.97	20	3 983.05	17.29
36	4	600	68	11 788.17	41.44	58	7 691.36	26.83
	6	900	56	10 239.31	41.32	47	6 160.87	27.12
	8	1 200	30	6 657.11	41.56	21	4 531.98	14.82
37	4	600	66	11 252.33	42.85	53	6 633.85	33.72
	6	900	52	9 395.75	42.87	43	4 875.10	23.40
	8	1 200	33	7 020.33	41.18	24	4 264.19	46.18
38	4	600	66	11 330.95	41.56	57	6 428.60	33.59
	6	900	53	9 657.26	42.40	41	6 024.72	30.25
	8	1 200	31	6 806.46	42.82	18	3 607.42	25.12
39	4	600	64	10 816.15	42.47	55	6 944.39	13.28
	6	900	51	9 158.53	43.66	40	4 685.69	48.52
	8	1 200	34	7 249.38	40.25	19	4 287.20	44.00
40	4	600	67	11 238.58	42.84	55	6 157.49	12.18
	6	900	51	9 485.01	41.19	38	5 988.15	65.37
	8	1 200	29	6 295.19	43.45	20	3 318.83	29.62