TY - JOUR
T1 - Search and Delivery Man Problems
T2 - When are depth-first paths optimal?
AU - Alpern, Steve
AU - Lidbetter, Thomas
N1 - Funding Information:
This material is based upon work supported by the National Science Foundation under Grant No. CMMI-1935826 .
Funding Information:
Steve Alpern acknowledges support from the AFIT Graduate School of Engineering and Management, FA8075-14-D-0025. This material is based upon work supported by the National Science Foundation under Grant No. CMMI-1935826.
Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2020/9/16
Y1 - 2020/9/16
N2 - 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.
AB - 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.
KW - Delivery Man Problem
KW - Depth-first search
KW - Networks
KW - Trees
UR - http://www.scopus.com/inward/record.url?scp=85081213232&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85081213232&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2020.02.026
DO - 10.1016/j.ejor.2020.02.026
M3 - Article
AN - SCOPUS:85081213232
VL - 285
SP - 965
EP - 976
JO - European Journal of Operational Research
JF - European Journal of Operational Research
SN - 0377-2217
IS - 3
ER -