Search and delivery man problems: when are depth-first paths optimal?

DOI10.1016/J.EJOR.2020.02.026MaRDI QIDQ2184055zbMATH OpenOpenAlexFDO

Authors Steve Alpern, Thomas Lidbetter

Publication date 27 May 2020

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.13178

zbMATH Keywords

delivery man problemdepth-first searchnetworkstrees

Mathematics Subject Classification ID

Search theory (90B40) Programming involving graphs or networks (90C35) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: 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.

Recommendations

• Depth-First Solutions for the Deliveryman Problem on Tree-Like Networks: An Evaluation Using a Permutation Model
• The delivery man problem on a tree network
• Probabilistic Sales-Delivery Man and Sales-Delivery Facility Location Problems on a Tree
• Sales‐delivery man problems on treelike networks
• Optimal search path for service in the presence of disruptions

Cites work

• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• A new approach to Gal's theory of search games on weakly Eulerian networks
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• A search problem on a bipartite network
• An improved approximation ratio for the minimum latency problem
• An Optimal Search Problem
• Approximation Schemes for Minimum Latency Problems
• Finding a hider by an unknown deadline
• Generalizations in the linear search problem
• Hide-and-seek games on a network, using combinatorial search paths
• scientific article; zbMATH DE number 2086925 (Why is no real title available?)
• Mining coal or finding terrorists: the expanding search paradigm
• More on the linear search problem
• Multiple searchers searching for a randomly distributed immobile target on a unit network
• Network search games with immobile hider, without a designated searcher starting point
• Network search games, with arbitrary searcher starting point
• On Submodular Search and Machine Scheduling
• On the linear search problem
• Search games
• Search games and other applications of game theory
• Search games on networks with travelling and search costs and with arbitrary searcher starting points
• Search games on trees with asymmetric travel times
• Search Games with Mobile and Immobile Hider
• Search games with multiple hidden objects
• Searching a variable speed network
• Searching symmetric networks with Utilitarian-Postman paths
• Star search -- a different show
• The delivery man problem on a tree network
• The minimum latency problem
• The Revenge of the Linear Search Problem
• The theory of search games and rendezvous.

Cited in

(1)

• Depth-First Solutions for the Deliveryman Problem on Tree-Like Networks: An Evaluation Using a Permutation Model

This page was built for publication: Search and delivery man problems: when are depth-first paths optimal?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2184055)