Search and Delivery Man Problems: When are depth-first paths optimal?

Steve Alpern, Thomas Lidbetter

Research output: Contribution to journalArticlepeer-review


Let h be a probability measure on the nodes and arcs of a network Q, viewed either as the location of a hidden object to be found or as the continuous distribution of customers receiving packages. We wish to find a trajectory starting from a specified root, or depot O that minimizes the expected search or delivery time. We call such a trajectory optimal. When Q is a tree, we ask for which h there is an optimal trajectory that is depth-first, and we find sufficient conditions and in some cases necessary and sufficient conditions on h. A consequence of our analysis is a determination of the optimal depot location in the Delivery Man Problem, correcting an error in the literature. We concentrate mainly on the search problem, with the Delivery Man Problem arising as a special case.

Original languageEnglish (US)
Pages (from-to)965-976
Number of pages12
JournalEuropean Journal of Operational Research
Issue number3
StatePublished - Sep 16 2020

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


  • Delivery Man Problem
  • Depth-first search
  • Networks
  • Trees


Dive into the research topics of 'Search and Delivery Man Problems: When are depth-first paths optimal?'. Together they form a unique fingerprint.

Cite this