Heuristics for Multi-Stage Interdiction of Stochastic Networks |
| |
Authors: | Harald Held David L Woodruff |
| |
Institution: | (1) Institute of Mathematics, University Duisburg-Essen, Duisburg, Germany, Italy;(2) Graduate School of Management, University of California, Davis, Davis, CA 95616, USA, Italy |
| |
Abstract: | 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. This 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. |
| |
Keywords: | stochastic programming network interdiction local search GRASP |
本文献已被 SpringerLink 等数据库收录! |
|