Integrated Routing and Scheduling Problem for the Airborne Deployment of Heterogeneous Multistatic Sonar Networks

ABSTRACT In this paper, we study the routing problem of an airborne carrier deploying a heterogeneous Multistatic Sonar Network (hMSN) for Anti‐Submarine Warfare (ASW). An hMSN combines monostatic (co‐located source and receiver) and bistatic (separate source and receiver) sonar systems from different buoy pairings. In fine , the goal is to determine the optimum deployment sequence for these limited‐life buoys, air‐dropped by the carrier. That is, we seek the deployment that achieves the optimum average insonification rate over a pre‐determined mission duration, which could be several consecutive hours of on‐site flying. This average coverage is calculated via hMSN snapshots taken at regular time steps, hence the scheduling aspect corresponding to the buoys actually active at time , that is, previously deployed and not yet terminated. This new problem in the literature is addressed through a two‐phase approach with (i) the spatial (static) optimization of the hMSN and (ii) the temporal (dynamic) optimization of the hMSN deployment sequence. In this way, the solution obtained as output for the coverage problem (i) is used as input data for the routing‐scheduling problem (ii). To solve it, we propose an exact method by means of a Mixed‐Integer Linear Program (MILP) and an approximate method by means of an ad‐hoc constructive heuristic. The results show that it is possible to use these methods to efficiently find a deployment sequence of these networks of operational dimensions with a discretization as fine as a minute, and for missions lasting up to 8 h.