Robotics and Autonomous Systems, vol.126, 2020 (SCI-Expanded)
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.