Heuristic Route Generation for the Navy Mission Planner (Defense)

Navy Mission Planner is a decision support tool for operational planning at the theater level. It takes as input a scenario defined by a list of ships and their (multi-mission) capabilities, a list of missions to be accomplished, their values to a commander, and their locations, and a fixed time horizon, and it produces as output an employment schedule consisting of a route plan and a set of missions to accomplish for each ship on each day in the scenario. It attempts to maximize the total value of missions covered in the scenario by utilizing each ship to the best of its capabilities, while balancing the geographic distribution of missions, the limited capability of the ships, and the limited time horizon. Prior versions used a limited enumeration routine to generate a manageable number of routes for each ship. We develop a heuristic route generator that reduces the runtime and provides better starting routes, improving the overall quality of solutions obtained by Navy Mission Planner.