Multi-Objective Marine Route Optimization Based on Extended A * Algorithm and Ship Performance Models

Abstract

Maritime transportation is increasingly being subjected to pressure to balance economic efficiency with environmental sustainability under regulatory frameworks such as global trade demands and the International Maritime Organization (IMO) greenhouse gas (GHG) strategy. This study proposes a multi-objective ship route optimization framework that combines the Extended A* algorithm with a physically-based ship performance model to jointly optimize speeds and routes to minimize fuel and time costs while satisfying navigational constraints. The framework discretizes the ocean area into a high-resolution grid and introduces no-go zones through a binary mask, where the navigable area accounts for 65.5% of the entire area. The model uses a weighted cost function to jointly optimize constant speed and route. Taking an 80,000-ton Panamax bulk carrier from Singapore to Tianjin as an example, the model yields an optimal speed of 16 knots, a total cost of US $268619.81, a fuel consumption of 216.30 tons, and a sailing time of 180.7 hours, which is a cost reduction of 10.2% compared to the benchmark scenario of 24 knots (with a total cost of about US $465,000). Although not explicitly optimized for carbon cost, the linear relationship between fuel and emissions ensures a proportional reduction in CO 2 emissions, helping to meet Carbon Intensity Index (CII) requirements. The algorithm takes only 52 seconds per scenario on standard hardware, improving computational efficiency by a factor of 10 - 20 over evolutionary class algorithms and supporting near real-time decision making. The framework has good reproducibility and can be integrated with the Electronic Chart Display and Information System (ECDIS), making it suitable for digital and sustainable shipping operations.