IDEAS home Printed from https://ideas.repec.org/a/spr/topjnl/v24y2016i3d10.1007_s11750-016-0416-1.html
   My bibliography  Save this article

Minisum and maximin aerial surveillance over disjoint rectangles

Author

Listed:
  • Orhan Karasakal

    (Bilkent University
    Decision Support Division, Turkish Navy HQ)

Abstract

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.

Suggested Citation

  • Orhan Karasakal, 2016. "Minisum and maximin aerial surveillance over disjoint rectangles," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 24(3), pages 705-724, October.
    • Handle: RePEc:spr:topjnl:v:24:y:2016:i:3:d:10.1007_s11750-016-0416-1
    DOI: 10.1007/s11750-016-0416-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11750-016-0416-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11750-016-0416-1?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Vansteenwegen, Pieter & Souffriau, Wouter & Oudheusden, Dirk Van, 2011. "The orienteering problem: A survey," European Journal of Operational Research, Elsevier, vol. 209(1), pages 1-10, February.
    2. K Y K Ng & N G F Sancho, 2009. "Regional surveillance of disjoint rectangles: a travelling salesman formulation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(2), pages 215-220, February.
    3. K Y K Ng & A Ghanmi, 2002. "An automated surface surveillance system," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(7), pages 697-708, July.
    4. Maria John & David Panton & Kevin White, 2001. "Mission Planning for Regional Surveillance," Annals of Operations Research, Springer, vol. 108(1), pages 157-173, November.
    5. Grob, Marcel J.H.B., 2006. "Routing of platforms in a maritime surface surveillance operation," European Journal of Operational Research, Elsevier, vol. 170(2), pages 613-628, April.
    6. David M. Panton & Anita W. Elbers, 1999. "Mission Planning for Synthetic Aperture Radar Surveillance," Interfaces, INFORMS, vol. 29(2), pages 73-88, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. K Y K Ng & N G F Sancho, 2009. "Regional surveillance of disjoint rectangles: a travelling salesman formulation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(2), pages 215-220, February.
    2. Dang, Duc-Cuong & Guibadj, Rym Nesrine & Moukrim, Aziz, 2013. "An effective PSO-inspired algorithm for the team orienteering problem," European Journal of Operational Research, Elsevier, vol. 229(2), pages 332-344.
    3. Ido Orenstein & Tal Raviv & Elad Sadan, 2019. "Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 683-711, December.
    4. Morteza Keshtkaran & Koorush Ziarati & Andrea Bettinelli & Daniele Vigo, 2016. "Enhanced exact solution methods for the Team Orienteering Problem," International Journal of Production Research, Taylor & Francis Journals, vol. 54(2), pages 591-601, January.
    5. Matteo Fischetti & Ivana Ljubić & Michele Monaci & Markus Sinnl, 2019. "Interdiction Games and Monotonicity, with Application to Knapsack Problems," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 390-410, April.
    6. Kobeaga, Gorka & Rojas-Delgado, Jairo & Merino, María & Lozano, Jose A., 2024. "A revisited branch-and-cut algorithm for large-scale orienteering problems," European Journal of Operational Research, Elsevier, vol. 313(1), pages 44-68.
    7. Stacy A. Voccia & Ann Melissa Campbell & Barrett W. Thomas, 2019. "The Same-Day Delivery Problem for Online Purchases," Service Science, INFORMS, vol. 53(1), pages 167-184, February.
    8. Racha El-Hajj & Rym Nesrine Guibadj & Aziz Moukrim & Mehdi Serairi, 2020. "A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit," Annals of Operations Research, Springer, vol. 291(1), pages 281-316, August.
    9. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    10. Dikas, G. & Minis, I., 2014. "Scheduled paratransit transport systems," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 18-34.
    11. Shu Zhang & Jeffrey W. Ohlmann & Barrett W. Thomas, 2018. "Dynamic Orienteering on a Network of Queues," Transportation Science, INFORMS, vol. 52(3), pages 691-706, June.
    12. Zhang, Shu & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2014. "A priori orienteering with time windows and stochastic wait times at customers," European Journal of Operational Research, Elsevier, vol. 239(1), pages 70-79.
    13. Dewil, R. & Vansteenwegen, P. & Cattrysse, D. & Van Oudheusden, D., 2015. "A minimum cost network flow model for the maximum covering and patrol routing problem," European Journal of Operational Research, Elsevier, vol. 247(1), pages 27-36.
    14. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    15. Shima Azizi & Özge Aygül & Brenton Faber & Sharon Johnson & Renata Konrad & Andrew C. Trapp, 2023. "Select, route and schedule: optimizing community paramedicine service delivery with mandatory visits and patient prioritization," Health Care Management Science, Springer, vol. 26(4), pages 719-746, December.
    16. Lin, Jun & Qian, Yanjun & Cui, Wentian & Goh, Thong Ngee, 2015. "An effective approach for scheduling coupled activities in development projects," European Journal of Operational Research, Elsevier, vol. 243(1), pages 97-108.
    17. Vansteenwegen, Pieter & Mateo, Manuel, 2014. "An iterated local search algorithm for the single-vehicle cyclic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 237(3), pages 802-813.
    18. Maria Fleischer Fauske & Carlo Mannino & Paolo Ventura, 2020. "Generalized Periodic Vehicle Routing and Maritime Surveillance," Transportation Science, INFORMS, vol. 54(1), pages 164-183, January.
    19. Yu, Bin & Shan, Wenxuan & Sheu, Jiuh-Biing & Diabat, Ali, 2022. "Branch-and-price for a combined order selection and distribution problem in online community group-buying of perishable products," Transportation Research Part B: Methodological, Elsevier, vol. 158(C), pages 341-373.
    20. Drexl, Michael, 2013. "A note on the separation of subtour elimination constraints in elementary shortest path problems," European Journal of Operational Research, Elsevier, vol. 229(3), pages 595-598.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:topjnl:v:24:y:2016:i:3:d:10.1007_s11750-016-0416-1. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.