Optimal search path for service in the presence of disruptions

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.