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.

To address the joint optimization problem of heavy-lift cargo stowage and speed decisions during transportation by semi-submersible ships, a joint optimization model of voyage and speed is established for semi-submersible ships. In this model, the initial metacentric height (GM) after free-surface correction is taken as the core safety constraint. Factors such as cargo mass, loading and unloading time windows, ship deadweight, and speed range are comprehensively considered. The objective function is set to minimize total transportation cost. A two-stage method is used to solve the model. Case study results show that the optimized total cost is 20.7% lower than that of the cargo allocation and speed scheme formulated based on manual experience. Fuel cost is reduced by 29.5%. Charter cost and port cost are reduced by 3.1% and 14.3%, respectively. The sensitivity analysis results for the minimum limit of GM and the fuel oil price show that improving the safety standard reduces the compliance of small vessels for heavy-lift cargo. This causes the tight capacity of large vessels. It may even make some cargo transportation demand difficult to satisfy. A rise in the fuel oil price significantly increases the fuel cost and reduces the enterprise profitability. Appropriately reducing speed is an effective strategy to mitigate the effect of the fuel oil price.