İNSANSIZ HAVA SİSTEMLERİ ROTA PLANLAMASI DİNAMİK ÇÖZÜM METOTLARI VE LİTERATÜR ARAŞTIRMASI

Year 2013, Volume: 1 Issue: 2, 51 - 72, 01.06.2013

Cihan Ercan Cevriye Gencer

Abstract

Savaş stratejisinin bir göstergesi olan muharebe araç ve gereçleri, teknoloji ile birlikte değişiklik göstermektedir. Yakın uzay ve uzayın da bir araç olarak kullanıldığı bilgi çağının savaşları; ok ve yayın kullanıldığı tarım dönemi ile top ve tüfeklerin kullanıldığı sanayi dönemi savaşlarından farklılık göstermektedir. Bu farklılıklar, harekât bölgesinin etki ve ilgi alanını genişlettiği gibi modern orduların kabiliyetlerini ve gereksinimlerini de etkilemektedir. Keşif ve gözetleme görevinin en etkin ve verimli şekilde yapabilmesi, envanterindeki sistemlerin modern olması ile birlikte bu sistemleri bilimsel yaklaşımlarla planlayabilme yeteneğine bağlıdır. Stratejik seviyede kullanılan İnsansız Hava Araçlarının (İHA) görevlendirmeleri esnasında karşılaşılan Araç Rotalama Problemleri (ARP), diğer sektörlerde olduğu gibi savunma sektöründe de oldukça yüksek maliyetlere sebep olabilmektedir. Bu nedenle İHA rota planlamalarının verimli bir şekilde çözümü, büyük tasarruflar sağlayacak olması ve hedeflerin zamanında gözetlenebilmeleri açısından önemlidir. Bu çalışmanın amacı, İnsansız Hava Sistemlerinin (İHS) dinamik rota planlamasına yönelik yapılan çalışmalarının incelenmesi ve ileride yapılabilecek çözüm yaklaşımlarına yön verilmesidir. Bu sayede, Türkiye’de henüz kullanılmaya başlayan stratejik İHS’lerin görev etkinliklerinin artırılması, proje ve kullanım maliyetlerinin düşürülmesi hedeflenmektedir.

Keywords

İnsansız Hava Sistemleri, İnsansız Dinamik Araç Rotalama Problemi Çözüm Yaklaşımları, Sezgisel Algoritmalar

Unmanned Aerial System Routing Problem Dynamic Solution Methods and Literature Review

Abstract

War tools and materials, which are an indicator of war strategy and development, vary with the technology. Modern Warfares in the information age, where near space and the space being used as a tool, differ from both the agricultural era wars, in which arrows and bows had been used as a tool, and industrial era battles, in which machine guns and tanks were employed. These characteristics influence this area of interest and area of influence in the area of responsibilities, and affect the ability and the necessity of modern armies as well. Being able to perform reconnaissance and surveillance missions in the most effective and efficient way is reliant on not only having the knowledge to create and invent them as well as having them in the inventor but also the ability of planning these systems with a modern scientific approach. Vehicle Routing Problem (VRP), encountered during the assignment of Unmanned Aerial Systems\Vehicles (UAS\V) which is being used at the strategic level, can lead to elevated costs in the defense sector as well as other sectors. For this reason, the efficient solution of route planning is a very important issue to provide major cost savings and to observe the targets timely.This study investigates the literature in “dynamic” route planning “solution” methods and defines the approaches for future “dynamic solution” studies of strategic UAVs which are being recently used in Turkey. Using this approach will increase the efficiency of usage of the UAVs and decrease the operating and project costs of them as well.

Keywords

Unmanned Aerial Systems, Dynamic Vehicle Routing Problem Solution Approaches, Heuristics

References

• Alpdoğan, K., 2008, A New Heuristic Approach to TSP (Yayımlanmamış Doktora Tezi), İstanbul, Marmara Üniversitesi. Attali, Jacques, 2007, Geleceğin Kısa Tarihi, (Çev. Turhan ILGAZ), Ankara, İmge Kitabevi.
• Aydemir, Emrah, 2006, Esnek Zaman Pencereli Araç Rotalama Problemi ve Bir Uygulama (Yayımlanmamış Yüksek Lisans Tezi), Ankara, Gazi Üniversitesi.
• Aytemiz, Tevfik, 2008, Kara Harp Okulu Savunma Bilimleri Enstitüsü 2008–2009 Eğitim-Öğretim Yılı Yaz Dönemi SB 5344 Hüristik Karar Yöntemleri Dersi Notları, Ankara.
• Bodin, L. D., Golden, B. L., Assad, A., Ball, M. O., 1983, “Routing and Scheduling of Vehicles and Crews: The State of the Art”, Computers and Operations Research, 10, 62-212.
• Boğ, S., 2006, Algorithms for the Vehicle Routing Problem with Time Windows and the Location-Routing Problem (Yayımlanmamış Yüksek Lisans Tezi), İstanbul, Koç Üniversitesi.
• Chandler, P. R., Patcher, M., 1998, “Research Issues in Autonomous Control of Tactical UAVs“, Proceedings of the American Control Conference Philadelphia, Pennsylvania, 394-398.
• Chin, Wang Jong, Sern, Victor Chua Yung, 2009, “Unmanned Aerial Vehicles: Development Trends&Technology Forecast”, Military Technology, 33,2, 70-80.
• Cook, W., Rich, J.L., 1999, "A parallel cutting-plane algorithm for the vehicle routing problem with time windows." Computational and Applied Mathematics Rice University, Houston EUA, 5.
• Cordeau, J. F., Gendreau, M., Laporte, G., Potvin, J.Y., Semet, F., 2002, “A Guide To Vehicle Routing Heuristics”, Journal of the Operational Research Society, 53, 512-522. Cura, T., 2008, Modern Sezgisel Teknikler ve Uygulamaları, Papatya Yayıncılık.
• Darcan, U., 2007, Stokastik Araç Rotalama Algoritmalarının Karşılaştırmalı İncelenmesi (Yayımlanmamış Yüksek Lisans Tezi), İstanbul , YTÜ Fen Bilimleri Enstitüsü.
• Dror, M., Powell, W., 1993, “Stochastic and Dynamic Models in Transportation”, Operations Research, Vol.41, 11-14.
• Dursun, P., 2009, Gezgin Satıcı Problemi için Veri Madenciliği Tabanlı Sezgisel Bir Yaklaşım (Yayımlanmamış Yüksek Lisans Tezi), Kocaeli, Kocaeli Üniversitesi.
• Ercan, C., Gencer, C., 2013, “Dinamik İnsansız Hava Sistemleri Rota Planlaması Literatür Araştırması ve İnsansız Hava Sistemleri Çalışma Alanları“, Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, Cilt 19, Sayı 2, 104-111.
• Erol, V., 2006, Araç Rotalama Problemleri için Popülasyon ve Komsuluk Tabanlı Metasezgisel Bir Algoritmanın Tasarımı ve Uygulaması (Yayımlanmamış Yüksek Lisans Tezi), İstanbul, Yıldız Teknik Üniversitesi, Sistem Mühendisliği.
• Gencer, C., Aydoğan, K.E., Kocabaş, S., 2009, “İnsansız Hava Araçlarının Rota Planlaması İçin Bir Karar Destek Sistemi”, Kara Harp Okulu Savunma Bilimleri Dergisi, 8(2), 59-73.
• Gerdan, O., 2007, Müşteriler Arası Malzeme Akışlı Eş Zamanlı Dağıtım-Toplama Yapılan Araç Rotalama Problemi ve Sezgisel Çözümü (Yayımlanmamış Doktora Tezi), Ankara, Gazi Üniversitesi Fen Bilimleri Enstitüsü.
• Gezdur, A., 2003, Capacitated Vehicle Routing Problem With TimeWindows (Yayımlanmamış Yüksek Lisans Tezi), İstanbul, Sabancı Üniversitesi.
• Gönülol, Semiye, 2009, A Heuristic Algorithm for an Integrated Routing and Scheduling Problem with Stops En-Route (Yayımlanmamış Yüksek Lisans Tezi), Ankara, Bilkent Üniversitesi.
• Hax, A.C., Candea, D, 1984, Production and Inventory Management, Prentice-Hall, Englewood Cliffs, NJ.
• Hromkovic, J., 2004, Algorithmics for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, Second Edition, Springer-Verlag, Berlin Heidelberg, Germany.
• Karaboğa, D., 2004, Yapay Zeka Optimizasyon Algoritmaları, Atlas Yayın Dağıtım. Kocabaş, S., 2003, İnsansız Hava Araçlarının Rota Planlaması için bir Karar Destek Sistemi (Yayımlanmamış Yüksek Lisans Tezi), Ankara, Kara Harp Okulu Savunma Bilimleri Enstitüsü.
• Kohl, N., Madsen, B.G., 1997, “An optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation”, Operations Researchs, Vol:45 Informs, 395-406.
• Kolen, A.W.J., Rinnooy, A.H.G., Trienekens, H.W.J.M., 1997, “Vehicle Routing with Time Windows”, Operations Research, Vol:35.
• Kontroravdis, G., Bard, J.F., 1994, “A GRASP for the Vehicle Routing Problem with Time Windows”, ORSA Journal on Computing Vol. 7, No. 1.
• Koyuncu, E., İnalhan, G., 2012, “Exploiting Delayed and Imperfect Information for Generating Approximate UAV Target Interception Strategy”, J Intell Robot Syst.
• Laporte G., 1991, “The Traveling Salesman Problem: An overview of Exact and Approximate Algorithms”, European Journal of Operations Research, 231.
• Larsen, A., 2000, The Dynamic Vehicle Routing Problem (Ph.D. Thesis), Danimarka, Technical University of Denmark, IMM, DTU.
• Larsen, A., Madsen, O.B.G., Solomon, M.G., 2007, “Classification of Dynamic Vehicle Routing Sytems”, Dynamic Fleet Management Concepts, Systems, Algorithms, & Case Studies (Editors: Vasileios Zeimpekis, Christos D. Tarantilis, George M. Giaglis, Ioannis Minis), Chapter 2, Springer.
• Lau, H.C., Sim, V., Teo, K.M., 2003, “Vehicle routing problem with time windows and a limited number of vehicles”, European Journal of Operations Research, 148, ss: 559-569.
• Lenstra, J., Kan, R.A., 1981. “Complexity of Vehicle Routing and Scheduling Problems”, Networks, Vol.11, pp.221-227.
• Neumann, V.J., Morgenstern, O., 1945, "Theory of Games and Economic Behavior", Bull. Amer. Math. Soc 51, ss: 498-504.
• Odom, E., 2002, “Future Employment of Unmanned Aerial Vehicles”, Aerospace Power Journal, 16,2.
• Osman İ., 1993, “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem”, Annals of Operations Research, 41:421-451.
• Öncan, T., 2004, On Unidirectional Cyclic Layouts, Hamiltonian Circuits, Capacitated Vehicle Routes and Minimal Spanning Trees (Yayımlanmamış Doktora Tezi), İstanbul, Boğaziçi Üniversitesi Endüstri Mühendisliği.
• Önder, İ., 2007(a), An Employee Transporting Problem and its Heuristic Solutions (Yayımlanmamış Yüksek Lisans Tezi), Ankara, Çankaya Üniversitesi.
• Önder, İ., 2007(b), A Genetic Algorithm for TSP with Backhauls Based on Conventional Heuristics (Yayımlanmamış Yüksek Lisans Tezi), Ankara, ODTÜ.
• Özaydın, Ekim, 2003, Integrated Vehicle Routing and Warehouse Location Problem (Yayımlanmamış Yüksek Lisans Tezi), İstanbul, Koç Üniversitesi.
• Özfırat, P. M., 2008, Exact And Heurıstıc Algorıthms For The Varıants Of The Vehıcle Routıng Problem (Yayımlanmamış Doktora Tezi), İzmir, Dokuz Eylül Üniversitesi, Endüstri Mühendisliği.
• Özkan, P., 2006, Araç Rotalama ve Çizelgeleme (Yayımlanmamış Yüksek Lisans Tezi), İstanbul, İTÜ, Fen Bilimleri Enstitüsü.
• Pakkan, Baha, Murat Ermiş, 2010, “İnsansız Hava Araçlarının Genetik Algoritma Yöntemiyle Çoklu Hedeflere Planlanması”, Havacılık ve Uzay Teknolojileri Dergisi, Cilt 4 Sayı 3, 77-84.
• Powell, W.B., Jaillet P., Odoni, A.R., 1995, “Stochastic and Dynamic Networks and Routing, in Network Routing”, Handbooks in OR and Management Science, Vol.8, North Holland: Amsterdam, 141- 295.
• Psaraftis, H. N., 1995, “Dynamic Vehicle Routing Problems: Status and Prospects”, Ann.Opns.Res., 61, 143-164
• Psaraftis, H. N., 1998, “Dynamic Vehicle Routing Problems”. B.L.Golden, A.A.Assad, eds. Vehicle Routing: Methods and Studies, Elsevier Science Publishers B.V.(North Holland), Amsterdam, 223- 248.
• Pustam, A., R., 2002, “Unmanned Aerial Vehicles: Trends and Prospects”, Military Technology, 26, 11, 44- 55.
• Sarıgöl, İ., 2007, A Clustared Based Heuristic for Location Routing Problems (Yayımlanmamış Yüksek Lisans Tezi), İstanbul, Sabancı Üniversitesi.
• Shima,T., Rasmussen, S., 2009, “UAV Cooperative Decision and Control Challenges and Practical Approaches”, Society for Industrial and Applied Mathematics, Philadelphia.
• Sujit, P.B., Sinha, A., Ghose, D., 2007, “Team, Game, and Negotiation based Intelligent Autonomous UAV Task Allocation for Wide Area Applications”, Studies in Computational Intelligence (SCI), 70, 39–75.
• Şeker, Şükran, 2007, Araç Rotalama Problemleri ve Zaman Pencereli Stokastik Araç Rotalama Problemine Genetik Algoritma Yaklaşımı (Yayımlanmamış Yüksek Lisans Tezi), İstanbul, Yıldız Teknik Üniversitesi Fen Bilimleri Enstitüsü.
• Tan, K.C., Lee, L.H., Zhu, Q.L., Ou. K., 2001, “Heuristic Methods for Vehicle Routing Problem with Time Windows”, Artificial Intelligence in Engineering, vol.15, ss.281-295.
• Taşkıran, D., 2006, A Revised Multiple Ant Colony System For Vehicle Routing Problems With TimeWindows (Yayımlanmamış Yüksek Lisans Tezi), İstanbul, Sabancı Üniversitesi.
• Tezer, T., 2009, Toplama ve Dağıtım Zaman Pencereli Araç Rotalama Problemi İçin Kesin Çözüm Yaklaşımı ve Örnek Uygulamalar (Yayımlanmamış Yüksek Lisans Tezi), Balıkesir, Balıkesir Üniversitesi Fen Bilimleri Fakültesi.
• Thompson, P.M., Psaraftis, H.N., 1993, “Cyclic Transfer Algorithms for the Multivehicle Routing and Scheduling Problems”, Operations Research 41, 935-946.
• Tokaylı, M.A., 2005, Zaman Pencereli Araç Rotalama Problemi için Bir Karar Destek Sistemi (Yayımlanmamış Yüksek Lisans Tezi), Ankara, Gazi Üniversitesi.
• Toth, P., D. Vigo, 2001, “The Vehicle Routing Problem”, SIAM Monograhs on Discrete Mathematics and Applications, SIAM Publishing, Philadelphia, PA.
• U.S. DoD Home Page. Erişim 12 Ağustos 2011, Unmanned System Integrated Roadmap 2010-2035, <http://www.dtic.mil >.
• Uzun, E., 2009, A Heuristic Algorithm for an Integrated Routing and Scheduling Problem with Stops En-Route (Yayımlanmamış Yüksek Lisans Tezi), Ankara, Bilkent Üniversitesi.
• Yılmaz, Şule, 2008, Çok Depolu Araç Rotalama Probleminin Karınca Kolonisi Optimizasyonu ile modellenmesi ve Bir Çözüm Önerisi (Yayımlanmamış Yüksek Lisans Tezi), İstanbul, Yıldız Teknik Üniversitesi Fen Bilimleri Enstitüsü. Zheng,W., Xiang-Pei, H., Yang, C., Wen-Li, L. 2007, “Real Time Modeling Method for Vehicle Routing Problems”, International Conference on Harbin, P.R. China, ICMSE.
• Zucker, M., Kuffner, J., Branicky, M., 2007, “Multipartite RRTs for Rapid Replanning in Dynamic Environments”, 2007 IEEE Conference on Robotics and Automation, Italy.