Article ID: | iaor2006612 |
Country: | Germany |
Volume: | 11 |
Issue: | 5/6 |
Start Page Number: | 483 |
End Page Number: | 500 |
Publication Date: | Dec 2005 |
Journal: | Journal of Heuristics |
Authors: | Woodruff David L., Held Harald |
Keywords: | heuristics, networks |
We describe and compare heuristic solution methods for a multi-stage stochastic network interdiction problem. The problem is to maximize the probability of sufficient disruption of the flow of information or goods in a network whose characteristics are not certain. In this formulation, interdiction subject to a budget constraint is followed by operation of the network, which is then followed by a second interdiction subject to a second budget constraint. Computational results demonstrate and compare the effectiveness of heuristic algorithms. The problem is interesting in that computing an objective function value requires tremendous effort. We exhibit classes of instances in our computational experiments where local search based on a transformation neighborhood is dominated by a constructive neighborhood.