Journals / Gazi University Journal of Science / 2018 / Volume: 31 Issue: 3

A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets

Pages
—
Publication Date
2018-09-01
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

It describes an efficient heuristic method capable of producing quick dynamic solutions on a series of empirical test problems.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The Dynamic Unmanned Aerial System Routing Problem (DUASRP) is a variant of the classic Vehicle Routing Problem (VRP) in which both planned and unplanned targets are observed by a fleet of Unmanned Aerial Systems (UASs).
📊
Key Findings & Data:In the dynamic environment of UAS, the rapid response for the new important targets is a very critical process, especially for the military operations in battlespace conditions.
💡
Conclusion & Impact:It describes an efficient heuristic method capable of producing quick dynamic solutions on a series of empirical test problems.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Decision Support Systems · VRP · Dynamic Vehicle Routing Problems

Abstract

The Dynamic Unmanned Aerial System Routing Problem (DUASRP) is a variant of the classic Vehicle Routing Problem (VRP) in which both planned and unplanned targets are observed by a fleet of Unmanned Aerial Systems (UASs). In the dynamic environment of UAS, the rapid response for the new important targets is a very critical process, especially for the military operations in battlespace conditions. This study describes a heuristic method for the solution of the dynamic heterogeneous UAS routing problems without causing the initial tour to be completely changed. For the dynamic routing of Unmanned Aerial Vehicles (UAV), it is necessary to determine a combination of the least additional costs of vehicle routes through a set of geographically scattered targets, and quick responses for immediate targets during the reconnaissance missions. The most frequent cases assumed in the existing literature of classical DUASs consider all UASs as identical (homogenous), all targets as having two geographical coordinates (x and y), and the thread of the targets are ignored. In this paper, a dynamic routing decision support system (DSS) based on both fuzzy clustering and leveraged cheapest insertion neighborhood method is studied for pop-up threat in the case where the UAV fleet is heterogeneous, and targets have both three-dimensional information and threads. Instead of selecting an a priori code, the proposed control methodology dynamically starts with the route based on observed behavior of the new target and the routes. It describes an efficient heuristic method capable of producing quick dynamic solutions on a series of empirical test problems.

🔖

Cite This Article

Ercan, C., Gencer, C. (2018). A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets. Gazi University Journal of Science, Volume: 31 Issue: 3. https://ajindex.com/articles/1269258

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (37)

  1. U.S. DoD Home Page. 2011. “Unmanned System Integrated Roadmap 2010-2035”.
  2. Goraj, Z., 2003, Aviation, Vol VII, No 1: 3-15
  3. Shima, Tal, and Steven J. Rasmussen, 2009. UAV cooperative decision and control: challenges and practical approaches. Vol
  4. Laporte, Gilbert, Michel Gendreau, J‐Y. Potvin, and Frédéric Semet. 2000. "Classical and modern heuristics for the vehicle routing problem." International transactions in operational research 7, no. 4‐5: 285-300
  5. Toth, P., and Vigo, D., 2001. The Vehicle Routing Problem, SIAM Monograhs on Discrete Mathematics and Applications, Philadelphia, PA: SIAM Publishing
  6. Psaraftis, Harilaos N. 1998. Vehicle Routing Methods and Studies: Dynamic Vehicle Routing Problems: 223-248. (North Holland), Amsterdam: Elsevier Science Publishers B.V
  7. Larsen, Allan. 2000. "The dynamic vehicle routing problem." PhD diss., Technical University of DenmarkDanmarks Tekniske Universitet
  8. Larsen, A., Madsen, O. B. G., and Solomon, M.G. 2007. Dynamic Fleet Management Concepts, Systems, Algorithms, and Case Studies: Classification of Dynamic Vehicle Routing Systems (38): 19-40, Springer Science & Business Media. Springer
  9. Ichoua, Soumia, Michel Gendreau, and Jean-Yves Potvin. 2000. "Diversion issues in real-time vehicle dispatching." Transportation Science 34, no. 4: 426-438
  10. Powell, Warren B., Patrick Jaillet, and Amedeo Odoni. 1995. "Stochastic and dynamic networks and routing." Handbooks in operations research and management science 8: 141-295
  11. Lund, K., H.F Madsen, and J.M. Rygaard. 1996. Vehicles Routing Problems with Varying Degrees of Dynamism, Technical Report IMM-REP-1996-1, Technical University of Denmark, Denmark
  12. Bianchi, Leonora. 2000. "Notes on dynamic vehicle routing-the state of the art." Technical Report IDSIA-05-01 (ftp://ftp.idsia.ch/pub/techrep)
  13. Psaraftis, Harilaos N. 1995. "Dynamic vehicle routing: Status and prospects." Annals of Operations Research 61, no. 1: 143-164
  14. Gendreau, Michel, Francois Guertin, Jean-Yves Potvin, and Eric Taillard. 1999. "Parallel tabu search for real-time vehicle routing and dispatching." Transportation Science 33, no. 4: 381-390
  15. O’Rourke, K., William B. Carlton, T. Glenn Bailey, and Raymond R. Hill. "Dynamic routing of unmanned aerial vehicles using reactive tabu search." 67th MORS Symposium
  16. Peape, W.E. 2002. “Complexity Results and Competitive Analysis for Vehicle Routing Problems”, PhD diss., Technical University of Eindhoven
  17. Chitty, Darren M., and Marcel L. Hernandez. 2004. "A hybrid ant colony optimisation technique for dynamic vehicle routing." Genetic and Evolutionary Computation–GECCO: 48-59. Springer Berlin Heidelberg
  18. Angelelli, Enrico, M. Grazia Speranza, and Martin WP Savelsbergh. 2007. "Competitive analysis for dynamic multiperiod uncapacitated routing problems." Networks 49, no. 4: 308-317
  19. Branke, Jürgen, Martin Middendorf, Guntram Noeth, and Maged Dessouky. 2005. "Waiting strategies for dynamic vehicle routing." Transportation Science 39, no. 3: 298-312
  20. Montemanni, Roberto, Luca Maria Gambardella, Andrea Emilio Rizzoli, and Alberto V. Donati. 2005. "Ant colony system for a dynamic vehicle routing problem." Journal of Combinatorial Optimization 10(4):327-343
  21. Ichoua, Soumia, Michel Gendreau, and Jean-Yves Potvin. 2006. "Exploiting knowledge about future demands for real-time vehicle dispatching." Transportation Science 40, no. 2: 211-225
  22. Jin, Yan, Yan Liao, Ali Minai, and Marios M. Polycarpou. 2005. "Balancing search and target response in cooperative unmanned aerial vehicle (UAV) teams." Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on 36, no. 3: 571-587
  23. Kim, Yoonsoo, Da-Wei Gu, and Ian Postlethwaite. 2008. "Real-time path planning with limited information for autonomous unmanned air vehicles." Automatica 44, no. 3: 696-712
  24. Shetty, Vijay K., Moises Sudit, and Rakesh Nagi. 2008. "Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles." Computers & Operations Research 35, no. 6: 1813-1828
  25. Duan, Hai-bin, Xiang-yin Zhang, Jiang Wu, and Guan-jun Ma. 2009. "Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments." Journal of Bionic Engineering 6, no. 2: 161-173
  26. Murray, Chase C., and Mark H. Karwan. 2010. "An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations." Naval Research Logistics 57, no. 7: 634-652
  27. Mufalli, Frank, Rajan Batta, and Rakesh Nagi. 2012. "Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans." Computers & Operations Research 39, no. 11: 2787-2799
  28. Royset, Johannes O., W. Matthew Carlyle, and R. Kevin Wood. 2009. "Routing military aircraft with a constrained shortest-path algorithm." Military Operations Research 14, no. 3: 31-52
  29. Turban, Efraim, J. Aronson, and Ting-Peng Liang. 2005. Decision Support Systems and Intelligent Systems. 7th ed. Pearson Prentice Hall
  30. Zucker, Matt, James Kuffner, and Michael Branicky. 2007. "Multipartite RRTs for rapid replanning in dynamic environments." Robotics and Automation, IEEE International Conference: 1603-1609. IEEE
  31. Yang, Kwangjin, and Salah Sukkarieh. 2008. "3D smooth path planning for a UAV in cluttered natural environments." In Intelligent Robots and Systems. IROS. IEEE/RSJ International Conference: 794-800. IEEE
  32. Ahuja, Ravindra K., James B. Orlin, and Dushyant Sharma. 2000. "Very large‐scale neighborhood search." International Transactions in Operational Research 7, no. 4‐5: 301-317
  33. Chu, Chao-Hsien, and Jack C. Hayya. 1991. "A fuzzy clustering approach to manufacturing cell formation." The International Journal of Production Research 29, no. 7: 1475-1487
  34. Frazzoli, Emilio, Munther Dahleh, and Eric Feron. 2001. Real-time motion planning for agile autonomous vehicles. In American Control Conference. IEEE Proceedings, vol. 1: 43-49
  35. Beard, Randal W., Timothy W. McLain, Michael Goodrich, and Erik P. Anderson. 2002. "Coordinated target assignment and intercept for unmanned air vehicles." Robotics and Automation, IEEE Transactions on 18, no. 6: 911-922
  36. Duan, Haibin, Yaxiang Yu, Xiangyin Zhang, and Shan Shao. 2010. "Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm." Simulation Modelling Practice and Theory 18, no. 8: 1104-1115 [37] Gencer, Cevriye, Emel Kızılkaya Aydoğan, and Sercan Kocabaş. 2009. "İnsansız Hava Araçlarının Rota Planlaması İçin Bir Karar Destek Sistemi." Savunma Bilimleri Dergisi 8, no.1
  37. Lenstra, J. K. 2003. Local search in combinatorial optimization. Princeton University Press.