Heuristics for the location of inspection stations on a network

This article considers the preventive flow interception problem (FIP) on a network. Given a directed network with known origin-destination path flows, each generating a certain amount of risk, the preventive FIP consists of o ptimally locating m facilities on the network in order to maximize the tota l risk reduction. A greedy search heuristic as well as several variants of an ascent search heuristic and of a tabu search heuristic are presented for the FIP. Computational results indicate that the best versions of the latt er heuristics consistently produce optimal or near optimal solutions on tes t problems. (C) 2000 John Wiley & Sons, Inc.