×

Minisum and maximin aerial surveillance over disjoint rectangles. (English) Zbl 1362.90325

Summary: The aerial surveillance problem (ASP) is finding the shortest path for an aerial surveillance platform that has to visit each rectangular area once and conduct a search in strips to cover the area at an acceptable level of efficiency and turn back to the base from which it starts. In this study, we propose a new formulation for ASP with salient features. The proposed formulation that is based on the travelling salesman problem enables more efficient use of search platforms and solutions to realistic problems in reasonable time. We also present a max-min version of ASP that maximizes the minimum probability of target detection given the maximum flight distance of an aerial platform. We provide computational results that demonstrate features of the proposed models.

MSC:

90C27 Combinatorial optimization
90C10 Integer programming

Software:

GAMS
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Brook A, Kendrik D, Meeraus A (1996) GAMS: a user’s guide. Body & Fraser Publishing Company, Massachusetts
[2] Chekuri C, Korula N, Pal M (2012) Improved algorithms for orienteering and related problems. ACM Trans Algorithms 8(3):1-27 · Zbl 1295.05225
[3] Dantzig GB, Fulkerson DR, Johnson SM (1954) Solution of a large-scale travelling salesman problem. Oper Res 2:393-410 · Zbl 1414.90372
[4] DOD Dictionary of Military Terms (2016) http://dtic.mil/doctrine/dod_dictionary/index.html. Accessed 9 Apr 2016 · Zbl 1085.90012
[5] Grob MJHB (2006) Routing of platforms in a maritime surface surveillance operation. Eur J Oper Res 170:613-628 · Zbl 1085.90012 · doi:10.1016/j.ejor.2004.02.029
[6] Jacobson SH, McLay LA, Hall SN, Henderson D, Vaughan DE (2006) Optimal search strategies using simultaneous generalized hill climbing algorithms. Math Comput Model 43:1061-1073 · Zbl 1170.90404 · doi:10.1016/j.mcm.2005.05.025
[7] John M, Panton D, White K (2001) Mission planning for regional surveillance. Ann Oper Res 108:157-173 · Zbl 1001.90518 · doi:10.1023/A:1016063129217
[8] Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J Assoc Comput Mach 7:326-329 · Zbl 0100.15101 · doi:10.1145/321043.321046
[9] Ng KYK, Ghanmi A (2002) An automated surface surveillance system. J Oper Res Soc 53:697-708 · Zbl 1130.90346 · doi:10.1057/palgrave.jors.2601363
[10] Ng KYK, Sancho NFG (2009) Regional surveillance of disjoint rectangles: a travelling salesman formulation. J Oper Res Soc 60:215-220 · Zbl 1168.90633 · doi:10.1057/palgrave.jors.2602507
[11] Panton DM, Elbers AW (1999) Mission planning for synthetic aperture radar surveillance. Interfaces 29:73-88 · doi:10.1287/inte.29.2.73
[12] Pietz J, Royset JO (2013) Generalized orienteering problem with resource dependent rewards. Nav Res Logist 60(4):294-312 · Zbl 1410.90030 · doi:10.1002/nav.21534
[13] Simonin C, Le Cadre JP, Dambreville F (2009) A hierarchical approach for planning a multisensor multizone search for a moving target. Comput Oper Res 36:2179-2192 · Zbl 1158.90360 · doi:10.1016/j.cor.2008.08.007
[14] Vansteenwegen P, Souffriau W, Oudheusten DV (2011) The orienteering problem: a survey. Eur J Oper Res 209(1):1-10 · Zbl 1205.90253 · doi:10.1016/j.ejor.2010.03.045
[15] Wagner DH, Mylander WC, Sanders TJ (1999) Naval operations analysis, 3rd edn. Naval Institute Press, Maryland
[16] Yakıcı E, Karasakal O (2013) A min-max vehicle routing problem with split delivery and heterogeneous demand. Optim Lett 7:1611-1625 · Zbl 1280.90017 · doi:10.1007/s11590-012-0571-8
[17] Zhang F, Wang G, Zeng Q, ye J (2013) An algorithm for minimal circumscribed rectangle of image object based on searching principle axis method. Res J Appl Sci Eng Technol 5(11):3083-3086
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.