Robust prepositioning and allocation of maritime search and rescue vessels with incident location uncertainty

This paper presents a new robust optimization approach for prepositioning search and rescue (SAR) vessels to coastal marine stations and allocating maritime areas to them. The objective is to maximize the coverage of maritime incidents, considering operational constraints related to vessel capacities, volunteers’ participation and involvement, total travel distances, and the timeliness of rescue operations. To account for uncertainty in the spatial distribution of future incidents, two types of uncertainty sets are developed, and the location-allocation is optimized for the worst-case distribution within each set. The first one is based on the Total Variation (TV) ϕ-divergence, while the second one uses the 1-Wasserstein distance to measure the deviation between the nominal and the true distribution. Furthermore, a Benders decomposition (BD) algorithm is developed to solve the robust problems more efficiently. The proposed approaches are implemented to design a SAR network in the Gulf of Finland using historical incident data. Numerical results demonstrated the superior out-of-sample average and quartile performances of the robust models, despite their higher computational burdens, compared to the deterministic one, and that the ϕ-divergence uncertainty set led to less conservative solutions compared to the Wasserstein-metric-based set. Furthermore, the BD algorithm significantly reduced the computational time for middle-range values of the uncertainty budgets, enabling real-sized instances to be solved effectively. A detailed sensitivity analysis was performed, and managerial insights were drawn from the results. Most notably, both the total allowable travel distance and the response time threshold significantly affected incident coverage in busy days, with a more profound impact of the former factor, whereas only the latter moderately affected coverage in low-activity days. The paper contributes to the maritime SAR literature by demonstrating how the spatial uncertainty of future incidents can be handled rigorously rather than relying naively on historical incident patterns to design SAR networks.