Algorithms for Path-Based Placement of Inspection Stations on Networks

Placement of inspection stations is a common task in transportation and communication networks. In this paper, two categories of problems involving placement of inspection stations are studied. The first category deals with the selection of inspection stations along a given path from an origin to a destination. The second considers simultaneous selection of both a path and inspection stations along that path. We formulate these problems under a variety of minimization objectives such as the maximum gap between two consecutive inspection stations, the expected penalty cost of failure along the path, and the total inspection cost. Our results include efficient algorithms for many formulations and complexity results as well as fully polynomial approximation schemes for other formulations. When considering cost objectives, we identify a core problem and show that the complexity of many formulations is directly related to the complexity of the core problem.