A Decision Support System for Dynamic Heterogeneous Unmanned Aerial System Fleets

Year 2018, Volume: 31 Issue: 3, 863 - 877, 01.09.2018

Cihan Ercan , Cevriye Gencer

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.

Keywords

Decision Support Systems, VRP, Dynamic Vehicle Routing Problems, Heuristics

References

• [1] U.S. DoD Home Page. 2011. “Unmanned System Integrated Roadmap 2010-2035”. http://www.dtic.mil. [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 (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. [38] Lenstra, J. K. 2003. Local search in combinatorial optimization. Princeton University Press.