Uçuş Menzili ve Hizmet Süresi Kısıtları Altında Çoklu İHA Yönlendirme için Etkin Genetik Algoritma

Son zamanlarda gerek askeri gerekse sivil amaçlı İnsansız Hava Aracı (İHA) kullanımı giderek popülerlik kazanmaktadır. Ancak İHA'ların etkin kullanımı için gerekli Servis Kalitesi(QoS)'ni karşılaması için benimsenen yaklaşımlarının sınırlamaları vardır. İHA'lar arasındaki kıyaslamanın önemli sınırlarından biri de uçuş menzilidir. Çoğu zaman, İHA'ların, yeterli enerji kaynağı olmaması ve böylelikle nispeten kısa uçuş menzillerine sahip olmalarıdır. İlave olarak, İHA'ları kullanan uygulamalar için, verilen hizmet süresi zamanı içerisinde ziyaret edilmesi gereken pek çok nokta olabilir. Üstelik, uygulamalar tarafından yönlendirilecek İHA'ların sayısı da sınırlıdır. Bu nedenle, gerçek hayattaki uygulamalarda, önceden belirlenen zaman aralığı pencerelerinde daha fazla noktanın ziyaret edilmesi maksadıyla belirli bir uçuş menzili olan çok sayıda İHA için bir optimizasyon sorunu ile karşılaşılmaktadır. Bu problemde biz, kullanılan İHA sayısını en aza indirmek ve zaman aralığı içerisinde ziyaret edilecek nokta sayısını en üst düzeye çıkarmak istiyoruz. Bu nedenle, Genetik bir algoritma tasarladık ve çeşitli uçuş menzilleri, servis zaman aralıkları ve nokta ağ topolojileri için kapsamlı simülasyon testleri yoluyla etkinliğini doğruladık. Daha da ötesinde, tasarlanan algoritma ile arzu edilen başarıyı sağlayabilecek rakip bir algoritma ile de sonuçlar karşılaştırılmıştır.

An Efficient Genetic Algorithm for Routing Multiple UAVs under Flight Range and Service Time Window Constraints

Recently using Unmanned Aerial Vehicles (UAVs) either for military or civilian purposes is getting popularity. However, UAVs have their own limitations which require adopted approaches to satisfy the Quality of Service (QoS). One of the important limitations of the UAVs encounter is the flight range. Most of the time, UAVs have very scarce energy resources and, thus, they have relatively short flight ranges. Besides, for the applications using UAVs, there could be many customers to be serviced for the given service time windows. Moreover, the number of UAVs managed by the applications is also limited. Therefore, in real life applications, we face with an optimization problem such that for a given number of UAVs with a specific flight range, they should be servicing more customers in the predetermined time windows. In this problem, we would like to minimize the number of used UAVs and maximize the number of serviced customers meeting the time window requirement. For this reason, we have designed a Genetic Algorithm and validated its effectiveness via extensive simulation tests for various flight ranges, time windows, and customer topologies. Furthermore, the results of the proposed algorithm with a rival algorithm supporting the expected success have also been compared.

___

  • [1] Chao, HaiYang, YongCan Cao, and YangQuan Chen. "Autopilots for small unmanned aerial vehicles: a survey." International Journal of Control, Automation and Systems 8.1 (2010): 36-44.
  • [2] Waharte, Sonia, and Niki Trigoni. "Supporting search and rescue operations with UAVs." Emerging Security Technologies (EST), 2010 International Conference on. IEEE, 2010.
  • [3] Murat Karakaya, “En Az Sayıda İnsansız Hava Aracı Kullanarak Sabit Hedeflerin Gozetlenmesinin Planlanması”, 15. Otomatik Kontrol Ulusal Toplantısı ve Sergisi (TOK2013), (2013): 519-524.
  • [4] Murat Karakaya, UAV Route Planning For Maximum PoI Coverage, Computer Science & Engineering: An International Journal (CSEIJ), Vol. 4, No. 1, ISSN: 2231 - 329X, 2014.
  • [5] Hamdi Demirel, Halil Savuran, Murat Karakaya, “İnsansız Hava Aracları İcin Radar Kaplama Alanlarından Kacınacak En Kısa Rotanın Hesaplanması”, 7.Savunma Teknolojileri Kongresi (SAVTEK-2014), 2014.
  • [6] Senem Aktas, Nergiz Kilinc, Hazan Daglayan, Ibrahim Cereci, Murat Karakaya, “UAV Route Planing for Avoidıng Enemy Radars”, The 1st International Conference on Engineering and Natural Sciences (ICENS 2015), Skopje, Macedonia, 2015.
  • [7] Ender Sevinc, Murat Karakaya, Maximizing UAV PoI Coverage under Flight Range and PoI Service Time Constraints, Lecture Notes on Software Engineering, Vol. 3, No. 4, 290-294, ISSN: 2301-3559, 2015.
  • [8] Zhang, Chunhua, and John M. Kovacs. "The application of small unmanned aerial systems for precision agriculture: a review." Precision agriculture 13.6 (2012): 693-712.
  • [9] Fornace, Kimberly M., et al. "Mapping infectious disease landscapes: unmanned aerial vehicles and epidemiology." Trends in parasitology 30.11 (2014): 514-519.
  • [10] Ballesteros, R., et al. "Applications of georeferenced highresolution images obtained with unmanned aerial vehicles. Part I: Description of image acquisition and processing." Precision Agriculture 15.6 (2014): 579-592.
  • [11] Watts, Adam C., Vincent G. Ambrosia, and Everett A. Hinkley. "Unmanned aircraft systems in remote sensing and scientific research: Classification and considerations of use." Remote Sensing 4.6 (2012): 1671-1692.
  • [12] VRPTW benchmark problems, 2005, [WWW document; retrieved January 2016] http://w.cba.neu.edu/~msolomon/problems.htm
  • [13] Goldberg, David E. The design of innovation: Lessons from and for competent genetic algorithms. Vol. 7. Springer Science & Business Media, 2013.
  • [14] S.N.Sivanandam, S.N.Deepa, Introduction to Genetic Algorithms, Springer-Verlag Berlin Heidelberg, 2008.
  • [15] Sevinç, E., Coşar, A., An Evolutionary Genetic Algorithm for Optimization of Distributed Database, The Computer Journal, v.54/5, 2011
  • [16] Goldberg, David, The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Norwell, MA: Kluwer Academic Publishers, Ch.1. ISBN 978-1402070983, 2002.
  • [17] S.N.Sivanandam, S.N.Deepa, Introduction to Genetic Algorithms, Springer-Verlag Berlin Heidelberg, 2008.
  • [18] UAV Specifications, [WWW document; retrieved January 2014] (MQ-1 Predator), http://www.bga-aeroweb.com/Defense/MQ-1- Predator-MQ-9-Reaper.html
  • [19] Murat Karakaya , Ender Sevinç, Planning Multiple UAVs to Visit Points of Interest Considering Flight Range and Service Time Constraints, The 2nd International Conference on Engineering and Natural Sciences (ICENS 2016), Sarajevo, Bosnia and Herzegovina, 2016.
  • [20] Desrochers, M., J. Desrosiers, M. M. Solomon. 1992. A new optimization algorithm for the vehicle routing problem with time windows. Oper. Res. 40 342–354.
  • [21] Irnich, S., D. Villeneuve. 2006. The shortest path problem with resource constraints and k-cycle elimination for k ≥ 3. INFORMS J. Comput. 18(3) 391–406.
  • [22] Jepsen, M., B. Petersen, S. Spoorendonk, D. Pisinger. 2006. A nonrobust branch-and-cut-and-price algorithm for the vehicle routing problem with time windows. Oper. Res. Forthcoming.
  • [23] Guy Desaulniers, François Lessard, Ahmed Hadjar, “Tabu Search, Partial Elementarity, and Generalized k-Path Inequalities for the Vehicle Routing Problem with Time Windows”, Transportation Science, Vol. 42, No. 3, August 2008, pp. 387–404
  • [24] Kallehauge, B., N. Boland, O. B. G. Madsen. 2007. Path inequalities for the vehicle routing problem with time windows. Networks 49 273–293.
  • [25] Cordeau, J-F.; Laporte, G.; Mercier, A., “A unified tabu search heuristic for vehicle routing problems with time windows”, Journal of the Operational Research Society, Volume 52, Number 8, 1 August 2001, pp. 928-936(9)
  • [26] G.B. Alvarenga, G.R. Mateus, G. de Tomic, A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows, Computers & Operations Research 34 (2007) 1561– 1584.
  • [27] Sunil Arya, David M. Mount, Nathan S. Netanyahu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal Journal of the ACM (JACM) JACM Homepage archive Volume 45 Issue 6, Nov. 1998 Pages 891-923
  • [28] Valavanis, Kimon P., and George J. Vachtsevanos. Handbook of Unmanned Aerial Vehicles. Springer Publishing Company, Incorporated, 2014.
  • [29] Olli Bräysy and Michel Gendreau, "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms.", Transportation science, vol. 39, no. 1, pp. 104-118, 2005.
  • [30]