Year 2018, Volume 31, Issue 3, Pages 863 - 877 2018-09-01

A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets

Cihan ERCAN [1] , Cevriye GENCER [2]

75 116

    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.

Decision Support Systems, VRP, Dynamic Vehicle Routing Problems, Heuristics
  • [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. 18. SIAM. [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 ( [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. [38] Lenstra, J. K. 2003. Local search in combinatorial optimization. Princeton University Press.
Subjects Science
Journal Section Industrial Engineering

Author: Cihan ERCAN
Country: Turkey

Author: Cevriye GENCER
Country: Turkey

Bibtex @research article { gujs347617, journal = {GAZI UNIVERSITY JOURNAL OF SCIENCE}, issn = {}, eissn = {2147-1762}, address = {Gazi University}, year = {2018}, volume = {31}, pages = {863 - 877}, doi = {}, title = {A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets}, key = {cite}, author = {ERCAN, Cihan and GENCER, Cevriye} }
APA ERCAN, C , GENCER, C . (2018). A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets. GAZI UNIVERSITY JOURNAL OF SCIENCE, 31 (3), 863-877. Retrieved from
MLA ERCAN, C , GENCER, C . "A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets". GAZI UNIVERSITY JOURNAL OF SCIENCE 31 (2018): 863-877 <>
Chicago ERCAN, C , GENCER, C . "A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets". GAZI UNIVERSITY JOURNAL OF SCIENCE 31 (2018): 863-877
RIS TY - JOUR T1 - A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets AU - Cihan ERCAN , Cevriye GENCER Y1 - 2018 PY - 2018 N1 - DO - T2 - GAZI UNIVERSITY JOURNAL OF SCIENCE JF - Journal JO - JOR SP - 863 EP - 877 VL - 31 IS - 3 SN - -2147-1762 M3 - UR - Y2 - 2018 ER -
EndNote %0 GAZI UNIVERSITY JOURNAL OF SCIENCE A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets %A Cihan ERCAN , Cevriye GENCER %T A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets %D 2018 %J GAZI UNIVERSITY JOURNAL OF SCIENCE %P -2147-1762 %V 31 %N 3 %R %U
ISNAD ERCAN, Cihan , GENCER, Cevriye . "A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets". GAZI UNIVERSITY JOURNAL OF SCIENCE 31 / 3 (September 2018): 863-877.