Nowadays, there are many unmanned aerial vehicles (UAVs) deployed in border patrol duties for intelligence, surveillance as well as reconnaissance which still suffer from the location routing problem. In other words, the location of these UAV base stations and the UAV flying routes is not optimized in a good way.
A new paper published by three authors aims to solve this problem and give UAVs an improved endurance. In order to formulate the problem, a binary integer programming model is developed – with two heuristic algorithms combined with local search strategies designed for solving it. An example based on the Sino-Vietnamese border is proposed for generating random test instances – analysing the performance of the two algorithms and comparing them with randomly generated instances.
Going into the Challenges of Border Patrol
As you probably know, border patrol is one of the military Intelligence, Surveillance and Reconnaissance (ISR) missions in which UAVs have become a natural choice for deployment – mostly because of their ability to detect targets and channel the information such as images, videos, sensor data and other things to base stations.
The main challenge here is the crime such as smuggling and the number and diversity of threats which require higher features to ensure peace and security near the borderline. In times when manual patrol is difficult for border guards, the use of UAVs is a perfect solution.
The main challenges start from the capacity constraints of base stations. The amount of UAVs must be put to a lower limit in order to make full use of each station. On top of that, both the amount and the location of base stations need to be optimized.
Formulating the Model
In the border patrol missions, there is a set of potential base stations and a set of determined patrol targets that are distributed in the border area. Considering the capacity constraints of bases and the limitations of UAVs, the objective of mission planning is to locate the base stations and plan the UAV routes in an effort to minimize the overall cost.
Obviously, there is a number of facts and assumptions needed to take into account here. As the paper states, they include the following:
- Assume that all UAVs are in the same type, which means that they have same fight endurance and flying speed.
- The flying speed of UAVs is assumed to be constant.
- The UAV must depart from and return to the same base station. The situation of swapping the UAVs between different stations are not considered.
- Each UAV can visit multiple targets, while each target can only be visited by one UAV.
- 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.
The feasible solution, according to the paper, can be constructed from seeing these assumptions and facts – as well as building a mathematical model based on algorithms that will plan the path of UAV in each station.
Drawing a Conclusion
The authors have drawn a conclusion that if an UAV is utilized with its flight endurance, it can lower the cost of feasible solutions, as well as the base establishing cost. In the mass use of UAVs and base stations, this can be important, especially considering the development of economy and the implementation of the opening-up policy, which would open a border trade for Guangxi towards the ASEAN gateway.
Considering the backgrounds of border patrol for ISR, the capacity is involved in the multi-depot location-routing problem. Therefore, the modified mathematical model as presented in the paper can be the perfect road-map towards developing an efficient approach for solving this kind of problem.
As the paper concludes:
“Experiments have been carried out to compare the performance of two algorithms. It can be addicted that neighborhood 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.”
Citation: “Optimization of Base Location and Patrol Routes for Unmanned Aerial Vehicles in Border Intelligence, Surveillance and Reconnaissance“, Yao Liu, Zhong Liu, Jianmai Shi, Guohua Wu and Chao Chen | https://www.preprints.org/manuscript/201809.0487/v1