Article ID: | iaor20042168 |
Country: | Netherlands |
Volume: | 9 |
Issue: | 2 |
Start Page Number: | 145 |
End Page Number: | 169 |
Publication Date: | Mar 2003 |
Journal: | Journal of Heuristics |
Authors: | Potvin Jean-Yves, Gendreau Michel, Sguin Ren, Guertin Franois, Blodgett Dale E. |
Keywords: | tabu search |
Effective utilization of scarce resources, in particular weapon resources, is a prominent issue in naval anti-air warfare. In this paper, defence plans are constructed to guide the allocation and scheduling of different types of defence weapons against anti-ship missiles, subject to various physical and operational constraints. To reduce the frequency of replanning, decision trees are considered to explicitly account, in a probabilistic manner, for all possible outcomes of a particular action. A construction heuristic is first developed to generate an initial tree. A tabu search heuristic then improves this tree through the removal or addition of defence actions, followed by update operations aimed at maintaining the consistency. Numerical results obtained on scenarios with an increasing number of threats show that substantial improvements, in terms of survivability of the ship, can be obtained in reasonable computation times using tabu search.