Search and Delivery Man Problems: When are depth-first paths optimal?
Search and Delivery Man Problems: When are depth-first paths optimal?
复制标题
搜索和送货员问题：深度优先路径何时是最佳的？
DOI：
10.1016/j.ejor.2020.02.026
复制
发表时间：
2020
影响因子：
6.4
通讯作者：
Lidbetter, Thomas
中科院分区：
文献类型：
--
作者：
Alpern, Steve;Lidbetter, Thomas
假设是网络节点和弧线上的概率度量Q，被视为要找到的隐藏对象的位置，或被视为接收包裹的客户的连续分布。我们希望找到从指定根开始的轨迹，或使预期搜索或交付时间最小化的轨迹。我们称这样的轨迹为最佳轨迹。当Q是一棵树时，我们问哪条最优轨道是深度优先的，我们找到了充分条件，在某些情况下还找到了充分条件和充分条件。我们分析的结果是确定了送货员问题中的最佳仓库位置，纠正了文献中的一个错误。我们主要集中在搜索问题上，送货员问题是一个特例。
Lethbe a probability measure on the nodes and arcs of a networkQ, 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 depotOthat minimizes the expected search or delivery time. We call such a trajectory optimal. WhenQis a tree, we ask for whichhthere is an optimal trajectory that is depth-first, and we find sufficient conditions and in some cases necessary and sufficient conditions onh. 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.
登录
查看更多内容
非对称旅行商问题的常因子逼近算法
DOI：
10.1145/3188745.3188824
发表时间：
2018
期刊：
--
影响因子：
--
作者：
Svensson O
通讯作者：
Svensson O
搜索具有不对称旅行时间的树上的游戏
DOI：
10.1137/090781115
发表时间：
2010
期刊：
SIAM J. Control. Optim.
影响因子：
--
作者：
S. Alpern
通讯作者：
S. Alpern
带有固定隐藏器的网络搜索游戏，没有指定的搜索者起点
影响因子：
0.6
作者：
S. Alpern;V. Baston;S. Gal
通讯作者：
S. Gal
关于最优搜索问题
DOI：
10.1137/1007106
发表时间：
1965
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
W. Franck
通讯作者：
W. Franck
DOI：
10.1287/moor.2018.0978
发表时间：
2016-07
期刊：
Math. Oper. Res.
影响因子：
--
作者：
R. Fokkink;T. Lidbetter;L. V'egh
通讯作者：
R. Fokkink;T. Lidbetter;L. V'egh