Solving the area coverage problem with UAVs: A vehicle routing with time windows variation


Creative Commons License

SEMİZ F., POLAT F.

Robotics and Autonomous Systems, vol.126, 2020 (SCI-Expanded) identifier identifier identifier

  • Publication Type: Article / Article
  • Volume: 126
  • Publication Date: 2020
  • Doi Number: 10.1016/j.robot.2020.103435
  • Journal Name: Robotics and Autonomous Systems
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Aerospace Database, Applied Science & Technology Source, Communication Abstracts, Compendex, Computer & Applied Sciences, INSPEC, zbMATH
  • Keywords: Vehicle routing problem, Unmanned aerial vehicle, VRPTW, Transportation problem, Simplex algorithm, TABU SEARCH ALGORITHM
  • Middle East Technical University Affiliated: Yes

Abstract

In real life, providing security for a set of large areas by covering the areas with Unmanned Aerial Vehicles (UAVs) is a difficult problem that consists of multiple objectives. These difficulties are even greater if the area coverage has to be sustained through a specific time window. We address this by considering a Vehicle Routing Problem with a Time Windows (VRPTW) variation in which the capacity of agents is counted as one and each customer (target area) is to be supplied with more than one vehicle simultaneously and without violating time windows. In this problem, our aim is to find a way to cover all areas with the necessary number of UAVs during the time windows, while minimizing the total distance traveled, and providing a fast solution by satisfying the additional constraint that each agent has limited fuel. We present a novel algorithm that relies on clustering the target areas according to their time windows, and then incrementally generating transportation problems with each cluster and the ready UAVs. We then solve the transportation problems with a simplex algorithm. The performance of the proposed algorithm and other algorithms implemented in order to compare the solution quality is evaluated through example scenarios with practical problem sizes.

Gerçek hayatta belirli alanlara insansız hava araçları (İHA)'lar kullanarak güvenlik sağlamak çok amaçlı zor bir problemdir. Bu zorluklar alan taramasının belirli zaman pencereleri içinde tamamlanması gerektiği söz konusu olduğunda daha da artmaktadırlar. Biz bu problemi bir zaman pencereli araç rotalama problemi olarak modelledik. Bu modellemede her etmenin kapasitesi bir olarak alınmış olup, taranacak olan her alan aynı anda birden fazla araç tarafından zaman penceresinin tamamı boyunca taranması planlanmıştır.  Bu problemde amacımız her bir alanı yeterince araç kullanarak tüm zaman penceresi boyunca tararken aynı zamanda katedilen mesafeyi minimize etmek, olabildiğince hızlı çözüm üretmek ve araçların yakıt miktarlarına uygun çözümler üretmektir. Bu çalışmada taranacak alanları zaman pencerelerine göre sınıflandıran ve daha sonrasında her bir alt problemi o anda hazır bulunan İHA'ları kullanarak bir ulaştırma problemi olarak modelledik ve bu ulaştırma problemlerini simplex algoritmasını kullanarak çözdük.  Önerilen methodun performansını geliştirdiğimiz alternatif methodlarla karşılaştırıp çeşitli büyüklükteki haritalardaki örnek problemlerdeki performanslarını karşılaştırdık.