A mixed integer programming framework for sonar placement to mitigate maritime security risk

An optimization model is proposed to keep ports and waterways under surveillance against threats from divers, torpedoes or explosives mounted on the hull of vessels. A sonar sensor is utilized for under water detection. The proposed model addresses two key concepts of sensor placement which are mostly ignored in the literature. These features are “multiple coverage” meaning that the detection probability in a section increases as the number of sensors covering that section increases and “range-dependant detection probability” implying that the detection probability decreases as the distance from a sensor increases. The proposed mathematical model is a mixed integer linear programming model. A greedy heuristic approach reaches near-optimal solutions for large scale scenarios. Numerical results are provided to show the accuracy and speed of the heuristic algorithm. It turns out that the algorithm performs reasonably well when the sonars are scarce in the region of interest. This is an advantage for using the heuristic method in real world scenarios, as the density of sonars is low in these scenarios due to the budget limitations.