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

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2000-03, Vol.12 (2), p.136-149
Main Authors: Rosenkrantz, Daniel J, Tayi, Giri K, Ravi, S. S
Format: Article
Language:English
Subjects:
Algorithms
Computer networks
dynamic programming
Inspections
networks
path problems
polynomial algorithms
Railroad accidents & safety
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.12.2.136.11895