Literature Review of Dynamic Unmanned Aerial System Routing Problems and Proposals For Future Studies of UASs

Abstract

Outwith the technological developments made with Unmanned Aerial Vehicles (UAV); other important issues for the users like effective planning and re-planning; providing the clear, concise and timely information to the decision makers is part of the Network Enabled Capability. Significant improvements to the Communication and Information systems have made it possible to find dynamic solutions for Vehicle Routing Problems. In this context, "Vehicle Routing" applications for UAVs in reconnaissance missions are increasing exponentially. This study investigates the literature in "dynamic route planning", defining the scope and identifying shortcomings for future studies in Unmanned Aerial Systems. Using this approach not only reduces stagnant travel time to target time but increases the usable times spent on targets.

Keywords

• Unmanned aerial systems, Unmanned aerial vehicles, Vehicle routing problems, Dynamic vehicle routing problem.

Dinamik İnsansız Hava Sistemleri Rota Planlaması Literatür Araştırması ve İnsansız Hava Araçları Çalışma Alanları

Öz

İnsansız Hava Sistemleri (İHS) ile sağlanan teknolojik olanaklar kadar önemli olan bir husus da, kullanıcının bu olanakları etkin şekilde planlayabilmesi, ihtiyacı olan anlık değişikliğe çabuk ayak uydurabilmesi, karar vericiler için önemli olabilecek bilgiyi doğru ve zamanında paylaşabilmesi, kısaca ağ üzerinde verimli çalışabilmesidir. Muhabere Elektronik ve Bilgi Sistemleri (MEBS)'ndeki gelişmeler, Araç Rotalama Probleminin (ARP) dinamik durumlarda da çözümünü mümkün kılmıştır. Bu bağlamda İHS'lerinin, keşif faaliyetleri rota planlanması kapsamındaki ARP uygulamaları her geçen gün gelişerek artmaktadır. Bu makalenin amacı, İHS'lerinin "dinamik rota planlaması" kapsamında yapılan literatür çalışmalarının incelenmesi, kapsamlarının tespiti, bu alandaki gelişmeler ile çalışılmayan alanların belirlenmesi ve böylelikle ileride araştırma yapılabilecek alanlara yön verilmesidir. Bu sayede, İHS'lerin havada kalış süresinin artırılmasından ziyade, havada kaldığı müddetçe yol için ayrılan "niteliksiz" zamanın azaltılarak, hedefler üzerindeki görevini icra ettiği "nitelikli" zamanın artırılması hedeflenmektedir.

Anahtar Kelimeler

• İnsansız hava sistemleri, İnsansız hava araçları, Araç rotalama problemi, Dinamik araç rotalama problemi.

References

1. Goraj, Z., “Civilian Unmanned Aerial Vehicles – Overview Of European Effort and Challenges for the Future”, Aviation Journal, Vilnius, VII (1), 3-15, 2003.
2. Argun, M., “Savaşların Yeni Cephesi”, Savunma ve Havacılık Dergisi, 2010/2, Cilt 24, 138, 2010.
3. FM 34-25-2, Unmanned Aerial Vehicles (Draft), Washington, http://www.fas.org/irp/doddir/army/fm34-25- 2/index.html. İnternet erişim tarihi: 06 Haziran 2012.
4. Toth, P. ve Vigo., D., The Vehicle Routing Problem, SIAM Monograhs on Discrete Mathematics and Applications, SIAM Publishing, Philadelphia, PA, 2001.
5. Dantzig, G.B. ve Ramser. J.H., “The Truck Dispatching Problem”, Management Science, Vol.6, No.1, 1959, 80-91. Published http://www.jstor.org/stable/2627477 24/11/2010 08:14. Stable URL: Erişim:
6. Şeker, Ş., “Araç Rotalama Problemleri ve Zaman Pencereli Stokastik Araç Rotalama Problemine Genetik Algoritma Yaklaşımı” (Yayımlanmış Yüksek Lisans Tezi), İstanbul, Yıldız Teknik Üniversitesi Fen Bilimleri Enstitüsü, 2007.
7. Kocabaş, S., “İnsansız Hava Araçlarının Rota Planlaması için bir Karar Destek Sistemi (Yayımlanmış Yüksek Lisans Tezi)”, Ankara, Kara Harp Okulu Savunma Bilimleri Enstitüsü, 2003.
8. O’Rourke. K.P., Bailey, T.G, Hill, M.R., ve Carlton, W.B., “Dynamic Routing of Unmanned Aerial Vehicles Using Reactive Tabu Search”, Military Operations Research, 6(1), 5-30, 1999.

9. Jin, Y., Liao,Y., Minai, A.A. ve Polycarpou, M.M., “Balancing Search and Target Response in Cooperative Unmanned Aerial Vehicle (UAV) Teams”, IEEE Trans Syst Man Cybern B Cybern, 36(3), 571-587, 2006.
10. Kim, Y., D.-W. Gu and I., Postlethwaite, “Real-time path planning with limited information for Autonomous uninhabited air vehicles”, Automatica, 44(3), 696-712, 2008.
11. Peng, X. ve Gao, X., “A Multi-objective Optimal Approach for UAV Routing in Reconnaissance Mission with Stochastic Observation Time”, Foundations of Intelligent Systems, 17th International Symposium, ISMIS 2008, Toronto, Canada, May 20-23, Proceedings, 246-255, 2008.
12. Duan, H., Zhang. X,, Wu, J. ve Ma. G., “Max-Min Adaptive Ant Colony Optimization Approach to Multi-UAVs Coordinated Trajectory Replanning in Dynamic and Uncertain Environments”, Journal of Bionic Engineering, 161-173, 2009.
13. Murray, C.C. ve Karwan, H.M., “An Extensible Modeling Framework for Dynamic Reassignment and Rerouting in Cooperative Airborne Operations”, Wiley Online Library, Naval Research Logistics 57 (7), 634-652, 2010.
14. Mansız, B., Yetenek Tabanlı Teknoloji Öngörüsü Modeli: İnsansız Hava Aracı Uygulaması (Yayımlanmış Yüksek Lisans Tezi), Ankara, Kara Harp Okulu Savunma Bilimleri Enstitüsü, 2010.
15. USA DoD Internet, Unmanned FY 2009–2034 Unmanned Systems Integrated Roadmap, 2009.
16. Bianchi, L., Notes on Dynamic Vehicle Routing –The State of Art, Technical Report IDSIA-05-01, 2000.
17. Psaraftis, H.N., Dynamic Vehicle Routing Problems In B.L. Golden, A.A. Assad, editors, Vehicle Routing: Methods and Studies, chapter 11, Elsevier Science Publishers B.V.(North Holland), Amsterdam, 223-248, 1998.
18. Erol, V., Araç Rotalama Problemleri için Popülasyon ve Komşuluk 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, 2006.
19. Braysy, O. ve Gendreau, M., “Tabu Search Heuristics for the Vehicle Routing Problem with Time Windows”, Sociedad de Estadistica e Investigacion Operativa Top, Vol. 10, No. 2, 211-237, 2002.
20. Taillard, E.D., “A Heuristic Column Generation Method For The Heterogeneous Fleet VRP”, RAIRO Rech. Oper., Vol. 33 (1), 1-14, 1999.
21. Pissinger D. ve Ropke, S., “A General Heuristic For Vehicle Routing Problems”, Computers & Opreations Research, 34 (8), 2403-2435, 2007.