A Branch and Bound Algorithm for Sector Allocation of a Naval Task Group

Abstract

A naval task group (TG) is a collection of naval combatants and auxiliaries that are grouped together for the accomplishment of one or more missions. Ships forming a TG are located in predefined sectors. We define determination of ship sector locations to provide a robust air defense formation as the sector allocation problem (SAP). A robust formation is one that is very effective against a variety of attack scenarios but not necessarily the most effective against any scenario. We propose a 0-1 integer linear programming formulation for SAP. The model takes the size and the direction of threat into account as well as the defensive weapons of the naval TG. We develop tight lower and upper bounds by incorporating some valid inequalities and use a branch and bound algorithm to exactly solve SAP. We report computational results that demonstrate the effectiveness of the proposed solution approach. (C) 2011 Wiley Periodicals, Inc. Naval Research Logistics 58: 655-669, 2011