This article advances the geographic grid approach to military unmanned aircraft systems (UAS) routing featured in the existing literature. Its contributions are twofold. First, it demonstrates an empirical scoring system to determine the most important areas for maritime domain awareness-focused intelligence, surveillance, and reconnaissance collection, applying the method to the South China Sea. Second, it introduces what we call the “team orienteering problem with prize-dependent loitering times” (TOP-PDLT) and uses that model to identify optimal UAS collection routes in the South China Sea. Compared with other grid-based UAS routing schemes that use service time-dependent profits, TOP-PDLT is shown to be particularly applicable to military use-cases.
GettingerD.Drone databook update: March 2020.Hudson, NY: Center for the Study of the Drone at Bard College, 2020.
2.
LingelSRhodesCCordovaA, et al. Methodology for improving the planning, execution, and assessment of intelligence, surveillance, and reconnaissance operations. Santa Monica, CA: RAND Corporation, 2008.
United States Government US Army. JP 2-01: Joint and national intelligence support to military operations.Arlington County, VA: Department of Defense, 2017.
5.
CoutinhoWPBattarraMFliegeJ.The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review. Comput Ind Eng2018; 120: 116–128.
6.
MacrinaGPuglieseLDPGuerrieroF, et al. Drone-aided routing: a literature review. Transp Res Part C Emerg Technol2020; 120: 102762.
7.
PoikonenSCampbellJF.Future directions in drone routing research. Networks2021; 77: 116–126.
8.
ViloriaDRSolano-CharrisELMuñoz-VillamizarA, et al. Unmanned aerial vehicles/drones in vehicle routing problems: a literature review. Int Trans Oper Res2021; 28: 1626–1657.
9.
KhoufiILaouitiAAdjihC.A survey of recent extended variants of the traveling salesman and vehicle routing problems for unmanned aerial vehicles. Drones2019; 3: 66.
10.
ChoPBattaR.UAV search path optimization for recording emerging targets. Mil Oper Res2021; 26: 27–48.
11.
DasdemirEBattaRKöksalanM, et al. UAV routing for reconnaissance mission: a multi-objective orienteering problem with time-dependent prizes and multiple connections. Comput Oper Res2022; 145: 105882.
12.
HencheyMJBattaRKarwanM, et al. A flight time approximation model for unmanned aerial vehicles: estimating the effects of path variations and wind. Mil Oper Res2014; 19: 51–68.
13.
JotraoSBattaR.Time-constrained UAV path planning in 3D network for maximum information gain. Mil Oper Res2021; 26: 5–25.
14.
MishraSBattaRSzczerbaRJ.A rule based approach for aircraft dispatching to emerging targets. Mil Oper Res2004; 9: 17–30.
15.
MoskalMDIIBattaR. A macrogrid approach for routing UAVs in support of information gathering. Mil Oper Res2017; 22: 35–54.
16.
MoskalMDIIBattaR. Adaptive unmanned aerial vehicle surveillance using a prize-collecting vertex routing model. Mil Oper Res2019; 24: 5–22.
17.
MoskalMDIIDasdemirEBattaR.Unmanned aerial vehicle information collection missions with uncertain characteristics. INFORMS J Comput2023; 35: 120–137.
18.
ThyagarajanKBattaRKarwanMH, et al. Planning dissimilar paths for military units. Mil Oper Res2005; 10: 25–42.
19.
XiaYBattaRNagiR.Controlling a fleet of unmanned aerial vehicles to collect uncertain information in a threat environment. Oper Res2017; 65: 674–692.
20.
BresnickTABuedeDMPisaniAA, et al. Airborne and space-borne reconnaissance force mixes: a decision analysis approach. Mil Oper Res1997; 3: 65–78.
21.
RhodesCHagenJWestergrenJ.A strategies-to-tasks framework for planning and executing intelligence, surveillance, and reconnaissance (ISR) operations. Santa Monica, CA: RAND Corporation, 2007.
22.
AveyPCDeschMC.What do policymakers want from us? Results of a survey of current and former senior national security decision makers. Int Stud Q2014; 58: 227–246.
23.
DuanHZhangXWuJ, et al. Max-min adaptive ant colony optimization approach to Multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments. J Bionic Eng2009; 6: 161–173.
24.
EversLDollevoetTBarrosAI, et al. Robust UAV mission planning. Ann Oper Res2014; 222: 293–315.
25.
ErdoğanGLaporteG.The orienteering problem with variable profits. Networks2013; 61: 104–116.
26.
GuitouniAMasriH.An orienteering model for the search and rescue problem. Comput Manag Sci2014; 11: 459–473.
27.
PietzJRoysetJO.Generalized orienteering problem with resource dependent rewards. Nav Res Logist2013; 60: 294–312.
28.
YuJAslamJKaramanS, et al. Anytime Planning of Optimal Schedules for a Mobile Sensing Robot. In: 2015 IEEE/RSJ international conference on intelligent robots and systems (IROS), Hamburg, Germany, 28 September 2015–2 October 2015, pp. 5279–5286. New York: IEEE.
29.
SharpTMahnkenTGSadovT.Extending deterrence by detection: the case for integrating unmanned aircraft systems into the indo-pacific partnership for maritime domain awareness.Washington, DC: Center for Strategic and Budgetary Assessments, 2023.
30.
ErcanCGencerC.A decision support system for dynamic heterogeneous unmanned aerial system fleets. Gazi Univ J Sci2018; 31: 863–877.
31.
RosalieMDanoyGChaumetteS, et al. Chaos-enhanced mobility models for multilevel swarms of UAVs. Swarm Evol Comput2018; 41: 36–48.
32.
ZhangYChenJShenL.Hybrid hierarchical trajectory planning for a fixed-wing UCAV performing air-to-surface multi-target attack. J Syst Eng Electron2012; 23: 536–552.
33.
ZhouTZhangJShiJ, et al. Multidepot UAV routing problem with weapon configuration and time window. J Adv Transp2018; 2018: 1–15.
34.
SinghalGBansodBMathewL.Unmanned aerial vehicle classification, applications and challenges: a review. Document No 2018110601. Published 2018. Preprints.org https://www.preprints.org/manuscript/201811.0601/v1
35.
OttoAAgatzNCampbellJ, et al. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: a survey. Networks2018; 72: 411–458.
36.
JeongHYLeeSSongBD.Truck-drone hybrid delivery routing: payload-energy dependency and no-fly zones. Int J Prod Econ2019; 214: 220–233.
37.
LuoHLiangZZhuM, et al. Integrated optimization of unmanned aerial vehicle task allocation and path planning under steady wind. PLoS ONE2018; 13(3): e0194690.
38.
TroudiAAddoucheSADellagiS, et al. Sizing of the drone delivery fleet considering energy autonomy. Sustainability2018; 10: 1–17.
39.
HamiltonTOchmanekD.Operating low-cost, reusable unmanned aerial vehicles in contested environments. Santa Monica, CA: RAND Corporation, 2020.
40.
EnthovenACSmithKW.How much is enough? Shaping the defense program 1961-1969. New York: Harper & Row, 1971.
DoaneDP.Aesthetic frequency classifications. Am Stat1976; 30: 181–183.
49.
LeggPARosinPLMarshallD, et al. Improving accuracy and efficiency of mutual information for multi-modal retinal image registration using adaptive probability density estimation. Comput Med Imaging Graph2013; 37: 597–606.
50.
Janes Group. GA-ASI predator B/MQ-9 Reaper/MQ-9B. Janes all the world’s aircraft: unmanned. Croydon, Jane’s Information Group, 2022.
51.
Janes Group. Northrop Grumman RQ-4 Global Hawk. Janes all the world’s aircraft: unmanned. Croydon, Jane’s Information Group, 2023.
Di SimoneAParkHRiccioD, et al. Sea target detection using spaceborne GNSS-R delay-doppler maps: theory and experimental proof of concept using TDS-1 data. IEEE J Sel Top Appl Earth Obs Remote Sens2017; 10: 4237–4255.
56.
SoldiGGaglioneDFortiN, et al. Space-based global maritime surveillance. Part I: satellite technologies. IEEE Aerosp Electron Syst Mag2021; 36: 8–28.
57.
ZhangZZhangLWuJ, et al. Optical and synthetic aperture radar image fusion for ship detection and recognition: current state, challenges, and future prospects. IEEE Geosci Remote Sens Mag2024; 12: 132–168. DOI: 10.1109/MGRS.2024.3404506.
58.
SoldiGGaglioneDFortiN, et al. Space-based global maritime surveillance. Part II: artificial intelligence and data fusion techniques. IEEE Aerosp Electron Syst Mag2021; 36: 30–42.
59.
WangJGuoJChenJ, et al. Uncertain team orienteering problem with time windows based on uncertainty theory. IEEE Access2019; 7: 63403–63414.
60.
ArchettiCSperanzaMGVigoD.Vehicle routing problems with profits. vehicle routing: problems, methods, and applications. Soc Ind Appl Math2014; 10: 273–297.
ArchettiCHertzASperanzaMG.Metaheuristics for the team orienteering problem. J Heuristics2006; 13: 49–76.
68.
BaylissCJuanAACurrieCSM, et al. A learnheuristic approach for the team orienteering problem with aerial drone motion constraints. Applied Soft Computing2020; 92: 106280. DOI: 10.1016/j.asoc.2020.106280.
69.
DorigoMGambardellaLM.Ant colony system: a cooperative learning approach to the travelling salesman problem. IEEE Trans Evol Comput1997; 1: 53–66.
70.
ElzeinADi CaroGA.A clustering metaheuristic for large orienteering problems. PLoS ONE2022; 17: e0271751. DOI: 10.1371/journal.pone.0271751.
71.
TangHMiller-HooksE.A tabu search heuristic for the team orienteering problem. Comput Oper Res2005; 32: 1379–1407.
72.
PanaderoJAmmouriovaMJuanÁA, et al. Combining parallel computing and biased randomization for solving the team orienteering problem in real-time. Appl Sci2021; 11: 12092.
73.
VerbeeckCVansteenwegenPAghezzafEH.Solving the stochastic time-dependent orienteering problem with time windows. Eur J Oper Res2016; 255: 699–718.
74.
YuQAdulyasakYRousseauL, et al. Team orienteering with time-varying profit. INFORMS J Comput2022; 34: 262–280.
75.
YuQFangKZhuN, et al. A metaheuristic approach to the orienteering problem with service time dependent profits. Eur J Oper Res2019; 273: 488–503.
76.
YuVFJewpanyabPLinS, et al. Team orienteering problem with time windows and time-dependent scores. Comput Ind Eng2019; 127: 213–224.
77.
BorazSC.Maritime domain awareness. Nav War Coll Rev2009; 62: 137–146.
78.
KhodadadianMDivsalarAVerbeeckC, et al. Time dependent orienteering problem with time windows and service time dependent profits. Comput Oper Res2022; 143: 105794.
79.
PengGSongGXingL, et al. An exact algorithm for agile earth observation satellite scheduling with time-dependent profits. Comput Oper Res2020; 120: 104946.
80.
SunPVeelenturfLPHewittM, et al. The time-dependent pickup and delivery problem with time windows. Transp Res Part B Methodol2018; 116: 1–24.
81.
LinSW.Solving the team orienteering problem using effective multi-start simulated annealing. Applied Soft Computing2013; 13: 1064–1073. DOI: 10.1016/j.asoc.2012.09.022.
82.
LinSWYuVF.Solving the team orienteering problem with time windows and mandatory visits by multi-start simulated annealing. Comput Ind Eng2017; 114: 195–205. DOI: 10.1016/j.cie.2017.10.020.
83.
YuVFSNabilaYShih-WeiL, et al. Simulated annealing with reinforcement learning for the set team orienteering problem with time windows. Expert Syst Appl2024; 238: 121996. DOI: 10.1016/j.eswa.2023.121996.
