An Integer Programming Model for the Heterogeneous UAV Fleet Routing Problems

Abstract

With the recent developments in wireless communication and computer processing, more unmanned aerial vehicles (UAVs) are used in the military field. As the numbers of UAVs and their varied capabilities have increased dramatically, new approaches for the planning of a heterogeneous fleet have become an ongoing area of research for the operations research community. In this paper, an integer programming solution for the heterogeneous UAV static vehicle routing problem (VRP) is presented. Explanations of UAVs with a VRP and their importance for military operations are also provided. In addition, differences between homogeneous and heterogeneous definitions for UAVs are detailed. We extend a previous study and conclude with acomparison of the model with the literature.

Keywords

• Static Vehicle Routing, Unmanned Aerial Vehicle, Integer Programming

Heterojen İHA Filosu Rotalama Problemi için Tam Sayılı Programlama Modeli

Abstract

Son zamanlarda, kablosuz haberleşme ve bilgisayar işlemcilerindeki gelişmeler sayesinde, operasyon sahasında daha çok İnsansız Hava Araçları (İHA) kullanılmaya başlanmıştır. Kullanılan İHA’ların ve çeşitlerinin hızla artması ile birlikte, heterojen İHA filolarının rota planlamaları için yeni yaklaşımlar, harekât araştırmacıları için ilgi çekici bir alan olagelmiştir. Bu çalışmada, değişik imkan ve kabiliyetlerdeki İHA‘lardan oluşan heterojen filoların statik araç rotalama problemleri (ARP) için tam sayılı programlama çözüm modeli önerilmiştir. İHA ve ARP’lerinin tanımları ile askeri operasyonlar için önemleri açıklanmış, ayrıca homojen ve heterojen İHA tanımları detaylandırılmıştır. Bir önceki çalışma genişletilmiş ve literatür ile karşılaştırmaları verilmiştir.

Keywords

• Statik Araç Rotalama, İnsansız Hava Araçları, Tam sayılı Programlama

References

1. Beard, R., Mclain, T., Goodrich, M. and Anderson, E.. (2002). Coordinated Target Assignment and Intercept For Unmanned Air Vehicles. IEEE Transactions on Robotics and Automation, 18(6), 911–922.
2. Bednowitz, N., Batta, R., and Nagi, R. (2013). Dispatching and Loitering Policies for Unmanned Aerial Vehicles under Dynamically Arriving Multiple Priority Targets. to appear in Journal of Simulation.
3. Bhattacharya, S., Başar, T. (2010). Game-theoretic Analysis of an Aerial Jamming Attack on a UAV Communication Network. 2010 American Control Conference. Marriott Waterfront, Baltimore, MD, USA.
4. Bicchi, Antonio, and Lucia Pallottino. (2000). On Optimal Cooperative Conflict Resolution For Air Traffic Management Systems. Intelligent Transportation Systems, IEEE Transactions on 1.4, 221-231.
5. Bortoff, S. (2000). Path-Planning For Unmanned Air Vehicles. Proc. American Control Conference. pp. 364–368.
6. Chandler, P. ,Rasmussen, S., and M. Pachter. (2000). UAV Cooperative Path Planning. Proceedings of the AIAA Guidance, Navigation, and Control Conference, Denver, CO.
7. Chandler, P.R., and Patcher,M. (1998). Research Issues in Autonomous Control of Tactical UAVs. Proceedings of the American Control Conference Philadelphia, Pennsylvania. 394-398.
8. Dantzig, G.B. and Ramser, J.H. (1959). The Truck Dispatching Problem. Management Science. Vol.6, No.1, 80-91. Published by: INFORMS Stable URL: http://www.jstor.org/stable/2627477 Retrieved: 24/11/2010 08:14.

9. Dowek, G., Munoz, C. and Geser, A. (2001). Tactical Conflict Detection And Resolution In A 3-D Airspace. Technical Report, ICASE ReportNo. 20017, NASA/CR-2001-210853.
10. Dror, M., and Powell, W. (1993). Stochastic and Dynamic Models in Transportation. Operations Research, Vol.41, 11-14.
11. Duan, H. B., Zhang, X. Y., Wu, J., and Ma, G. J. (2009). Max-Min Adaptive Ant Colony Optimization Approach To Multi-Uavs Coordinated Trajectory Replanning In Dynamic And Uncertain Environments. Journal of Bionic Engineering, 6(2), 161-173.
12. Edison, Eugene, and Tal Shima. (2011). Integrated Task Assignment And Path Optimization For Cooperating Uninhabited Aerial Vehicles Using Genetic Algorithms. Computers & Operations Research 38.1, 340-356.
13. Ercan, C., and Gencer, C. (2013). Literature Review of Dynamic Unmanned Aerial System Routing Problems and Proposals For Future Studies of UASs. Pamukkale University Journal of Engineering Sciences, Cilt 19/2, 104
14. Eun, Y. and H., Bang. (2006). Cooperative Control Of Multiple Unmanned Aerial Vehicles Using The Potential Field Theory. Journal of Aircraft, 43(6), 1805–1814.
15. Gencer, C., Aydoğan, K. E. and Kocabaş, S. (2009). İnsansız Hava Araçlarının Rota Planlaması için Bir Karar Destek Sistemi. Kara Harp Okulu Savunma Bilimleri Dergisi, 8(2), 59-73.
16. Gennery, Donald B. (1999). Traversability Analysis and Path Planning For a Planetary Rover. Autonomous Robots 6.2, 131-146.
17. Goraj, Z. (2003). Civilian Unmanned Aerial Vehicles – Overview Of European Effort And Challenges For The Future. Aviation Journal, Vilnius, VII(1), 3Hebert, Jeffrey M. (2001). Air Vehicle Path Planning. No. AFIT/DS/ENG/01-04. Air Force Inst. of Tech Wright-Patterson AFB Oh School Of Engineering And Management.
18. Henchey, M., Batta, R., Karwan, M., and Crassidis, A. (2013). A Flight Time Approximation Model for Unmanned Aerial Vehicles: Estimating the Effects of Flight Dynamics and Wind. to appear in Military Operations Research.
19. Hsu, D., Latombe, J. C. and Motwani, R. (1997). Path Planning In Expansive Configuration Spaces. IEEE Int. Conf. on Robotics and Automation, Albuquerque, NM, pp. 2719–2726.
20. Jin, Y., Liao, Y., Minai, A. A. and M.M. Polycarpou. 2006. Balancing Search and Target Response in Cooperative Unmanned Aerial Vehicle (UAV) Teams. IEEE Trans Syst Man Cybern B Cybern, 36(3), 571-587.
21. Jun, Myungsoo, and Raffaello D’Andrea. (2002). Path Planning For Unmanned Aerial Vehicles In Uncertain And Adversarial Environments. Cooperative Control: Models, Applications and Algorithms, 95-111.
22. Kavraki, L. E., Svestka, P., Latombe, J. C. and Overmars, M. H. (1996). Probabilistic Roadmaps For Path Planning In High-Dimensional Configuration Spaces. IEEE Transactions on Robotics and Automation, 12(4), 566–580.
23. Kim, Yoonsoo, Da-Wei Gu, and Ian Postlethwaite. (2008). Real-Time Path Planning With Limited Information For Autonomous Unmanned Air Vehicles. Automatica 44.3, 696-712.
24. Kumar, Rajesh. (1997). Tactical Reconnaissance: UAVs Versus Manned Aircraft. No. AU/ACSC/0349/97-03. Air Command And Staff Coll Maxwell AFB AL.
25. Li, S. M., Boskovic, J. D., Seereeram, S., Prasanth, R., Amin, J., Mehra, R. K., Beard, R. and Mclain, T.W. (2002). Autonomous Hierarchical Control Of Multiple Unmanned Combat Air Vehicles. American Control Conf ., Anchorage, AK, vol. 1, pp. 274–279.
26. Lim, K. K., Ong, Y. S., Lim, M. H., Chen, X., and Agarwal, A. (2008). Hybrid Ant Colony Algorithms For Path Planning In Sparse Graphs. Soft Computing, 12(10), 981-994.
27. Mclain, T. (2000). Cooperative Rendezvous Of Multiple Unmanned Air Vehicles. Proc. AIAA Guidance and Control Conf ., Denver.
28. Mittal, Shashi, and Kalyanmoy Deb. (2007). Three-Dimensional Offline Path Planning for UAVs Using Multiobjective Evolutionary Algorithms. Proceedings of the Congress on Evolutionary Computation (CEC2007),(Singapore).
29. Mufalli, F., Batta, R., and Nagi, R. (2012). Simultaneous Sensor Selection and Routing of Unmanned Aerial Vehicles for Complex Mission Plans. Computers and Operations Research, Vol. 39, No. 11, pp. 2787-2799.
30. Murray, C. C. and Karwan, H. M. (2010). An Extensible Modeling Framework for Dynamic Reassignment and Rerouting in Cooperative Airborne Operations. Wiley Online Library, Naval Research Logistics 57(7), 6346
31. Odom, Earl. (2002). Future Employment of Unmanned Aerial Vehicles. Aerospace Power Journal.
32. Pachikara, A. J., Kehoe, J. J. and Lind, R. (2009). A Path-Parameterization Approach Using Trajectory Primitives For 3-Dimensional Motion Planning, AIAA Guidance, Navigation, and Control Conf., Chicago, August. AIAA 2009-5625.
33. Peng, Xingguang, and Xiaoguang Gao. (2008). A Multi-Objective Optimal Approach For UAV Routing In Reconnaissance Mission With Stochastic Observation Time. Foundations of Intelligent Systems, Springer Berlin Heidelberg, 246-255.
34. Pohl, Adam J., and Gary B. Lamont. (2008). Multi-Objective UAV Mission Planning Using Evolutionary Computation. Proceedings of the 40th Conference on Winter Simulation. Winter Simulation Conference.
35. Rabbath, C., Gagnon, E. and Lauzon, M. (2004). On the Cooperative Control of Multiple Unmanned Aerial Vehicles. IEEE Canadian Review, 8–15.
36. Richards, A., Bellingham, J., Tillerson, M. and How, J. (2002). Coordination and control of multiple UAVs. AIAA Conf. Guidance, Navigation, and Control, Monterey, CA, Aug. 2002, Paper AIAA-2002-4288.
37. Royset, J. O., Carlyleand, W., and Wood, R. (2009). Routing Military Aircraft with a Constrained Shortest-Path Algorithm. Military Operations Research, 14(3), pp. 31-52.
38. Ryan, J., Bailey, T. Moore J., and Carlton W., (1998). Reactive Tabu Search In Unmanned Aerial Reconnaissance Simulations. Proc. 30th Conf. Winter Simulation, Washington, DC, pp. 873–880.
39. Schoenwald, D.A. (2000). AUVs: In Space, Air, Water, and on the Ground. IEEE Control Systems Magazine.
40. Shanmugavel, M., Tsourdos, A., Z˙ Bikowski, R. and White, B. A. (2006). 3D Dubins Sets Based Coordinated Path Planning For Swarm Of UAVs. AIAA Guidance, Navigation and Control Conf. and Exhibit, Keystone, CO, 21– 24 August. AIAA-2006-6211.
41. Shanmugavel, M., Tsourdos,A., Zbikowski, R. and White, B.A. (2005). Path Planning Of Multiple Uavs in an Environment Of Restricted Regions. Proc. ASME Int. Mechanical Engineering Congress and Exposition, IMECE2005, 5–11 November, Orlando, FL. IMECE2005-79682.
42. Shetty. V. K., Sudit. M., and Nagi, R. (2008). Priority Based Assignment and Routing of a Fleet of Unmanned Combat Aerial Vehicles. Computers & Operations Research 35, 1813-1828.
43. Tompkins, Paul, Anthony Stentz, and David Wettergreen, (2004). Global Path Planning for Mars Rover Exploration. Aerospace Conference, Proceedings, 2004 IEEE. Vol. 2.
44. Toth, P. and Vigo, D. (2001). The Vehicle Routing Problem, SIAM Monograhs on Discrete Mathematics and Applications. SIAM Publishing, Philadelphia, PA.
45. U.S. DoD (Office of the Secretary of Defense). (2005). Unmanned Aircraft Systems Roadmap 2005–2030, .
46. U.S. DoD (Office of the Secretary of Defense). (2011). U. S. Army UAS Center of Excellence, U.S. Army Roadmap for UASs 2011-2036, resources/UnmannedSystemsIntegratedRoadmapFY2011.pdf>.
47. U.S. DoD Home Page. (2010). Retrieved, 12 August 2011, Unmanned System Integrated Roadmap 2010-2035, < Hata! Köprü başvurusu geçerli değil. >.
48. Valavanis, K. P. Vachtsevanos, G. J. Antsaklis, P. J. (2007). Advances in Unmanned Aerial Vehicles. Chapter 18: Conclusions and the Road Ahead, Kimon P. Valavanis (ed.), Springer, Netherlands, 533–543.
49. Vargas, Ronny A. (2012). Unmanned Systems: Operational Considerations for the 21st Century Joint Task Force Commander and Staff. Army Command And General Staff Coll Fort Leavenworth KS.
50. Wilson, J. (2007). UAV Worldwide Roundup 2007, Aerospace America, pp. 30–
51. Yang, H. I. and Zhao, Y. J. (2004). Trajectory Planning For Autonomous Aerospace Vehicles Amid Obstacles and Conflicts. Journal of Guidance, Control and Dynamics, 27, 997–1008.
52. Yang, K. and Sukkarieh, S. (2008). 3D Smooth Path Planning for a UAV in Cluttered Natural Environments. IEEE International Conference on Intelligent Robots and Systems, Nice, France, 794-800.
53. Zeitlin, A. D. and Mclaughlin, M. P. (2007). Safety of Cooperative Collision Avoidance for Unmanned Aircraft. IEEE Aerospace and Electronics Magazine, 9–13.
54. İnsansız Sistemler ve Statik Araç Rotalama Problemleri İnsansız sistemler, insan müdahalesi olmadan verilen görevleri icra edebilecek şekilde hareket edebilen yer, hava, sualtı, suüstü araçlarından oluşan elektro-mekanik sistemlerdir (Vargas, 2012). İHA’lar, insansız sistemler içerisinde en yaygın kullanılanı ve en önemli olanıdır. ABD’de 2011 yılı başkanlık bütçesinden insansız sistemler için ayrılan kaynağın %94’lük büyük bir bölümünün İHA’lar için ayrılması, bunun en çarpıcı göstergesidir (ABD İHA Yol Haritası, 2011). Silahlı Kuvvetler için, İHA’lar gibi değerli sistemlere sahip olmak önemli omakla birlikte, envanterde bulunan bu sistemlerin etkin olarak kullanılması da önem arz etmektedir. Bu kapsamda, İHA’ların rota planlamaları elle veya bilimsel olarak hazırlanabilir. Ancak, verimli bir planlama için bilimsel yaklaşımlar özellikle hedef sayısının çok olduğu durumlarda en iyi rotanın bulunması için elzemdir. ARP için çözüm yaklaşımları iki başlık altında toplanabilir: Kesin ve sezgisel algoritmalar. Kesin algoritmaların zayıf tarafı, en iyi çözümün bulunması için ihtiyaç duyulan işlem zamanıdır. Ancak bazı statik durumlarda, bu çalışmanın da ana konusu olan en iyi rotanın bulunması, işlem zamanından daha öncelikli olabilir. Bunun sebebi, rutin bazı askeri uygulamalarda statik rota planlamaları, İHA’ların göreve başlamalarından çok önce yapılmaları ve en iyi rotanın bulunması için yeterince zamanın olmasından kaynaklanmaktadır. Problem Savunma bütçelerinde dahi “ayağını yorganına göre uzat” prensibini göz ardı edemeyiz. İHA’lar keşfedildikleri andan itibaren, silahlı kuvvetler için önemli bir kuvvet çarpanı olmuşlardır. Kullanımlarının artması ve operatör sayılarının azalması, statik rota planlamalarını en iyileyecek çalışmaları tetiklemiştir. Bu çalışmada, belirlenen bazı operasyonel tahditler altında, planlanan hedeflerin hepsini dolaşacak en iyi rotanın bulunması amaçlanmıştır. Çalışmada, daha gerçekçi askeri ortamın modellenebilmesi için;  İHA’ların heterojen olduğu ve değişik dayanıklıklarının olabileceği,  Herbir İHA’ın hızlarının bilindiği ve sabit olduğu ancak birbirlerinden farklı olabileceği,  İHA ve hedef sayılarının planlama öncesi bilindiği,  Herbir hedef için zaman penceresi (ZP) kısıtı olduğu ve İHA’lar tarafından hedeflerin verilen ZP içerisinde gözetlenebileceği,  İniş ve kalkış için tek bir yer kontrol istasyonunun olduğu kabul edilmiştir.
55. Tamsayılı Programlama Tabanlı Bir Model Önerisi Çalışmada, İHA ARP için tamsayılı programlama çözüm önerisi sunulmuş ve GAMS paket programı ile çözülmüştür. Bir önceki (Gencer vd., 2009) çalışma genişletilmiş ve çözüm için gereken işlem süresi kısaltılmıştır. Bir önceki çalışmadan farklı olarak;  İHA’lar homojen değil heterojen olarak ele alınmış,  İHA’ların uçuş yükseklikleri sabit değil, hedeflerdeki tehditlere bağlı olarak değişken kabul edilmiş,  Herbir hedef için servis süresi eklenmiş,  Hedef servis sürelerinin birbirinden farklı olabilmesi sağlanmış,  Hedefler arasındaki bazı yolların uçuşa kapatılabilme imkanı tanınmış,  Enlem ve boylam bilgileri ile birlikte yükseklik bilgileri de ele alınarak 3 boyutlu rotalar çalışılmış,  Daha az kısıt kullanılarak işlem süreleri azaltılmış,  Hedeflerin bizzat kendi imkanlarından kaynaklanan tehditler probleme dahil edilmiş ve statik problemin 6 değişik versiyonu incelenmiştir. Bazı değerler, önceki çalışmadaki veriler esas alınarak GAMS paket programında kodlanarak çözülmüş ve önceki çalışma ile karşılaştırılmıştır. Bu çalışmayı bir öncekinden farklı kılan özellik sadece işlem zamanının kısaltılması değil aynı zamanda problemin heterojen olarak ele alınmasıdır. Tartışma ve Sonuç Uzay ve haberleşme teknolojilerindeki hızlı ilerlemeler sayesinde, İHA’ların sonraki nesilleri daha da farklılaşacak, heterojenleşecek ve daha az operatör müdahalesine ihtiyaç duyacaktır. İHA teknolojilerinin ilerlemesiyle, geleceğin orduları daha karmaşık tehditler barındıran ortamlarda operasyon yapmak zorunda kalacaklardır. Heterojen İHA’ların varlığı sebebiyle, rota planlamaları için daha gelişmiş algoritmalara ihtiyaç duyulacaktır. Birleşik/çokuluslu çok boyutlu ağ destekli yetenek konseptine uygun olarak, tek İHA yönetiminden müşterek/birleşik İHA yönetimine geçilecektir. GAMS 21.5 programından elde edilen sonuçlara göre, önerilen model bir önceki modele göre daha kısa sürede sonuç üretebilmekte ve heterojen filolar için de kullanılabilmektedir. Bir önceki çalışmanın senoryası, test senoryası olarak kullanılmış, böylelikle kısıtlar ihlal edilmeden daha kısa sürede çözüme ulaşılabileceği gösterilmeye çalışılmıştır. Bu tür çalışmaların, İHA destekli yapılan askeri uygulamalarda;  Askeri keşif görev etkinliğinin arttırılacağı,  Durumsal farkındalığın arttıralacağı,  Operasyon maliyetinin azaltılacağı,  Karar desteği sağlanacağı ve karar döngüsünün kısaltılacağı,  Daha otonom İHA’ların göreve sevk edileceği,  Eğitim ihtiyacının azaltılacağı,  İhtiyaç duyulan pilot/operatör sayısının azalacağı,  Operasyon esnasında ihtiyaç duyulan haberleşme bant genişliği ihtiyacının azaltılacağı öngörülmektedir.