Optimal routing of coordinated aircraft to identify moving surface contacts

Abstract

A warship at sea requires awareness of the ships in its vicinity in order to operate safely. This can be a daunting task, even when equipped with multiple shipboard systems. If naval air assets are available, a Tactical Action Officer (TAO) directs them to gain additional information about as many surface Contacts of Interest (COI) as possible. These air asset routes can be inefficient because there are no shipboard systems to aid with route planning. Additional complications include COIs moving during a route and some COIs being more important to visit than others. This thesis formulates and implements two Optimal Routing of Coordinated Aircraft (ORCA) Integer Linear Programs (ILP) to plan air asset routes that visit as many prioritized COIs as possible in a fixed time horizon. We report computation results planning for up to four air assets and up to 80 COIs. Solution time for both ILPs is less than half an hour for typically encountered routing scenarios with less than 40 COIs. For 80 COIs, we find solutions in less than two minutes to visit 61 COIs, or up to 77 if we can wait two hours to obtain the solution.