Planning the optimal transit for a ship through a mapped minefield

Abstract

This thesis develops (a) a mission-planning tool for a Navy Mine Counter Measure (MCM) force to find a minimum-risk route for a surface ship through a mapped minefield, and (b) a heuristic to identify a sequence of mines whose clearance (removal and/or deactivation) leads to a rapid reduction of the risk of a minimum-risk path. All modeling concepts reflect the requirements of the Republic of China Navy's MCM operations. The problem is formulated and solved as a shortest-path problem in a network. A grid of nodes, representing waypoints, is embedded in a representation of the operating area, while arcs are created to link waypoints. The risk function is defined in terms of the closest point of approach distance between each mine that falls within a maximum danger radius along a route. A complete planning tool is implemented using Excel and Visual Basic for Applications. A basic test scenario describes an operational area of 1,000 by 3,000 yards containing 30 mines; node spacing is 100 yards. The minimum-risk path is found in few seconds on a laptop computer, while a greedy "mine clearance list" is found in a few minutes.