A heuristic algorithm for U.S. naval mission resource allocation

Abstract

Current military leadership is directing the U.S. Navy to engage in theater security cooperation activities or missions to bolster confidence and build trust relationships with other national military forces. Using ships efficiently by maximizing the value of missions accomplished in any time period is important because these missions affect world security, as well as our own national security. Recent research has developed a mixed-integer programming optimization model called Central-West Africa Resource and Mission Allocation (CARMA) that seeks to efficiently route a single naval vessel embarked with expeditionary partnership teams conducting theater security cooperation missions, to maximize the total mission value. The two current algorithms for solving CARMA require commercial software to solve the associated optimization models. This thesis develops a custom-built, license-free heuristic algorithm that provides decent solutions to CARMA in a fraction of the time of these algorithms. The developed heuristic uses limited enumeration to generate feasible routes and mission schedules for the ship. In the scenarios tested, the solution produced by the heuristic is not only generated in a fraction of the time of the current algorithms, but the total mission value collected is within 5% - 7% of those solution values.