# Biobjective UAV/UGV Collaborative Rendezvous Planning in Persistent Intelligent Task-Based Wireless Communication

Authors: Qin Wang; Hua Chen; Junwei Tian; Jia Wang; Yu Su
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

This paper addresses a multiobjective Unmanned Aerial Vehicle (UAV) and Unmanned Ground Vehicle (UGVs) collaboration scheduling problem in which UAVs must be recharged periodically during a persistent task, such as wireless communication and making aerial panoramic VR video by UAV. The proposal is to introduce a UGV/UAV cooperative system in which UAVs should be recharged by UGVs periodically, and also, the UGVs have to visit their task points expect for the recharge points. The objective of the problem is to schedule and plan paths with the tradeoff of path length and makespan for UAVs and UGVs. The mathematical model which can be considered a combinatorial multiobjective optimization problem is presented firstly, and the solution of the problem is composed of presubsolution and postsubsolution. The multiobjective adaptive large neighborhood is hybrid with the Pareto local search (MOALP) to resolve the problem. The experimental result shows that the proposed algorithm outperforms the compared algorithms on the rendezvous planning problem for UAVs and UGVs working collaboratively in intelligent tasks.


---

## Body

## 1. Introduction

Unmanned Aerial Vehicles (UAVs) have been successfully used for many applications in both civil and military scenarios, such as surveillance, precision agriculture, package delivery, and facility inspection. Multiple sensors can be equipped to obtain various information because UAVs are flexible; however, the endurance capability of UAV greatly limits its operation time. Recently, researches which try to enable UAVs working in persistent tasks have been drawn much attention.It is a great challenge for the UAV/UGV collaboration system working in persistent tasks since UAVs have a short endurance. Previously, two kinds of methods are widely studied to improve the operation time of the UAV/UGV collaboration system in the literature; the first kind of method is to set recharging stations for UAVs in the environment to improve the endurance of UAVs; in this case, UAVs are required to visit recharging stations periodically and be replenished by battery swapping systems; for the second type of method, UGVs are used as mobile recharging stations, and UAVs need to be replenished by rendezvousing with a UGV periodically.The problem of path planning for UAV/UGV collaboration systems has been widely investigated in existing literatures. Sunder and Rathinam [1] deployed multiple depots (charging stations) in the environment to refuel one UAV working in monitoring applications, the mixed integer linear programming (MILP) model is presented, and a local search heuristic was proposed for resolving the problem. [2] considered multi-UAVs and charging stations in the working scenario, and the problem is transformed into a generalized traveling salesman problem (GTSP) and then resolved by a GTSP solver.Different from [1, 2], mobile robots were utilized in some literatures instead of using charging depots, and Maini and Sujit [3] proposed a model named FCURP-MRS which ensures that UAVs can be recharged by UGVs by generating UGV paths and UAV paths, respectively. [4–6] studied the path planning problem for mobile charging robots. In [4, 5], multiple working robots and one charging robot were considered in the problem, and the problem is resolved by using both dynamic programming and local search heuristics. In [6], the authors studied the single charging cycle problem and multirobot charging problem, and they proposed the integer linear programming method and multirobot Noon-Bean transformation to solve the problem, respectively.Multiobjective path planning for the UAV/UGV collaboration system working in persistent tasks has been seldom studied in the previous related works while there exist a lot of researches on multiobjective path planning for robots, such as [7–12]. In [7, 10], NSGA-II which was introduced in [13] was used to obtain the Pareto front of the multiobjective path planning problem. Zhu et al. [8] proposed two multiobjective memetic algorithms (MOMAs) for the wheeled robot path planning problem, and the algorithm was evaluated in both simulation and real environment. In [9], the authors developed a new multiobjective optimization algorithm which is called the multiobjective firefly algorithm (MO-FA) to resolve a path planning problem which has three objectives. In [12], a local search heuristic was hybrid with SPEA2 to find the efficient solutions of the presented problem.Researches on the combinatorial multiobjective problems (CMOPs) have a significant contribution to the study of multiobjective path planning, especially for scheduling problems. Heuristic algorithms have been widely studied for approximating the Pareto front of CMOPs because it is usually NP-hard to find the exact Pareto front of a CMOP. The Pareto local search (PLS) is one of the efficient algorithms for resolving CMOPs, and it is an extension of a single-objective local search [14]. Lust and Teghem [15] proposed 2PPLS, and it is a variant of PLS which consists of two phases of PLS in the algorithm. Based on PLS, various meta-heuristics have been proposed; in [16], the authors combined the idea of PLS and MOEA/D, and the proposed algorithm MOMAD contains three populations which represent subproblem solutions, PLS solutions, and external solutions, respectively. [17] proposed the Grid Weighted Sum Pareto Local Search (GWS-PLS), its main contribution is using the grid Pareto dominance instead of the Pareto dominance, and the grid Pareto dominance method enables the algorithm to adapt to both concave and convex problems; results show that GWS-PLS performs well in the multiobjective traveling salesman problem and multiobjective knapsack problem. Recently, [18–20] studied the multiobjective adaptive large neighborhood search (MOALNS), which is a heuristic algorithm based on the single objective of the adaptive large neighborhood search. In [21], the authors proposed MOALNS/D which is an improved version of MOALNS by combining the idea of decomposition with MOALNS.In this paper, we mainly focus on multiobjective path planning for UAV/UGV collaboration systems working in persistent tasks; as mentioned above, the present related works often have the following shortcomings: firstly, path planning for charging robots was focused on while seldom works considered both replenishment robots and UAVs; secondly, the charging robots were only considered mobile charging stations while these robots can also complete other tasks; and thirdly, the single objective was considered in previous works while the decision-maker may need to tradeoff multiobjectives when planning paths for path planning for UAV/UGV collaboration systems.In this paper, we firstly present a new scheduling problem and then propose an efficient algorithm for resolving the problem. The contributions of our work are shown as follows:(1)
The problem is formulated as mixed integer linear programming, and planning paths for UAVs and UGVs simultaneously as well as UGVs have multitask points to visit(2)
The presented mathematical model is a biobjective optimization problem, which is firstly considered in this filed as far as we have known(3)
A memetic algorithm which combines PLS and MOALNS is proposed for resolving the presented path planning problem(4)
To resolve the problem efficiently, several heuristics and the local search procedure are developed for the algorithmThe remainder of the paper is organized as follows. In Section2, we formally define the problem, and the corresponding mathematic model is presented. In Section 3, we present the framework of the proposed algorithm as well as the initialization method, solution representation, operators for the presubsolution, and proposed Hybrid Pareto Local Search (HPLS). In Section 4, we give details on MOALNS in HPLS, which contains five removal heuristics and three insertion heuristics. In Section 5, we implement the proposed algorithm for the presented problem and compare it with three other algorithms. In Section 6, we provide conclusions and avenues for future research.


## 2. Problem Statement

The problem we addressed in this paper is a combinational optimization problem, and we define and formulate it as follows.Given a set of UAV and UGV working points, denote them asVu andVg, respectively; the number of UAVs and UGVs are M and N, respectively; UAVs have a fixed velocity of vu while the maximum velocity of UGVs is vmax, and UAVs have the maximum endurance of Tc, which means that all UAVs need to be replenished by UGVs periodically. A solution of the problem consists of paths of UAVs and UGVs, and two objectives, total length and makespan, should be optimized simultaneously to obtain an external set which contains a set of efficient solutions. The UAV and UGV paths should meet the following conditions: each UAV working point should be visited exactly once by any UAV, and according to the planned UAV path, all recharging points and the corresponding time will be generated, UGVs need to visit each UGV working point exactly, and also all recharging points should be visited by UAV before the UAV runs out of energy. Other notations used for the mathematical model are given as follows:vuk: the kth UAV working point, where k∈1,⋯,K and Vu=⋃1<k<Kvuk is the set of all UAV working pointsvgh: the hth UGV working point, where h∈1,⋯,H and Vg=⋃1<h<Hvgh is the set of all UGV working pointsxijm: a binary variable which equals to 1 if the mth UAV travels from the ith UAV working point to the jth UAV working point and 0 if otherwisexi′j′n′: a binary variable which equals to 1 if the nth UGV travels from the i′th UGV working point to the j′th working point and 0 if otherwisecij: the Euclidean distance between the ith UAV working point and jth UAV working pointci′j′′: the Euclidean distance between the i′th UGV working point and j′th UGV working pointpum: the mth UAV path, where m∈1,⋯,M is the index of UAVpgn: the nth UGV path, where n∈1,⋯,N is the index of UGVtvc: the recharging time of vcτnl: the lth recharging point in the nth UGV path, wherel∈1,⋯,Ln, Ln is the number of recharging points inpgn, and Vc=⋃1≤n≤N⋃1≤l≤Lτnl is the set of all recharging pointsThe formal definition of the problem is as follows: letG1=Vu,Eu,c be an undirected graph, the problem is to find a path pu, which contains M subpaths: pum, and each subpath has the same start position: vu1; meanwhile, for each vertex in Vu\vu1, it should be visited exactly once by pu. For the M subpaths, the set of recharging vertices Vc can be obtained by considering Tc, and let G2=Vg⋃Vc,c′ be another undirected graph, finding a path pg which contains N subpaths: pgn, and the start vertex of each subpath is vg1; in addition, each vertex in Vg⋃Vc\vg1 should be visited by pg exactly once, and the arrival time of each vertex in Vc should be less than its corresponding recharging time. A solution of the problem is composed of pu andpg. The optimization problem is biobjective; furthermore, the minimization of total length implies reducing the sum of the length of pu andpg, and the minimization of makespan implies reducing the time consumption of the UAV/UGV collaboration system.The subsegment in one postsubsolution can be described as follows: for a postsubsolutionpgm, its subsegments can have two cases: (1) the path formed between two adjacent recharging points and (2) the path between the last recharging point and the end ofpgm. Figure 1 shows an example of the subsegment, in which snz denotes the zth subsegment in the nth UGV path; then, the length of subsegment snz is
(1)lnz=∑i=1snz−1csnzi,snzi+1.Figure 1
An example of the subsegments in the postsubsolution.There have been two objectives in the proposed problem: path length and makespan. For the objective function of length costL, it contains two components: Luand Lg, which represent the length of UAV paths and the length of UGV paths, respectively, and the effect of the objective of makespan is to minimize the maximum working time of UAVs and UGVs. The two objectives can be, respectively, formulated as the following two equations.
(2)min∑m=1MLum+∑n=1NLgn,(3)minmaxTum,Tgn,whereLum and Lgn represent the length of pumand pgn, respectively, and Tumand Tgn denote the makespan of pum and pgn, respectively. Lum, Lgn, Tum, and Tgn can be calculated according to
(4)Lum=∑i=1K∑j=1Kcijxijm,(5)Lgm=∑i′=1H∑j′=1Hci′j′′xi′j′n,(6)Tum=Lumvu,(7)Tgn=tnsn+∑e∈Epnce.The objective functions are subjected to the following constraints:(8)∑m=1M∑i=1Kxijm=1,∀j∈2,⋯,K,(9)∑m=1M∑j=2Kxijm=1,∀j∈1,⋯,K,(10)∑n=1N∑i′=1H+Lxi′j′n′=1,∀j′∈2,⋯,H+L,(11)∑n=1N∑j′=2H+Lxi′j′n′=1,∀i′∈1,⋯,H+L,(12)tns−tns−1≤Tc,∀n∈1,⋯,N,∀s∈1,⋯,sn,(13)xijm=1,∀i∈1,⋯,K,∀j∈1,⋯,K,∀m∈1,⋯,M,(14)xi′j′n=1,∀i∈1,⋯,K,∀j∈1,⋯,K,∀n∈1,⋯,N.where equations (8) and (9) can guarantee that the edge that enters each node in Vu is selected and the edge that leaves each node in Vu is selected, respectively. Equations (10) and (11) make sure that every node in Vg⋃Vc is selected to be visited exactly. Equation (12) implies that the solution should meet the constraint of recharging time windows; i.e., the time interval between two adjacent recharging points in the path shall not exceed the maximum interval Tc. Equation (13) formulates the domain of variable xijm, which expresses whether the mth UAV travels from vui to vuj or not; similarly, equation (14) expresses whether the nth UGV travels from vgi′ to vgj′ or not.


## 3. Proposed Approach

In this section, the structure of the solution is presented firstly, and then, the framework of MOALP and operators for the presubsolution are given.


### 3.1. Solution Representation

The structure of the solution is shown in Figure2, and it can be seen from the figure that the solution of the problem consists of two components: UAV path and UGV path, and vu1 and vg1 are the UAV start point and UGV start point, respectively; both UAV and UGV paths are composed of several subpaths, and every subpath is corresponding to a robot path; furthermore, the length of the UAV path is fixed at M+K−1, and the UGV path length is not fixed since the recharging point set is determined by the UAV path.Figure 2
Structure of the solution.


### 3.2. Framework of MOALP

The proposed algorithm in this paper integrates the multiobjective adaptive large neighborhood search (MOALNS) into the PLS framework, and it is called multiobjective ALNS hybrid with PLS (MOALP); the detail of MOALP is shown in Algorithm1.Similar to MOMAD [16], MOALP maintains three populations during the optimization process, which are as follows:
(1)
PP: the population will be undergone PLS(2)
PL: this population contains the solutions corresponding to subproblems(3)
PE: the external population contains all nondominated solutions found so farAlgorithm 1: Framework of MOALP.
Require: an instance; number of subproblems:N;set of reference vectors λ1,⋯,λN.Ensure:PE1:InitializationN↓,PL↑,PP↑,PE↑,λ↑2: repeat3:HPLSPP↓,PE↕,PL↕4:fork∈1,⋯,Ndo5:select_popk↓,PL↓,p1↑,p2↑6:PMXp1↓,p2↓,pa↑7:generate_pgpa↓,pg↑8:MOALNS/Dpa↓,pg↓,PT↑,PE↕9:updatePT↓,PP↕10:updateDPT↓,PP↕,λ↓11: end for12:until stopping criteria was met


### 3.3. Initialization

The initialization method for the postsubsolution is as follows: first of all, a temporary initial postsubsolution is set by random initialization; then, a reinforcement procedure for the postsubsolution which is shown in Figure3 is applied in the temporary set to improve the number of feasible solutions in the initial set. The solution reinforcement proposed in this paper is based on the following two facts: firstly, given a postsubsolution, recharging points are sequential for each UGV path, and secondly, in a UGV path, the distance of two adjacent recharging points is less than Dmax, where Dmax=vmaxtτnl+1−tτnl.Figure 3
Solution reinforcement.The operators which are proposed for resolving the multiple travelling salesman problem are used to generate presubsolutions, and in this paper, we use the PMX crossover operator and single-point mutation operator as the variation operators to generate presubsolutions.


### 3.4. PLS Hybrids with MOALNS (HPLS)

MOALNS is hybrids with PLS to resolve the presented combinatorial multiobjective optimization problem in this paper, and it is called Hybrid PLS (HPLS). The framework of HPLS is shown in Algorithm2.Algorithm 2: HPLS.
Require:PP,PEEnsure:PP,PE1:P=PP2:whileP≠∅do3:Pa=∅4:fors∈Pdo5:MO−ALNSpg′↓,PT↑6:updatePE↕,PT↕7:updatePa↕,PT↕8:end for9:end whileIn HPLS,PP refers to the population which will undergo HPLS; different from PLS, we here use the presented MOALNS as the local search heuristics. Once a postsubsolution pg′ was input into MOALNS, a temporary set called PT will be produced, where PT is an efficient set for the input postsubsolution pg′; the external set PE will be updated by PT during every iteration. MOALNS can be regarded as the problem-specific multiobjective local search for HPLS, while PLS often adapts a problem-specific single-objective local search heuristic.


## 3.1. Solution Representation

The structure of the solution is shown in Figure2, and it can be seen from the figure that the solution of the problem consists of two components: UAV path and UGV path, and vu1 and vg1 are the UAV start point and UGV start point, respectively; both UAV and UGV paths are composed of several subpaths, and every subpath is corresponding to a robot path; furthermore, the length of the UAV path is fixed at M+K−1, and the UGV path length is not fixed since the recharging point set is determined by the UAV path.Figure 2
Structure of the solution.


## 3.2. Framework of MOALP

The proposed algorithm in this paper integrates the multiobjective adaptive large neighborhood search (MOALNS) into the PLS framework, and it is called multiobjective ALNS hybrid with PLS (MOALP); the detail of MOALP is shown in Algorithm1.Similar to MOMAD [16], MOALP maintains three populations during the optimization process, which are as follows:
(1)
PP: the population will be undergone PLS(2)
PL: this population contains the solutions corresponding to subproblems(3)
PE: the external population contains all nondominated solutions found so farAlgorithm 1: Framework of MOALP.
Require: an instance; number of subproblems:N;set of reference vectors λ1,⋯,λN.Ensure:PE1:InitializationN↓,PL↑,PP↑,PE↑,λ↑2: repeat3:HPLSPP↓,PE↕,PL↕4:fork∈1,⋯,Ndo5:select_popk↓,PL↓,p1↑,p2↑6:PMXp1↓,p2↓,pa↑7:generate_pgpa↓,pg↑8:MOALNS/Dpa↓,pg↓,PT↑,PE↕9:updatePT↓,PP↕10:updateDPT↓,PP↕,λ↓11: end for12:until stopping criteria was met


## 3.3. Initialization

The initialization method for the postsubsolution is as follows: first of all, a temporary initial postsubsolution is set by random initialization; then, a reinforcement procedure for the postsubsolution which is shown in Figure3 is applied in the temporary set to improve the number of feasible solutions in the initial set. The solution reinforcement proposed in this paper is based on the following two facts: firstly, given a postsubsolution, recharging points are sequential for each UGV path, and secondly, in a UGV path, the distance of two adjacent recharging points is less than Dmax, where Dmax=vmaxtτnl+1−tτnl.Figure 3
Solution reinforcement.The operators which are proposed for resolving the multiple travelling salesman problem are used to generate presubsolutions, and in this paper, we use the PMX crossover operator and single-point mutation operator as the variation operators to generate presubsolutions.


## 3.4. PLS Hybrids with MOALNS (HPLS)

MOALNS is hybrids with PLS to resolve the presented combinatorial multiobjective optimization problem in this paper, and it is called Hybrid PLS (HPLS). The framework of HPLS is shown in Algorithm2.Algorithm 2: HPLS.
Require:PP,PEEnsure:PP,PE1:P=PP2:whileP≠∅do3:Pa=∅4:fors∈Pdo5:MO−ALNSpg′↓,PT↑6:updatePE↕,PT↕7:updatePa↕,PT↕8:end for9:end whileIn HPLS,PP refers to the population which will undergo HPLS; different from PLS, we here use the presented MOALNS as the local search heuristics. Once a postsubsolution pg′ was input into MOALNS, a temporary set called PT will be produced, where PT is an efficient set for the input postsubsolution pg′; the external set PE will be updated by PT during every iteration. MOALNS can be regarded as the problem-specific multiobjective local search for HPLS, while PLS often adapts a problem-specific single-objective local search heuristic.


## 4. MOALNS for the Postsubsolution

MOALNS is adopted as the solver for obtaining the postsubsolution, and its framework is shown in Algorithm3. It is obvious that MOALNS is an extension of a single-objective ALNS [21].Algorithm 3: MOALNS for the postsubsolution.
Require: A solution:p.Ensure: A temporary efficient set:PT1:x=pg2:initializeT↑,c↑,ω↑3:repeat4:x′=x5: Randomly select a removal heuristicR, and remove several vertices from x by usingR.6: Randomly select an insertion heuristicI, and repair x by usingI.7:local_optimizationx8:acceptance_criteriax′↓,x↓,accept↑9:ifaccept==0then10:PT=PT,x11:end if12:until stop criteria was metSimilar to ALNS, several different removal and insertion heuristics can be applied in the algorithm; in this work, we propose the following removal and insertion heuristics for MOALNS.


### 4.1. Removal Heuristics

The removal heuristics developed in this paper can be divided into two different types: removal heuristics for UGV working points and removal heuristics for recharging points. UGV working points and recharging points will be omitted to WP removal and CP removal, respectively, in the rest of the paper.(1)
WP worst removalGiven a UGV working pointuj∈pg\Vc⋃vg1 which is served by the nth UGV in a postsubsolutionpgn, we define the cost of the vertex uj as rj, and rj can be calculated by the following equation:
(15)rj=cuj−1+cuj,uj+1−cuj−1,uj+1,whereuj+1≠va1 and rj=cuj−1,uj when uj+1=va1; then, the WP which has the highest cost will be removed from the postsubsolution according to the following equation:
(16)argmin1≤j≤pgnrj.(2)
WP random removalThe WP random removal simply selects a UGV working point at random and removes it from the postsubsolution.(3)
WP segment removalIn this heuristic, a segment is randomly selected and removed from the current postsubsolutionpg; this heuristic is inspired by the segment removal developed in [22], which was used for resolving the generalized traveling salesman problem.
(4)
CP worst removalGiven a postsubsolutionpg, considering the j th recharging point in the postsubsolution pgn, where n∈1,⋯,N and j∈1,⋯,sn, the removal cost of unj is defined as the sum of rnj and dnj, where rnj and dnj represent the cost of length and time constraint penalty, respectively. For a recharging point τnj in pgn, its cost of length is defined as rnj=cτnj−1,τnj+cτnj,τnj+1−cτnj−1, where j≠Ln and rnj=cτnj−1,τnj whenj=Ln.The cost of the time constraint of vertexτnj is defined as dnj=pτnj−1,τnj+pτnj,τnj+1−pτnj−1,τnj−1, where j≠Ln and dnj=pτnj−1,τnj when j=Ln; px,y is a penalty function which is defined as the following equation.
(17)px,y=1,cx,yvmax>tx−ty,0,cx,yvmax≤tx−ty.The recharging point which would be removed can be found by calculating the following equation:(18)argmin1≤n≤Nmin1≤j≤Lnβdnj+rnj,whereLgn<β<+∞ is a weight parameter. The positive effects of the calculation method of the cost for this heuristic are twofold: firstly, the existence of βdnj can make sure that the adjacent recharging points meet the recharging time window constraint, so the feasibility of the postsubsolution can be ensured during iterations. Furthermore, by considering rnj in the removal cost, not only can the total length of postsubsolution be decreased but also the makespan of it can be reduced since there will be more time redundancy for UGVs to visit UGV working points.
(5)
CP random removalSimilar to the WP random removal, one recharging point inpg will be selected and removed randomly in the CP random removal.


### 4.2. Insertion Heuristics

Two insertion heuristics for WP insertion and one insertion heuristic for CP insertion are proposed to insert WP or CP into the postsubsolution.(1)
WP cheapest insertionGiven a partial postsubsolutionpgn, the vertex u∈Vg\pg which has the minimum insertion cost and insertion position can be obtained by minimizing
(19)Inzju=csnzj,u+cu,snzj+1−csnzj,snzj+1,wheresnz means the zth subsegment in the nth UGV path andz∈1,⋯,Ln+1.
(2)
WP nearest insertionGiven a partial postsubsolutionpgn, we first calculate the distance between every u∈Vg\pg and each subsegment snz according to
(20)distu,snz=minv∈snzcu,v.And then, the nearest insertion can be formulated as(21)argminu∈Vg\pgmin1≤n≤Nmin1≤h≤Hndistu,snz.When the insertion vertexu and insertion subsegment lnz were obtained by using equation (21), the vertex would be inserted into the selected subsegment snz by using the cheapest insertion.
(3)
CP unified worst insertionGiven a partial postsubsolutionpgn, the insertion cost in this heuristic is the weighted sum of penalty for the recharging time window constraint ITnzj, recharging point insertion cost IHnzj, and total length cost ILnzj, where n,z,j represent the index of UGV, subsegment, and point in the subsegment, respectively.The insertion cost for the recharging time window constraint is defined asITnzju=pτnz−1,u+pu,τnz, where z≠Ln+1,∀j∈1,⋯,snz, and ITnzju=pτnz−1,u when z=Ln. The factor of the recharging point insertion cost is IHnzju=cτnz−1,u+cu,τnz+1−cτnz−1,τnz+1, where z≠Ln+1,∀j∈1,⋯,snz, and IHnzju=cτnz−1,u when z=Ln+1. The total length cost is ILnzju=csnzj,u+cu,snzj+1−csnzj,snzj+1, where j≠snz, and ILnzju=csnzj,u when j=snz. The total insertion cost for a charging point in this heuristic can be calculated by
(22)Ianzj=βITnzju+λ1IHnzju+λ2ILnzju,whereλ1 and λ2 are the weight of CP insertion length cost and path length cost, respectively, and the smaller λ1 is, the more minimization of makespan is considered, and the smaller λ2 is, the more minimization of path length is considered. In addition, Lgn<β+∞, and βITnzju represents the constraint of recharging time windows. The CP which is to be inserted and the corresponding insertion position can be obtained according to the following equation.
(23)argminu∈Vc\pmin1≤n≤Nmin1≤h≤Lnmin1≤j≤snzIanzj.


### 4.3. Local Optimization

Except for removal and insertion heuristics given above, a local optimization method is also developed to improve the performance of the local solution during every iteration, and it can be regarded as a procedure for recharging points to be reallocated based on the current postsubsolution. Given a postsubsolutionpg, the basic idea of local optimization is solution reconstruction which firstly removes all recharging points from the postsubsolution pgn and then inserts them into pg again by means of the local reallocation method.The insertion cost for recharging points of local optimization contains three components: recharging time window constraint costIWnzj, path length cost ILnzj, and makespan cost IMnzj, where n,z,j represent the index of UGV, subsegment, and point in the subsegment, respectively. In detail, IWnzj is defined as equation (24); ILnzj=cτnj−1,τnj+cτnj,τnj+1−cτnj−1, where j≠Ln and rnj=cτnj−1,τnj when j=Ln; IWnzj=ILnzju/vmax where z=Ln+1, Tn+ILnzju/vmax>Tmax, and otherwiseIWnzj=0.
(24)IWnzju=∞,lnz+lLnzjuvmax>tτnz−1−tτnz,0,lnz+lLnzjuvmax≤tτnz−1−tτnz.The total insertion cost of local optimization isIonzj=IWnzju+ϵILnzju+1−ϵIMnzju, where 0≤ϵ≤1 is a coefficient which is used to tradeoff the path length and makespan by changing the value of ϵ. The total insertion cost is minimized to select the insertion point and position as defined in the following equation.
(25)argminu∈Vc\pgmin1≤n≤Nmin1≤h≤Lnmin1≤j≤snzIonzj.


### 4.4. Weight-Adaptive Approach, Acceptance Criteria, and Stopping Criteria

In MOALNS, the score of heuristics is updated during every iteration, and in this paper, we use the weight-adaptive approach in accordance with [23], and particularly, five different senses are considered when updating the score of insertion and removal heuristics, which is shown in Table 1, and δ1>δ2>δ3>δ4>δ5 is ensured. The standard simulated annealing is adopted as the search framework of the proposed MOALNS, and the acceptance criterion is as follows:
(26)Paccept=minefs′−fsT,1,Table 1
Relation betweenm and S.
ParameterDescriptionδ1Tnew is a nondominated solution in the solution setδ2Tnew is not dominated in the solution set but is nondominated in the current neighborhoodδ3Tnew is not a nondominated solution, but it dominates the current solutionδ4Tnew is not dominated or dominates the current solution and is accepted by the algorithmδ5Tnew is dominated by the current solution and is accepted by the algorithmwhereT is the temperature and its initial value is set to be Tinit; T is updated in every iteration of the algorithm as shown in equation (27), where c is the cooling rate.
(27)Ti+1=Ti−cTi.The stopping criterion of MOALNS is as follows: the temperature will be reheating if no improvement is made to the current solution after the firstR1 iterations, and MOALNS ends if no improvement is made to the current solution after the first R2 iterations. And no improvement is that the new solution cannot dominate the current solution.


## 4.1. Removal Heuristics

The removal heuristics developed in this paper can be divided into two different types: removal heuristics for UGV working points and removal heuristics for recharging points. UGV working points and recharging points will be omitted to WP removal and CP removal, respectively, in the rest of the paper.(1)
WP worst removalGiven a UGV working pointuj∈pg\Vc⋃vg1 which is served by the nth UGV in a postsubsolutionpgn, we define the cost of the vertex uj as rj, and rj can be calculated by the following equation:
(15)rj=cuj−1+cuj,uj+1−cuj−1,uj+1,whereuj+1≠va1 and rj=cuj−1,uj when uj+1=va1; then, the WP which has the highest cost will be removed from the postsubsolution according to the following equation:
(16)argmin1≤j≤pgnrj.(2)
WP random removalThe WP random removal simply selects a UGV working point at random and removes it from the postsubsolution.(3)
WP segment removalIn this heuristic, a segment is randomly selected and removed from the current postsubsolutionpg; this heuristic is inspired by the segment removal developed in [22], which was used for resolving the generalized traveling salesman problem.
(4)
CP worst removalGiven a postsubsolutionpg, considering the j th recharging point in the postsubsolution pgn, where n∈1,⋯,N and j∈1,⋯,sn, the removal cost of unj is defined as the sum of rnj and dnj, where rnj and dnj represent the cost of length and time constraint penalty, respectively. For a recharging point τnj in pgn, its cost of length is defined as rnj=cτnj−1,τnj+cτnj,τnj+1−cτnj−1, where j≠Ln and rnj=cτnj−1,τnj whenj=Ln.The cost of the time constraint of vertexτnj is defined as dnj=pτnj−1,τnj+pτnj,τnj+1−pτnj−1,τnj−1, where j≠Ln and dnj=pτnj−1,τnj when j=Ln; px,y is a penalty function which is defined as the following equation.
(17)px,y=1,cx,yvmax>tx−ty,0,cx,yvmax≤tx−ty.The recharging point which would be removed can be found by calculating the following equation:(18)argmin1≤n≤Nmin1≤j≤Lnβdnj+rnj,whereLgn<β<+∞ is a weight parameter. The positive effects of the calculation method of the cost for this heuristic are twofold: firstly, the existence of βdnj can make sure that the adjacent recharging points meet the recharging time window constraint, so the feasibility of the postsubsolution can be ensured during iterations. Furthermore, by considering rnj in the removal cost, not only can the total length of postsubsolution be decreased but also the makespan of it can be reduced since there will be more time redundancy for UGVs to visit UGV working points.
(5)
CP random removalSimilar to the WP random removal, one recharging point inpg will be selected and removed randomly in the CP random removal.


## 4.2. Insertion Heuristics

Two insertion heuristics for WP insertion and one insertion heuristic for CP insertion are proposed to insert WP or CP into the postsubsolution.(1)
WP cheapest insertionGiven a partial postsubsolutionpgn, the vertex u∈Vg\pg which has the minimum insertion cost and insertion position can be obtained by minimizing
(19)Inzju=csnzj,u+cu,snzj+1−csnzj,snzj+1,wheresnz means the zth subsegment in the nth UGV path andz∈1,⋯,Ln+1.
(2)
WP nearest insertionGiven a partial postsubsolutionpgn, we first calculate the distance between every u∈Vg\pg and each subsegment snz according to
(20)distu,snz=minv∈snzcu,v.And then, the nearest insertion can be formulated as(21)argminu∈Vg\pgmin1≤n≤Nmin1≤h≤Hndistu,snz.When the insertion vertexu and insertion subsegment lnz were obtained by using equation (21), the vertex would be inserted into the selected subsegment snz by using the cheapest insertion.
(3)
CP unified worst insertionGiven a partial postsubsolutionpgn, the insertion cost in this heuristic is the weighted sum of penalty for the recharging time window constraint ITnzj, recharging point insertion cost IHnzj, and total length cost ILnzj, where n,z,j represent the index of UGV, subsegment, and point in the subsegment, respectively.The insertion cost for the recharging time window constraint is defined asITnzju=pτnz−1,u+pu,τnz, where z≠Ln+1,∀j∈1,⋯,snz, and ITnzju=pτnz−1,u when z=Ln. The factor of the recharging point insertion cost is IHnzju=cτnz−1,u+cu,τnz+1−cτnz−1,τnz+1, where z≠Ln+1,∀j∈1,⋯,snz, and IHnzju=cτnz−1,u when z=Ln+1. The total length cost is ILnzju=csnzj,u+cu,snzj+1−csnzj,snzj+1, where j≠snz, and ILnzju=csnzj,u when j=snz. The total insertion cost for a charging point in this heuristic can be calculated by
(22)Ianzj=βITnzju+λ1IHnzju+λ2ILnzju,whereλ1 and λ2 are the weight of CP insertion length cost and path length cost, respectively, and the smaller λ1 is, the more minimization of makespan is considered, and the smaller λ2 is, the more minimization of path length is considered. In addition, Lgn<β+∞, and βITnzju represents the constraint of recharging time windows. The CP which is to be inserted and the corresponding insertion position can be obtained according to the following equation.
(23)argminu∈Vc\pmin1≤n≤Nmin1≤h≤Lnmin1≤j≤snzIanzj.


## 4.3. Local Optimization

Except for removal and insertion heuristics given above, a local optimization method is also developed to improve the performance of the local solution during every iteration, and it can be regarded as a procedure for recharging points to be reallocated based on the current postsubsolution. Given a postsubsolutionpg, the basic idea of local optimization is solution reconstruction which firstly removes all recharging points from the postsubsolution pgn and then inserts them into pg again by means of the local reallocation method.The insertion cost for recharging points of local optimization contains three components: recharging time window constraint costIWnzj, path length cost ILnzj, and makespan cost IMnzj, where n,z,j represent the index of UGV, subsegment, and point in the subsegment, respectively. In detail, IWnzj is defined as equation (24); ILnzj=cτnj−1,τnj+cτnj,τnj+1−cτnj−1, where j≠Ln and rnj=cτnj−1,τnj when j=Ln; IWnzj=ILnzju/vmax where z=Ln+1, Tn+ILnzju/vmax>Tmax, and otherwiseIWnzj=0.
(24)IWnzju=∞,lnz+lLnzjuvmax>tτnz−1−tτnz,0,lnz+lLnzjuvmax≤tτnz−1−tτnz.The total insertion cost of local optimization isIonzj=IWnzju+ϵILnzju+1−ϵIMnzju, where 0≤ϵ≤1 is a coefficient which is used to tradeoff the path length and makespan by changing the value of ϵ. The total insertion cost is minimized to select the insertion point and position as defined in the following equation.
(25)argminu∈Vc\pgmin1≤n≤Nmin1≤h≤Lnmin1≤j≤snzIonzj.


## 4.4. Weight-Adaptive Approach, Acceptance Criteria, and Stopping Criteria

In MOALNS, the score of heuristics is updated during every iteration, and in this paper, we use the weight-adaptive approach in accordance with [23], and particularly, five different senses are considered when updating the score of insertion and removal heuristics, which is shown in Table 1, and δ1>δ2>δ3>δ4>δ5 is ensured. The standard simulated annealing is adopted as the search framework of the proposed MOALNS, and the acceptance criterion is as follows:
(26)Paccept=minefs′−fsT,1,Table 1
Relation betweenm and S.
ParameterDescriptionδ1Tnew is a nondominated solution in the solution setδ2Tnew is not dominated in the solution set but is nondominated in the current neighborhoodδ3Tnew is not a nondominated solution, but it dominates the current solutionδ4Tnew is not dominated or dominates the current solution and is accepted by the algorithmδ5Tnew is dominated by the current solution and is accepted by the algorithmwhereT is the temperature and its initial value is set to be Tinit; T is updated in every iteration of the algorithm as shown in equation (27), where c is the cooling rate.
(27)Ti+1=Ti−cTi.The stopping criterion of MOALNS is as follows: the temperature will be reheating if no improvement is made to the current solution after the firstR1 iterations, and MOALNS ends if no improvement is made to the current solution after the first R2 iterations. And no improvement is that the new solution cannot dominate the current solution.


## 5. Experimental Results

### 5.1. Performance Metrics

(1)
Set coverage (C-metric) [16]: let A and B be two efficient sets of an MOP; CA,B is defined as the percentage of the solutions in B that are dominated by at least one solution in A; that is,
(28)CA,B=∣u∈B∣∃v∈A:vdominatesu∣B.(2)
Hypervolume (HV) [16]: let r=r1,r2,⋯,rmT be a reference point in the objective space which is dominated by all solutions in a PF approximation S. HV (S) indicates the volume of the region in the objective space which is dominated by S and dominatesr.
(29)HVS=volume⋃x∈sf1x,r1×⋯fmx,rm.


### 5.2. Test Instances

Since the problem presented in this paper is a new problem in the literature and there are no established benchmark sets yet, we developed some instances for computational studies to test our proposed algorithm. Three different UAV working senses and five UGV working senses were generated, and the details of the tested instances are shown in Table2.Table 2
Scenario configuration.
IndexUAV scenarioUGV scenario12312345Num WPs8142081216202415 instances were developed by combining UAV and UGV scenarios, and based on these instances, velocity of UAV (vu), maximum velocity of UGVs (vmax), number of UAVs (M), and number of UGVs (N) were set, and particularly, vu=2m/s and vmax=2m/s were ensured. An example of instance is like 1-5-2-3, which means using UAV scenario 1 and UGV scenario 5; the number of UAVs and UGVs is 2 and 3, respectively.


### 5.3. Compared Algorithms

To show the performance of MOALP, we compare it with three other algorithms.(1)
PLS [15]: this algorithm is designed for combinatorial MOP, and an external set and search set are maintained in the algorithm. In this paper, we use PMX to generate the neighborhood of the presubsolution, and then, local search heuristics proposed in this paper are integrated with PLS to find the efficient set of postsubsolutions(2)
MOMAD [16]: this algorithm is a memetic algorithm which is based on the framework of PLS, and it uses the idea of decomposition to improve the diversity of the attained PF. In the simulation experiments of this work, we implemented the framework of MOMAD and integrated local search heuristics with MOMAD to be adaptive to the problem presented in this paper(3)
MOALNS [20]: multiobjective adaptive large neighborhood search (MOALNS) is an extension of ALNS in multiobjective optimization, its major components include solution destroy, solution repair, weight adaptive, solution acceptance. In this paper, we use a standard Simulated Annealing (SA) as the optimization framework, as well as the proposed removal and insertion heuristics, and also, PMX is implemented to generate the neighborhood of presubsolution.


#### 5.3.1. Parameter Setting

For MOALP, PLS, MOMAD, and MOALNS, we set the size of PL to be 50, and the number of working points to be removed isrand0.2H,0.3H, where H is the total number of working points. The number of recharging points to be removed is rand0.2H,0.4H, where Nc is the total number of recharging points in the current solution. Table 3 shows the parameter setting of MOALP, where λ1 has two values: 0.3 and 0.4, which means there exists two insertion heuristics for recharging points, while there have been two insertion heuristics for working points; four insertion heuristics are implemented in the algorithm since we combine a working point insertion with a recharging point insertion heuristic as one integral insertion heuristic; similarly, there have been 6 removal heuristics since three working removal and two recharging removal heuristics are implemented in the algorithm.Table 3
Parameter configuration of MOALP and the compared algorithms.
Parameterϵλ1λ2γ1γ2R1R2σ1σ2σ3σ4σ5Value0.10.3,0.40.30.50.052Nc5Nc107532


### 5.4. Results

Each algorithm runs independently for 5 times, and we use the average of indicators as the compared data resource. TheC-metric values of all the comparisons on each instance are reported in Table 4. The hypervolume values of the efficient sets produced by these algorithms are plotted in Table 5. The average running time consumed by these algorithms is given in Table 6.Table 4
Coverage values (%) between MOALP and MOALNS, MOMAD, and PLS on the problem.
InstanceMOALNSMOMADPLSCA,BCB,ACA,BCB,ACA,BCB,A1-1-2-276.720.065.033.377.016.71-2-2-272.028.020.056.068.70.01-3-3-460.016.165.717.851.44.01-4-2-349.327.551.333.575.314.01-5-2-367.115.463.04.090.00.02-1-2-363.313.380.00.0100.00.02-2-2-226.730.050.016.990.06.72-3-3-424.720.069.30.093.30.02-4-3-471.810.776.70.096.70.02-5-2-473.325.090.00.0100.00.03-1-2-356.526.7100.00.0100.00.03-2-3-425.020.790.00.095.00.03-3-2-444.050.0100.00.0100.00.03-4-2-360.033.0100.00.0100.00.03-5-3-540.013.6100.00.096.70.0Table 5
Hypervolume values of MOALP, MOALNS, MOMAD, and PLS.
InstanceMOALPMOALNSMOMADPLS1-1-2-21.526E+071.126E+071.876E+071.034E+071-2-2-22.323E+070.964E+071.720E+071.433E+071-3-3-43.312E+073.182E+073.284E+072.290E+071-4-2-32.769E+072.735E+071.869E+071.855E+071-5-2-32.417E+072.183E+071.863E+070.986E+072-1-2-30.840E+081.265E+080.408E+080.357E+082-2-2-21.617E+080.955E+080.937E+080.295E+082-3-3-42.810E+082.247E+080.907E+081.218E+082-4-3-41.952E+081.700E+080.796E+080.629E+082-5-2-42.112E+081.421E+080.351E+080.794E+083-1-2-34.848E+086.202E+080.563E+080.655E+083-2-3-48.900E+085.962E+081.090E+081.549E+083-3-2-44.435E+083.711E+080.762E+080.593E+083-4-2-37.478E+085.425E+080.895E+081.241E+083-5-3-54.353E+084.451E+081.209E+080.948E+08Table 6
Running time (s) of MOALP, MOALNS, MOMAD, and PLS.
InstanceMOALPMOALNSMOMADPLS1-1-2-216167281-2-2-219177311-3-3-4302111451-4-2-3302310531-5-2-3362914622-1-2-34744361372-2-2-24738171032-3-3-47759471732-4-3-47267451822-5-2-49892672923-1-2-3100862174753-2-3-41301001105083-3-2-41571212118183-4-2-31461101725553-5-3-5211168558954MOALP outperforms PLS on all test instances in theC-metric, and on 11 out of 15 test instances, CA,B equals to 0.0% which means that solutions in the efficient set obtained by PLS cannot dominate that of MOALP at least once. MOALP has the better C-metric than MOMAD except for 1-2-2-2, and when compared with MOALNS, MOALP performs better than MOALNS on 13 out of 15 instances; furthermore, on 11 test instances, the C-metric of MOALP is more than 10% higher than that of MOALNS.On 11 out of 15 test instances, the hypervolume values of MOALP are shown in Table5; it can be seen that MOALP performs better than all compared algorithms, and except for instances 2-1-2-3, 3-1-3-2, and 3-5-3-5, MOALP outperforms MOALNS in the hypervolume indicator.Regarding the running time, the average running time consumed by MOALP is lower than that of PLS, and compared with MOMAD, the running time of MOALP is shorter on large-scale instances, and PLS runs for the longest time in all test instances.In Figure4, four nondominated solutions resolved by our proposed algorithm MOALP are presented, and it can be seen that UAVs and UGVs can work collaboratively to enable them work in persistent tasks.Figure 4
Nondominated solutions resolved by MOALP: (a) nondominated solution 1, (b) nondominated solution 2, (c) nondominated solution 3, and (d) nondominated solution 4.
(a)(b)(c)(d)


### 5.5. Result Visualization

Figure4 shows four nondominated solutions of instance 1-4-2-3, obtained by using MOALP; we can see that there exist two UAV paths and three UGV paths in the solution; also, the start point of UGV is 1000,1500; the objectives of the four solutions are 2.548E+04,4489, 2.696E+04,4433, 2.798E+04,4264, and 2.969E+04,3505, respectively.


## 5.1. Performance Metrics

(1)
Set coverage (C-metric) [16]: let A and B be two efficient sets of an MOP; CA,B is defined as the percentage of the solutions in B that are dominated by at least one solution in A; that is,
(28)CA,B=∣u∈B∣∃v∈A:vdominatesu∣B.(2)
Hypervolume (HV) [16]: let r=r1,r2,⋯,rmT be a reference point in the objective space which is dominated by all solutions in a PF approximation S. HV (S) indicates the volume of the region in the objective space which is dominated by S and dominatesr.
(29)HVS=volume⋃x∈sf1x,r1×⋯fmx,rm.


## 5.2. Test Instances

Since the problem presented in this paper is a new problem in the literature and there are no established benchmark sets yet, we developed some instances for computational studies to test our proposed algorithm. Three different UAV working senses and five UGV working senses were generated, and the details of the tested instances are shown in Table2.Table 2
Scenario configuration.
IndexUAV scenarioUGV scenario12312345Num WPs8142081216202415 instances were developed by combining UAV and UGV scenarios, and based on these instances, velocity of UAV (vu), maximum velocity of UGVs (vmax), number of UAVs (M), and number of UGVs (N) were set, and particularly, vu=2m/s and vmax=2m/s were ensured. An example of instance is like 1-5-2-3, which means using UAV scenario 1 and UGV scenario 5; the number of UAVs and UGVs is 2 and 3, respectively.


## 5.3. Compared Algorithms

To show the performance of MOALP, we compare it with three other algorithms.(1)
PLS [15]: this algorithm is designed for combinatorial MOP, and an external set and search set are maintained in the algorithm. In this paper, we use PMX to generate the neighborhood of the presubsolution, and then, local search heuristics proposed in this paper are integrated with PLS to find the efficient set of postsubsolutions(2)
MOMAD [16]: this algorithm is a memetic algorithm which is based on the framework of PLS, and it uses the idea of decomposition to improve the diversity of the attained PF. In the simulation experiments of this work, we implemented the framework of MOMAD and integrated local search heuristics with MOMAD to be adaptive to the problem presented in this paper(3)
MOALNS [20]: multiobjective adaptive large neighborhood search (MOALNS) is an extension of ALNS in multiobjective optimization, its major components include solution destroy, solution repair, weight adaptive, solution acceptance. In this paper, we use a standard Simulated Annealing (SA) as the optimization framework, as well as the proposed removal and insertion heuristics, and also, PMX is implemented to generate the neighborhood of presubsolution.


### 5.3.1. Parameter Setting

For MOALP, PLS, MOMAD, and MOALNS, we set the size of PL to be 50, and the number of working points to be removed isrand0.2H,0.3H, where H is the total number of working points. The number of recharging points to be removed is rand0.2H,0.4H, where Nc is the total number of recharging points in the current solution. Table 3 shows the parameter setting of MOALP, where λ1 has two values: 0.3 and 0.4, which means there exists two insertion heuristics for recharging points, while there have been two insertion heuristics for working points; four insertion heuristics are implemented in the algorithm since we combine a working point insertion with a recharging point insertion heuristic as one integral insertion heuristic; similarly, there have been 6 removal heuristics since three working removal and two recharging removal heuristics are implemented in the algorithm.Table 3
Parameter configuration of MOALP and the compared algorithms.
Parameterϵλ1λ2γ1γ2R1R2σ1σ2σ3σ4σ5Value0.10.3,0.40.30.50.052Nc5Nc107532


## 5.3.1. Parameter Setting

For MOALP, PLS, MOMAD, and MOALNS, we set the size of PL to be 50, and the number of working points to be removed isrand0.2H,0.3H, where H is the total number of working points. The number of recharging points to be removed is rand0.2H,0.4H, where Nc is the total number of recharging points in the current solution. Table 3 shows the parameter setting of MOALP, where λ1 has two values: 0.3 and 0.4, which means there exists two insertion heuristics for recharging points, while there have been two insertion heuristics for working points; four insertion heuristics are implemented in the algorithm since we combine a working point insertion with a recharging point insertion heuristic as one integral insertion heuristic; similarly, there have been 6 removal heuristics since three working removal and two recharging removal heuristics are implemented in the algorithm.Table 3
Parameter configuration of MOALP and the compared algorithms.
Parameterϵλ1λ2γ1γ2R1R2σ1σ2σ3σ4σ5Value0.10.3,0.40.30.50.052Nc5Nc107532


## 5.4. Results

Each algorithm runs independently for 5 times, and we use the average of indicators as the compared data resource. TheC-metric values of all the comparisons on each instance are reported in Table 4. The hypervolume values of the efficient sets produced by these algorithms are plotted in Table 5. The average running time consumed by these algorithms is given in Table 6.Table 4
Coverage values (%) between MOALP and MOALNS, MOMAD, and PLS on the problem.
InstanceMOALNSMOMADPLSCA,BCB,ACA,BCB,ACA,BCB,A1-1-2-276.720.065.033.377.016.71-2-2-272.028.020.056.068.70.01-3-3-460.016.165.717.851.44.01-4-2-349.327.551.333.575.314.01-5-2-367.115.463.04.090.00.02-1-2-363.313.380.00.0100.00.02-2-2-226.730.050.016.990.06.72-3-3-424.720.069.30.093.30.02-4-3-471.810.776.70.096.70.02-5-2-473.325.090.00.0100.00.03-1-2-356.526.7100.00.0100.00.03-2-3-425.020.790.00.095.00.03-3-2-444.050.0100.00.0100.00.03-4-2-360.033.0100.00.0100.00.03-5-3-540.013.6100.00.096.70.0Table 5
Hypervolume values of MOALP, MOALNS, MOMAD, and PLS.
InstanceMOALPMOALNSMOMADPLS1-1-2-21.526E+071.126E+071.876E+071.034E+071-2-2-22.323E+070.964E+071.720E+071.433E+071-3-3-43.312E+073.182E+073.284E+072.290E+071-4-2-32.769E+072.735E+071.869E+071.855E+071-5-2-32.417E+072.183E+071.863E+070.986E+072-1-2-30.840E+081.265E+080.408E+080.357E+082-2-2-21.617E+080.955E+080.937E+080.295E+082-3-3-42.810E+082.247E+080.907E+081.218E+082-4-3-41.952E+081.700E+080.796E+080.629E+082-5-2-42.112E+081.421E+080.351E+080.794E+083-1-2-34.848E+086.202E+080.563E+080.655E+083-2-3-48.900E+085.962E+081.090E+081.549E+083-3-2-44.435E+083.711E+080.762E+080.593E+083-4-2-37.478E+085.425E+080.895E+081.241E+083-5-3-54.353E+084.451E+081.209E+080.948E+08Table 6
Running time (s) of MOALP, MOALNS, MOMAD, and PLS.
InstanceMOALPMOALNSMOMADPLS1-1-2-216167281-2-2-219177311-3-3-4302111451-4-2-3302310531-5-2-3362914622-1-2-34744361372-2-2-24738171032-3-3-47759471732-4-3-47267451822-5-2-49892672923-1-2-3100862174753-2-3-41301001105083-3-2-41571212118183-4-2-31461101725553-5-3-5211168558954MOALP outperforms PLS on all test instances in theC-metric, and on 11 out of 15 test instances, CA,B equals to 0.0% which means that solutions in the efficient set obtained by PLS cannot dominate that of MOALP at least once. MOALP has the better C-metric than MOMAD except for 1-2-2-2, and when compared with MOALNS, MOALP performs better than MOALNS on 13 out of 15 instances; furthermore, on 11 test instances, the C-metric of MOALP is more than 10% higher than that of MOALNS.On 11 out of 15 test instances, the hypervolume values of MOALP are shown in Table5; it can be seen that MOALP performs better than all compared algorithms, and except for instances 2-1-2-3, 3-1-3-2, and 3-5-3-5, MOALP outperforms MOALNS in the hypervolume indicator.Regarding the running time, the average running time consumed by MOALP is lower than that of PLS, and compared with MOMAD, the running time of MOALP is shorter on large-scale instances, and PLS runs for the longest time in all test instances.In Figure4, four nondominated solutions resolved by our proposed algorithm MOALP are presented, and it can be seen that UAVs and UGVs can work collaboratively to enable them work in persistent tasks.Figure 4
Nondominated solutions resolved by MOALP: (a) nondominated solution 1, (b) nondominated solution 2, (c) nondominated solution 3, and (d) nondominated solution 4.
(a)(b)(c)(d)


## 5.5. Result Visualization

Figure4 shows four nondominated solutions of instance 1-4-2-3, obtained by using MOALP; we can see that there exist two UAV paths and three UGV paths in the solution; also, the start point of UGV is 1000,1500; the objectives of the four solutions are 2.548E+04,4489, 2.696E+04,4433, 2.798E+04,4264, and 2.969E+04,3505, respectively.


## 6. Conclusions and Future Work

In this paper, we propose a multiobjective UAV/UGV collaboration path planning problem, which firstly considers multitasks for UGVs in persistent tasks. To resolve the presented problem, MOALP is proposed. The core of the algorithm is the hybridization of the Pareto local search and multiobjective large neighborhood search, and for the MOALNS in MOALP, we develop a mechanism for removal and insertion heuristics, which contains several removal and insertion heuristics for UGV working points and recharging points; besides, a local optimization method is also implemented after each iteration of MOALNS to improve the performance of the algorithm. The experiments have been conducted to verify MOALP. The comparisons of MOALP with three other algorithms (PLS, MOMAD, and MOALNS) show the efficiency of MOALP in 15 instances.An important avenue of the proposed algorithm for future work is to extend MOALP to resolve more CMOPs, such as mTSP and mKP, and it also can be used to resolve more problems in applications of UAV/UGV collaborative systems.



---

*Source: 9578783-2021-08-15.xml*