Optimal search path for service in the presence of disruptions

摘要

We consider the following basic search path problem: a customer residing at a node of a network needs to obtain service from one of the facilities; facility locations are known and fixed. Facilities may become inoperational with certain probability; the state of the facility only becomes known when the facility is visited. Customer travel stops when the first operational facility is found. The objective is to minimize the expected total travel distance. We show that this problem is NP-hard and develop a forward dynamic programming procedure. The efficiency of this procedure is improved by utilizing the special structure of the network and features of the optimal search paths. Polynomial procedures are developed for path and cycle networks. Through a set of computational experiments we show that the "visit closest unvisited facility" heuristic is quite efficient, especially when the failure probability is small. Our results substantiate optimal location models that rely on the behavioral assumptions of this heuristic.