Cooperative task allocation for mixed manned and unmanned ground systems

doi:10.23919/JSEE.2026.000075

Abstract

Abstract:

In this paper, a cooperative task allocation problem of ground manned and unmanned systems is investigated. Considering roads and threats in the urban security environment, the cooperative scout and strike problem is modeled as a heterogeneous fleet vehicle routing problem with time window. Firstly, a task allocation model for scout and strike of the mixed manned and unmanned systems is constructed, with the objective functions of minimizing the total task completion time and reducing our damage. Secondly, dangerous areas and risky road segments are further taken into account. Then, by integrating the search capability of removal and insertion operation in large-scale neighborhood search (LNS), a hybrid algorithm combining genetic algorithm (GA) and LNS (GA-LNS) is designed, which enhances the local search ability of GA. Finally, the effectiveness of the proposed model and algorithm is evaluated by conducting numerous computational experiments on the Solomon test set and providing a simulated example of urban security exercise. The experimental results show that GA-LNS is more competitive than advanced heuristic algorithms. In addition, compared with the use of manned vehicles alone, the cooperative task allocation of manned and unmanned vehicles in the ground urban security environment has broad application prospects.

Key words: manned and unmanned system, vehicle routing problem, hybrid genetic algorithm

Jin Su, Yuanqing Xia. Cooperative task allocation for mixed manned and unmanned ground systems[J]. Journal of Systems Engineering and Electronics, 2026, 37(4): 1413-1428.

Figures/Tables 12

Fig 1

Table 1

Fig 2

Fig 3

Table 2

Table 3

Table 4

Table 5

Fig 4

Table 6

Table 7

Table 8

References 36

1	Zhong Y, Yao P Y, Zhang J Y, et al Formation and adjustment of manned/unmanned combat aerial vehicle cooperative engagement system. Journal of Systems Engineering and Electronics, 2018, 29 (4): 756. doi: 10.21629/jsee.2018.04.10
2	Force US Air. United states air force unmanned aircraft systems flight plan 2009-2047[R]. Washington DC: Department of Defense, 2009.
3	How J, Kuwata Y, King E. Flight demonstrations of cooperative control for UAV teams[C]// AIAA 3rd Unmanned Unlimited Technical Conference on Workshop and Exhibit, 2004. DOI: 10.2514/6.2004-6490.
4	Poudel S, Moh S Priority-aware task assignment and path planning for efficient and load-balanced multi-UAV operation. Vehicular Communications, 2023, 42, 100633. doi: 10.1016/j.vehcom.2023.100633
5	Manyam S G, Casbeer D W, Sundar K. Path planning for cooperative routing of air-ground vehicles[C]// IEEE American Control Conference, 2016: 4630.
6	Fawaz W, Atallah R, Assi C, et al Unmanned aerial vehicles as store-carry-forward nodes for vehicular networks. IEEE Access, 2017, 5, 23710. doi: 10.1109/ACCESS.2017.2765498
7	Poikonen S, Wang X, Golden B The vehicle routing problem with drones: extended models and connections. Networks, 2017, 70 (1): 34. doi: 10.1002/net.21746
8	Ding W J, Cao H, Guo H, et al Investigation on optimal path for submarine search by an unmanned underwater vehicle. Computers & Electrical Engineering, 2019, 79, 106468. doi: 10.1016/j.compeleceng.2019.106468
9	Yan Z P, Zhang J Z, Zeng J, et al Three-dimensional path planning for autonomous underwater vehicles based on a whale optimization algorithm. Ocean Engineering, 2022, 250, 111070. doi: 10.1016/j.oceaneng.2022.111070
10	Sadraey M H. Manned-unmanned aircraft teaming[C]// IEEE Aerospace Conference, 2018. DOI: 10.1109/ AERO.2018.8396747.
11	Murray C C, Chu A G The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 2015, 54, 86. doi: 10.1016/j.trc.2015.03.005
12	Deng C, Wang S W, Huang Z, et al Unmanned aerial vehicles for power line inspection: a cooperative way in platforms and communications. Journal of Communications, 2014, 9 (9): 687. doi: 10.12720/jcm.9.9.687-692
13	Agatz N, Bouman P, Schmidt M Optimization approaches for the traveling salesman problem with drone. Transportation Science, 2018, 52 (4): 965. doi: 10.1287/trsc.2017.0791
14	Ha Q M, Deville Y, Pham Q D, et al On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 2018, 86, 597. doi: 10.1016/j.trc.2017.11.015
15	Wang Z, Sheu J B Vehicle routing problem with drones. Transportation Research Part B: Methodological, 2019, 122, 350. doi: 10.11606/d.55.2019.tde-29082019-091040
16	Savuran H, Karakaya M Route optimization method for unmanned air vehicle launched from a carrier. Lecture Notes on Software Engineering, 2015, 3 (4): 279. doi: 10.7763/LNSE.2015.V3.204
17	Hu M L, Liu W D, Lu J Q, et al On the joint design of routing and scheduling for vehicle-assisted multi-UAV inspection. Future Generation Computer Systems, 2019, 94, 214. doi: 10.1016/j.future.2018.11.024
18	Chen J Y C, Barnes M J Human–agent teaming for multirobot control: a review of human factors issues. IEEE Trans. on Human-Machine Systems, 2014, 44 (1): 13. doi: 10.1109/THMS.2013.2293535
19	Kolling A, Walker P, Chakraborty N, et al Human interaction with robot swarms: a survey. IEEE Trans. on Human-Machine Systems, 2015, 46 (1): 9.
20	Koc C, Bektas T, Jabali O, et al The impact of depot location, fleet composition and routing on emissions in city logistics. Transportation Research Part B: Methodological, 2016, 84, 81. doi: 10.1016/j.trb.2015.12.010
21	Yagmur E, Kesen S E Multi-trip heterogeneous vehicle routing problem coordinated with production scheduling: memetic algorithm and simulated annealing approaches. Computers & Industrial Engineering, 2021, 161, 107649. doi: 10.1016/j.cie.2021.107649
22	Qin W, Zhuang Z L, Huang Z Z, et al A novel reinforcement learning-based hyper-heuristic for heterogeneous vehicle routing problem. Computers & Industrial Engineering, 2021, 156, 107252. doi: 10.1016/j.cie.2021.107252
23	Banyai T Optimization of material supply in smart manufacturing environment: a metaheuristic approach for matrix production. Machines, 2021, 9 (10): 220. doi: 10.3390/machines9100220
24	Bac U, Erdem M Optimization of electric vehicle recharge schedule and routing problem with time windows and partial recharge: a comparative study for an urban logistics fleet. Sustainable Cities and Society, 2021, 70, 102883. doi: 10.1016/j.scs.2021.102883
25	Sabar N R, Bhaskar A, Chung E, et al An adaptive memetic approach for heterogeneous vehicle routing problems with two-dimensional loading constraints. Swarm and Evolutionary Computation, 2020, 58, 100730. doi: 10.1016/j.swevo.2020.100730
26	Baradaran V, Shafaei A, Hosseinian A H Stochastic vehicle routing problem with heterogeneous vehicles and multiple prioritized time windows: mathematical modeling and solution approach. Computers & Industrial Engineering, 2019, 131, 187. doi: 10.1016/j.cie.2019.03.047
27	Han Z L, Wang D Q, Liu F, et al Multi-AGV path planning with double-path constraints by using an improved genetic algorithm. PloS one, 2017, 12 (7): e0181747. doi: 10.1371/journal.pone.0181747
28	Hou D K, Fan H M, Ren X X, et al Time-dependent multi-depot heterogeneous vehicle routing problem considering temporal–spatial distance. Sustainability, 2021, 13 (9): 4674. doi: 10.3390/su13094674
29	Penna P H V, Subramanian A, Ochi L S, et al A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet. Annals of Operations Research, 2019, 273 (1): 5.
30	Zheng X J, Gao F, Tong X Y Research on green vehicle path planning of AGVs with simultaneous pickup and delivery in intelligent workshop. Symmetry, 2023, 15 (8): 1505. doi: 10.3390/sym15081505
31	Pisinger D, Ropke S A general heuristic for vehicle routing problems. Computers & Operations Research, 2007, 34 (8): 2403. doi: 10.1016/j.cor.2005.09.012
32	Shi Y, Boudouh T, Grunder O A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert Systems with Applications, 2017, 72, 160. doi: 10.1016/j.eswa.2016.12.013
33	Solomon M M Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 1987, 35 (2): 254. doi: 10.1287/opre.35.2.254
34	Wang C, Mu D, Zhao F, et al A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering, 2015, 83, 111. doi: 10.1016/j.cie.2015.02.005
35	Alvarenga G B, Mateus G R, De Tomi G A genetic and set partitioning two-phase approach for the vehicle rout- ing problem with time windows. Computers & Operations Research, 2007, 34 (6): 1561. doi: 10.1016/j.cor.2005.07.025
36	Wu H G, Gao Y L, Wang W T, et al A hybrid ant colony algorithm based on multiple strategies for the vehicle routing problem with time windows. Complex & Intelligent Systems, 2023, 9 (3): 2491. doi: 10.1007/s40747-021-00401-1

Parameter	Description
$ {{G}} $	Undirected graph, current urban network structure
$ A $	Set of graph edges
$ K $	Set of all vehicles
$ {K_{{\mathrm{Type}}}} $	Set of vehicle type
$ S $	The ordered node set of the path
$ {V_0} $	Terrorists point set
$ V $	Set of nodes in an undirected graph
$ i,j $	Node index, $ i,j \in V $
$ {x_i},{y_i} $	Position of location $ i $
$ n $	Terrorists point set number
$ m $	Number of manned-unmanned anti-riot vehicles
$ k $	Anti-riot vehicle in the set $ K $, $ k \in \{ 1,2,3, \cdots ,m\} $
$ \beta _j^{^{{\mathrm{threat}}}} $	Threat level of terrorist $ j $
$ {D_{{\mathrm{com}}}} $	The maximum communication distance of the manned-unmanned system
$ {Q_k} $	Endurance time of $ k $
$ {c_{{k_1}{k_2}}} $	The linear distance of $ {k_1} $ and $ {k_2} $, $ \forall i,j \in V,i \ne j $
$ {P_{{\mathrm{mvL}}}} $	The upper limit of injury probability of manned vehicle
$ [r_j^{\min },\;r_j^{\max }] $	The range of threat scope
[$ {{\mathrm{ET}}_i} $, $ {{\mathrm{LT}}_i} $]	The time window of $ i $
$ {s_i} $	Scout and strike time of $ i $
$ {v_k} $	The speed of vehicle
$ {d_{ij}} $	Distance between node $ i $ and node $ j $
$ {t_{ij}} $	Vehicle travel time from point $ i $ to point $ j $
$ {T_{ik}} $	Arrival time of vehicle $ k $ at point $ i $
$ M $	A sufficiently large number
$ {x_{ijk}} $	$ {x}_{ijk}=\left\{\begin{aligned}&1, \;\;k\text{ travels from node }i\;{\mathrm{to}}\;{\mathrm{node}}\;j\\&0, \;\;{\mathrm{otherwise}}\end{aligned}\right. $
$ {c_{ij}} $	$ {c}_{ij}=\left\{\begin{aligned}&1,\;\;ij \text{ is a dangerous road}\\&0,\;\; {\mathrm{otherwise}}\end{aligned}\right. $

Test case	Best-known solution	GA	GA-LNS
Test case	NV/TD	Average (NV/TD)	Average NV	Average TD	Best TD	Best (NV/TD)
C101	3.0/191.30	3.0/191.81	3.0	191.38	191.38	3/191.38
C102	3.0/190.30	3.0/190.74	3.0	190.45	190.45	3/190.45
C103	3.0/190.30	3.0/190.74	3.0	190.73	190.71	3/190.71
C104	3.0/186.90	3.0/187.45	3.0	187.30	187.30	3/187.30
C205	2.0/214.70	2.0/215.54	2.0	215.59	215.59	2/215.59
C206	3.0/214.70	2.0/215.54	2.0	214.96	214.90	2/214.90
C207	2.0/214.50	2.0/215.34	2.0	215.34	215.30	2/215.30
C208	2.0/214.50	−	2.0	214.97	214.82	2/214.82
R105	6.0/530.50	6.0/531.54	6.0	535.77	535.77	6/535.77
R106	3.0/465.40	5.0/466.48	5.0	466.48	466.48	5/466.48
R107	4.0/424.30	4.6/425.27	4.0	424.67	424.67	4/424.67
R108	4.0/397.30	4.0/398.29	4.0	401.12	400.36	4/400.35
R205	3.0/393.00	2.8/395.82	3.0	393.85	393.85	3/393.85
R206	3.0/374.40	1.8/379.85	3.0	376.23	376.23	3/376.23
R207	3.0/361.60	1.8/369.21	3.0	361.71	361.71	3/361.71
R208	1.0/328.20	−	1.0	328.79	328.79	1/328.79
RC101	4.0/461.10	4.0/462.61	4.0	463.55	463.55	4/463.55
RC102	3.0/351.80	3.0/352.74	3.0	352.39	352.39	3/352.39
RC103	3.0/332.80	3.0/333.92	3.0	333.92	333.92	3/333.92
RC104	3.0/306.60	3.0/308.39	3.0	308.39	308.39	3/308.39
RC205	3.0/338.00	3.0/338.93	3.0	338.76	338.76	3/338.76
RC206	3.0/324.00	2.4/326.14	3.0	325.10	325.10	3/325.10
RC207	3.0/298.30	2.6/298.95	3.0	298.88	298.88	3/298.88
RC208	2.0/269.10	−	2.0	269.57	269.57	2/269.57

Test case	Best-known solution	GA-LNS
Test case	NV/TD	Average NV	Average TD	Best TD	Best (NV/TD)
C101	5.0/362.40	5.0	362.58	362.44	5/362.44
C102	5.0/361.40	5.0	362.25	361.89	5/361.89
C103	5.0/361.40	5.0	365.73	363.90	5/363.90
C104	5.0/358.00	5.0	358.00	358.00	5/358.00
C205	3.0/359.80	3.0	361.36	361.36	3/361.36
C206	3.0/359.80	3.0	359.80	359.80	3/359. 80
C207	3.0/359.60	3.0	362.78	361.30	3/361.30
C208	2.0/350.50	2.0	352.12	350.50	2/350.50
R105	9.0/899.30	9.0	907.81	907.81	9/907.81
R106	5.0/793.00	5.0	797.56	795.88	5/795.88
R107	7.0/711.10	7.0	712.06	712.06	7/712.06
R108	6.0/617.70	6.0	621.59	619.28	6/619.28
R205	4.0/690.10	4.0	698.04	695.17	4/695.17
R210	4.0/645.60	3.0	650.85	650.85	3/650.85
R211	3.0/535.50	3.0	539.96	538.07	3/538.07
R204	2.0/506.40	2.0	506.40	506.40	2/506.40
RC101	8.0/9440	8.2	957.31	949.10	8/949.10
RC102	7.0/822.50	7.0	831.77	825.58	7/825.58
RC103	6.0/710.90	6.4	706.25	693.05	6/724.60
RC104	5.0/545.80	5.0	546.57	546.25	5/546.25
RC205	5.0/630.20	5.0	631.38	631.07	5/632.63
RC206	5.0/610.00	5.0	610.95	610.77	5/610.77
RC207	4.0/558.60	4.2	559.30	559.00	4/559.00
RC204	3.0/444.20	3.0	444.97	444.97	3/444.97

Test case	Best-known solution	GA-LNS
Test case	NV/TD	Average NV	Average TD	Best TD	Best (NV/TD)
C101	10.0/828.94	10.0	831.03	831.03	10/831.03
C102	10.0/828.94	10.4	844.57	839.69	10/839.69
C103	10.0/828.06	10.0	844.39	844.39	10/844.39
C104	10.0/824.78	10.0	840.91	831.77	10/831.77
C205	3.0/588.88	3.0	588.88	588.88	3/588.88
C206	3.0/588.49	3.0	588.49	588.49	3/588.49
C207	3.0/588.29	3.0	588.29	588.29	3/588.29
C208	3.0/588.32	3.0	588.32	588.32	3/588.32
R105	14.0/1377.11	14.8	1469.05	1396.72	14/1396.72
R106	12.0/1252.03	12.6	1274.60	1258.37	12/1258.37
R107	10.0/1104.66	10.2	1111.25	1105.43	10/1105.43
R108	9.0/960.88	9.6	969.60	966.61	9/974.08
R205	3.0/994.43	3.2	998.52	994.43	3.0/994.43
R206	3.0/906.14	3.0	906.14	906.14	3/906.14
R207	2.0/890.61	3.0	836.41	822.30	3/822.30
R208	2.0/726.82	2.8	719.31	733.83	2/733.83
RC101	14.0/1696.95	16.4	1766.89	1728.57	16/1754.85
RC102	12.0/1554.75	14.8	1569.32	1556.70	14/1556.70
RC103	11.0/1261.67	10.0	1401.54	1378.23	12/1378.23
RC104	10.0/1135.48	11.0	1255.43	1210.58	11/1210.58
RC205	4.0/1297.65	5.6	1193.14	1173.71	5/1173.71
RC206	3.0/1146.32	4.4	1097.70	1081.84	4/1081.84
RC207	3.0/1061.41	4.7	1008.31	1003.09	5/1003.09
RC208	3.0/828.14	4.2	818.44	807.94	4/807.94

Algorithm	Index	C1	C2	R1	R2	RC1	RC2
Published best [33]	NV	10.00	3.00	11.25	2.50	11.75	3.25
Published best [33]	TD	826.95	588.77	1174.27	879.86	1412.33	1083.76
GA-LNS	NV	10.00	3.00	11.25	2.75	13.25	4.50
GA-LNS	TD	828.95	588.95	1178.82	861.39	1475.09	1016.64
p-SA [34]	NV	10.25	3.00	11.75	2.50	12.25	3.25
p-SA [34]	TD	972.16	588.50	1180.23	911.22	1448.82	1122.68
GA [35]	NV	10.00	3.00	11.75	4.50	12.75	6.25
GA [35]	TD	825.95	586.00	1150.85	877.78	1039.99	1015.13
ACO [36]	NV	11.75	4.00	15.00	3.25	15.50	4.00
ACO [36]	TD	1446.43	745.26	1697.62	1348.50	2011.04	1720.70
HACO [36]	NV	11.75	4.00	15.00	3.25	15.50	4.00
HACO [36]	TD	1448.28	714.51	1657.72	1325.75	1979.50	1692.59