Premium
Heuristics for the location of inspection stations on a network
Author(s) -
Gendreau Michel,
Laporte Gilbert,
Parent Isabelle
Publication year - 2000
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(200006)47:4<287::aid-nav2>3.0.co;2-r
Subject(s) - heuristics , tabu search , heuristic , computer science , mathematical optimization , path (computing) , flow network , greedy algorithm , reduction (mathematics) , operations research , artificial intelligence , mathematics , algorithm , computer network , geometry
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 optimally locating m facilities on the network in order to maximize the total 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 latter heuristics consistently produce optimal or near optimal solutions on test problems. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 287–303, 2000