# Multidepot UAV Routing Problem with Weapon Configuration and Time Window

Authors: Tianren Zhou; Jiaming Zhang; Jianmai Shi; Zhong Liu; Jincai Huang
Journal: Journal of Advanced Transportation
 (2018)

---

## Abstract

In recent wars, there is an increasing trend that unmanned aerial vehicles (UAVs) are utilized to conduct military attacking missions. In this paper, we investigate a novel multidepot UAV routing problem with consideration of weapon configuration in the UAV and the attacking time window of the target. A mixed-integer linear programming model is developed to jointly optimize three kinds of decisions: the weapon configuration strategy in the UAV, the routing strategy of target, and the allocation strategy of weapons to targets. An adaptive large neighborhood search (ALNS) algorithm is proposed for solving the problem, which is tested by randomly generated instances covering the small, medium, and large sizes. Experimental results confirm the effectiveness and robustness of the proposed ALNS algorithm.


---

## Body

## 1. Introduction

With the development of information technologies, artificial intelligence, and new materials, as well as their wide application in unmanned aerial vehicles (UAVs), the abilities of UAVs on autonomously flying, endurance, and stealth have been greatly improved. There are many advantages of UAVs to conduct military operations, such as low cost, high agility, good stealth, and no risk of casualties. Thus, in several recent local wars, there was an increasing trend to employ UAVs for completing military missions. During the Gulf War [1, 2], the US army deployed the “Pioneer” and the “Pointer” UAVs to conduct military tasks, such as battlefield reconnaissance, surveillance, artillery support, and target damage assessment. In the Kosovo war [3, 4], NATO employed over 200 UAVs during the war. In the Afghanistan war [5], the UAV named “Global Hawk” was used to directly destroy enemy targets. The outstanding performance of UAVs in current wars has proved their military value, and more UAVs are introduced and used to replace manned aircrafts for carrying out various military missions.When UAVs are used to perform attack missions on enemy targets, commanders need to consider the constraints on UAV load and the hanging points for weapons and should determine the type and quantity of weapons equipped in the UAV while optimizing the flight path for visiting the targets. In the UAV mission planning process, commanders also have to determine the type and quantity of weapons that the UAV delivers to each target, ensuring that these weapons can cause sufficient damage on the target and meet the mission’s damage requirements. Modern wars are usually joint operations of multiple services (army, navy, air force, etc.), and there are many cooperative actions among different military units. Thus, for most of the targets attacked by UAVs, the attacking actions are required to complete in specific time windows. In the military operations research field, most literatures related to UAV mission planning focused on task assignment, path planning, and routing separately. To the best of our knowledge, the UAV routing problem with weapon configuration and time window has not been studied.The UAV routing problems were usually solved based on models and algorithms utilized in vehicle routing problem (VRP). The weapon configuration in the UAV and allocation to the targets are quite different from the product delivery to customer in the common VRP. For a target, the attacking effect is different if it is attacked by different weapons. Table1 presents the combat ability matrix of three different weapons on two targets. It can be seen that if the destroy requirement for the bridge target is restricted over 90 in the mission, there are a number of combinations of weapons that can satisfy the requirement, such as 3 small smart bombs, 1 small smart bomb, 1 small precision guided bomb, and 1 laser-guided bomb. Thus, the weapons delivered to a target are not deterministic and are impacted by the weapon configuration and routing strategies of the UAV, while the types and quantities of products delivered to each customer are deterministic in the general VRP problem.Table 1
Weapon-target combat ability matrix.
Small smartbomb Small precision guided bomb Laser-guided bomb Bridge 0.35 0.65 0.95 Communication station 0.4 0.55 0.75Motivated by the practical requirement in military mission planning of UAV, we investigated the multidepot UAV routing problem with weapon configuration and time window (MD-URP-WC&TW), which can be viewed as a new extension on the traditional VRP. In MD-URP-WC&TW, three kinds of decisions should be cooperatively optimized, which are the weapon configuration strategy in the UAV, the routing strategy of target, and the allocation strategy of weapons to targets. The interaction among these decisions makes the modelling and solution of the problem more complex. In this paper, a mixed-integer linear programming model is developed to formulate the problem, and a powerful adaptive large neighborhood search (ALNS) based metaheuristic is proposed to obtain better feasible solutions.The paper is organized as follows. In Section2, the related literatures are reviewed. The formulated model is developed in Section 3, and the proposed ALNS algorithm, including its main steps, is presented in Section 4. The computational results are reported and analyzed in Section 5. Section 6 concludes the paper.


## 2. Literature Review

Multidepot UAV routing problem with consideration of weapon configuration and time window is related to main streams of literatures, which are UAV path planning/routing and UAV task assignment. A review of the literatures on these two fields is summarized below.The earlier studies in the field of UAV flight path optimization mainly focused on optimizing the UAV flight path from the control level. It is necessary to consider the influence of the turning angle, obstacle avoidance, and weather conditions (such as wind power level) on the UAV. Based on these constraints, an optimal flight path is found for the UAV [6]. Edison and Shima [7] studied the mission planning and path planning of multi-UAV in military operations. They fully considered flight parameters, such as the minimum turning radius, in the proposed mathematical model and solved the problem using a genetic algorithm. Zhang et al. [8] studied multi-UAV path planning, considering mobility, collision avoidance, and flight information sharing, and proposed the Cooperative and Geometric Learning Algorithm (CGLA) to solve the above problem. Moon et al. [9] developed a multilevel planning model for multi-UAV task assignment and path planning, taking into account practical constraints such as collision avoidance between UAVs, and solved the problem by the A∗ algorithm. Yang et al. [10] studied the path planning problem of UAV in terms of obstacle avoidance, decomposed the original goal and constraint function of UAV path planning into a new set of evaluation functions, and proposed the evolutionary algorithm for solving the problem.With the improvement in intelligent control technology for UAVs, UAVs can independently complete the flight between the target points. In recent years, studies on UAV path planning have begun to focus on tactical optimization in order to minimize the overall minimum flight distance by optimizing the sequence of UAV to visit the target. Shetty et al. [11] studied multi-UAV task assignment and routing problems based on target priority and distinguished the targets by their degrees of importance using the Tabu search algorithm. Mufalli et al. [12] studied the multi-UAV routing problem for target reconnaissance considering the load constraints of the UAV and solved the problem by the column generation and heuristic algorithm. Liu et al. [13] studied the UAV deployment and routing problem for road-traffic information collection. Subject to the number of UAVs and the maximum cruise distance, a multiobjective optimization model was developed. Moyo and Plessis [14] studied the inspection path optimization problem for the cable network of UAVs and described it as a traveling salesman problem (TSP). Guerriero et al. [15] proposed a system of UAVs that are able to communicate, self-organize, and cooperate. A multicriteria optimization model was developed to determine the distributed dynamic schedule of UAVs and ensure both spatial coverage and temporal coverage of specific targets. Evers et al. [16] studied multi-UAV path planning with target reconnaissance time windows. Luo et al. [17] studied the two-echelon routing problem of mounting UAV on a ground vehicle (GV), where the GV acts as the mobile depot for launching and recycling the UAV, while the UAV visits the targets for information collection.In order to facilitate multi-UAV collaborative task allocation during mission planning, Ghalenoei et al. [18] proposed the Discrete Invasive Weed Optimization Algorithm for specific target attributes and geographical locations. George et al. [19] proposed an online task assignment algorithm based on UAV task alliance to deal with unexpected tasks, which involves requesting adjacent UAVs to form task alliances and replanning the tasks. Zhong et al. [20] studied the UAV task assignment problem with dynamic changes in target value over time, taking into account various constraints including UAV flight altitude, maximum climb height, and maximum turning radius. Hu et al. [21] studied the assignment of UAV collaborative tasks using the hierarchical assignment method and solved the problem by an improved ant colony algorithm. Yin et al. [22] described the UAV collaborative task assignment problem as a multiobjective optimization problem and solved it using a Pareto-dominated multiobjective discrete particle swarm optimization algorithm. Jin [23] studied the distributed UAV task allocation problem where the tasks are divided into detection, attack, and verification.As far as current UAV mission planning and path planning studies are concerned, no study has focused on the integrated optimization of UAV flight path for target attack and airborne weapons configuration. Taking into account the type and quantity of weapons on board, during the UAV path planning process, there exists a new direction for traditional path planning, which is of great significance for improving the efficiency of UAV mission planning in the military.


## 3. Model Formulation

The MD-URP-WC&TW considers a set of targets, each of which must be attacked once by one UAV. The weapons delivered to the target must be able to destroy it over a required destroy level. There are multiple depots for the UAV, where the weapons are configured for each UAV, subject to the UAV’s constraints on payload and hanging points. An illustration of the MD-URP-WC&TW is presented in Figure1. In the MD-URP-WC&TW, the commander has to optimize the decisions on which depot the UAV leaves, which targets are visited in what sequence, what type and how many weapons are configured on the UAV, and what type and how many weapons are delivered to each target. The objective is to minimize the number of UAVs employed, the overall weapons consumed for destroying all the targets, and the total cost (time/distance) traveled by all UAVs.Figure 1
An illustration of the MD-URP-WC&TW.


### 3.1. Symbol Description

The notations and symbols utilized in the model formulation are presented as follows.(1)
Sets
N: the set of targets, and N={1,2,…,n}M: the set of depots, and M={n+1,n+2,…,n+m}U: the set of UAVs, and U={1,2,…,u}W: the set of different weapon types, and W={1,2,…,w}(2)
Parameters
ai: damage demand of target i, and i∈Nc: the payload capacity of the UAVg: the number of hanging points of the UAVtij: the time of UAV flying from target i to target j, and i,j∈N,i≠jfh: the cost of a weapon of type h, and h∈Wqh: the weight of a weapon of type h, and h∈Wbih: the combat ability of weapon h on target i, and i∈N,  h∈Wr: the duration time of UAVei: the earliest allowed hitting time of target i, and i∈Nli: the latest allowed hitting time of target i, and i∈Nsi: the spent time of UAV hitting target i, and i∈Nwki: the waiting time of UAV k hovering above target i, and k∈U, i∈NL: a large enough number(3)
Decision Variables
xijk: binary variable, which is equal to 1 if a target j is attacked after target i by UAV k and 0 otherwisetki: continuous variable, the moment of UAV k reaching target iykhi: integer variable, which denotes the number of weapons h on UAV k used to attack target i, and ykhi≥0.


### 3.2. Mathematical Model

The MD-URP-WC&TW can be formulated as the following mixed-integer programming model:(1)minZ=P1∑i=n+1n+m∑j=1n∑k=1uxijk+P2∑h=1w∑k=1u∑i=1nfhykhi+P3∑i=1n+m∑j=1n+m∑k=1utij+wki+sixijk(2)subject  to:∑k=1u∑i=0,i≠jn+mxijk=1,∀j∈N(3)∑k=1u∑j=0,i≠jn+mxijk=1,∀i∈N(4)∑i=1n+mxipk-∑j=1n+mxpjk=0,∀p∈N∪M,k∈U(5)∑h=1wqh∑i=1nykhi≤c,∀k∈U(6)∑h=1w∑i=1nykhi≤g,∀k∈U(7)∑k=1v∑h=1wbhiykhi≤ai,∀i∈N(8)ykhi≤L∑j=1nxijk,∀i∈N,k∈U,h∈W(9)∑i=0n+m∑j=0n+mtij+si+wkixijk≤r,∀k∈U(10)tki+tij+wki+si-L1-xijk≤tkj,∀i∈N(11)tki+wki≥ei,∀i∈N(12)tki+wki+si≤li,∀i∈N(13)tki≥0,∀i∈N,k∈U(14)ykhi≥0,∀k∈U,h∈W,i∈N(15)xijk∈0,1,∀i∈N,j∈N,k∈U.The objective function consists of three parts. The first part represents the total number of UAVs used in combat operations, the second part shows the total cost of the weapons used in combat operations, and the third part expresses the total flight time for all UAVs in combat operations.P1, P2, and P3 are the weight coefficients of each part to adjust the three parts of the objective function to the same number of units. Constraints (2) and (3) define that every target can be hit by one UAV. Flow conservation is guaranteed by constraints (4). Constraints (5) ensure that that the total weight of category l weapons carried by each UAV cannot exceed its load limit. Constraints (6) ensure that the number of weapons mounted on each UAV does not exceed the number of weapons hanging on the UAV. Constraints (7) regulate that the damage demand of each target must be fulfilled. Constraints (8) ensure that the UAV can only drop off weapons to the target visited by it. Constraints (9) guarantee that the endurance of the UAV must not be exceeded. Constraints (10) ensure that the arriving time of UAV k at target i is no later than the arriving time at target j if UAV k attacks target i after target j. Constraints (11) and (12) are time window constraints for the UAV to perform a task. Constraints (13), (14), and (15) are the constraints of decision variables


## 3.1. Symbol Description

The notations and symbols utilized in the model formulation are presented as follows.(1)
Sets
N: the set of targets, and N={1,2,…,n}M: the set of depots, and M={n+1,n+2,…,n+m}U: the set of UAVs, and U={1,2,…,u}W: the set of different weapon types, and W={1,2,…,w}(2)
Parameters
ai: damage demand of target i, and i∈Nc: the payload capacity of the UAVg: the number of hanging points of the UAVtij: the time of UAV flying from target i to target j, and i,j∈N,i≠jfh: the cost of a weapon of type h, and h∈Wqh: the weight of a weapon of type h, and h∈Wbih: the combat ability of weapon h on target i, and i∈N,  h∈Wr: the duration time of UAVei: the earliest allowed hitting time of target i, and i∈Nli: the latest allowed hitting time of target i, and i∈Nsi: the spent time of UAV hitting target i, and i∈Nwki: the waiting time of UAV k hovering above target i, and k∈U, i∈NL: a large enough number(3)
Decision Variables
xijk: binary variable, which is equal to 1 if a target j is attacked after target i by UAV k and 0 otherwisetki: continuous variable, the moment of UAV k reaching target iykhi: integer variable, which denotes the number of weapons h on UAV k used to attack target i, and ykhi≥0.


## 3.2. Mathematical Model

The MD-URP-WC&TW can be formulated as the following mixed-integer programming model:(1)minZ=P1∑i=n+1n+m∑j=1n∑k=1uxijk+P2∑h=1w∑k=1u∑i=1nfhykhi+P3∑i=1n+m∑j=1n+m∑k=1utij+wki+sixijk(2)subject  to:∑k=1u∑i=0,i≠jn+mxijk=1,∀j∈N(3)∑k=1u∑j=0,i≠jn+mxijk=1,∀i∈N(4)∑i=1n+mxipk-∑j=1n+mxpjk=0,∀p∈N∪M,k∈U(5)∑h=1wqh∑i=1nykhi≤c,∀k∈U(6)∑h=1w∑i=1nykhi≤g,∀k∈U(7)∑k=1v∑h=1wbhiykhi≤ai,∀i∈N(8)ykhi≤L∑j=1nxijk,∀i∈N,k∈U,h∈W(9)∑i=0n+m∑j=0n+mtij+si+wkixijk≤r,∀k∈U(10)tki+tij+wki+si-L1-xijk≤tkj,∀i∈N(11)tki+wki≥ei,∀i∈N(12)tki+wki+si≤li,∀i∈N(13)tki≥0,∀i∈N,k∈U(14)ykhi≥0,∀k∈U,h∈W,i∈N(15)xijk∈0,1,∀i∈N,j∈N,k∈U.The objective function consists of three parts. The first part represents the total number of UAVs used in combat operations, the second part shows the total cost of the weapons used in combat operations, and the third part expresses the total flight time for all UAVs in combat operations.P1, P2, and P3 are the weight coefficients of each part to adjust the three parts of the objective function to the same number of units. Constraints (2) and (3) define that every target can be hit by one UAV. Flow conservation is guaranteed by constraints (4). Constraints (5) ensure that that the total weight of category l weapons carried by each UAV cannot exceed its load limit. Constraints (6) ensure that the number of weapons mounted on each UAV does not exceed the number of weapons hanging on the UAV. Constraints (7) regulate that the damage demand of each target must be fulfilled. Constraints (8) ensure that the UAV can only drop off weapons to the target visited by it. Constraints (9) guarantee that the endurance of the UAV must not be exceeded. Constraints (10) ensure that the arriving time of UAV k at target i is no later than the arriving time at target j if UAV k attacks target i after target j. Constraints (11) and (12) are time window constraints for the UAV to perform a task. Constraints (13), (14), and (15) are the constraints of decision variables


## 4. Algorithm

ALNS is an extension of the large neighborhood search algorithm and is first proposed by Ropke and Pisinger [24], which has been widely employed for solving complex vehicle routing problems [25, 26]. The main procedure of ALNS is illustrated in Algorithm 1. The ALNS starts from an initial feasible solution and conducts iteratively search for better solutions. The initial feasible solution is usually generated by a constructive heuristic. In each iteration, the current solution is destroyed and repaired by heuristics, which are selected based on their past performances.Algorithm 1:Procedure of the ALNS.
Input: s i n i t i a l: initial solution; six neighborhood structures. Output: the best solution s∗. s ∗ ← s i n i t i a l; s c u r r e n t ← s i n i t i a l; initialize scores on neighborhood structures; whileacceptance standards not meet do select a neighborhood structure; modify  scurrent by chosen structure to generate snew; if  snew is accepted then s c u r r e n t ← s n e w; end if  Z(snew)≤Z(s∗)  then s ∗ ← s n e w; end update scores on neighborhood structures; end Return  s∗.


### 4.1. The Heuristic Algorithm for Constructing an Initial Solution

The heuristic algorithm for generating an initial solution aims to rapidly construct a feasible solution, which includes four main steps. First, weapons are assigned to each target according to its damage requirements based on some heuristic rules. Second, the targets are clustered to the depots through the clustering strategies. Third, a complete tour is constructed to visit all the targets assigned to a depot. Finally, the feasible flight path for each UAV is constructed.


#### 4.1.1. Weapon Allocation Strategy

The weapon assignment strategy is to determine the type and quantity of weapons used to attack the target and meet its damage requirement. Two strategies are designed to dispose and assign weapons to the targets.(a) Assigning Strategy Based on Destroy Effect. The assigning strategy based on destroy effect is to select the weapon with the highest destroy effect on the target and assign it to the target. The main procedure is illustrated in Algorithm 2.Algorithm 2:Procedure of the assigning strategy based on destroy effect.
Input:  ai, bim, for i∈N,  m∈W; Output:  watim: the number of weapon m assigned to target i. Set  watim=0(m∈W); m ∗ = arg ⁡ max ⁡ b i m ,   m ∈ W; w a t i m ∗ = a i / b i m ∗; m ′ = arg ⁡ min ⁡ f m ∣ m ∈ W   a n d   a i - w a t i m ∗ b i m ∗ - b i m ≤ 0; w a t i m ′++; Return  watim(m∈W).(b) Assigning Strategy Based on Cost-Effectiveness. In the assigning strategy based on cost-effectiveness, a measurement named as “cost-effectiveness” is introduced as follows:(16)effim=bimfm.The weapon with the highest “cost-effectiveness” is preferentially selected and assigned to the target. The main procedure for the assigning strategy based on cost-effectiveness is illustrated in Algorithm3.Algorithm 3:Procedure of the assigning strategy based on cost-effectiveness.
Input: e f f i m: the cost-effectiveness ratio of weapon m against target i; q m: the weight of weapon m, m∈W; c: the UAV’s payload; g: the number of hanging points in the UAV. Output: w a t i m: the number of weapon m assigned to target i. Set  CWH=-1, watim=0(m∈W); while  (CWH<0)  do m ∗ = arg ⁡ max ⁡ e f f i m ,   m ∈ W; w a t i m ∗ = a i / b i m ∗; if  (∑m=1Mqmwatim≤c and ∑m=1Mwatim≤g) then C W H = 1; end else w a t i m ∗ = 0; W = W / m ∗; end end Return  watim(m∈W).


#### 4.1.2. Target Clustering Strategy

Three target clustering strategies are designed for assigning targets to each depot, which are distance based clustering, greedy search clustering, and virtual feedback clustering.(a) Distance Based Clustering (DC). The basic idea of the DC strategy is to assign each target to its closest depot. The distance between each target point and each depot is first calculated, and then the targets are clustered to their closest depot.(b) Greedy Search Clustering (GSC). In the GSC strategy, each depot is first allowed to select one target randomly, and then the target closest to the selected target is added. The operation is repeated until all targets are assigned to the appropriate depots. The GSC strategy is illustrated in Figure 2.Figure 2
The operation process for the GSC strategy.(c) Virtual Feedback Clustering (VFC). The basic idea of the VFC strategy is to assume that there is a virtual depot around the known depots, and all UAVs performing the striking task are from the virtual depot. We can obtain S, a set of path planning schemes for multiple UAVs departing from the virtual depot. In addition, S={s1,s2,…,su}, where u denotes the quantity of UAVs used. Then, the virtual depot is changed to the actual depot for each route in S. The total flying distance is computed every time after the depot is changed. The targets corresponding to the changing scheme with the shortest distance are assigned to the appropriate depots. The above operation is repeated until all elements in set S are assigned.


#### 4.1.3. Target Sequencing Strategy

The target sequencing strategy aims to determine the sequence in which the UAV visits the targets, subject to their time windows. There are four strategies for sequencing the targets, which are sequencing based on distance (SD), sequencing based on earliest striking time (SEST), sequencing based on latest striking time (SLST), and sequencing based on time window width (STWW). The SD strategy aims to sort all targets by the distance to the depot in an ascending order. A UAV first visits the closest target and then the next target at a longer distance after departing from the depot. The UAV visits the remaining targets in the same manner until all targets are visited. The SEST strategy is to visit all targets in an ascending order by the earliest striking time of the target; that is, the targets with earlier striking time should be attacked earlier. In the SLST strategy, all targets are visited in a descending order of the latest striking time. The STWW strategy is to visit all targets in an ascending order of the time window width.


#### 4.1.4. Feasible Route Construction (FRC)

In this step, a feasible route for each UAV is constructed, while considering the constraints on endurance, payload, the number of hanging points in UAV, and the time window of the target. The main procedure of the FRC algorithm is presented in Algorithm4.Algorithm 4:Procedure of the FRC algorithm.
Input: n: the total number of targets; E 5 + W × n: the basic information matrix related with the target. The first line(E[0,n]) of the matrix is the target’s number; The second line (E[1,n]) of the matrix stores the earliest allowed strike time of the target; The third line ( E [ 2 , n ] ) of the matrix stores the target’s latest hit time; The fourth line(E[3,n]) of the matrix stores the target time that UCAV hit the goal; The fifth line(E[4,n]) of the matrix stores the time it takes UCAV to fly to the target; The sixth line(E[5,n]) of the matrix stores the time it takes UCAV to fly from the previous target to the target; The seventh line(E[6,n]) of the matrix stores the total number of weapons assigned to the target; The eighth line(E[7,n]) stores the total weight of the weapon assigned to the target point. c u m m T o D e p o t: time accumulated from depot to target i and i′ to depot; c u m m T o N e x t: time accumulated from target i to target i′; c u m m E x e c u t e: total time for all target points visited by UAV; c u m m W e a p o n: the total numbers of weapons after visiting all targets; c u m m Weight: The total weight of weapons after visiting all targets; e n d u r: UAV endurance; p a y l o a d: UAV maximum payload; h a r d p o i n t: The number of UAV hanging points; n u m U C A V: The number of UAV. Output: ζ: A matrix set containing  numUCAV number of new information matrix E 4 × ( a - b ) v, where  v=1,2,…,numUAV. Set  a=n;  b=0;  numUAV=1;  cummToDepot=0;  cummToNext=0;  cummExecute=0; while  (b<n-1)  do while  (cumm<endur)  do for  (i=b; i<a; i++)  do c u m m E x e c u t e = c u m m E x e c u t e + E [ 3 , i ];  cummToDepot=E[4,b]+E[4,a-1]; c u m m T o N e x t = c u m m T o N e x t + E [ 5 , i ];  cummWeapon=cummWeapon+E[6,i]; c u m m Weight = c u m m Weight + E [ 7 , i ]; end c u m m = c u m m E x e c u t e + c u m m T o D e p o t + c u m m T o N e x t; If  (cummWeapon>hardpoint  or  cummWeight>payload or c u m m ≥ e n d u r  or  cumm-E[4,a-1]<E[1,a-1]  or  cumm-E[4,a-1]>E[2,a-1]) do a - -;  cummExecute=0;  cummToDepot=0;  cummToNext=0; c u m m W e a p o n = 0;  cummWeight=0; end else b = a;  numUCAV++;  a=n; Output a new encoding matrix  E4×(a-b)v; end end c u m m E x e c u t e = 0;  cummToDepot=0;  cummToNext=0; end Return  ζ.The basic idea of FRC is to let a UAV depart from the depot and visit the targets one by one. The total weight and quantity of the weapons carried by the UAV and its total actual flight time are calculated when it arrives at a target. Then, constraints (5), (6), (9), (11), and (12) are checked, and the target is added to the UAV’s route if all these constraints are satisfied. If any constraint is not met, the UAV returns to the depot and the target is assigned to a new UAV and its route. The operation is repeated until all targets are visited.


### 4.2. Neighbourhood Structures

In ALNS, the neighborhood structures are employed to slightly diversify the starting point of local search. In this section, six neighborhood structures are designed for effectively searching the solution space.(a) Depot Exchanging (DE). In the DE operator, firstly, one depot is selected randomly, and one flight route is also selected from the routes starting at this depot. In this way, we select m depots and m routes. Then the depots corresponding to the m selected routes are exchanged. We further verify whether the new routes satisfy the constraints on endurance of the UAV and the time windows of the targets. If the constraints are met, a new solution is obtained. The depots are exchanged again if any constraint is not satisfied. The above steps are repeated until a new feasible solution is obtained. It should be noted that it is impossible to guarantee that each DE operation obtains an improved feasible solution, and sometimes it is even not possible to obtain a feasible solution.(b) Targets Reclustering (TRC). The TRC operator is to construct a new feasible solution by reclustering all target nodes. When the targets are reclustered, target sequencing and feasible route construction strategies in the above section are conducted to generate a new solution.(c) Weapons Reconfiguration (WR). The basic idea of the WR operator is to first delete the weapon assignment schemes for k(1≤k<n) targets and invoke the appropriate weapon allocation strategies to reassign weapons for these targets. A new weapon assignment scheme follows the “deletion” and “reassignment” operations.(d) Reducing the Number of Weapons (RNW). The basic idea of the RNW structure is to reduce the total cost by adjusting the quantity of weapons assigned to the target. In the RNW structure, we first select the target with the most weapons. Then, the type and number of weapons assigned to this target are changed in an attempt to reduce the quantity of weapons. If the RNW operation successfully reduces the quantity of weapons at a target, it provides potentials for reducing the cost of weapons, the quantity of UAVs, and the flying distance.(e) Reducing the Cost of Weapons (RCW). The basic idea of the RCW structure is to reduce the total cost by replacing high-cost weapons with low-cost weapons. In the RCW structure, we first select the target with the highest cost of weapons in the weapon assignment schemes and then attempt to replace the high-cost weapons with combination of low-cost weapons. It should be noted that the RCW operation cannot guarantee that the weapon exchange always reduces the total cost. For example, the cost of weapons at a target may be lowered, and in the same time the weight and number of the weapons at this target may increase, which may make the value of the objective increase.(f) Reducing the Weight of Weapons (RWW). The RWW structure is a variant of the RCW structure. Its basic idea is to reduce the quantity of weapons and, thus, improve the objective by replacing the heavy weapons with relatively lighter weapons in the weapon assignment schemes. In the RWW structure, we first select the target with the highest weight of weapons and then attempt to replace the heaviest weapons with relatively lighter weapons. The damage requirements for the target point must be verified when the weapons are being replaced. In other words, the adjusted weapon assignment schemes should meet Constraints (5) and (7).


### 4.3. Adaptive Learning Strategy

The six neighborhood structures provide potentials to improve a solution from different perspectives. The first neighborhood structure, DE, may improve the solution by adjusting the UAV flight loop. The second neighborhood structure, TRC, may improve the solution by changing the depot. The third to sixth neighborhood structures, WR, RNW, RCW, and RWW, may improve the solution by adjusting the weapon assignment scheme. Different neighborhood structures may lead to different improvement results. To achieve more extensive neighborhood search, this section presents an adaptive learning strategy to dynamically adjust the weights of the six structures during the neighborhood search process.The six neighborhood structures are randomly selected to adjust the solution under the “roulette” principle. Given the weights of the neighborhood structures,wi  (i=1,…,6), the probability of structure j to be selected is ωj/∑i=1hωi. The weights of the six neighborhood structures are adaptively updated every φevo iteration by evaluating their performance in these earlier φevo iterations. We note φevo iterations as an evaluation segment. Assuming the initial weight of every neighborhood structure is 1, in the jth evolution, the weight of structure i is as follows:(17)ωi,j+1=ωij1-r+rσijεij,where rr∈[0,1] is a constant, εij is the number of times the neighborhood structure i is invoked in the jth evolution, and σij is the score of the neighborhood structure i in the jth evolution.The neighborhood structurei in the jth evolution is scored according to the following scoring rules:( 1 )  σij0=0: the initial score of structure i(i=1,2,…,6) at the beginning of the jth evaluation is set to be 0.( 2 )  σij1=30: 30 scores are added to structure i if the new solution is the best one generated in the jth evolution.( 3 )  σij1=20: 20 scores are added to structure i if the new solution is better than the average one generated in the jth evolution.( 4 )  σij1=10: 10 scores are added to structure i if the new solution is worse than the average one generated in the jth evolution.( 5 )  σij1=5: 5 scores are added to structure i if the new solution is better than the worst one generated in the jth evolution but can be accepted by the algorithm.


### 4.4. Acceptance Standard and Criteria for Termination

#### 4.4.1. Acceptance Standard for Solutions

In the ALNS algorithm, the acceptance standard for the generated solutions is defined on the basis of the record-to-record algorithm proposed by Dueck [27]. It is assumed that g∗ is the objective function value of the current optimal solution, called record. It is assumed that δ is the difference between the objective function value of the current solution and g∗, called deviation.It is assumed thatR is the solution, R′ is the neighborhood solution to R, and gR′ is the objective function value of R′.WhengR′<g∗+δ, the neighborhood solution R′ can be accepted, where δ=0.1×g∗. And g∗ is only allowed to be updated when gR′<g∗.


#### 4.4.2. Criteria for Termination of Algorithm Search

In the study, there are two criteria for termination of the ALNS algorithm:( 1 ) The iteration process should be terminated when the quality of the solution does not improve after the number of iterations reaches a given value.( 2 ) The iteration process should be terminated when the number of iterations reaches a given value.


## 4.1. The Heuristic Algorithm for Constructing an Initial Solution

The heuristic algorithm for generating an initial solution aims to rapidly construct a feasible solution, which includes four main steps. First, weapons are assigned to each target according to its damage requirements based on some heuristic rules. Second, the targets are clustered to the depots through the clustering strategies. Third, a complete tour is constructed to visit all the targets assigned to a depot. Finally, the feasible flight path for each UAV is constructed.


### 4.1.1. Weapon Allocation Strategy

The weapon assignment strategy is to determine the type and quantity of weapons used to attack the target and meet its damage requirement. Two strategies are designed to dispose and assign weapons to the targets.(a) Assigning Strategy Based on Destroy Effect. The assigning strategy based on destroy effect is to select the weapon with the highest destroy effect on the target and assign it to the target. The main procedure is illustrated in Algorithm 2.Algorithm 2:Procedure of the assigning strategy based on destroy effect.
Input:  ai, bim, for i∈N,  m∈W; Output:  watim: the number of weapon m assigned to target i. Set  watim=0(m∈W); m ∗ = arg ⁡ max ⁡ b i m ,   m ∈ W; w a t i m ∗ = a i / b i m ∗; m ′ = arg ⁡ min ⁡ f m ∣ m ∈ W   a n d   a i - w a t i m ∗ b i m ∗ - b i m ≤ 0; w a t i m ′++; Return  watim(m∈W).(b) Assigning Strategy Based on Cost-Effectiveness. In the assigning strategy based on cost-effectiveness, a measurement named as “cost-effectiveness” is introduced as follows:(16)effim=bimfm.The weapon with the highest “cost-effectiveness” is preferentially selected and assigned to the target. The main procedure for the assigning strategy based on cost-effectiveness is illustrated in Algorithm3.Algorithm 3:Procedure of the assigning strategy based on cost-effectiveness.
Input: e f f i m: the cost-effectiveness ratio of weapon m against target i; q m: the weight of weapon m, m∈W; c: the UAV’s payload; g: the number of hanging points in the UAV. Output: w a t i m: the number of weapon m assigned to target i. Set  CWH=-1, watim=0(m∈W); while  (CWH<0)  do m ∗ = arg ⁡ max ⁡ e f f i m ,   m ∈ W; w a t i m ∗ = a i / b i m ∗; if  (∑m=1Mqmwatim≤c and ∑m=1Mwatim≤g) then C W H = 1; end else w a t i m ∗ = 0; W = W / m ∗; end end Return  watim(m∈W).


### 4.1.2. Target Clustering Strategy

Three target clustering strategies are designed for assigning targets to each depot, which are distance based clustering, greedy search clustering, and virtual feedback clustering.(a) Distance Based Clustering (DC). The basic idea of the DC strategy is to assign each target to its closest depot. The distance between each target point and each depot is first calculated, and then the targets are clustered to their closest depot.(b) Greedy Search Clustering (GSC). In the GSC strategy, each depot is first allowed to select one target randomly, and then the target closest to the selected target is added. The operation is repeated until all targets are assigned to the appropriate depots. The GSC strategy is illustrated in Figure 2.Figure 2
The operation process for the GSC strategy.(c) Virtual Feedback Clustering (VFC). The basic idea of the VFC strategy is to assume that there is a virtual depot around the known depots, and all UAVs performing the striking task are from the virtual depot. We can obtain S, a set of path planning schemes for multiple UAVs departing from the virtual depot. In addition, S={s1,s2,…,su}, where u denotes the quantity of UAVs used. Then, the virtual depot is changed to the actual depot for each route in S. The total flying distance is computed every time after the depot is changed. The targets corresponding to the changing scheme with the shortest distance are assigned to the appropriate depots. The above operation is repeated until all elements in set S are assigned.


### 4.1.3. Target Sequencing Strategy

The target sequencing strategy aims to determine the sequence in which the UAV visits the targets, subject to their time windows. There are four strategies for sequencing the targets, which are sequencing based on distance (SD), sequencing based on earliest striking time (SEST), sequencing based on latest striking time (SLST), and sequencing based on time window width (STWW). The SD strategy aims to sort all targets by the distance to the depot in an ascending order. A UAV first visits the closest target and then the next target at a longer distance after departing from the depot. The UAV visits the remaining targets in the same manner until all targets are visited. The SEST strategy is to visit all targets in an ascending order by the earliest striking time of the target; that is, the targets with earlier striking time should be attacked earlier. In the SLST strategy, all targets are visited in a descending order of the latest striking time. The STWW strategy is to visit all targets in an ascending order of the time window width.


### 4.1.4. Feasible Route Construction (FRC)

In this step, a feasible route for each UAV is constructed, while considering the constraints on endurance, payload, the number of hanging points in UAV, and the time window of the target. The main procedure of the FRC algorithm is presented in Algorithm4.Algorithm 4:Procedure of the FRC algorithm.
Input: n: the total number of targets; E 5 + W × n: the basic information matrix related with the target. The first line(E[0,n]) of the matrix is the target’s number; The second line (E[1,n]) of the matrix stores the earliest allowed strike time of the target; The third line ( E [ 2 , n ] ) of the matrix stores the target’s latest hit time; The fourth line(E[3,n]) of the matrix stores the target time that UCAV hit the goal; The fifth line(E[4,n]) of the matrix stores the time it takes UCAV to fly to the target; The sixth line(E[5,n]) of the matrix stores the time it takes UCAV to fly from the previous target to the target; The seventh line(E[6,n]) of the matrix stores the total number of weapons assigned to the target; The eighth line(E[7,n]) stores the total weight of the weapon assigned to the target point. c u m m T o D e p o t: time accumulated from depot to target i and i′ to depot; c u m m T o N e x t: time accumulated from target i to target i′; c u m m E x e c u t e: total time for all target points visited by UAV; c u m m W e a p o n: the total numbers of weapons after visiting all targets; c u m m Weight: The total weight of weapons after visiting all targets; e n d u r: UAV endurance; p a y l o a d: UAV maximum payload; h a r d p o i n t: The number of UAV hanging points; n u m U C A V: The number of UAV. Output: ζ: A matrix set containing  numUCAV number of new information matrix E 4 × ( a - b ) v, where  v=1,2,…,numUAV. Set  a=n;  b=0;  numUAV=1;  cummToDepot=0;  cummToNext=0;  cummExecute=0; while  (b<n-1)  do while  (cumm<endur)  do for  (i=b; i<a; i++)  do c u m m E x e c u t e = c u m m E x e c u t e + E [ 3 , i ];  cummToDepot=E[4,b]+E[4,a-1]; c u m m T o N e x t = c u m m T o N e x t + E [ 5 , i ];  cummWeapon=cummWeapon+E[6,i]; c u m m Weight = c u m m Weight + E [ 7 , i ]; end c u m m = c u m m E x e c u t e + c u m m T o D e p o t + c u m m T o N e x t; If  (cummWeapon>hardpoint  or  cummWeight>payload or c u m m ≥ e n d u r  or  cumm-E[4,a-1]<E[1,a-1]  or  cumm-E[4,a-1]>E[2,a-1]) do a - -;  cummExecute=0;  cummToDepot=0;  cummToNext=0; c u m m W e a p o n = 0;  cummWeight=0; end else b = a;  numUCAV++;  a=n; Output a new encoding matrix  E4×(a-b)v; end end c u m m E x e c u t e = 0;  cummToDepot=0;  cummToNext=0; end Return  ζ.The basic idea of FRC is to let a UAV depart from the depot and visit the targets one by one. The total weight and quantity of the weapons carried by the UAV and its total actual flight time are calculated when it arrives at a target. Then, constraints (5), (6), (9), (11), and (12) are checked, and the target is added to the UAV’s route if all these constraints are satisfied. If any constraint is not met, the UAV returns to the depot and the target is assigned to a new UAV and its route. The operation is repeated until all targets are visited.


## 4.1.1. Weapon Allocation Strategy

The weapon assignment strategy is to determine the type and quantity of weapons used to attack the target and meet its damage requirement. Two strategies are designed to dispose and assign weapons to the targets.(a) Assigning Strategy Based on Destroy Effect. The assigning strategy based on destroy effect is to select the weapon with the highest destroy effect on the target and assign it to the target. The main procedure is illustrated in Algorithm 2.Algorithm 2:Procedure of the assigning strategy based on destroy effect.
Input:  ai, bim, for i∈N,  m∈W; Output:  watim: the number of weapon m assigned to target i. Set  watim=0(m∈W); m ∗ = arg ⁡ max ⁡ b i m ,   m ∈ W; w a t i m ∗ = a i / b i m ∗; m ′ = arg ⁡ min ⁡ f m ∣ m ∈ W   a n d   a i - w a t i m ∗ b i m ∗ - b i m ≤ 0; w a t i m ′++; Return  watim(m∈W).(b) Assigning Strategy Based on Cost-Effectiveness. In the assigning strategy based on cost-effectiveness, a measurement named as “cost-effectiveness” is introduced as follows:(16)effim=bimfm.The weapon with the highest “cost-effectiveness” is preferentially selected and assigned to the target. The main procedure for the assigning strategy based on cost-effectiveness is illustrated in Algorithm3.Algorithm 3:Procedure of the assigning strategy based on cost-effectiveness.
Input: e f f i m: the cost-effectiveness ratio of weapon m against target i; q m: the weight of weapon m, m∈W; c: the UAV’s payload; g: the number of hanging points in the UAV. Output: w a t i m: the number of weapon m assigned to target i. Set  CWH=-1, watim=0(m∈W); while  (CWH<0)  do m ∗ = arg ⁡ max ⁡ e f f i m ,   m ∈ W; w a t i m ∗ = a i / b i m ∗; if  (∑m=1Mqmwatim≤c and ∑m=1Mwatim≤g) then C W H = 1; end else w a t i m ∗ = 0; W = W / m ∗; end end Return  watim(m∈W).


## 4.1.2. Target Clustering Strategy

Three target clustering strategies are designed for assigning targets to each depot, which are distance based clustering, greedy search clustering, and virtual feedback clustering.(a) Distance Based Clustering (DC). The basic idea of the DC strategy is to assign each target to its closest depot. The distance between each target point and each depot is first calculated, and then the targets are clustered to their closest depot.(b) Greedy Search Clustering (GSC). In the GSC strategy, each depot is first allowed to select one target randomly, and then the target closest to the selected target is added. The operation is repeated until all targets are assigned to the appropriate depots. The GSC strategy is illustrated in Figure 2.Figure 2
The operation process for the GSC strategy.(c) Virtual Feedback Clustering (VFC). The basic idea of the VFC strategy is to assume that there is a virtual depot around the known depots, and all UAVs performing the striking task are from the virtual depot. We can obtain S, a set of path planning schemes for multiple UAVs departing from the virtual depot. In addition, S={s1,s2,…,su}, where u denotes the quantity of UAVs used. Then, the virtual depot is changed to the actual depot for each route in S. The total flying distance is computed every time after the depot is changed. The targets corresponding to the changing scheme with the shortest distance are assigned to the appropriate depots. The above operation is repeated until all elements in set S are assigned.


## 4.1.3. Target Sequencing Strategy

The target sequencing strategy aims to determine the sequence in which the UAV visits the targets, subject to their time windows. There are four strategies for sequencing the targets, which are sequencing based on distance (SD), sequencing based on earliest striking time (SEST), sequencing based on latest striking time (SLST), and sequencing based on time window width (STWW). The SD strategy aims to sort all targets by the distance to the depot in an ascending order. A UAV first visits the closest target and then the next target at a longer distance after departing from the depot. The UAV visits the remaining targets in the same manner until all targets are visited. The SEST strategy is to visit all targets in an ascending order by the earliest striking time of the target; that is, the targets with earlier striking time should be attacked earlier. In the SLST strategy, all targets are visited in a descending order of the latest striking time. The STWW strategy is to visit all targets in an ascending order of the time window width.


## 4.1.4. Feasible Route Construction (FRC)

In this step, a feasible route for each UAV is constructed, while considering the constraints on endurance, payload, the number of hanging points in UAV, and the time window of the target. The main procedure of the FRC algorithm is presented in Algorithm4.Algorithm 4:Procedure of the FRC algorithm.
Input: n: the total number of targets; E 5 + W × n: the basic information matrix related with the target. The first line(E[0,n]) of the matrix is the target’s number; The second line (E[1,n]) of the matrix stores the earliest allowed strike time of the target; The third line ( E [ 2 , n ] ) of the matrix stores the target’s latest hit time; The fourth line(E[3,n]) of the matrix stores the target time that UCAV hit the goal; The fifth line(E[4,n]) of the matrix stores the time it takes UCAV to fly to the target; The sixth line(E[5,n]) of the matrix stores the time it takes UCAV to fly from the previous target to the target; The seventh line(E[6,n]) of the matrix stores the total number of weapons assigned to the target; The eighth line(E[7,n]) stores the total weight of the weapon assigned to the target point. c u m m T o D e p o t: time accumulated from depot to target i and i′ to depot; c u m m T o N e x t: time accumulated from target i to target i′; c u m m E x e c u t e: total time for all target points visited by UAV; c u m m W e a p o n: the total numbers of weapons after visiting all targets; c u m m Weight: The total weight of weapons after visiting all targets; e n d u r: UAV endurance; p a y l o a d: UAV maximum payload; h a r d p o i n t: The number of UAV hanging points; n u m U C A V: The number of UAV. Output: ζ: A matrix set containing  numUCAV number of new information matrix E 4 × ( a - b ) v, where  v=1,2,…,numUAV. Set  a=n;  b=0;  numUAV=1;  cummToDepot=0;  cummToNext=0;  cummExecute=0; while  (b<n-1)  do while  (cumm<endur)  do for  (i=b; i<a; i++)  do c u m m E x e c u t e = c u m m E x e c u t e + E [ 3 , i ];  cummToDepot=E[4,b]+E[4,a-1]; c u m m T o N e x t = c u m m T o N e x t + E [ 5 , i ];  cummWeapon=cummWeapon+E[6,i]; c u m m Weight = c u m m Weight + E [ 7 , i ]; end c u m m = c u m m E x e c u t e + c u m m T o D e p o t + c u m m T o N e x t; If  (cummWeapon>hardpoint  or  cummWeight>payload or c u m m ≥ e n d u r  or  cumm-E[4,a-1]<E[1,a-1]  or  cumm-E[4,a-1]>E[2,a-1]) do a - -;  cummExecute=0;  cummToDepot=0;  cummToNext=0; c u m m W e a p o n = 0;  cummWeight=0; end else b = a;  numUCAV++;  a=n; Output a new encoding matrix  E4×(a-b)v; end end c u m m E x e c u t e = 0;  cummToDepot=0;  cummToNext=0; end Return  ζ.The basic idea of FRC is to let a UAV depart from the depot and visit the targets one by one. The total weight and quantity of the weapons carried by the UAV and its total actual flight time are calculated when it arrives at a target. Then, constraints (5), (6), (9), (11), and (12) are checked, and the target is added to the UAV’s route if all these constraints are satisfied. If any constraint is not met, the UAV returns to the depot and the target is assigned to a new UAV and its route. The operation is repeated until all targets are visited.


## 4.2. Neighbourhood Structures

In ALNS, the neighborhood structures are employed to slightly diversify the starting point of local search. In this section, six neighborhood structures are designed for effectively searching the solution space.(a) Depot Exchanging (DE). In the DE operator, firstly, one depot is selected randomly, and one flight route is also selected from the routes starting at this depot. In this way, we select m depots and m routes. Then the depots corresponding to the m selected routes are exchanged. We further verify whether the new routes satisfy the constraints on endurance of the UAV and the time windows of the targets. If the constraints are met, a new solution is obtained. The depots are exchanged again if any constraint is not satisfied. The above steps are repeated until a new feasible solution is obtained. It should be noted that it is impossible to guarantee that each DE operation obtains an improved feasible solution, and sometimes it is even not possible to obtain a feasible solution.(b) Targets Reclustering (TRC). The TRC operator is to construct a new feasible solution by reclustering all target nodes. When the targets are reclustered, target sequencing and feasible route construction strategies in the above section are conducted to generate a new solution.(c) Weapons Reconfiguration (WR). The basic idea of the WR operator is to first delete the weapon assignment schemes for k(1≤k<n) targets and invoke the appropriate weapon allocation strategies to reassign weapons for these targets. A new weapon assignment scheme follows the “deletion” and “reassignment” operations.(d) Reducing the Number of Weapons (RNW). The basic idea of the RNW structure is to reduce the total cost by adjusting the quantity of weapons assigned to the target. In the RNW structure, we first select the target with the most weapons. Then, the type and number of weapons assigned to this target are changed in an attempt to reduce the quantity of weapons. If the RNW operation successfully reduces the quantity of weapons at a target, it provides potentials for reducing the cost of weapons, the quantity of UAVs, and the flying distance.(e) Reducing the Cost of Weapons (RCW). The basic idea of the RCW structure is to reduce the total cost by replacing high-cost weapons with low-cost weapons. In the RCW structure, we first select the target with the highest cost of weapons in the weapon assignment schemes and then attempt to replace the high-cost weapons with combination of low-cost weapons. It should be noted that the RCW operation cannot guarantee that the weapon exchange always reduces the total cost. For example, the cost of weapons at a target may be lowered, and in the same time the weight and number of the weapons at this target may increase, which may make the value of the objective increase.(f) Reducing the Weight of Weapons (RWW). The RWW structure is a variant of the RCW structure. Its basic idea is to reduce the quantity of weapons and, thus, improve the objective by replacing the heavy weapons with relatively lighter weapons in the weapon assignment schemes. In the RWW structure, we first select the target with the highest weight of weapons and then attempt to replace the heaviest weapons with relatively lighter weapons. The damage requirements for the target point must be verified when the weapons are being replaced. In other words, the adjusted weapon assignment schemes should meet Constraints (5) and (7).


## 4.3. Adaptive Learning Strategy

The six neighborhood structures provide potentials to improve a solution from different perspectives. The first neighborhood structure, DE, may improve the solution by adjusting the UAV flight loop. The second neighborhood structure, TRC, may improve the solution by changing the depot. The third to sixth neighborhood structures, WR, RNW, RCW, and RWW, may improve the solution by adjusting the weapon assignment scheme. Different neighborhood structures may lead to different improvement results. To achieve more extensive neighborhood search, this section presents an adaptive learning strategy to dynamically adjust the weights of the six structures during the neighborhood search process.The six neighborhood structures are randomly selected to adjust the solution under the “roulette” principle. Given the weights of the neighborhood structures,wi  (i=1,…,6), the probability of structure j to be selected is ωj/∑i=1hωi. The weights of the six neighborhood structures are adaptively updated every φevo iteration by evaluating their performance in these earlier φevo iterations. We note φevo iterations as an evaluation segment. Assuming the initial weight of every neighborhood structure is 1, in the jth evolution, the weight of structure i is as follows:(17)ωi,j+1=ωij1-r+rσijεij,where rr∈[0,1] is a constant, εij is the number of times the neighborhood structure i is invoked in the jth evolution, and σij is the score of the neighborhood structure i in the jth evolution.The neighborhood structurei in the jth evolution is scored according to the following scoring rules:( 1 )  σij0=0: the initial score of structure i(i=1,2,…,6) at the beginning of the jth evaluation is set to be 0.( 2 )  σij1=30: 30 scores are added to structure i if the new solution is the best one generated in the jth evolution.( 3 )  σij1=20: 20 scores are added to structure i if the new solution is better than the average one generated in the jth evolution.( 4 )  σij1=10: 10 scores are added to structure i if the new solution is worse than the average one generated in the jth evolution.( 5 )  σij1=5: 5 scores are added to structure i if the new solution is better than the worst one generated in the jth evolution but can be accepted by the algorithm.


## 4.4. Acceptance Standard and Criteria for Termination

### 4.4.1. Acceptance Standard for Solutions

In the ALNS algorithm, the acceptance standard for the generated solutions is defined on the basis of the record-to-record algorithm proposed by Dueck [27]. It is assumed that g∗ is the objective function value of the current optimal solution, called record. It is assumed that δ is the difference between the objective function value of the current solution and g∗, called deviation.It is assumed thatR is the solution, R′ is the neighborhood solution to R, and gR′ is the objective function value of R′.WhengR′<g∗+δ, the neighborhood solution R′ can be accepted, where δ=0.1×g∗. And g∗ is only allowed to be updated when gR′<g∗.


### 4.4.2. Criteria for Termination of Algorithm Search

In the study, there are two criteria for termination of the ALNS algorithm:( 1 ) The iteration process should be terminated when the quality of the solution does not improve after the number of iterations reaches a given value.( 2 ) The iteration process should be terminated when the number of iterations reaches a given value.


## 4.4.1. Acceptance Standard for Solutions

In the ALNS algorithm, the acceptance standard for the generated solutions is defined on the basis of the record-to-record algorithm proposed by Dueck [27]. It is assumed that g∗ is the objective function value of the current optimal solution, called record. It is assumed that δ is the difference between the objective function value of the current solution and g∗, called deviation.It is assumed thatR is the solution, R′ is the neighborhood solution to R, and gR′ is the objective function value of R′.WhengR′<g∗+δ, the neighborhood solution R′ can be accepted, where δ=0.1×g∗. And g∗ is only allowed to be updated when gR′<g∗.


## 4.4.2. Criteria for Termination of Algorithm Search

In the study, there are two criteria for termination of the ALNS algorithm:( 1 ) The iteration process should be terminated when the quality of the solution does not improve after the number of iterations reaches a given value.( 2 ) The iteration process should be terminated when the number of iterations reaches a given value.


## 5. Experiments

In this section, computational experiments are conducted to test the performance of the proposed algorithms. All the algorithms are coded with Visual C# 4.0 and the test environment is set up on a computer with Intel Core i7-4790 CPU, 3.60 GHz, 32 GB RAM, running on Windows 7.


### 5.1. Experimental Design

In order to fully test the performance of the proposed algorithms, instances with four different sizes are randomly generated, respectively: 10 targets, 20 targets, 50 targets, and 100 targets. Three different types of UAVs were utilized, which are UAVs with 4 hanging points and 600 kg loads, 6 hanging points and 900 kg loads, and 8 hanging points and 1200 kg loads. Three sizes of combat areas, 500 × 300 km2, 800 × 500 km2, and 1200 × 800 km2, are utilized. The experimental scale settings are shown in Table 2. The values of parameters for the weapons are illustrated in Tables 3 and 4. In the experiment, the service time of targets (unit: hours) is generated randomly in (0,1]. The target’s time window is also generated randomly between 0 hours and 12 hours. Meanwhile, the following restrictions are considered in the random generation process: (1) the earliest allowed strike time, ei, for target i is no less than the time-consumed by the UAV flying from the depot to the target, t0i; (2) the difference between the latest required strike time of target i, li, and its earliest allowed attack time, ei, is no more than τ  (τ=5 hours) and is no less than the service time Si.Table 2
Experimental scale.
Number of targets Area(km2) Number of stations φ l e a r n Small scale 10 500 × 300 2 2000 20 500 × 300 3 10000 Medium scale 50 800 × 500 5 15000 Large scale 100 1200 × 800 10 20000Table 3
UAV-related parameters.
Name Value of parameter s Payload capacity (kg) 600; 900; 1200 Number of hanging points 4; 6; 8 Weapons W1; W2; W3 Cruising speed (km/h) 180 Endurance (h) 20Table 4
Value of parameters for the weapons.
W1 Weight (kg) 75 Cost ($ thousand) 68 W2 Weight (kg) 165 Cost ($ thousand) 184 W3 Weight (kg) 240 Cost ($ thousand) 22In practical battlefields, there is usually a safe distance between the depot and the enemy target. Thus, the depots and the enemy targets are randomly generated in different combat zones, which can ensure that the distance between each depot and any enemy target is over 100 km.


### 5.2. Computational Results Analysis

#### 5.2.1. Small-Scale Experiment

The results of small-scale experiments with 10 targets and 20 targets are shown in Tables5 and 6. In the table, column 3 presents the initial feasible solutions obtained by the constructive heuristic and column 4 presents the final solutions obtained by ALNS. Column 5 presents the computational time consumed by the ALNS algorithm, and column 6 proposes the improvement (Impro.) of the final solution relative to the initial solution. In order to further analyze the performance of the six neighborhood structures utilized in ALNS, we calculated the percentage of the number of times that each neighborhood structure is invoked in the overall iterations of ALNS. The results are shown in columns 7 to 12, respectively. As we can see from Table 5, when the ALNS algorithm is used to solve the instances with 10 targets, the average computational time is 11.31 seconds and the average improvement of the final solution compared to the initial solution is 43.66%. As shown in columns 7 to 12, the percentages of six neighborhood structures invoked are quite different from each other, and there is no same situation for any two of the thirty instances, which indicates that the adaptive learning strategy can efficiently adjust the weights of the neighborhood structures in the search process.Table 5
Experimental results for instances with 10 targets.
UAV capacity No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures(%) DE TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 1 5.03 × 106 3.18 × 106 13.20 36.76 20.80 19.86 17.78 14.57 13.90 13.08 2 5.80 × 106 3.60 × 106 11.80 37.99 14.74 19.46 18.28 16.08 17.42 14.02 3 5.99 × 106 3.10 × 106 13.42 48.10 15.33 18.16 19.73 15.96 15.65 15.17 4 4.95 × 106 3.05 × 106 10.57 38.39 12.31 16.51 19.86 19.36 16.83 15.11 5 5.08 × 106 3.39 × 106 9.67 33.22 10.69 16.98 17.83 18.40 18.57 17.54 6 6.22 × 106 3.90 × 106 12.70 37.25 9.14 17.18 19.74 15.74 18.73 19.46 7 5.49 × 106 3.69 × 106 10.58 32.66 14.83 18.96 18.66 13.80 18.41 15.34 8 5.89 × 106 3.83 × 106 13.21 34.92 13.79 21.73 17.73 14.41 18.29 14.05 9 5.74 × 106 3.35 × 106 9.32 41.60 15.55 15.97 17.98 15.59 14.93 19.98 10 5.50 × 106 3.55 × 106 11.69 35.49 21.57 16.17 19.52 13.25 14.38 15.10  6 hanging points and load of 900 kg 11 5.97 × 106 3.15 × 106 10.09 47.19 5.15 19.91 19.00 17.29 19.44 19.22 12 6.39 × 106 3.25 × 106 9.05 49.06 12.93 15.82 18.47 19.82 16.74 16.22 13 6.70 × 106 3.73 × 106 9.63 44.31 12.81 19.09 19.47 17.44 14.77 16.43 14 7.65 × 106 4.17 × 106 9.78 45.50 20.33 18.84 14.62 14.17 16.89 15.15 15 5.71 × 106 3.11 × 106 12.23 45.47 8.54 18.36 19.57 17.28 17.23 19.02 16 6.73 × 106 3.28 × 106 13.74 51.24 22.04 18.63 16.87 15.90 13.06 13.50 17 6.44 × 106 3.45 × 106 9.55 46.35 14.26 14.92 18.01 13.89 19.25 19.68 18 6.50 × 106 3.41 × 106 11.27 47.51 23.64 18.13 14.66 13.62 15.88 14.08 19 6.08 × 106 3.13 × 106 9.72 48.49 16.21 19.32 16.31 16.81 14.31 17.03 20 6.39 × 106 3.47 × 106 9.34 45.60 20.63 19.23 18.30 15.25 13.46 13.13  8 hanging points andd load of 1200 kg 21 6.62 × 106 3.47 × 106 9.46 47.51 17.01 16.69 18.02 17.28 15.88 15.12 22 6.64 × 106 3.85 × 106 13.31 42.01 19.70 17.29 15.94 13.25 15.60 18.22 23 7.24 × 106 3.95 × 106 11.74 45.47 17.60 14.33 16.03 18.37 19.80 13.87 24 6.68 × 106 3.97 × 106 13.05 40.45 12.88 14.21 16.13 19.23 19.14 18.40 25 7.56 × 106 3.99 × 106 11.97 47.16 20.57 18.55 13.64 14.26 19.45 13.53 26 6.54 × 106 3.44 × 106 13.12 47.27 19.19 13.33 16.44 19.64 15.17 16.22 27 6.32 × 106 3.59 × 106 12.99 43.15 24.02 17.15 16.51 13.55 15.27 13.50 28 7.22 × 106 3.44 × 106 10.67 52.34 14.81 19.32 15.77 17.46 15.05 17.59 29 6.79 × 106 3.80 × 106 10.91 43.99 22.74 15.30 13.49 19.20 15.92 13.35 30 7.63 × 106 3.56 × 106 11.62 53.25 12.65 13.63 16.58 18.86 19.19 19.09  Average  11.31 43.66Table 6
Experimental results for instances with 20 targets.
No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures (%) ED TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 31 9.29 × 106 7.99 × 106 25.08 14.06 14.96 19.45 22.51 13.57 12.61 16.89 32 9.95 × 106 7.86 × 106 29.48 20.95 13.85 23.27 19.55 16.19 10.36 16.79 33 9.52 × 106 7.53 × 106 30.99 20.86 16.81 25.79 19.06 17.31 11.47 9.56 34 9.83 × 106 8.07 × 106 22.95 17.94 15.11 21.05 25.03 17.84 11.96 9.00 35 9.09 × 106 7.28 × 106 27.39 19.82 12.11 21.15 25.34 11.45 9.83 20.12 36 9.12 × 106 7.77 × 106 27.27 14.72 15.26 22.53 25.28 16.09 14.20 6.63 37 1.01 × 107 8.76 × 106 25.81 13.79 15.49 23.81 22.07 10.52 11.49 16.63 38 9.84 × 106 8.20 × 106 30.67 16.73 18.63 22.15 22.06 17.50 8.83 10.83 39 8.89 × 106 8.01 × 106 27.86 9.96 13.65 27.04 22.04 16.33 10.36 10.59 40 8.47 × 106 7.29 × 106 27.57 13.90 15.96 22.04 22.95 16.18 11.39 11.48  6 hanging points and load of 900 kg 41 1.20 × 107 9.60 × 106 30.70 20.60 11.62 27.00 18.25 17.18 11.49 14.46 42 1.29 × 107 9.79 × 106 24.09 24.31 16.92 22.51 25.38 17.22 13.60 4.38 43 1.33 × 107 9.34 × 106 22.89 30.09 18.46 23.41 12.80 15.21 17.79 12.34 44 1.33 × 107 8.26 × 106 23.50 38.28 16.97 18.44 24.67 16.07 11.29 12.57 45 1.19 × 107 9.12 × 106 26.76 23.52 16.07 22.29 23.09 12.16 11.54 14.85 46 1.10 × 107 8.50 × 106 30.74 23.07 18.26 19.21 25.69 16.15 12.17 8.50 47 1.27 × 107 8.56 × 106 25.03 32.66 16.38 21.77 21.93 17.11 13.04 9.77 48 1.26 × 107 1.01 × 107 24.80 20.74 14.49 26.74 22.69 14.24 11.99 9.85 49 1.18 × 107 8.49 × 106 26.08 28.57 18.57 27.77 22.50 13.33 14.57 3.26 50 1.32 × 107 8.94 × 106 24.54 32.52 16.15 26.93 20.09 11.52 11.44 13.87  8 hanging points and load of 1200 kg 51 1.43 × 107 9.95 × 106 26.52 30.51 15.49 25.87 21.20 11.28 11.92 14.24 52 1.52 × 107 9.48 × 106 30.54 37.89 18.06 25.97 24.02 8.00 15.44 8.52 53 1.45 × 107 1.01 × 107 24.07 30.03 16.64 26.98 22.41 14.01 11.48 8.49 54 1.37 × 107 8.37 × 106 27.08 39.04 16.72 26.59 21.11 12.01 12.21 11.36 55 1.45 × 107 9.05 × 106 26.82 37.54 14.94 24.46 20.83 8.31 13.15 18.31 56 1.44 × 107 9.57 × 106 27.77 33.48 17.16 24.76 23.44 10.91 17.25 6.49 57 1.57 × 107 8.84 × 106 22.61 43.82 17.91 25.26 17.04 9.17 11.60 19.03 58 1.52 × 107 7.09 × 106 29.85 53.48 15.55 27.12 18.33 17.31 10.01 11.69 59 1.52 × 107 9.34 × 106 24.19 38.55 18.10 26.68 23.02 9.71 12.69 9.80 60 1.57 × 107 1.01 × 107 30.57 35.82 18.22 23.98 17.40 9.48 10.67 20.27  Average  26.81 27.24The average computational time for instances with 20 targets, as shown in Table6, is 26.81 seconds and the average improvement on the initial solution is 27.24%. Compared to the results for instances with 10 targets, the ALNS consumes more time and obtains lower improvement on the initial solution.In order to show the experimental results more intuitively, the routing results of instance #51 in Table6 are graphically displayed in Figure 3. As shown in Figure 3, eight UAVs have to be dispatched from three stations.Figure 3
An illustration of the routing results for instance #51.


#### 5.2.2. Medium-Scale and Large-Scale Experiments

From Tables5 and 6, we can see that the performance of ALNS on improving the initial solution decreases as the problem scale increases, when the total number of iterations remains unchanged. In order to get better results, the number of iterations, φlearn, is increased as the problem size increases, and we set φlearn=15000 for solving instances with 50 targets and set cases φlearn=20000 for solving instances with 100 targets.The results are presented in Tables7 and 8. As we can see from Table 7, when ALNS algorithm is used to solve the instances with 50 targets, the average computational time of the algorithm is 60.55 seconds and the average improvement of the final solution compared to the initial solution is 19.25%. The results for instances with 100 targets in Table 8 show that the average calculation time is 206.13 seconds and the average improvement (Impro.) of the final solution compared to the initial solution is 19.54%.Table 7
Experimental results for instances with 50 targets.
No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures(%) ED TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 61 3.35 × 107 3.20 × 107 59.69 4.46 10.50 22.76 22.44 15.30 11.43 17.56 62 3.72 × 107 3.44 × 107 56.95 7.45 11.10 24.07 17.84 13.08 16.10 17.80 63 3.39 × 107 3.23 × 107 57.32 4.54 19.79 20.75 15.30 12.66 16.38 15.12 64 3.46 × 107 3.28 × 107 56.96 5.04 23.46 19.37 13.76 13.06 12.10 18.25 65 3.30 × 107 3.06 × 107 68.17 7.41 21.78 20.11 13.19 12.78 14.06 18.08 66 3.51 × 107 3.32 × 107 54.77 5.50 17.78 20.41 16.11 13.90 13.20 18.59 67 3.52 × 107 3.25 × 107 56.30 7.56 18.26 24.86 17.57 11.40 9.22 18.69 68 3.45 × 107 3.27 × 107 61.88 5.03 14.37 21.09 18.57 14.69 12.44 18.84 69 3.27 × 107 3.03 × 107 62.30 7.21 13.00 23.52 18.74 15.91 13.64 15.20 70 3.47 × 107 3.33 × 107 55.12 3.85 17.30 25.14 16.69 12.63 15.35 12.88  6 hanging points and load of 900 kg 71 4.77 × 107 3.74 × 107 68.75 21.54 9.32 25.79 21.98 14.09 12.93 15.88 72 4.96 × 107 3.86 × 107 56.85 22.13 15.47 24.27 15.60 11.88 14.43 18.34 73 4.87 × 107 3.99 × 107 59.32 18.15 20.42 19.93 12.99 13.79 17.33 15.53 74 4.94 × 107 3.18 × 107 61.99 35.53 13.55 23.68 12.31 12.40 20.02 18.04 75 5.15 × 107 3.77 × 107 53.88 26.77 18.06 24.24 17.84 12.95 14.95 11.95 76 4.93 × 107 3.54 × 107 60.40 28.20 22.48 20.44 18.56 15.93 10.02 12.57 77 4.69 × 107 3.26 × 107 68.43 30.50 17.02 19.07 17.26 13.46 17.28 15.91 78 4.72 × 107 3.74 × 107 55.20 20.78 11.15 21.77 18.02 16.34 19.78 12.94 79 4.96 × 107 3.45 × 107 53.17 30.54 22.13 18.85 15.84 16.79 13.53 12.85 80 4.53 × 107 3.69 × 107 68.45 18.51 12.85 23.26 16.22 12.89 11.82 22.97  8 hanging points and load of 1200 kg 81 6.10 × 107 4.30 × 107 52.75 29.44 8.48 23.58 15.94 15.55 17.53 18.92 82 5.93 × 107 4.09 × 107 66.12 30.98 21.03 24.70 18.63 11.64 11.34 12.66 83 5.43 × 107 3.47 × 107 62.99 36.03 22.70 19.28 14.33 15.63 13.99 14.06 84 5.96 × 107 4.72 × 107 75.37 20.84 27.16 18.19 15.18 14.37 11.51 13.60 85 5.91 × 107 4.95 × 107 73.27 16.18 16.92 24.71 13.61 16.42 10.41 17.93 86 6.05 × 107 4.90 × 107 56.48 19.09 18.93 23.75 12.21 16.04 13.86 15.20 87 5.74 × 107 3.75 × 107 64.69 34.66 14.46 25.86 13.52 15.18 13.05 17.93 88 5.57 × 107 4.16 × 107 58.70 25.33 21.77 20.12 18.03 14.46 13.95 11.67 89 5.82 × 107 4.06 × 107 58.46 30.24 18.71 18.80 11.79 17.14 16.96 16.60 90 5.92 × 107 4.49 × 107 51.90 24.17 20.14 22.80 14.02 13.89 12.45 16.70  Average  60.55 19.25Table 8
Experimental results for instances with 100 targets.
Mounting capacity No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures (%) ED TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 91 7.33 × 107 6.83 × 107 204.43 6.76 21.18 15.28 18.09 12.89 17.32 15.24 92 8.01 × 107 7.25 × 107 205.93 9.35 16.54 16.49 16.26 16.45 16.23 18.03 93 8.51 × 107 7.82 × 107 211.70 8.06 19.48 15.34 14.49 14.61 21.55 14.53 94 7.89 × 107 7.37 × 107 220.81 6.53 14.71 21.19 14.30 17.58 15.08 17.14 95 7.91 × 107 7.29 × 107 219.74 7.85 16.44 16.99 18.39 17.44 19.53 11.21 96 8.04 × 107 7.31 × 107 217.34 9.12 17.87 13.10 19.75 15.45 18.68 15.17 97 7.11 × 107 6.50 × 107 192.37 8.56 13.44 20.88 17.49 18.78 13.49 15.93 98 7.55 × 107 6.88 × 107 198.87 8.87 20.91 14.70 14.29 17.50 13.19 19.41 99 7.71 × 107 6.99 × 107 194.00 9.25 15.53 15.60 17.96 15.88 17.79 17.25 100 7.80 × 107 7.23 × 107 202.40 7.27 15.87 20.67 16.63 17.69 13.05 16.09  6 hanging points and load of 900 kg 101 1.18 × 108 8.82 × 107 225.35 25.31 18.43 18.51 14.48 18.59 12.09 17.91 102 1.17 × 108 8.26 × 107 219.91 29.76 13.23 21.82 12.90 15.40 17.13 19.52 103 1.09 × 108 9.64 × 107 213.12 12.15 15.09 15.12 17.07 17.00 17.22 18.48 104 1.22 × 108 8.89 × 107 228.37 27.59 18.45 12.26 19.70 17.29 13.78 18.52 105 1.15 × 108 9.09 × 107 191.45 21.32 19.63 13.89 17.66 17.59 17.63 13.61 106 1.10 × 108 7.43 × 107 222.58 33.01 15.78 21.92 14.89 14.47 19.88 13.06 107 1.14 × 108 8.88 × 107 222.52 22.42 21.29 20.88 17.36 12.13 14.23 14.11 108 1.07 × 108 8.90 × 107 215.35 17.20 21.16 19.81 12.18 19.09 12.02 15.73 109 1.17 × 108 8.69 × 107 180.88 25.76 14.27 20.96 19.56 18.42 19.60 7.18 110 1.11 × 108 7.41 × 107 228.02 33.78 15.23 12.16 15.77 22.21 19.09 15.54  8 hanging points and load of 1200 kg 111 1.09 × 108 8.44 × 107 183.16 22.87 19.92 18.84 19.68 16.15 13.72 11.69 112 1.18 × 108 9.54 × 107 212.02 19.54 15.76 14.67 15.71 19.65 15.35 18.85 113 1.23 × 108 7.86 × 107 199.23 36.35 12.91 12.66 17.86 15.13 15.83 25.61 114 1.14 × 108 8.10 × 107 222.06 29.23 18.14 18.15 13.13 16.75 16.49 17.35 115 1.24 × 108 1.01 × 108 194.09 18.98 15.28 19.08 16.69 15.03 18.62 15.30 116 1.17 × 108 9.42 × 107 192.35 20.10 21.79 16.18 15.02 12.80 18.89 15.32 117 1.11 × 108 7.22 × 107 181.79 34.77 14.87 15.41 14.75 22.46 15.44 17.07 118 1.18 × 108 9.57 × 107 211.81 19.30 19.56 20.63 13.06 14.44 12.62 19.69 119 1.14 × 108 8.60 × 107 186.32 25.14 16.96 21.16 13.86 15.80 19.13 13.09 120 1.18 × 108 8.33 × 107 185.89 29.90 16.88 16.85 18.06 19.91 14.56 13.74  Average  206.13 19.54The computational time for the heuristic to construct initial feasible solution is less than one second, and thus we do not report the detailed time for all instances. The maximum computational time for the instance with 100 targets is 228.37 seconds, which is acceptable for mission planning in current wars. For most of the instances, the ALNS can make good improvement on their initial solutions, which indicates that the solution obtained by the ALNS is relatively better and can satisfy the requirement of practical mission planning. We note that the improvement on some instances is less than 10%, and the similarity of these instances is that the UAV utilized in them has 4 hanging points and a payload of 600 kg. We can see that the combination scale for solving these instances is lower, and the constructive heuristic can present a better initial solution, which provides a better start point for the ALNS. Thus, although the ALNS may find a relative good solution, its improvement compared to the initial solution is not so big.


## 5.1. Experimental Design

In order to fully test the performance of the proposed algorithms, instances with four different sizes are randomly generated, respectively: 10 targets, 20 targets, 50 targets, and 100 targets. Three different types of UAVs were utilized, which are UAVs with 4 hanging points and 600 kg loads, 6 hanging points and 900 kg loads, and 8 hanging points and 1200 kg loads. Three sizes of combat areas, 500 × 300 km2, 800 × 500 km2, and 1200 × 800 km2, are utilized. The experimental scale settings are shown in Table 2. The values of parameters for the weapons are illustrated in Tables 3 and 4. In the experiment, the service time of targets (unit: hours) is generated randomly in (0,1]. The target’s time window is also generated randomly between 0 hours and 12 hours. Meanwhile, the following restrictions are considered in the random generation process: (1) the earliest allowed strike time, ei, for target i is no less than the time-consumed by the UAV flying from the depot to the target, t0i; (2) the difference between the latest required strike time of target i, li, and its earliest allowed attack time, ei, is no more than τ  (τ=5 hours) and is no less than the service time Si.Table 2
Experimental scale.
Number of targets Area(km2) Number of stations φ l e a r n Small scale 10 500 × 300 2 2000 20 500 × 300 3 10000 Medium scale 50 800 × 500 5 15000 Large scale 100 1200 × 800 10 20000Table 3
UAV-related parameters.
Name Value of parameter s Payload capacity (kg) 600; 900; 1200 Number of hanging points 4; 6; 8 Weapons W1; W2; W3 Cruising speed (km/h) 180 Endurance (h) 20Table 4
Value of parameters for the weapons.
W1 Weight (kg) 75 Cost ($ thousand) 68 W2 Weight (kg) 165 Cost ($ thousand) 184 W3 Weight (kg) 240 Cost ($ thousand) 22In practical battlefields, there is usually a safe distance between the depot and the enemy target. Thus, the depots and the enemy targets are randomly generated in different combat zones, which can ensure that the distance between each depot and any enemy target is over 100 km.


## 5.2. Computational Results Analysis

### 5.2.1. Small-Scale Experiment

The results of small-scale experiments with 10 targets and 20 targets are shown in Tables5 and 6. In the table, column 3 presents the initial feasible solutions obtained by the constructive heuristic and column 4 presents the final solutions obtained by ALNS. Column 5 presents the computational time consumed by the ALNS algorithm, and column 6 proposes the improvement (Impro.) of the final solution relative to the initial solution. In order to further analyze the performance of the six neighborhood structures utilized in ALNS, we calculated the percentage of the number of times that each neighborhood structure is invoked in the overall iterations of ALNS. The results are shown in columns 7 to 12, respectively. As we can see from Table 5, when the ALNS algorithm is used to solve the instances with 10 targets, the average computational time is 11.31 seconds and the average improvement of the final solution compared to the initial solution is 43.66%. As shown in columns 7 to 12, the percentages of six neighborhood structures invoked are quite different from each other, and there is no same situation for any two of the thirty instances, which indicates that the adaptive learning strategy can efficiently adjust the weights of the neighborhood structures in the search process.Table 5
Experimental results for instances with 10 targets.
UAV capacity No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures(%) DE TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 1 5.03 × 106 3.18 × 106 13.20 36.76 20.80 19.86 17.78 14.57 13.90 13.08 2 5.80 × 106 3.60 × 106 11.80 37.99 14.74 19.46 18.28 16.08 17.42 14.02 3 5.99 × 106 3.10 × 106 13.42 48.10 15.33 18.16 19.73 15.96 15.65 15.17 4 4.95 × 106 3.05 × 106 10.57 38.39 12.31 16.51 19.86 19.36 16.83 15.11 5 5.08 × 106 3.39 × 106 9.67 33.22 10.69 16.98 17.83 18.40 18.57 17.54 6 6.22 × 106 3.90 × 106 12.70 37.25 9.14 17.18 19.74 15.74 18.73 19.46 7 5.49 × 106 3.69 × 106 10.58 32.66 14.83 18.96 18.66 13.80 18.41 15.34 8 5.89 × 106 3.83 × 106 13.21 34.92 13.79 21.73 17.73 14.41 18.29 14.05 9 5.74 × 106 3.35 × 106 9.32 41.60 15.55 15.97 17.98 15.59 14.93 19.98 10 5.50 × 106 3.55 × 106 11.69 35.49 21.57 16.17 19.52 13.25 14.38 15.10  6 hanging points and load of 900 kg 11 5.97 × 106 3.15 × 106 10.09 47.19 5.15 19.91 19.00 17.29 19.44 19.22 12 6.39 × 106 3.25 × 106 9.05 49.06 12.93 15.82 18.47 19.82 16.74 16.22 13 6.70 × 106 3.73 × 106 9.63 44.31 12.81 19.09 19.47 17.44 14.77 16.43 14 7.65 × 106 4.17 × 106 9.78 45.50 20.33 18.84 14.62 14.17 16.89 15.15 15 5.71 × 106 3.11 × 106 12.23 45.47 8.54 18.36 19.57 17.28 17.23 19.02 16 6.73 × 106 3.28 × 106 13.74 51.24 22.04 18.63 16.87 15.90 13.06 13.50 17 6.44 × 106 3.45 × 106 9.55 46.35 14.26 14.92 18.01 13.89 19.25 19.68 18 6.50 × 106 3.41 × 106 11.27 47.51 23.64 18.13 14.66 13.62 15.88 14.08 19 6.08 × 106 3.13 × 106 9.72 48.49 16.21 19.32 16.31 16.81 14.31 17.03 20 6.39 × 106 3.47 × 106 9.34 45.60 20.63 19.23 18.30 15.25 13.46 13.13  8 hanging points andd load of 1200 kg 21 6.62 × 106 3.47 × 106 9.46 47.51 17.01 16.69 18.02 17.28 15.88 15.12 22 6.64 × 106 3.85 × 106 13.31 42.01 19.70 17.29 15.94 13.25 15.60 18.22 23 7.24 × 106 3.95 × 106 11.74 45.47 17.60 14.33 16.03 18.37 19.80 13.87 24 6.68 × 106 3.97 × 106 13.05 40.45 12.88 14.21 16.13 19.23 19.14 18.40 25 7.56 × 106 3.99 × 106 11.97 47.16 20.57 18.55 13.64 14.26 19.45 13.53 26 6.54 × 106 3.44 × 106 13.12 47.27 19.19 13.33 16.44 19.64 15.17 16.22 27 6.32 × 106 3.59 × 106 12.99 43.15 24.02 17.15 16.51 13.55 15.27 13.50 28 7.22 × 106 3.44 × 106 10.67 52.34 14.81 19.32 15.77 17.46 15.05 17.59 29 6.79 × 106 3.80 × 106 10.91 43.99 22.74 15.30 13.49 19.20 15.92 13.35 30 7.63 × 106 3.56 × 106 11.62 53.25 12.65 13.63 16.58 18.86 19.19 19.09  Average  11.31 43.66Table 6
Experimental results for instances with 20 targets.
No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures (%) ED TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 31 9.29 × 106 7.99 × 106 25.08 14.06 14.96 19.45 22.51 13.57 12.61 16.89 32 9.95 × 106 7.86 × 106 29.48 20.95 13.85 23.27 19.55 16.19 10.36 16.79 33 9.52 × 106 7.53 × 106 30.99 20.86 16.81 25.79 19.06 17.31 11.47 9.56 34 9.83 × 106 8.07 × 106 22.95 17.94 15.11 21.05 25.03 17.84 11.96 9.00 35 9.09 × 106 7.28 × 106 27.39 19.82 12.11 21.15 25.34 11.45 9.83 20.12 36 9.12 × 106 7.77 × 106 27.27 14.72 15.26 22.53 25.28 16.09 14.20 6.63 37 1.01 × 107 8.76 × 106 25.81 13.79 15.49 23.81 22.07 10.52 11.49 16.63 38 9.84 × 106 8.20 × 106 30.67 16.73 18.63 22.15 22.06 17.50 8.83 10.83 39 8.89 × 106 8.01 × 106 27.86 9.96 13.65 27.04 22.04 16.33 10.36 10.59 40 8.47 × 106 7.29 × 106 27.57 13.90 15.96 22.04 22.95 16.18 11.39 11.48  6 hanging points and load of 900 kg 41 1.20 × 107 9.60 × 106 30.70 20.60 11.62 27.00 18.25 17.18 11.49 14.46 42 1.29 × 107 9.79 × 106 24.09 24.31 16.92 22.51 25.38 17.22 13.60 4.38 43 1.33 × 107 9.34 × 106 22.89 30.09 18.46 23.41 12.80 15.21 17.79 12.34 44 1.33 × 107 8.26 × 106 23.50 38.28 16.97 18.44 24.67 16.07 11.29 12.57 45 1.19 × 107 9.12 × 106 26.76 23.52 16.07 22.29 23.09 12.16 11.54 14.85 46 1.10 × 107 8.50 × 106 30.74 23.07 18.26 19.21 25.69 16.15 12.17 8.50 47 1.27 × 107 8.56 × 106 25.03 32.66 16.38 21.77 21.93 17.11 13.04 9.77 48 1.26 × 107 1.01 × 107 24.80 20.74 14.49 26.74 22.69 14.24 11.99 9.85 49 1.18 × 107 8.49 × 106 26.08 28.57 18.57 27.77 22.50 13.33 14.57 3.26 50 1.32 × 107 8.94 × 106 24.54 32.52 16.15 26.93 20.09 11.52 11.44 13.87  8 hanging points and load of 1200 kg 51 1.43 × 107 9.95 × 106 26.52 30.51 15.49 25.87 21.20 11.28 11.92 14.24 52 1.52 × 107 9.48 × 106 30.54 37.89 18.06 25.97 24.02 8.00 15.44 8.52 53 1.45 × 107 1.01 × 107 24.07 30.03 16.64 26.98 22.41 14.01 11.48 8.49 54 1.37 × 107 8.37 × 106 27.08 39.04 16.72 26.59 21.11 12.01 12.21 11.36 55 1.45 × 107 9.05 × 106 26.82 37.54 14.94 24.46 20.83 8.31 13.15 18.31 56 1.44 × 107 9.57 × 106 27.77 33.48 17.16 24.76 23.44 10.91 17.25 6.49 57 1.57 × 107 8.84 × 106 22.61 43.82 17.91 25.26 17.04 9.17 11.60 19.03 58 1.52 × 107 7.09 × 106 29.85 53.48 15.55 27.12 18.33 17.31 10.01 11.69 59 1.52 × 107 9.34 × 106 24.19 38.55 18.10 26.68 23.02 9.71 12.69 9.80 60 1.57 × 107 1.01 × 107 30.57 35.82 18.22 23.98 17.40 9.48 10.67 20.27  Average  26.81 27.24The average computational time for instances with 20 targets, as shown in Table6, is 26.81 seconds and the average improvement on the initial solution is 27.24%. Compared to the results for instances with 10 targets, the ALNS consumes more time and obtains lower improvement on the initial solution.In order to show the experimental results more intuitively, the routing results of instance #51 in Table6 are graphically displayed in Figure 3. As shown in Figure 3, eight UAVs have to be dispatched from three stations.Figure 3
An illustration of the routing results for instance #51.


### 5.2.2. Medium-Scale and Large-Scale Experiments

From Tables5 and 6, we can see that the performance of ALNS on improving the initial solution decreases as the problem scale increases, when the total number of iterations remains unchanged. In order to get better results, the number of iterations, φlearn, is increased as the problem size increases, and we set φlearn=15000 for solving instances with 50 targets and set cases φlearn=20000 for solving instances with 100 targets.The results are presented in Tables7 and 8. As we can see from Table 7, when ALNS algorithm is used to solve the instances with 50 targets, the average computational time of the algorithm is 60.55 seconds and the average improvement of the final solution compared to the initial solution is 19.25%. The results for instances with 100 targets in Table 8 show that the average calculation time is 206.13 seconds and the average improvement (Impro.) of the final solution compared to the initial solution is 19.54%.Table 7
Experimental results for instances with 50 targets.
No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures(%) ED TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 61 3.35 × 107 3.20 × 107 59.69 4.46 10.50 22.76 22.44 15.30 11.43 17.56 62 3.72 × 107 3.44 × 107 56.95 7.45 11.10 24.07 17.84 13.08 16.10 17.80 63 3.39 × 107 3.23 × 107 57.32 4.54 19.79 20.75 15.30 12.66 16.38 15.12 64 3.46 × 107 3.28 × 107 56.96 5.04 23.46 19.37 13.76 13.06 12.10 18.25 65 3.30 × 107 3.06 × 107 68.17 7.41 21.78 20.11 13.19 12.78 14.06 18.08 66 3.51 × 107 3.32 × 107 54.77 5.50 17.78 20.41 16.11 13.90 13.20 18.59 67 3.52 × 107 3.25 × 107 56.30 7.56 18.26 24.86 17.57 11.40 9.22 18.69 68 3.45 × 107 3.27 × 107 61.88 5.03 14.37 21.09 18.57 14.69 12.44 18.84 69 3.27 × 107 3.03 × 107 62.30 7.21 13.00 23.52 18.74 15.91 13.64 15.20 70 3.47 × 107 3.33 × 107 55.12 3.85 17.30 25.14 16.69 12.63 15.35 12.88  6 hanging points and load of 900 kg 71 4.77 × 107 3.74 × 107 68.75 21.54 9.32 25.79 21.98 14.09 12.93 15.88 72 4.96 × 107 3.86 × 107 56.85 22.13 15.47 24.27 15.60 11.88 14.43 18.34 73 4.87 × 107 3.99 × 107 59.32 18.15 20.42 19.93 12.99 13.79 17.33 15.53 74 4.94 × 107 3.18 × 107 61.99 35.53 13.55 23.68 12.31 12.40 20.02 18.04 75 5.15 × 107 3.77 × 107 53.88 26.77 18.06 24.24 17.84 12.95 14.95 11.95 76 4.93 × 107 3.54 × 107 60.40 28.20 22.48 20.44 18.56 15.93 10.02 12.57 77 4.69 × 107 3.26 × 107 68.43 30.50 17.02 19.07 17.26 13.46 17.28 15.91 78 4.72 × 107 3.74 × 107 55.20 20.78 11.15 21.77 18.02 16.34 19.78 12.94 79 4.96 × 107 3.45 × 107 53.17 30.54 22.13 18.85 15.84 16.79 13.53 12.85 80 4.53 × 107 3.69 × 107 68.45 18.51 12.85 23.26 16.22 12.89 11.82 22.97  8 hanging points and load of 1200 kg 81 6.10 × 107 4.30 × 107 52.75 29.44 8.48 23.58 15.94 15.55 17.53 18.92 82 5.93 × 107 4.09 × 107 66.12 30.98 21.03 24.70 18.63 11.64 11.34 12.66 83 5.43 × 107 3.47 × 107 62.99 36.03 22.70 19.28 14.33 15.63 13.99 14.06 84 5.96 × 107 4.72 × 107 75.37 20.84 27.16 18.19 15.18 14.37 11.51 13.60 85 5.91 × 107 4.95 × 107 73.27 16.18 16.92 24.71 13.61 16.42 10.41 17.93 86 6.05 × 107 4.90 × 107 56.48 19.09 18.93 23.75 12.21 16.04 13.86 15.20 87 5.74 × 107 3.75 × 107 64.69 34.66 14.46 25.86 13.52 15.18 13.05 17.93 88 5.57 × 107 4.16 × 107 58.70 25.33 21.77 20.12 18.03 14.46 13.95 11.67 89 5.82 × 107 4.06 × 107 58.46 30.24 18.71 18.80 11.79 17.14 16.96 16.60 90 5.92 × 107 4.49 × 107 51.90 24.17 20.14 22.80 14.02 13.89 12.45 16.70  Average  60.55 19.25Table 8
Experimental results for instances with 100 targets.
Mounting capacity No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures (%) ED TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 91 7.33 × 107 6.83 × 107 204.43 6.76 21.18 15.28 18.09 12.89 17.32 15.24 92 8.01 × 107 7.25 × 107 205.93 9.35 16.54 16.49 16.26 16.45 16.23 18.03 93 8.51 × 107 7.82 × 107 211.70 8.06 19.48 15.34 14.49 14.61 21.55 14.53 94 7.89 × 107 7.37 × 107 220.81 6.53 14.71 21.19 14.30 17.58 15.08 17.14 95 7.91 × 107 7.29 × 107 219.74 7.85 16.44 16.99 18.39 17.44 19.53 11.21 96 8.04 × 107 7.31 × 107 217.34 9.12 17.87 13.10 19.75 15.45 18.68 15.17 97 7.11 × 107 6.50 × 107 192.37 8.56 13.44 20.88 17.49 18.78 13.49 15.93 98 7.55 × 107 6.88 × 107 198.87 8.87 20.91 14.70 14.29 17.50 13.19 19.41 99 7.71 × 107 6.99 × 107 194.00 9.25 15.53 15.60 17.96 15.88 17.79 17.25 100 7.80 × 107 7.23 × 107 202.40 7.27 15.87 20.67 16.63 17.69 13.05 16.09  6 hanging points and load of 900 kg 101 1.18 × 108 8.82 × 107 225.35 25.31 18.43 18.51 14.48 18.59 12.09 17.91 102 1.17 × 108 8.26 × 107 219.91 29.76 13.23 21.82 12.90 15.40 17.13 19.52 103 1.09 × 108 9.64 × 107 213.12 12.15 15.09 15.12 17.07 17.00 17.22 18.48 104 1.22 × 108 8.89 × 107 228.37 27.59 18.45 12.26 19.70 17.29 13.78 18.52 105 1.15 × 108 9.09 × 107 191.45 21.32 19.63 13.89 17.66 17.59 17.63 13.61 106 1.10 × 108 7.43 × 107 222.58 33.01 15.78 21.92 14.89 14.47 19.88 13.06 107 1.14 × 108 8.88 × 107 222.52 22.42 21.29 20.88 17.36 12.13 14.23 14.11 108 1.07 × 108 8.90 × 107 215.35 17.20 21.16 19.81 12.18 19.09 12.02 15.73 109 1.17 × 108 8.69 × 107 180.88 25.76 14.27 20.96 19.56 18.42 19.60 7.18 110 1.11 × 108 7.41 × 107 228.02 33.78 15.23 12.16 15.77 22.21 19.09 15.54  8 hanging points and load of 1200 kg 111 1.09 × 108 8.44 × 107 183.16 22.87 19.92 18.84 19.68 16.15 13.72 11.69 112 1.18 × 108 9.54 × 107 212.02 19.54 15.76 14.67 15.71 19.65 15.35 18.85 113 1.23 × 108 7.86 × 107 199.23 36.35 12.91 12.66 17.86 15.13 15.83 25.61 114 1.14 × 108 8.10 × 107 222.06 29.23 18.14 18.15 13.13 16.75 16.49 17.35 115 1.24 × 108 1.01 × 108 194.09 18.98 15.28 19.08 16.69 15.03 18.62 15.30 116 1.17 × 108 9.42 × 107 192.35 20.10 21.79 16.18 15.02 12.80 18.89 15.32 117 1.11 × 108 7.22 × 107 181.79 34.77 14.87 15.41 14.75 22.46 15.44 17.07 118 1.18 × 108 9.57 × 107 211.81 19.30 19.56 20.63 13.06 14.44 12.62 19.69 119 1.14 × 108 8.60 × 107 186.32 25.14 16.96 21.16 13.86 15.80 19.13 13.09 120 1.18 × 108 8.33 × 107 185.89 29.90 16.88 16.85 18.06 19.91 14.56 13.74  Average  206.13 19.54The computational time for the heuristic to construct initial feasible solution is less than one second, and thus we do not report the detailed time for all instances. The maximum computational time for the instance with 100 targets is 228.37 seconds, which is acceptable for mission planning in current wars. For most of the instances, the ALNS can make good improvement on their initial solutions, which indicates that the solution obtained by the ALNS is relatively better and can satisfy the requirement of practical mission planning. We note that the improvement on some instances is less than 10%, and the similarity of these instances is that the UAV utilized in them has 4 hanging points and a payload of 600 kg. We can see that the combination scale for solving these instances is lower, and the constructive heuristic can present a better initial solution, which provides a better start point for the ALNS. Thus, although the ALNS may find a relative good solution, its improvement compared to the initial solution is not so big.


## 5.2.1. Small-Scale Experiment

The results of small-scale experiments with 10 targets and 20 targets are shown in Tables5 and 6. In the table, column 3 presents the initial feasible solutions obtained by the constructive heuristic and column 4 presents the final solutions obtained by ALNS. Column 5 presents the computational time consumed by the ALNS algorithm, and column 6 proposes the improvement (Impro.) of the final solution relative to the initial solution. In order to further analyze the performance of the six neighborhood structures utilized in ALNS, we calculated the percentage of the number of times that each neighborhood structure is invoked in the overall iterations of ALNS. The results are shown in columns 7 to 12, respectively. As we can see from Table 5, when the ALNS algorithm is used to solve the instances with 10 targets, the average computational time is 11.31 seconds and the average improvement of the final solution compared to the initial solution is 43.66%. As shown in columns 7 to 12, the percentages of six neighborhood structures invoked are quite different from each other, and there is no same situation for any two of the thirty instances, which indicates that the adaptive learning strategy can efficiently adjust the weights of the neighborhood structures in the search process.Table 5
Experimental results for instances with 10 targets.
UAV capacity No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures(%) DE TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 1 5.03 × 106 3.18 × 106 13.20 36.76 20.80 19.86 17.78 14.57 13.90 13.08 2 5.80 × 106 3.60 × 106 11.80 37.99 14.74 19.46 18.28 16.08 17.42 14.02 3 5.99 × 106 3.10 × 106 13.42 48.10 15.33 18.16 19.73 15.96 15.65 15.17 4 4.95 × 106 3.05 × 106 10.57 38.39 12.31 16.51 19.86 19.36 16.83 15.11 5 5.08 × 106 3.39 × 106 9.67 33.22 10.69 16.98 17.83 18.40 18.57 17.54 6 6.22 × 106 3.90 × 106 12.70 37.25 9.14 17.18 19.74 15.74 18.73 19.46 7 5.49 × 106 3.69 × 106 10.58 32.66 14.83 18.96 18.66 13.80 18.41 15.34 8 5.89 × 106 3.83 × 106 13.21 34.92 13.79 21.73 17.73 14.41 18.29 14.05 9 5.74 × 106 3.35 × 106 9.32 41.60 15.55 15.97 17.98 15.59 14.93 19.98 10 5.50 × 106 3.55 × 106 11.69 35.49 21.57 16.17 19.52 13.25 14.38 15.10  6 hanging points and load of 900 kg 11 5.97 × 106 3.15 × 106 10.09 47.19 5.15 19.91 19.00 17.29 19.44 19.22 12 6.39 × 106 3.25 × 106 9.05 49.06 12.93 15.82 18.47 19.82 16.74 16.22 13 6.70 × 106 3.73 × 106 9.63 44.31 12.81 19.09 19.47 17.44 14.77 16.43 14 7.65 × 106 4.17 × 106 9.78 45.50 20.33 18.84 14.62 14.17 16.89 15.15 15 5.71 × 106 3.11 × 106 12.23 45.47 8.54 18.36 19.57 17.28 17.23 19.02 16 6.73 × 106 3.28 × 106 13.74 51.24 22.04 18.63 16.87 15.90 13.06 13.50 17 6.44 × 106 3.45 × 106 9.55 46.35 14.26 14.92 18.01 13.89 19.25 19.68 18 6.50 × 106 3.41 × 106 11.27 47.51 23.64 18.13 14.66 13.62 15.88 14.08 19 6.08 × 106 3.13 × 106 9.72 48.49 16.21 19.32 16.31 16.81 14.31 17.03 20 6.39 × 106 3.47 × 106 9.34 45.60 20.63 19.23 18.30 15.25 13.46 13.13  8 hanging points andd load of 1200 kg 21 6.62 × 106 3.47 × 106 9.46 47.51 17.01 16.69 18.02 17.28 15.88 15.12 22 6.64 × 106 3.85 × 106 13.31 42.01 19.70 17.29 15.94 13.25 15.60 18.22 23 7.24 × 106 3.95 × 106 11.74 45.47 17.60 14.33 16.03 18.37 19.80 13.87 24 6.68 × 106 3.97 × 106 13.05 40.45 12.88 14.21 16.13 19.23 19.14 18.40 25 7.56 × 106 3.99 × 106 11.97 47.16 20.57 18.55 13.64 14.26 19.45 13.53 26 6.54 × 106 3.44 × 106 13.12 47.27 19.19 13.33 16.44 19.64 15.17 16.22 27 6.32 × 106 3.59 × 106 12.99 43.15 24.02 17.15 16.51 13.55 15.27 13.50 28 7.22 × 106 3.44 × 106 10.67 52.34 14.81 19.32 15.77 17.46 15.05 17.59 29 6.79 × 106 3.80 × 106 10.91 43.99 22.74 15.30 13.49 19.20 15.92 13.35 30 7.63 × 106 3.56 × 106 11.62 53.25 12.65 13.63 16.58 18.86 19.19 19.09  Average  11.31 43.66Table 6
Experimental results for instances with 20 targets.
No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures (%) ED TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 31 9.29 × 106 7.99 × 106 25.08 14.06 14.96 19.45 22.51 13.57 12.61 16.89 32 9.95 × 106 7.86 × 106 29.48 20.95 13.85 23.27 19.55 16.19 10.36 16.79 33 9.52 × 106 7.53 × 106 30.99 20.86 16.81 25.79 19.06 17.31 11.47 9.56 34 9.83 × 106 8.07 × 106 22.95 17.94 15.11 21.05 25.03 17.84 11.96 9.00 35 9.09 × 106 7.28 × 106 27.39 19.82 12.11 21.15 25.34 11.45 9.83 20.12 36 9.12 × 106 7.77 × 106 27.27 14.72 15.26 22.53 25.28 16.09 14.20 6.63 37 1.01 × 107 8.76 × 106 25.81 13.79 15.49 23.81 22.07 10.52 11.49 16.63 38 9.84 × 106 8.20 × 106 30.67 16.73 18.63 22.15 22.06 17.50 8.83 10.83 39 8.89 × 106 8.01 × 106 27.86 9.96 13.65 27.04 22.04 16.33 10.36 10.59 40 8.47 × 106 7.29 × 106 27.57 13.90 15.96 22.04 22.95 16.18 11.39 11.48  6 hanging points and load of 900 kg 41 1.20 × 107 9.60 × 106 30.70 20.60 11.62 27.00 18.25 17.18 11.49 14.46 42 1.29 × 107 9.79 × 106 24.09 24.31 16.92 22.51 25.38 17.22 13.60 4.38 43 1.33 × 107 9.34 × 106 22.89 30.09 18.46 23.41 12.80 15.21 17.79 12.34 44 1.33 × 107 8.26 × 106 23.50 38.28 16.97 18.44 24.67 16.07 11.29 12.57 45 1.19 × 107 9.12 × 106 26.76 23.52 16.07 22.29 23.09 12.16 11.54 14.85 46 1.10 × 107 8.50 × 106 30.74 23.07 18.26 19.21 25.69 16.15 12.17 8.50 47 1.27 × 107 8.56 × 106 25.03 32.66 16.38 21.77 21.93 17.11 13.04 9.77 48 1.26 × 107 1.01 × 107 24.80 20.74 14.49 26.74 22.69 14.24 11.99 9.85 49 1.18 × 107 8.49 × 106 26.08 28.57 18.57 27.77 22.50 13.33 14.57 3.26 50 1.32 × 107 8.94 × 106 24.54 32.52 16.15 26.93 20.09 11.52 11.44 13.87  8 hanging points and load of 1200 kg 51 1.43 × 107 9.95 × 106 26.52 30.51 15.49 25.87 21.20 11.28 11.92 14.24 52 1.52 × 107 9.48 × 106 30.54 37.89 18.06 25.97 24.02 8.00 15.44 8.52 53 1.45 × 107 1.01 × 107 24.07 30.03 16.64 26.98 22.41 14.01 11.48 8.49 54 1.37 × 107 8.37 × 106 27.08 39.04 16.72 26.59 21.11 12.01 12.21 11.36 55 1.45 × 107 9.05 × 106 26.82 37.54 14.94 24.46 20.83 8.31 13.15 18.31 56 1.44 × 107 9.57 × 106 27.77 33.48 17.16 24.76 23.44 10.91 17.25 6.49 57 1.57 × 107 8.84 × 106 22.61 43.82 17.91 25.26 17.04 9.17 11.60 19.03 58 1.52 × 107 7.09 × 106 29.85 53.48 15.55 27.12 18.33 17.31 10.01 11.69 59 1.52 × 107 9.34 × 106 24.19 38.55 18.10 26.68 23.02 9.71 12.69 9.80 60 1.57 × 107 1.01 × 107 30.57 35.82 18.22 23.98 17.40 9.48 10.67 20.27  Average  26.81 27.24The average computational time for instances with 20 targets, as shown in Table6, is 26.81 seconds and the average improvement on the initial solution is 27.24%. Compared to the results for instances with 10 targets, the ALNS consumes more time and obtains lower improvement on the initial solution.In order to show the experimental results more intuitively, the routing results of instance #51 in Table6 are graphically displayed in Figure 3. As shown in Figure 3, eight UAVs have to be dispatched from three stations.Figure 3
An illustration of the routing results for instance #51.


## 5.2.2. Medium-Scale and Large-Scale Experiments

From Tables5 and 6, we can see that the performance of ALNS on improving the initial solution decreases as the problem scale increases, when the total number of iterations remains unchanged. In order to get better results, the number of iterations, φlearn, is increased as the problem size increases, and we set φlearn=15000 for solving instances with 50 targets and set cases φlearn=20000 for solving instances with 100 targets.The results are presented in Tables7 and 8. As we can see from Table 7, when ALNS algorithm is used to solve the instances with 50 targets, the average computational time of the algorithm is 60.55 seconds and the average improvement of the final solution compared to the initial solution is 19.25%. The results for instances with 100 targets in Table 8 show that the average calculation time is 206.13 seconds and the average improvement (Impro.) of the final solution compared to the initial solution is 19.54%.Table 7
Experimental results for instances with 50 targets.
No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures(%) ED TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 61 3.35 × 107 3.20 × 107 59.69 4.46 10.50 22.76 22.44 15.30 11.43 17.56 62 3.72 × 107 3.44 × 107 56.95 7.45 11.10 24.07 17.84 13.08 16.10 17.80 63 3.39 × 107 3.23 × 107 57.32 4.54 19.79 20.75 15.30 12.66 16.38 15.12 64 3.46 × 107 3.28 × 107 56.96 5.04 23.46 19.37 13.76 13.06 12.10 18.25 65 3.30 × 107 3.06 × 107 68.17 7.41 21.78 20.11 13.19 12.78 14.06 18.08 66 3.51 × 107 3.32 × 107 54.77 5.50 17.78 20.41 16.11 13.90 13.20 18.59 67 3.52 × 107 3.25 × 107 56.30 7.56 18.26 24.86 17.57 11.40 9.22 18.69 68 3.45 × 107 3.27 × 107 61.88 5.03 14.37 21.09 18.57 14.69 12.44 18.84 69 3.27 × 107 3.03 × 107 62.30 7.21 13.00 23.52 18.74 15.91 13.64 15.20 70 3.47 × 107 3.33 × 107 55.12 3.85 17.30 25.14 16.69 12.63 15.35 12.88  6 hanging points and load of 900 kg 71 4.77 × 107 3.74 × 107 68.75 21.54 9.32 25.79 21.98 14.09 12.93 15.88 72 4.96 × 107 3.86 × 107 56.85 22.13 15.47 24.27 15.60 11.88 14.43 18.34 73 4.87 × 107 3.99 × 107 59.32 18.15 20.42 19.93 12.99 13.79 17.33 15.53 74 4.94 × 107 3.18 × 107 61.99 35.53 13.55 23.68 12.31 12.40 20.02 18.04 75 5.15 × 107 3.77 × 107 53.88 26.77 18.06 24.24 17.84 12.95 14.95 11.95 76 4.93 × 107 3.54 × 107 60.40 28.20 22.48 20.44 18.56 15.93 10.02 12.57 77 4.69 × 107 3.26 × 107 68.43 30.50 17.02 19.07 17.26 13.46 17.28 15.91 78 4.72 × 107 3.74 × 107 55.20 20.78 11.15 21.77 18.02 16.34 19.78 12.94 79 4.96 × 107 3.45 × 107 53.17 30.54 22.13 18.85 15.84 16.79 13.53 12.85 80 4.53 × 107 3.69 × 107 68.45 18.51 12.85 23.26 16.22 12.89 11.82 22.97  8 hanging points and load of 1200 kg 81 6.10 × 107 4.30 × 107 52.75 29.44 8.48 23.58 15.94 15.55 17.53 18.92 82 5.93 × 107 4.09 × 107 66.12 30.98 21.03 24.70 18.63 11.64 11.34 12.66 83 5.43 × 107 3.47 × 107 62.99 36.03 22.70 19.28 14.33 15.63 13.99 14.06 84 5.96 × 107 4.72 × 107 75.37 20.84 27.16 18.19 15.18 14.37 11.51 13.60 85 5.91 × 107 4.95 × 107 73.27 16.18 16.92 24.71 13.61 16.42 10.41 17.93 86 6.05 × 107 4.90 × 107 56.48 19.09 18.93 23.75 12.21 16.04 13.86 15.20 87 5.74 × 107 3.75 × 107 64.69 34.66 14.46 25.86 13.52 15.18 13.05 17.93 88 5.57 × 107 4.16 × 107 58.70 25.33 21.77 20.12 18.03 14.46 13.95 11.67 89 5.82 × 107 4.06 × 107 58.46 30.24 18.71 18.80 11.79 17.14 16.96 16.60 90 5.92 × 107 4.49 × 107 51.90 24.17 20.14 22.80 14.02 13.89 12.45 16.70  Average  60.55 19.25Table 8
Experimental results for instances with 100 targets.
Mounting capacity No. Initial solution Final solution Time(s) Impro.(%) Invoked percentages of neighborhood structures (%) ED TRC WR RNW RCW RWW 4 hanging points and load of 600 kg 91 7.33 × 107 6.83 × 107 204.43 6.76 21.18 15.28 18.09 12.89 17.32 15.24 92 8.01 × 107 7.25 × 107 205.93 9.35 16.54 16.49 16.26 16.45 16.23 18.03 93 8.51 × 107 7.82 × 107 211.70 8.06 19.48 15.34 14.49 14.61 21.55 14.53 94 7.89 × 107 7.37 × 107 220.81 6.53 14.71 21.19 14.30 17.58 15.08 17.14 95 7.91 × 107 7.29 × 107 219.74 7.85 16.44 16.99 18.39 17.44 19.53 11.21 96 8.04 × 107 7.31 × 107 217.34 9.12 17.87 13.10 19.75 15.45 18.68 15.17 97 7.11 × 107 6.50 × 107 192.37 8.56 13.44 20.88 17.49 18.78 13.49 15.93 98 7.55 × 107 6.88 × 107 198.87 8.87 20.91 14.70 14.29 17.50 13.19 19.41 99 7.71 × 107 6.99 × 107 194.00 9.25 15.53 15.60 17.96 15.88 17.79 17.25 100 7.80 × 107 7.23 × 107 202.40 7.27 15.87 20.67 16.63 17.69 13.05 16.09  6 hanging points and load of 900 kg 101 1.18 × 108 8.82 × 107 225.35 25.31 18.43 18.51 14.48 18.59 12.09 17.91 102 1.17 × 108 8.26 × 107 219.91 29.76 13.23 21.82 12.90 15.40 17.13 19.52 103 1.09 × 108 9.64 × 107 213.12 12.15 15.09 15.12 17.07 17.00 17.22 18.48 104 1.22 × 108 8.89 × 107 228.37 27.59 18.45 12.26 19.70 17.29 13.78 18.52 105 1.15 × 108 9.09 × 107 191.45 21.32 19.63 13.89 17.66 17.59 17.63 13.61 106 1.10 × 108 7.43 × 107 222.58 33.01 15.78 21.92 14.89 14.47 19.88 13.06 107 1.14 × 108 8.88 × 107 222.52 22.42 21.29 20.88 17.36 12.13 14.23 14.11 108 1.07 × 108 8.90 × 107 215.35 17.20 21.16 19.81 12.18 19.09 12.02 15.73 109 1.17 × 108 8.69 × 107 180.88 25.76 14.27 20.96 19.56 18.42 19.60 7.18 110 1.11 × 108 7.41 × 107 228.02 33.78 15.23 12.16 15.77 22.21 19.09 15.54  8 hanging points and load of 1200 kg 111 1.09 × 108 8.44 × 107 183.16 22.87 19.92 18.84 19.68 16.15 13.72 11.69 112 1.18 × 108 9.54 × 107 212.02 19.54 15.76 14.67 15.71 19.65 15.35 18.85 113 1.23 × 108 7.86 × 107 199.23 36.35 12.91 12.66 17.86 15.13 15.83 25.61 114 1.14 × 108 8.10 × 107 222.06 29.23 18.14 18.15 13.13 16.75 16.49 17.35 115 1.24 × 108 1.01 × 108 194.09 18.98 15.28 19.08 16.69 15.03 18.62 15.30 116 1.17 × 108 9.42 × 107 192.35 20.10 21.79 16.18 15.02 12.80 18.89 15.32 117 1.11 × 108 7.22 × 107 181.79 34.77 14.87 15.41 14.75 22.46 15.44 17.07 118 1.18 × 108 9.57 × 107 211.81 19.30 19.56 20.63 13.06 14.44 12.62 19.69 119 1.14 × 108 8.60 × 107 186.32 25.14 16.96 21.16 13.86 15.80 19.13 13.09 120 1.18 × 108 8.33 × 107 185.89 29.90 16.88 16.85 18.06 19.91 14.56 13.74  Average  206.13 19.54The computational time for the heuristic to construct initial feasible solution is less than one second, and thus we do not report the detailed time for all instances. The maximum computational time for the instance with 100 targets is 228.37 seconds, which is acceptable for mission planning in current wars. For most of the instances, the ALNS can make good improvement on their initial solutions, which indicates that the solution obtained by the ALNS is relatively better and can satisfy the requirement of practical mission planning. We note that the improvement on some instances is less than 10%, and the similarity of these instances is that the UAV utilized in them has 4 hanging points and a payload of 600 kg. We can see that the combination scale for solving these instances is lower, and the constructive heuristic can present a better initial solution, which provides a better start point for the ALNS. Thus, although the ALNS may find a relative good solution, its improvement compared to the initial solution is not so big.


## 6. Summary

This paper focuses on the mathematical model and solution algorithm design for a multidepot UAV routing problem with consideration of weapon configuration in UAV and time window of the target. A four-step heuristic is designed to construct an initial feasible solution, and then the ALNS algorithm is proposed to find better solutions. Experiments for instances with different scales indicate that the constructive heuristic can obtain a feasible solution in one second, and the ALNS algorithm can efficiently improve the quality of the solutions. For the largest instances with 100 targets, the proposed algorithms can present a relative good solution within 4 minutes. Thus, the overall performance of the algorithm can satisfy the practical requirement of commanders for military mission planning of UAVs in current wars.The UAV routing problem with weapon configuration and time window is new extension on the traditional vehicle routing problem, and there are many new topics required to study in future research. More efficient algorithms should be developed and compared with the ALNS algorithm, which is a broad and hard research. As the problem considered in this paper is quite complicated, there are no benchmark instances that consider exactly the same situation in literatures. Thus, we generate random instance based on practical military operation rules to test the proposed algorithm. In next research, benchmark instances from practical military applications need to be constructed and used to test the performance of different algorithms.



---

*Source: 7318207-2018-05-23.xml*