Abstract
The location-routing problem (LRP) of unmanned aerial vehicles (UAV) in border patrol for Intelligence, Surveillance, and Reconnaissance is investigated, where the locations of UAV base stations and the UAV flying routes for visiting the targets in border area are jointly optimized. The capacity of the base station and the endurance of the UAV are considered. A binary integer programming model is developed to formulate the problem, and two heuristic algorithms combined with local search strategies are designed for solving the problem. The experiment design for simulating the distribution of stations and targets in border is proposed for generating random test instances. Also, an example based on the practical border in Guangxi is presented to illustrate the problem and the solution approach. The performance of the two algorithms is analysed and compared through randomly generated instances.
1. Introduction
Border patrol is one of military Intelligence, Surveillance, and Reconnaissance (ISR) missions. In many ISR missions especially monitoring mission, Unmanned Aerial Vehicles (UAVs) have become a natural choice with the deployment of air surveillance technology [1, 2]. In border patrol, some areas located on or inside the borderline which have the high rates of illegal activities would be focused. Thus, it is feasible to deploy UAVs to detect the targets regularly and ferry the information such as images, videos, sensor data, etc. to base stations.
However, patrol mission faces severe challenges with rampant crimes such as smuggling. And an increasingly concern is raised with more diversified forms of crimes. To be able to cope with the complexity and diversity of threats effectively, much higher requirements need to be satisfied to ensure the peace and security near the borderline, such as high patrol efficiency and fast reaction speed. Furthermore, due to the harsh environment and complex geographical conditions, it is dangerous for border guards to patrol manually. And the widespread use of the camera is also difficult with its high cost. Therefore, it is meaningful to apply the unmanned aerial vehicles (UAVs) to the border patrol.
Even though unmanned patrol is of great significance, there are still some challenges. Initially, the capacity constraints of base stations should be taken into account. To make full use of each established station, it is not practicable for the amount of its UAVs to be under a lower limit, while it is also unreasonable to exceed an upper limit with the limitations of military ranks. Moreover, since more than one base station should be established to ensure the mission complement, both the amount and the location of base stations need to be optimized. Meanwhile, the flight paths of UAVs are also supposed to be jointly planned. These factors are all involved to minimize the total cost, which increases the complexity of the problem.
After considering the above-mentioned factors, this paper provides a solution for border patrol, which is structured as follows: Section 2 presents the literature review, and Section 3 illustrates the main assumptions and constructs the optimization model. Section 4 introduces two constructive heuristics and the local search improving strategies. The experimental design and computational results are proposed in Section 5. At last, Section 6 presents the conclusion and future works.
2. Literature Review
In regard to location-routing problem, there are many scholars doing the research after Jacobsen and Madsen [3] integrated the study of locations and routing in 1980. Tuzun et al. [4] promoted that LRP is an NP-hard problem. Min et al. [5] proposed a classification of location-routing problems based on facility capacities, vehicle capacities, and so on. Afterwards, LRP with capacity constraints on depots and vehicles was considered more often, called capacitated LRP (CLRP) [6]. Due to the complexity of the problem, a few exact approaches are available, such as branch-and-cut algorithm [7] and column generation approach [8], but can only be used to solve small instances. Therefore, heuristics are designed, which can present an appropriate solution in acceptable running time for the large-scale instances. Barreto et al. [9] proposed a constructive heuristic and employed clustering analysis. There are also many metaheuristics based on neighbourhood search [10]. Greedy randomized adaptive search procedure (GRASP) is designed [11] and even improved with evolutionary local search (ELS) [12]. Hybrid genetic algorithms (GA) [13], simulated annealing heuristic [14], and two-phase hybrid heuristics [15] are also proposed. Nevertheless, only the upper bound of the depot’s capacity is considered in most of the current literatures. It is not economical nor appropriate if the depot’s capacity occupied actually is too small. Thus, this paper takes the lower bound of the depot’s capacity into account to ensure the efficient utilization of the depot’s capacity. Besides, most current researches are conducted in the commercial background such as parcel delivery, and the potential depots are located within the region and the customers are usually around the depots. But in some situations, such as border patrol, the potential base stations are always located inside the border, while the targets are located in the border lines.
For the route planning of UAVs, many researches have been carried out. In 2004, Harder et al. [16] put forward the general architecture of UAVs’ route problem and designed the components of the architecture. The constraints of ammunition load are first considered by Shetty et al. [17]. To scheme the attack path in the war, the main idea is distributing the attack targets to different UAVs and visiting targets in the sequence of importance-differentiation. Mufalli et al. [18] also take the limitations of drone payload into account and use the column-generated heuristics for both sensor selection and flight path. Besides, multiple vehicles and time windows are solved [19]. As for the military applications, unmanned combat aerial vehicles are applied to destruct predetermined targets with the constraints of munitions [17]. Moreover, Avellar, Gustavo S. C. et al. [20] present a solution for the problem of using a group of unmanned air vehicles (UAVs) equipped with image sensors to gather intelligence information, which the objective is to minimum time coverage of ground areas. Persistent Intelligence, Surveillance, and Reconnaissance (PISR) routing problem is also considered by minimizing the time of delivering the collected data to the control station [2]. Unfortunately, most of these researches are based on the traditional routing problem, with little touch and exploration on the optimization of base location and flight path.
From the current literature, there are a few studies on the location-routing problem for UAVs, with mainly two having investigated it. The first one is that İnci Sarıçiçek et al. [21] studied border patrols of UAVs in Turkey in 2014, which uses a two-stage solution method, leading to ineffectiveness of integrating the base location into path planning. The second one is in 2016. Yakıcı [22] studied the base location and path planning under the background of maritime target reconnaissance. However, the constraints of the amount of UAVs are not contained in his study.
In this paper, both capacity constraints on base stations and endurance limitations on UAVs are taken into account in the location-routing problem. And a programming model and two heuristic algorithms are constructed to solve the problem.
3. Model Formulation
In the border patrol mission, there exist a set of potential base stations and a set of determined patrol targets distributed in the border area. Considering the capacity constraints of bases and the endurance limitations of UAVs, the objective of mission planning is to locate the base stations and plan the UAVs’ routes in an effort to minimize the overall cost. For starters, this section presents the assumptions, defines the problem, and builds the mathematical model.
3.1. Problem Assumptions
(i)Assume that all UAVs are in the same type, which means that they have same fight endurance and flying speed.(ii)The flying speed of UAVs is assumed to be constant.(iii)The UAV must depart from and return to the same base station. The situation of swapping the UAVs between different stations is not considered.(iv)Each UAV can visit multiple targets, while each target can only be visited by one UAV.(v)Patrol cost for each mile is only concerned with UAV’s property. Uncertain or unexpected situations, such as weather changes, are not taken into consideration.
3.2. Problem Description
Figure 1 presents an example of the optimization problem for the UAV base location and patrol routes. In patrol missions, a series of base stations with the corresponding equipment are essential. These stations are established inside the borderline: can be reconstructed with the existing sentry posts for reducing the construction cost or be built near the border to reduce the flight distance of UAVs. Thus, the set of all potential locations can be constituted as . Once a base station is determined, the equipped facilities, such as takeoff and recovery device, would generate a fixed establishing cost (). Furthermore, under the considerations of economic cost and military establishment, there exists a limitation on the capacity of base stations. For each base station, it is not reasonable for the amount of its UAVs to be under the lower limit which the station would be underutilized, nor to exceed the upper limit with the limitations of military ranks.
Another necessary element in this problem is patrol targets, which are some small areas located on or inside the borderline where have the high rates of illegal activities like smuggling. Since the sensor of the drone detects one area at one time, these areas can be simplified into nodes. Then we get a set . All target points in this set must be detected once in this mission. And the distance between any two targets (or target and base) () is known. Moreover, UAVs would be consumed some service time to spy on each target, denoted by ().
As for UAVs, is used to denote the set of all UAVs. Since UAVs require maintenance before and after usage, there is a fixed use cost . It could be different for each UAV, but with all UAVs in the same type, it is assumed to be constant to simplify the calculation. Furthermore, knowing that UAVs would fly at a constant speed, the flying time from node to node two nodes () can be given. Besides, the total time containing flying time and service time cannot exceed the UAVs’ maximum flight duration .
The final objective function is formed via the sum of three primary costs: minimize the base establishing cost; accomplish the patrol mission with as few drones as possible; minimize the flight cost of UAVs.
3.3. Mathematical Model
The parameters and variables used in the model are listed as follows.
Sets : , set of all potential base stations : , set of all patrol targets : , set of all UAVs
Parameters : fixed establishing cost of base () : fixed use cost of UAV () : unit patrol cost of UAVs per kilometre : the distance between two targets (or target and base) () : the flying time between two targets (or target and base) () : detecting time for target () : upper limit of the capacity of bases : lower limit of the capacity of bases : the UAVs’ maximum flight duration
Decision Variables , if UAV () fly from node to (); otherwise. , if a base station is determined to be built on node (); otherwise. : auxiliary variable for subtour elimination constraints in the route of UAV ().The objective function (1) minimizes the sum of base establishing cost, UAVs’ use cost and its patrol cost. Constraint (2) expresses the limitation in flow conservation. Constraint (3) ensures that each target point must be visited and assigned to only one UAV. Constraint (4) restricts the time elapsed in each UAV’s flight, containing both flying time and detecting time. Constraint (5) requires that each UAV can be scheduled at most once in one mission planning. Constraints (6) and (7) define the limitations on the capacity of base station, of which the number of equipped UAVs cannot exceed the upper and lower limit. Constraint (8) makes sure that each UAV must turn back to the base station which it departs from. Subtour elimination constrains are expressed in (9). Constraints (10) to (12) declare the variable domains.
4. Algorithms
In this section, two different hybrid heuristics are introduced to construct the feasible solution: nearest point searching algorithm or saving algorithm. Then neighbourhood search serves as an optimization tool to finalize the optimization solution.
4.1. Hybrid Heuristics
4.1.1. Heuristic Based on Clustering and Nearest Point Search (H1)
Heuristic based on clustering and nearest point search (H1) utilizes the strategy of Nearest Neighbour. Nearest Neighbour is a well-known constructive search algorithm that is one of the earliest methods proposed for TSP problems [23]. It adopts the principle of selecting the next nearest unvisited node until all nodes have been covered. It runs fast; however, the optimality of the tours it produces highly depends on the layout of the given nodes.
In H1, every target point is allocated to the nearest base station at first. Then for each station which has assigned targets, the path of UAV is arranged one by one until all assigned targets are detected or the number of UAVs reaches the upper limit of the station. If there are unvisited targets, then allocate the remaining points to the second nearest station. At last, there is a check function to find whether there are some stations that the number of UAVs does not reach lower limit. If so, close the station and reallocate the targets.
The corresponding pseudocode is shown in H1 and the detailed explanation of the heuristic is shown in Algorithm 1.
| ||||||||||||||||||||||||||||
As shown in pseudocode, every target is allocated to its nearest station with the known positions of the potential base stations and target points (Line ). Then sort the selected base stations (Line ) and plan the path of UAVs in each station. While detecting the targets, prioritize the base with the most targets (Line ). As for the details (Line ), launch one UAV at a time, and choose the nearest unvisited target as the next access point. Judge whether the UAV can return back to the original station after visiting the next point. If so, the UAV travels to the next point and keeps detecting, while turning back to the start if not. Repeat the step until all assigned targets are detected or the number of UAVs reaches the upper limit of the station. At this time, check whether there is assigned targets unvisited after sending out all UAVs (Line ). If so, allocate the remaining targets to the second nearest station (Line ).
After all targets have been detected, find whether there are some stations not having enough numbers of UAVs (Line ). If so, give priority to the base with the least targets and close the station (Line ). Then allocate targets of the station to the Nearest Neighbour station (Line ). After that, redetect targets for the new neighbour station (Line ) like what have done in Line .
4.1.2. Heuristic Based on Clustering and CW Saving Search (H2)
Clarke and Wright proposed the saving algorithm in 1964 [24]. This algorithm provides an easy way to solve the vehicle routing problem, but it considers neither the location problem nor the restriction on the numbers of vehicles.
Similar to H1, heuristic based on clustering and CW saving search (H2) first allocates each target point to its nearest base station and has a check function at last. Different from H1 using Nearest Neighbour, CW saving search algorithm is applied in H2 while planning paths to detect targets. The corresponding pseudocode is shown in H2 and the detailed explanation of the heuristic is shown in Algorithm 2.
| ||||||||||||||||||||||||||||
Since the overall framework of H2 is similar to that of H1, the same process will not be repeated in this part. After selecting the base with the most targets, calculate the corresponding distance matrix and saving matrix (Line ). In terms of the details (Line ), launch one UAV at a time. Refer to the saving matrix and merge the target points as many as possible under the limitation of UAVs’ flight endurance, which would generate a flight path for a UAV. Repeat the step until all assigned targets are detected or all UAVs have been sent out. Moreover, CW saving search also works in redetecting targets in Line .
4.2. Neighbourhood Search Improvement
Although the hybrid heuristics can construct a feasible solution quickly, the solution still has room for improvement. For example, some stations can be replaced by another station or some other stations and some UAV routes still can be optimized. Thus, neighbourhood search is introduced to optimize the solution obtained through the heuristics in Section 4.1 and reduce the overall cost. The framework of neighbourhood search is displayed in the pseudocode shown in Algorithm 3.
| ||||||||||||||||||||||||||||||||||||
Given an initial solution, the main process iterates over the parameter until it reaches the preset value of maximum iterations (Line ). In each interaction, a solution would be generated through the operation of closing base stations, which would be described in Section 4.2.1. Then, from Line to Line , local search is performed. After initializing the neighbourhood list (Line ), the local search will not end until running all neighbourhoods without improvement (Line ). Neighbourhood list would be explored exhaustively every time, which returns the best improvement (Line ). Compared with the current solution , if is better, then is the new solution and reinitialize the neighbourhood list, which would restart the counter (Lines –). The neighbourhoods used in this part are detailed in Sections 4.2.2–4.2.4.
Therefore, combining two heuristics with the neighbourhood research respectively, we can produce two algorithms and generate two optimal solutions.
4.2.1. Operation of Closing the Base Station
In the feasible solutions, there exists a possibility that some base stations have not fully utilized the UAVs. Therefore, it might useful to reduce the establishing cost through shutting down some stations. As Figure 2 shows, just two UAVs are launched for both station A and station B, which have not dispatched all UAVs. At this time, we can try to close one of these two stations and find whether these targets can be detected by the UAVs from only one station. If so, then station B can be closed. Furthermore, after closing the base station, the flight paths in station A would be rearranged. To save the calculation time, Nearest Neighbourhood algorithm is used, which is displayed in Figure 2.
4.2.2. Neighbourhood 1: Opt2
This neighbourhood relocates two targets on one flight path in a tentative solution. This operation is mainly meant to reduce the cross-over routes or overlapping routes. In Figure 3, the initial route is 1 → 2 → 3. Then points 2 and 3 are selected and their positions are swapped to see whether there is a better solution.
4.2.3. Neighbourhood 2: Exchange Targets
This neighbourhood is set to swap a target with another one which locates on another path in a tentative solution. The two paths can belong to the same station or two adjacent stations. Figure 4 presents the situation that two targets are in different paths of one station. After exchanging the points 3 and 4, the flight distance of both two flight paths would be decreased, which could help lower the flight cost.
4.2.4. Neighbourhood 3: Insertion
This neighbourhood removes a target and reinserts it in other position in a tentative solution, which may change the owner base station of the target. Figure 5(a) illustrates a relatively straightforward move in one station. Additionally, the path represented by Figure 5(b) relocates the target 6 from station B to station A.
5. Experiment Design and Results
In this section, experiments are designed based on actual characteristics of border patrol and two algorithms are tested with the constructed cases.
5.1. Experiment Design
When designing the experiment, the particularity of border patrol should be taken into account. Since the detection goal is part of borderline, the mission area should be set as an irregular strip area. Thus, as displayed in Figure 6, it is assumed that the detection area is a rectangle with aspect ratio of 2: 1.
In the mission planning, the target points should be located on the borderline while the base stations are inside the borderline. It means that there would be a boundary between potential bases and target points, which is different from the cases in delivery system. Therefore, a random curve is first generated as a boundary (note: this boundary differs from the borderline; the border is in the area of target points). Then base stations and target points are separately generated on both sides of the boundary, which is the dotted line in Figure 6. Five potential base stations are below the boundary line while twenty target points are above it.
As the target points are abstracted from a small area on the borderline, they should not be too close to each other; otherwise two points could be merged into one node. It is same for the potential stations. It would be impractical to build two stations in a close range. For the purpose of this characteristic, all nodes are generated one by one. Take the base stations as an example, every time a new station is produced, the distance between the station and every existing station would be judged. If the distance is too short, the position would be abandoned and regenerated until there are enough base stations.
The parameters of UAV mainly refer to the public parameters from two typical UAVs which have been applied to border patrol. The detailed parameter is presented in Table 1. After some proper randomization, the experiment parameters are generated, such as the flight endurance, patrol speed, and so on.
5.2. Experiment Result
With the experiment data generated, two algorithms are tested and compared with each other. For the sake of illustration, H1-NS represents the combination of the heuristic based on clustering and nearest point search (H1) and the neighbourhood search while H2-NS contains the heuristic based on clustering and CW saving search (H2) and the neighbourhood search.
5.2.1. Results of H1-NS on Test Case
Take a small-scale case (5 base stations and 20 target points) generated randomly. Figure 7(a) shows the feasible solution given by H1 while the improved solution is provided after neighbourhood search as Figure 7(b) depicts.
(a) Feasible solution given by H1
(b) Improved solution after NS
In Figure 7(a), it is can be seen that the performance of Nearest Neighbour is flawed. Obviously, when the UAV departures from Station 5 and then visits Target 17 and Target 20, the rest of energy cannot support it to return to the base if continuing detecting Target 22, which causes one more UAV to be sent to specially visit Target 22.
However, after neighbourhood search, the solution is improved a lot. Some fight paths are merged and adjusted, which reduces the number of UAVs used as well as the flight distance of UAV. For example, the routes 5→17→20→5 and 5→22→5 are merged into 5→17→22→20→5. And the detecting order of Target 14 and 23 is interchanged, decreasing the UAV’s redundant flight. Although the number of stations has not changed, the number of drones has decreased after optimization. Only 7 UAVs are used in the final solution, which is two less than that of the initial solution. As displayed in Table 2, the overall costs have been decreased from 372992 to 274386 down by 26 percent, proving the feasibility of H1 and effectiveness of neighbourhood search.
5.2.2. Results of H2-NS on Test Case
The same case is also applied to test H2-NS. The feasible solution given by H2 is presented by Figure 8(a) and the improved after NS in Figure 8(b).
(a) Feasible solution given by H1
(b) Improved solution after NS
The conclusion can be drawn that the CW saving algorithm has utilized the flight endurance as far as possible, which is fairly obvious in the feasible solution. Compared with the cost of feasible solution in H1, H2 reduces the cost from 372992 to 336496.
After the adjustment of the neighbourhood search, the structure of the solution has changed a lot. Although the number of the UAVs has not decreased, the base station 1 is closed and replaced by the other two stations, which reduce the base establishing cost.
The detailed comparison is shown in Table 3. The overall costs have been reduced from 336496 to 189061, dropping by 44%. Therefore, H2-NS seems to be more accurate than H1-NS and can solve the problem better.
5.2.3. Comparison
See Table 4.
5.3. Example Based on the Sino-Vietnamese Border
In this section, a practical border is used as the example case and solved by the preceding algorithms.
As is shown in Figure 9, there are about 8 cities and 103 towns bordering in Guangxi Zhuang Autonomous Region. With the development of economy and the implementation of opening-up policy, especially under “Belt and Road” initiative, Guangxi develops an increasingly flourishing border trade. However, smuggling also increases at the same time. Since the border area is mainly delimited by rivers or mountains and has few natural barriers, this part of the border is prone to smuggling which is difficult to monitor. According to the official report, 6726 smuggling cases were seized in Guangxi in 2006. Thus, it is meaningful to apply UAVs on the border patrol, which can improve the patrol efficiency and reaction speed. Therefore, take the Guangxi section of the border as an example.
As displayed in Figure 10, with the ranging tool of Google Map, the linear distance of this part is about 320 km. Then Paint software is used to discretize this line. Fifty target points are marked on the border and twenty base stations are chosen randomly inside the line. Furthermore, the relative positions of these 70 nodes are obtained via the pixel measurement.
It is assumed that all targets and potential bases are located in the area of 320 kilometres multiplied by 160 kilometres. Mapping these nodes into this area, the distribution map looks like Figure 11. The blue dots are target points and the red blocks are potential base stations.
Two algorithms are applied to solve the practical case. The results are shown in Table 5. Since the result of H2-NS is obviously superior to another one, take the result of H2-NS as the final solution, in which the cost is 480309 and the calculation takes 0.06840 seconds.
The potential base stations are numbered 1 through 20 when the target points are represented by 21 to 70. Then the detailed bases and flight paths can be listed in Table 6 and the corresponding route map is shown in Figure 12. The final result selects 6 bases and launches 15 UAVs.
6. Conclusions
In this paper, considering the background of border patrol for ISR, the capacity constraints of bases are involved in the multidepot location-routing problem. Hence, a modified mathematical model has been presented. The primary objective of this research is to develop an efficient approach for solving this kind of problem. Thus, two hybrid heuristics with neighbourhood search are promoted. One is based on clustering and nearest point search, and the other one is based on clustering and CW saving search.
In addition, experiments have been carried out to compare the performance of two algorithms. It can be addicted that neighbourhood search plays an optimizing role to the solution. And the heuristic based on CW saving search provides a better solution while consuming more time than the other one. Furthermore, an example based on a practical borderline is proposed. Both algorithms are applied to solve the border patrol on the practical borderline and provide the final solution.
Finally, two improvements in solving this kind of problem can be envisaged. First, the current neighbourhood search can be scaled up to find a global optimal solution. Second, more variants of this kind of problem can be exploited. For example, dynamic detecting could be added.
Data Availability
The data used to support the findings of this study are available from the corresponding author upon request.
Conflicts of Interest
The authors declare that there are no conflicts of interest regarding the publication of this paper.
Acknowledgments
The research is supported by the National Natural Science Foundation of China (no. 71771215 and no. 71471174).