IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v74y2019i2d10.1007_s10589-019-00121-w.html
   My bibliography  Save this article

Minimizing the average searching time for an object within a graph

Author

Listed:
  • Ron Teller

    (Ben Gurion University of the Negev)

  • Moshe Zofi

    (Ben Gurion University of the Negev
    Sapir College)

  • Moshe Kaspi

    (Ben Gurion University of the Negev)

Abstract

This paper presents a new graph search problem for which a searcher wishes to find an object that may be found at a set of locations. The searcher doesn’t know the object’s exact location, but does know the a-prior probability of finding the object at each location. He wishes to build a searching path for reaching the object that starts from a given location and ends when reaching the object (or after searching the entire set with a false result). The objective is to find a searching path which will minimize the average searching time. We consider two scenarios for this problem: one when there is an unknown number of objects on the set and another when there is exactly one object on the set (the sum of probabilities is equal to 1). We show that this problem is NP-Hard, and supply a branch and bound algorithm for finding an optimal solution for large scale problems. We also study greedy approaches and other heuristics and compare the performance of these algorithms in various situations.

Suggested Citation

  • Ron Teller & Moshe Zofi & Moshe Kaspi, 2019. "Minimizing the average searching time for an object within a graph," Computational Optimization and Applications, Springer, vol. 74(2), pages 517-545, November.
    • Handle: RePEc:spr:coopap:v:74:y:2019:i:2:d:10.1007_s10589-019-00121-w
    DOI: 10.1007/s10589-019-00121-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-019-00121-w
    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/s10589-019-00121-w?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. Hiroyuki Sato & Johannes O. Royset, 2010. "Path optimization for the resource‐constrained searcher," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(5), pages 422-440, August.
    2. Lau, Haye & Huang, Shoudong & Dissanayake, Gamini, 2008. "Discounted MEAN bound for the optimal searcher path problem with non-uniform travel times," European Journal of Operational Research, Elsevier, vol. 190(2), pages 383-397, October.
    3. Scott Shorey Brown, 1980. "Optimal Search for a Moving Target in Discrete Time and Space," Operations Research, INFORMS, vol. 28(6), pages 1275-1289, December.
    4. Arun Jotshi & Rajan Batta, 2009. "Investigating the benefits of re-optimisation while searching for two immobile entities on a network," International Journal of Mathematics in Operational Research, Inderscience Enterprises Ltd, vol. 1(1/2), pages 37-75.
    5. Jotshi, Arun & Batta, Rajan, 2008. "Search for an immobile entity on a network," European Journal of Operational Research, Elsevier, vol. 191(2), pages 347-359, December.
    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. Johannes O. Royset & Hiroyuki Sato, 2010. "Route optimization for multiple searchers," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(8), pages 701-717, December.
    2. Galindo, Gina & Batta, Rajan, 2013. "Review of recent developments in OR/MS research in disaster operations management," European Journal of Operational Research, Elsevier, vol. 230(2), pages 201-211.
    3. Duvocelle, Benoit & Flesch, János & Staudigl, Mathias & Vermeulen, Dries, 2022. "A competitive search game with a moving target," European Journal of Operational Research, Elsevier, vol. 303(2), pages 945-957.
    4. Morin, Michael & Abi-Zeid, Irène & Quimper, Claude-Guy, 2023. "Ant colony optimization for path planning in search and rescue operations," European Journal of Operational Research, Elsevier, vol. 305(1), pages 53-63.
    5. Steve Alpern & Thomas Lidbetter, 2014. "Searching a Variable Speed Network," Mathematics of Operations Research, INFORMS, vol. 39(3), pages 697-711, August.
    6. Steven M. Shechter & Farhad Ghassemi & Yasin Gocgun & Martin L. Puterman, 2015. "Technical Note—Trading Off Quick versus Slow Actions in Optimal Search," Operations Research, INFORMS, vol. 63(2), pages 353-362, April.
    7. Steve Alpern & Thomas Lidbetter, 2013. "Mining Coal or Finding Terrorists: The Expanding Search Paradigm," Operations Research, INFORMS, vol. 61(2), pages 265-279, April.
    8. Joseph Kadane, 2015. "Optimal discrete search with technological choice," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 81(3), pages 317-336, June.
    9. J F J Vermeulen & M van den Brink, 2005. "The search for an alerted moving target," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(5), pages 514-525, May.
    10. Steve Alpern, 2011. "Find-and-Fetch Search on a Tree," Operations Research, INFORMS, vol. 59(5), pages 1258-1268, October.
    11. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    12. Calvin Kielas-Jensen & Venanzio Cichella & David Casbeer & Satyanarayana Gupta Manyam & Isaac Weintraub, 2021. "Persistent Monitoring by Multiple Unmanned Aerial Vehicles Using Bernstein Polynomials," Journal of Optimization Theory and Applications, Springer, vol. 191(2), pages 899-916, December.
    13. Kress, M. & Royset, J.O. & Rozen, N., 2012. "The eye and the fist: Optimizing search and interdiction," European Journal of Operational Research, Elsevier, vol. 220(2), pages 550-558.
    14. Jesse Pietz & Johannes O. Royset, 2013. "Generalized orienteering problem with resource dependent rewards," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(4), pages 294-312, June.
    15. Frédéric Dambreville & Jean‐Pierre Le Cadre, 2002. "Detection of a Markovian target with optimization of the search efforts under generalized linear constraints," Naval Research Logistics (NRL), John Wiley & Sons, vol. 49(2), pages 117-142, March.
    16. Hohzaki, Ryusuke & Iida, Koji, 2001. "Optimal ambushing search for a moving target," European Journal of Operational Research, Elsevier, vol. 133(1), pages 120-129, August.
    17. Hong, Sung-Pil & Cho, Sung-Jin & Park, Myoung-Ju, 2009. "A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search," European Journal of Operational Research, Elsevier, vol. 193(2), pages 351-364, March.
    18. Manon Raap & Silja Meyer-Nieberg & Stefan Pickl & Martin Zsifkovits, 2017. "Aerial Vehicle Search-Path Optimization: A Novel Method for Emergency Operations," Journal of Optimization Theory and Applications, Springer, vol. 172(3), pages 965-983, March.
    19. Baycik, N. Orkun & Sharkey, Thomas C. & Rainwater, Chase E., 2020. "A Markov Decision Process approach for balancing intelligence and interdiction operations in city-level drug trafficking enforcement," Socio-Economic Planning Sciences, Elsevier, vol. 69(C).
    20. Lawrence D. Stone & Alan R. Washburn, 1991. "Introduction special issue on search theory," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(4), pages 465-468, August.

    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:coopap:v:74:y:2019:i:2:d:10.1007_s10589-019-00121-w. 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.