Assessment of a Heuristic Algorithm for Scheduling Theater Security Cooperation Naval Missions

摘要

Theater Security Cooperation (TSC) is a U.S. strategy for improving multi-national relationships through cooperative efforts. Spitz develops the Central-West Africa Resource and Mission Allocation (CARMA) optimization model, which posits a naval vessel carrying various expeditionary partnership teams to transit an area of responsibility and conduct missions garnering the maximum amount of TSC value. CARMA can be solved with formal, mixed-integer optimization, at the expense of computational time. This thesis modifies the original Spitz's scenarios to test H-CARMA, a fast heuristic algorithm developed by Dwyer, and its performance under shorter planning horizons, multiple budget constraints and different distribution of missions and TSC value across countries. Most of the scenarios evidence shortcomings of H-CARMA that were not apparent in the earlier scenarios tested by Dwyer. In all but one of the reviewed cases, H-CARMA generates solutions with total TSC value less than 81% of those using Spitz's algorithms, and, in the worst of these cases, the solution only achieves 51 percent. When there is no slack in terms of time and budget, MIP solutions outperform those of H-CARMA by more than 25% in most cases examined. We identify sources for some of these deficiencies and recommend changes to address them.