Author Information

Graduate School of Science and Engineering, Ritsumeikan University, Kusatsu 525-8577, Japan

Graduate School of Information Science and Technology, Osaka University, Suita 565-0871, Japan

*

Authors to whom correspondence should be addressed.

Received: 07 March 2024 Accepted: 23 April 2024 Published: 26 April 2024

© 2024 The authors. This is an open access article under the Creative Commons Attribution 4.0 International License (https://creativecommons.org/licenses/by/4.0/).

ABSTRACT:
The rising cost and scarcity of human
labor pose challenges in security patrolling tasks, such as facility security. Drones
offer a promising solution to replace human patrols. This paper proposes two
methods for finding the minimum number of drones required for efficient
surveillance routing: an ILP-based method and a greedy method. We evaluate these
methods through experiments, comparing the minimum number of required drones
and algorithm runtime. The findings indicate that the ILP-based method
consistently yields the same or a lower number of drones needed for
surveillance compared to the greedy method, with a 73.3% success rate in
achieving better results. However, the greedy method consistently finishes
within one second, whereas the ILP-based method sometimes significantly increases
when dealing with 14 more locations. As a case study, we apply the greedy
method to identify the minimum drone surveillance route for the Osaka-Ibaraki
Campus of Ritsumeikan University.

Keywords:
Drones; Arc Routing Problem; ILP; Greedy Method

Security guards are entrusted with the critical task of patrolling facilities, both internally and externally, and promptly reporting any suspicious activity. These duties are physically and mentally demanding, and can on occasion be hazardous. Furthermore, security guards frequently work night shifts and extended hours. As a consequence of these factors, the security industry is grappling with a labor shortage. Additionally, the industry faces the challenge of rising labor costs [1]. For instance, Ritsumeikan University spends a staggering 120 million yen annually on security alone [2]. Drones present a promising solution to address these issues. Drones offer several advantages over traditional human patrols. Firstly, their integrated cameras allow for real-time monitoring, enabling immediate detection of anomalies [3]. Secondly, they provide access to hazardous or difficult-to-reach areas [4]. Additionally, initiatives to utilize drones for security patrols are gaining traction in Japan, as evidenced by demonstration tests conducted by ALSOK [5]. One key challenge associated with drone deployment is their limited battery capacity, restricting their flight duration [6]. Consequently, efficient surveillance routes must be pre-determined, considering the maximum flight time.
The Drone Arc Routing Problem (DARP), an extension of the Arc Routing Problem (ARP), is a common approach to optimizing drone patrol routes [7]. Unlike the node routing problem that focuses on services performed node, ARP focuses on services performed along network edges [8].
Previous studies have explored various aspects of drone-based security patrols. In [9], a Vehicle-Drone Arc Routing Problem (VD-ARP) was introduced, combining vehicles and drones for urban traffic patrols, aiming to minimize total patrol time while considering drone flight time. However, this approach faces limitations due to the high cost of vehicles and their unsuitability for indoor facility patrols. Another study [10] addressed facility patrolling and guarding using drones, proposing a method to minimize the number of drones with flexible drone starting points. However, this method suffers from NP-hardness, making it unsuitable for large-sized problems.
This paper presents an extension of the method proposed in [10] that addresses its limitations.
The contributions of this paper are threefold: (1) We first define the problem of determining surveillance routes with a minimum number of drones; (2) We formulate the problem as an integer linear program (ILP), enabling the exploration of optimal solutions; (3) We develop a heuristic algorithm to efficiently solve large-scale instances of the problem. We then compare the performance of our heuristic with the ILP-based approach through comprehensive experimental results.
The structure of this paper is as follows: Section 2 describes the literature review. Section 3 describes the ILP-based method and the greedy method. Section 4 describes the experimental methods, results, and discussion. Section 5 describes the overall summary and future work.

In addition, the constraints that the problem should satisfy are as follows.
Constraint (2) guarantees that every aisle between points

Constraint (3) prohibits any drone from traveling that non-existent aisle if there is no aisle connecting points

Constraint (4) prevents a drone from remaining stationary at the same point for the entire duration.

Constraint (5) ensures that for each point and each drone, the number of times the drone enters the point equals the number of times it exits.

Constraint (6) indicates that the flight time of each drone is within the maximum value.

Constraints (7) and (8) show the relationship between “

Constraint (9) guarantees that the route will be a circuit.

Constraints (10) and (11) indicate that the

Constraint (12) guarantees that the

The 1–7 lines define the “

4.1.3. Discussions
The significant increase in algorithm runtime observed for problems with 14 or more points when utilizing an ILP-based method can be attributed to several factors. These factors include:
• In problems involving 14 or more points, the resulting number of drones is two or three. This is because the problem size is close to the upper bound of what can be patrolled by two drones. Consequently, if two drones are deemed insufficient for patrolling the area, a complete recalculation of the problem is required.
• When the minimum number of drones required is three, the number of candidate optimal routes becomes significantly larger compared to the case where two or fewer drones are required. Consequently, the time required to determine the optimal solution increases.
The observed deterioration in the number of drones required when utilizing the greedy method compared to the ILP-based method can be attributed to several factors, primarily stemming from the inherent differences between the two approaches. These factors include: The ILP-based method considers all possible routes and selects the most efficient one with the minimum number of drones. In contrast, the greedy method prioritizes the shortest route at each step without considering the overall efficiency.
On the other hand, the greedy algorithm is not susceptible to the increased complexity of the overall problem caused by an increasing number of points. This is because the greedy algorithm’s focus on local optimization remains consistent regardless of the problem’s size.
The ILP-based method is well-suited for solving smaller problems due to its efficiency. However, for large-sized problems, the greedy method becomes a preferable choice due to its significantly faster algorithm runtime, even though it may not always find the absolute optimal solution.

Our paper proposes two methods for facility patrols: an ILP-based method and a greedy method. We compare their performance in terms of the minimum number of drones required and algorithm runtime through experiments. The experiments revealed that the ILP-based method effectively reduces the number of drones needed for patrolling compared to the greedy method. On the other hand, the ILP-based method’s algorithm runtime can significantly increase for problems with more than 14 points. In contrast, the greedy method consistently achieves fast algorithm runtime regardless of problem size. A case study using Ritsumeikan University OIC applied the greedy method to determine the minimum number of drones required for patrolling the facility. The findings of this study can be utilized to implement a flexible approach, where the ILP-based method is employed for problems with less than 13 points, and the greedy method is used for larger problems. This adaptive strategy can be leveraged to find drone patrol routes based on the problem scale. Furthermore, this strategy can help to avoid the need for an excessive number of drones, thereby contributing to the reduction of facility security costs.
Due to its inherent focus on local optimality, the greedy algorithm may produce solutions that deviate significantly from the global optimum. However, the solution generated by the greedy algorithm can serve as a valuable initial solution for a genetic algorithm. Consequently, investigating the implementation of genetic algorithms presents a promising avenue for future research. Additionally, a comparative analysis between the genetic algorithm and other heuristic methods is warranted, as the extensive search space explored by genetic algorithms can lead to increased algorithm runtime.
Furthermore, identifying the optimal depot locations could lead to a more efficient drone patrol route with fewer drones required.

Conceptualization, K.M. and H.T.; Methodology, K.M., M.N, H.N. and H.T.; Software, K.M.; Investigation, K.M.; Resources, H.T.; Data Curation, K.M.; Writing—Original Draft Preparation, K.M.; Writing—Review & Editing, K.M., M.N, H.N. and H.T; Visualization, K.M.; Supervision, H.T.; Project Administration, K.M.; Funding Acquisition, H.T.

Not applicable.

Not applicable.

This work is partly supported by Japan Society for the Promotion of Science (KAKENHI Grant Number 20H04160) and partly commissioned by New Energy and Industrial Technology Development Organization (Project Number JPNP22006).

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

1.

Kakiuchi R, Tran DT, Lee JH. Evaluation of human behavior detection and interaction with information projection for drone-based night-time security. * Drones*** 2023**,* 7,* 307. [Google Scholar]

2.

Ritsumei University Aims to Introduce Drone Patrols on Campus in 2025. (In Japanese). Available online: https://www.nikkei.com/article/DGXZQOUF152BH0V10C22A9000000/ (accessed on 7 March 2024).

3.

Yi W, Sutrisna M. Drone Scheduling for Construction Site Surveillance. * Comput.-Aided Civil Infrastruct. Eng.*** 2021**,* 36,* 3–13. [Google Scholar]

4.

Kim SJ, Lim GJ. Drone-Aided Border Surveillance with an Electrification Line Battery Charging System. * J. Intell. Robotic Syst.*** 2018**,* 92,* 657–670. [Google Scholar]

5.

[Japan’s First Fully] Indoor Demonstration of AI-Powered Fully Autonomous Flying Drone Security System at TOKYO SKYTREE TOWN~Realization of Human Power Saving and Efficiency Improvement in Security Using Drones~ (In Japanese). Available online: https://www.alsok.co.jp/company/news/news_details.htm?cat=2&id2=1039 (accessed on 7 March 2024).

6.

Dorling K, Heinrichs J, Messier GG, Magierowski S. Vehicle Routing Problems for Drone Delivery. * IEEE Trans. Syst. Man Cybern. Syst.*** 2016**,* 47,* 70–85. [Google Scholar]

7.

Campbell JF, Corberán Á, Plana I, Sanchis JM. Drone Arc Routing Problems. * Networks *** 2018**,* 72,* 543–559. [Google Scholar]

8.

Corberán Á, Eglese R, Hasle G, Plana I, Sanchis JM. Arc Routing Problems: A Review of the Past, Present, and Future. * Networks*** 2021**,* 77,* 88–115. [Google Scholar]

9.

Wu G, Zhao K, Cheng J, Ma M. A Coordinated Vehicle-Drone Arc Routing Approach Based on Improved Adaptive Large Neighborhood Search. * Sensors*** 2022**,* 22,* 3702. [Google Scholar]

10.

Mori K, Nishira M, Nishikawa H, Tomiyama H. Surveillance Routing with a Minimum Number of Drones. In Proceedings of the 2023 Eleventh International Symposium on Computing and Networking Workshops (CANDARW), Matsue, Japan, 27–30 November 2023; pp. 366–367.

11.

Mei-Ko K. Graphic Programming Using Odd or Even Points. * Chin. Math.*** 1962**,* 1,* 237–277. [Google Scholar]

12.

Calogiuri T, Ghiani G, Guerriero E, Mansini R. A Branch-and-Bound Algorithm for the Time-Dependent Rural Postman Problem.* Comput. Operations Res.*** 2019**,* 102,* 150–157. [Google Scholar]

13.

Monroy-Licht M, Amaya CA, Langevin A. Adaptive Large Neighborhood Search Algorithm for the Rural Postman Problem with Time Windows. * Networks*** 2017**,* 70,* 44–59. [Google Scholar]

14.

Monroy IM, Amaya CA, Langevin A. The Periodic Capacitated Arc Routing Problem with Irregular Services. * Discret. Appl. Mat.*** 2013**,* 161,* 691–701. [Google Scholar]

15.

Benavent E, Corberán Á, Laganà D, Vocaturo F. The Periodic Rural Postman Problem with Irregular Services on Mixed Graphs. * Eur. J. Oper. Res.*** 2019**,* 276,* 826–839. [Google Scholar]

16.

Archetti C, Guastaroba G, Speranza MG. An ILP-Refined Tabu Search for the Directed Profitable Rural Postman Problem. * Discret. Appl. Math.*** 2014**,* 163,* 3–16. [Google Scholar]

17.

Bianchessi N, Corberán Á, Plana I, Reula M, Sanchis JM. The Profitable Close-Enough Arc Routing Problem. * Comput. Oper. Res.*** 2022**,* 140,* 105653. [Google Scholar]

18.

Moazzeni S, Tavana M, Darmian SM. A Dynamic Location-Arc Routing Optimization Model for Electric Waste Collection Vehicles. * J. Clean. Prod.*** 2022**,* 364,* 132571. [Google Scholar]

19.

Amini A, Tavakkoli-Moghaddam R, Ebrahimnejad S. A Robust Location-Arc Routing Problem Under Uncertainty: Mathematical Model with Lower and Upper Bounds.* Comput. Appl. Math.*** 2020**,* 39,* 1–36. [Google Scholar]

20.

Manyam SG, Casbeer DW, Sundar K. Path Planning for Cooperative Routing of Air-Ground Vehicles. In Proceedings of the 2016 American Control Conference (ACC), Boston, MA, USA, 6–8 July 2016; pp. 4630–4635.

21.

Luo Z, Liu Z, Shi J. A Two-Echelon Cooperated Routing Problem for a Ground Vehicle and Its Carried Unmanned Aerial Vehicle. * Sensors*** 2017**,* 17,* 1144. [Google Scholar]

22.

Hu M, Liu W, Lu J, Fu R, Peng K, Ma X, et al. On the Joint Design of Routing and Scheduling for Vehicle-Assisted Multi-UAV Inspection. * Future Gener. Comput. Syst.*** 2019**,* 94,* 214–223. [Google Scholar]

23.

Xu B, Zhao K, Luo Q, Wu G, Pedrycz W. A GV-Drone Arc Routing Approach for Urban Traffic Patrol by Coordinating a Ground Vehicle and Multiple Drones. * Swarm Evolut. Comput.*** 2023**,* 77,* 101246. [Google Scholar]

24.

Luo H, Zhang P, Wang J, Wang G, Meng F. Traffic Patrolling Routing Problem with Drones in an Urban Road System. * Sensors*** 2019**,* 19,* 5164. [Google Scholar]

25.

Munishkin AA, Milutinović D, Casbeer DW. Min-Max Time Efficient Inspection of Ground Vehicles by a UAV Team. * Robot. Auton. Syst.*** 2020**,* 125,* 103370. [Google Scholar]

26.

Petitprez E, Georges F, Raballand N, Bertrand S. Deployment Optimization of a Fleet of Drones for Routine Inspection of Networks of Linear Infrastructures. In Proceedings of the 2021 International Conference on Unmanned Aircraft Systems (ICUAS), Athens, Greece, 15–18 June 2021.

27.

Bang-Jensen J, Gutin G, Yeo A. When the Greedy Algorithm Fails. * Discret. Optim.*** 2004**,* 1,* 121–127. [Google Scholar]

28.

Johnson DS, Gutin G, McGeoch LA, Yeo A, Zhang W, Zverovitch A. Experimental Analysis of Heuristics for the ATSP. In *The Traveling Salesman Problem and Its Variations*; Springer: Boston, MA, USA, 2007; pp. 445–487.

29.

Ritsumeikan University Campus Map. Available online: https://en.ritsumei.ac.jp/campusmap/ (accessed on 7 March 2024).

Mori K, Nishira M, Nishikawa H, Tomiyama H. Exact and Heuristic Approaches to Surveillance Routing with a Minimum Number of Drones. *Drones and Autonomous Vehicles* **2024**, *1*, 10004. https://doi.org/10.35534/dav.2024.10004

Mori K, Nishira M, Nishikawa H, Tomiyama H. Exact and Heuristic Approaches to Surveillance Routing with a Minimum Number of Drones. *Drones and Autonomous Vehicles*. 2024; 1(2):10004. https://doi.org/10.35534/dav.2024.10004

TOP