A branch and bound algorithm for sector allocation of a naval task group

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. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Bi‐objective missile rescheduling for a naval task group with dynamic disruptions

This paper considers the rescheduling of surface‐to‐air missiles (SAMs) for a naval task group (TG), where a set of SAMs have already been scheduled to intercept a set of anti‐ship missiles (ASMs). In missile defense, the initial engagement schedule is developed according to the initial state of the defensive and attacking units. However, unforeseen events may arise during the engagement, creating a dynamic environment to be handled, and making the initial schedule infeasible or inefficient. In this study, the initial engagement schedule of a TG is assumed to be disrupted by the occurrence of a destroyed ASM, the breakdown of a SAM system, or an incoming new target ASM. To produce an updated schedule, a new biobjective mathematical model is formulated that maximizes the no‐leaker probability value for the TG and minimizes the total deviation from the initial schedule. With the problem shown to be NP‐hard, some special cases are presented that can be solved in polynomial time. We solve small size problems by the augmented ? ‐ constraint method and propose heuristic procedures to generate a set of nondominated solutions for larger problems. The results are presented for different size problems and the total effectiveness of the model is evaluated.