Dynamic Underway Replenishment Route Optimization for Naval Formations Considering Formation Stability

To enhance fleet replenishment efficiency and ensure navigational safety, this paper investigates the Underway Replenishment Routing Problem (URRP), focusing on the dynamic characteristics of receiving ships. Mathematical models for replenishment ship travel time and formation vessel speed adjustment are formulated, explicitly considering navigational state transitions and formation stability (risk control). Consequently, a dynamic route optimization model is constructed to provide intelligent decision support for fleet commanders. An intelligent optimization algorithm, the Hybrid Genetic Algorithm with Adaptive Variable Neighborhood Search (HGA-AVNS), is proposed to solve this model. Computational results demonstrate that the proposed approach outperforms the traditional empirical replenishment strategy, validating its effectiveness in enhancing maritime safety and operational efficiency. Extensive sensitivity analyses further reveal that under the strict premise of maintaining formation stability, appropriately reducing the cruise speed can offset the increase in overall speed over ground (SOG) induced by following ocean currents, thereby preventing systematic time loss. Additionally, fine-tuning the execution timing of sudden tactical turning based on the replenishment ship’s real-time operational status can further maximize overall replenishment efficiency without compromising navigational safety.