A graph environment must be explored by a collection of mobile robots. Some of the robots, a priori unknown, may turn out to be unreliable. The graph is weighted and each node is assigned a deadline. The exploration is successful if each node of the graph is visited before its deadline by a reliable robot. The edge weight corresponds to the time needed by a robot to traverse the edge. Given the number of robots which may crash, is it possible to design an algorithm, which will always guarantee the exploration, independently of the choice of the subset of unreliable robots by the adversary? We find the optimal time, during which the graph may be explored. Our approach permits to find the maximal number of robots, which may turn out to be unreliable, and the graph is still guaranteed to be explored. We concentrate on line graphs and rings, for which we give positive results. We start with the case of the collections involving only reliable robots. We give algorithms finding optimal times needed for exploration when the robots are assigned to fixed initial positions as well as when such starting positions may be determined by the algorithm. We extend our consideration to the case when some number of robots may be unreliable. Our most surprising result is that solving the line exploration problem with robots at given positions, which may involve crash-faulty ones, is NP-hard. The same problem has polynomial solutions for a ring and for the case when the initial robots' positions on the line are arbitrary. The exploration problem is shown to be NP-hard for star graphs, even when the team consists of only two reliable robots.
The (Directed) Rural Postman Problem (DRPP) is a general case of the Chinese Postman Problem where a subset of the set of arcs of a given (directed) graph is 'required' to be traversed at minimum cost. @cite_3 presents a branch and bound algorithm for the exact solution of the DRPP based on bounds computed from Lagrangian Relaxation. @cite_4 studies the polyhedron associated with the Rural Postman Problem and characterizes its facial structure. @cite_2 gives a survey of the directed and undirected rural postman problem and also discusses applications.
@cite_4 @cite_3 @cite_2
2072370153 74564317 2126141749
Abstract In this paper we study the polyhedron associated with the Rural Postman Problem (RPP). Because the RPP is NP-hard, we cannot expect to find a complete description of the rural postman polyhedron of a general graph, but a partial knowledge of such a description frequently proves to be useful for both theoretical and computational purposes. We have tried to characterize the facial structure of this unbounded full-dimensional polyhedron. Sets of valid inequalities inducing facets have been studied as well as their use in a cutting-plane algorithm. The application of this algorithm to a set of RPP instances taken from the literature and two instances of larger size taken from a real world graph is described. All these instances were solved to optimality. The Directed Rural Postman Problem (DRPP) is a general case of the Chinese Postman Problem where a subset of the set of arcs of a given directed graph is ‘required’ to be traversed at minimum cost. If this subset does not form a weakly connected graph but forms a number of disconnected components the problem is NP-Complete, and is also a generalization of the asymmetric Travelling Salesman Problem. In this paper we present a branch and bound algorithm for the exact solution of the DRPP based on bounds computed from Lagrangean Relaxation (with shortest spanning arborescence sub-problems) and on the fathoming of some of the tree nodes by the solution of minimum cost flow problems. Computational results are given for graphs of up to 80 vertices, 179 arcs and 71 ‘required’ arcs. This is the second half of a two-part survey on arc routing problems. The first part appeared in the March-April 1995 issue of this journal. Here, the rural postman problem RPP is reviewed. The paper is organized as follows: applications, the undirected RPP, the directed RPP, the stacker crane problem, and the capacitated arc routing problem.