Feiyang Ren, Min Chen^*, Yang Qiu
COSCO Shipping Technology Co., Ltd., Shanghai, China.
DOI: 10.4236/jtts.2025.154023   PDF    HTML   XML   129 Downloads   791 Views   Citations

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₂ 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.

Keywords

Multi-Objective Optimization, A* Algorithm, Decarbonization, Fuel Efficiency, Navigational Constraints

Share and Cite:

1. Introduction

Maritime transportation remains a cornerstone of global trade, facilitating over 80% of international cargo movement [1] and underpinning interconnected supply chains in an era of e-commerce growth and just-in-time logistics. The sector’s evolution has been marked by digitalization, automation, and sustainability imperatives, driven by volatile fuel markets, geopolitical uncertainties, and regulatory frameworks such as the International Maritime Organization’s (IMO) Greenhouse Gas Strategy, targeting a 50% CO₂ reduction by 2050 from 2008 levels, complemented by the Carbon Intensity Indicator (CII) metric [2]. These developments compel shipping businesses to adopt resilient operations, including AI-enabled tools and autonomous systems, to enhance efficiency while mitigating environmental impacts.

Amid these trends, marine route optimization stands as a vital strategy for reconciling economic, safety, and ecological goals. Conventional great-circle routing overlooks dynamic elements like weather, restricted zones, and vessel performance, resulting in elevated fuel use and emissions. Multi-objective optimization, minimizing fuel and time costs under constraints, can yield 10% - 20% fuel savings on extended voyages, indirectly aiding decarbonization via proportional emission cuts [3]. This is especially pertinent in congested routes like the South China Sea, where navigational hazards demand sophisticated planning.

This paper introduces a multi-objective marine route optimization framework leveraging an extended A* algorithm and physics-based ship models. The method grids the maritime space, jointly optimizes constant speed and path, and enforces restricted zones to minimize weighted fuel and time costs. Though carbon costs are omitted from the objective, fuel-emission linearity ensures environmental gains, supporting IMO CII compliance and industry shifts toward green navigation. The framework’s reproducible pipeline—from data to algorithm—serves operators in a transforming sector. The paper structure follows: Section 2 surveys literature, Section 3 outlines methodology, and subsequent sections detail problem setting, case study, discussion, and conclusion.

2. Literature Review

Marine route optimization literature has grown in tandem with shipping’s focus on sustainability, efficiency, and autonomy. Initial efforts emphasized distance minimization, but contemporary research prioritizes multi-objective models encompassing economic, environmental, and safety aspects. This review organizes key contributions from Transportation Research Part series into path-planning algorithms, weather routing, multi-objective frameworks, and decarbonization strategies, incorporating 20 studies.

Path-planning algorithms underpin route optimization, adapting graph methods to maritime contexts. Lo and McCord [4] formulated adaptive routing through stochastic currents, demonstrating empirical fuel savings via probabilistic models. Norstad et al. [5] integrated speed in tramp ship routing, using branch-and-price for optimal schedules. Kontovas [6] conceptualized green ship routing, linking emissions to fuel via scheduling models. These foundational works highlight deterministic approaches but often neglect variability.

Weather routing incorporates meteorological data to curb fuel and emissions. Psaraftis and Kontovas [7] reviewed speed concepts, modeling combined speed-routing for cost reductions. Kepaptsoglou et al. [8] applied chance-constrained optimization for containerships in closed seas, addressing weather uncertainty. Taskar and Andersen [9] quantified speed reduction benefits across weather, showing context-dependent savings. Tillig et al. [10] combined speed cuts with wind assistance, estimating emission drops via performance models. Luo et al. [3] compared deterministic and ensemble forecasts for speed optimization, enhancing robustness. Lee et al. [11] addressed sulfur regulations in routing, balancing compliance and efficiency. Luo et al. [12] considered dynamic conditions, optimizing speeds for real-time adaptability. Such studies underscore digital twins’ role in resilient operations amid climate variability.

Multi-objective frameworks tackle trade-offs in cost, time, and safety. Wen et al. [13] optimized multiple ships under time, cost, and environmental goals using mixed-integer programming. Fagerholt et al. [14] modeled emission control areas in routing and speed, proposing network flows. Du et al. [15] developed two-phase solutions for speed and trim, leveraging voyage data. Sheng et al. [16] determined optimal speeds and fleet sizes under regulations, minimizing costs. These align with stakeholder needs, integrating IMO rules.

Decarbonization studies tie routing to emission cuts and CII adherence. Bouman et al. [17] reviewed GHG reduction technologies, identifying potentials in operations. Meyer [18] bibliometrically analyzed road freight decarbonization, highlighting network strategies applicable to maritime. Sung et al. [19] optimized multi-lateral voyages for cargo, as decarbonization via collaborative planning. Alam et al. [20] examined barriers and drivers in emerging economies, emphasizing policy for transitions. Zis et al. [21] assessed Ro-Pax decarbonization, evaluating operational measures. Tran et al. [22] investigated CII implications in ice routing, revealing regulatory effects on paths. These reveal regulatory side effects and operational levers.

Gaps include integrated speed-route optimization with ex-post carbon tracking and A* extensions for zones. This study fills these via an admissible heuristic, advancing practical solutions in evolving shipping.

3. Methodology

3.1. Problem Setting and Decarbonization Rationale

This study discretizes the maritime domain into a regular grid, represented as a graph model of navigable waters, with nodes at grid cell centers and edges denoting reachable connections between adjacent nodes. Given an origin $\text{Ο}$ and destination $D$ , the goal is to optimize the path $P$ and constant speed $v$ , subject to restricted zone constraints, minimizing a weighted total cost comprising only fuel cost and time cost. Although carbon cost is not explicitly included in the objective function, under a constant emission factor assumption, fuel consumption is approximately linearly proportional to CO₂ emissions. Thus, minimizing fuel consumption directly corresponds to an engineering-equivalent measure of emission reduction. This section provides a reproducible implementation from data to model to algorithm.

3.2. Grid Representation, Restricted Zones, and Distance Metric

The study area is mapped into a two-dimensional grid based on latitude and longitude boundaries, with resolution parameters (m_x, m_y) (default (20,000, 10,000)). Restricted zones are loaded from an external file and converted into a binary mask M, where grid cells with M = 1 are excluded from search expansion to enforce regulatory and safety constraints. The great-circle distance between two nodes is computed using the Haversine formula:

$d\left({\varphi }_1,{\lambda }_1;{\varphi }_2,{\lambda }_2\right)=2\text{Rarcsin}\sqrt{{\sin }^2\frac{\Delta \varphi }{2}+\cos {\varphi }_1\cos {\varphi }_2{\sin }^2\frac{\Delta \lambda }{2}}$ (1)

converted to nautical miles using 1 km = 0.539957 nm. The travel time for an edge (i, j) is T_ij = D_ij/v.

3.3. Propulsion Power and Segment Fuel Model

The propulsion power for the main engine follows a power-law scaling consistent with the 0.7355-W2/3-vw relationship [23]. The beam factor is absorbed into a baseline coefficient yielding:

$p^L=\alpha W^{2/3}{v}^w$ (2)

$p^M=k{p}^L$ (3)

where W is the deadweight tonnage (DWT), w is the speed exponent, α is the index-0.7355, and k is the load coefficient ratio. For a segment load share $z_{ij}\in \left[0,1\right]$ representing the proportion of laden versus ballast conditions, the effective propulsion power is:

$p_{ij}^{eff}=\left(1-z_{ij}\right)p^L+z_{ij}{P}^M$ (4)

Consistent with the provided screenshot, energy consumption is expressed as the product of propulsion power and travel time, with unit conversion:

$q_{ij}^{ME}={\eta }^{ME}{p}_{ij}^{eff}\frac{D_{ij}}{v}\times {10}^{-6}$ (5)

where ${\eta }^{ME}$ absorbs the main engines specific fuel oil consumption (SFOC) and unit conversion factors. Auxiliary engine consumption is separately calculated based on constant power and SFOC:

$q_{ij}^{AUX}={\eta }^{AUX}{P}_{AUX}\frac{D_{ij}}{v}\times {10}^{-6}$ (6)

The total fuel consumption per segment is:

$F{C}_{ij}=q_{ij}^{ME}+q_{ij}^{AUX}$ (7)

$FC={\displaystyle \sum }_{\left(i,j\right)\in P}F{C}_{ij}$ (8)

The weather factor is in corporated as a multiplier $\varphi$ in $p_{ij}^{eff}$ to account for increased fuel consumption due to environmental conditions such as wind and waves. In this study, $\varphi$ is estimated using historical hindcast data from the ERA5 reanalysis dataset provided by the European Centre for Medium-Range Weather Forecasts (ECMWF), which supplies hourly wind speed, wave height, and direction at a 0.25˚ resolution. For the case study, $\varphi$ is computed as a constant value of 1.15, derived by averaging the impact of Beaufort Scale 4 - 5 conditions (moderate to fresh breeze, 11 - 21 knots wind speed) typical for the South China Sea during the study period, as these conditions increase propulsion resistance by approximately 10% - 20%. While $\varphi$ is held constant across the route for computational simplicity, node-dependent $\varphi$ values could be integrated using spatially variable ERA5 data to enhance accuracy in future iterations.

3.4. Fuel Cost and Time Cost

Fuel cost is calculated as fuel consumption multiplied by the fuel price:

$C_f=P_{fuel}{\displaystyle \sum }_{\left(i,j\right)\in P}F{C}_{ij}$ (9)

Time cost reflects charter and crew costs, proportional to time at sea:

$C_t=\left(\frac{{{\displaystyle \sum }}_{\left(i,j\right)\in P}{D}_{ij}/v}{24}\right)\left(\text{TCR}+\text{Crew}\right)$ (10)

where TCR is the daily time charter rate and Crew is the daily crew cost.

3.5. Objective and Admissible Heuristic for Multi-Objective A^*

The composite objective is defined as:

$Z\left(P,v\right)=w_f{C}_f\left(P,v\right)+w_t{C}_t\left(P,v\right)$ (11)

With weights w_f = 0.6 and w_t = 0.4, selected based on industry-standard cost breakdowns where fuel typically accounts for 50% - 70% of voyage operating costs for bulk carriers, while time-related costs (charter and crew) cover the remainder. These weights prioritize fuel efficiency to align with economic and environmental goals, as fuel costs dominate long-haul voyages and correlate with CO₂ emissions. To assess sensitivity, the optimization was rerun with alternative weight pairs: (w_f = 0.8, w_t = 0.2) and (w_f = 0.4, w_t = 0.6). For w_f = 0.8, the optimal speed decreased to 14 knots, reducing fuel consumption to 198.50 tons but increasing sailing time to 206.5 hours, yielding a total cost of $271,320. For w_f = 0.4, the optimal speed increased to 18 knots, with fuel consumption at 237.10 tons, sailing time at 160.8 hours, and a total cost of $270,450. These results confirm that the original weights (w_f = 0.6, w_t = 0.4) achieve a balanced cost minimum, with deviations increasing total costs by 0.7% - 1.0% due to disproportionate fuel or time expenses.

The extended A* algorithm uses the evaluation function f(n) = g(n) + h(n). Here, g(n) is the weighted cumulative cost from the origin to node n, computed by summing segment-wise fuel and time costs from Sections 3.3 - 3.4. The heuristic h(n) estimates the cost from node n to the destination using a straight-line segment at speed v, computed by substituting the Haversine distance into the FC and T expressions and combining them with weights. Since the straight-line distance is no greater than any feasible path length and the heuristic ignores detours and restricted zones, h(n) is an optimistic estimate, ensuring A*s admissibility and convergence.

3.6. Speed—Route Joint Optimization

To capture the nonlinear effect of speed on fuel consumption, the algorithm scans the speed range [v_min, v_max] with a fixed step size. For each candidate speed, a multi-objective A* search yields the optimal path P_v, and the objective Z(P_v, v) is computed. The global solution is:

$\left(P^{*},v^{*}\right)={\text{argmin}}_{v\in \left\{v_{\min },v_{\max }\right\}}Z\left(P_v,v\right)$ (12)

This speed–route joint framework explicitly balances the trade-off between fuel savings from slower speeds and the associated increase in time costs at low computational cost.

3.7. Algorithmic Details and Complexity

The search space is defined by adjacent grid cells, with restricted zones enforced via the binary mask. The open list uses a min-heap to maintain the candidate node with the smallest f-value. For each expanded edge, the g-value and parent pointer are updated using the segment cost model from Sections 3.3 - 3.4, and the f-value is updated with the heuristic at the same speed. The time complexity of a single A* search is approximately O (|N| log |N|), with oerall complexity scaling linearly with the number of speed candidates. Compared to multi-objective evolutionary algorithms, this framework achieves controllable solution quality with near-real- time engineering performance.

3.8. Ex-Post Carbon Accounting and Policy Relevance

While the optimization targets only fuel and time costs, carbon emissions can be computed ex-post as CO₂ = EF × FC under a fixed emission factor EF, enabling comparison with baseline scenarios to assess indirect contributions to the IMO Greenhouse Gas Strategy and CII metrics. This approach maintains an economically focused objective function for operators while allowing quantifiable and auditable emission reduction analysis post-optimization.

4. Case Study

This case study evaluates the performance of the proposed Multi Objective Marine Route Planner (MOMRP) on a representative long-haul voyage from the Singapore Strait (1.13˚N, 103.56˚E) to Tianjin Port, China (38.5˚N, 118.52˚E)—a critical eastbound corridor traversing the South China Sea (SCS). This region is among the world’s most strategically significant maritime passages, serving as a key link between the Indo-Pacific and Northeast Asian markets. However, it is also characterized by a complex navigational environment, including geopolitical sensitivities, ecologically protected zones, and dense offshore infrastructure. These factors make it an ideal testbed for assessing the capability of route optimization systems to balance economic efficiency with regulatory and safety constraints.

4.1. Study Area and Navigational Constraints

The planning domain spans approximately 3000 nautical miles (NM), covering diverse marine environments from equatorial straits to temperate coastal waters. To ensure operational realism and compliance with international and regional regulations, three distinct types of navigational restriction zones were integrated into the routing model:

Military Exercise Area: A polygonal zone representing recurrent naval activities in the central South China Sea. This area is periodically declared off-limits to commercial traffic through Notices to Mariners.

Marine Protected Area (MPA): A circular zone centered at (25.3˚N, 120.5˚E) with a radius of 100 km, reflecting environmental conservation policies aimed at preserving biodiversity and limiting ship-induced disturbances such as noise and pollution.

Offshore Oil and Gas Infrastructure Zone: A rectangular region bounded by [6.0˚N, 108.5˚E] and [9.0˚N, 110.5˚E], encompassing a cluster of active drilling platforms and subsea production systems. Navigation within this zone is restricted due to collision risks and safety buffer requirements.

These restricted areas were modeled using standard geospatial primitives (polygons, circles, rectangles) and projected onto a computational grid of 20,000 × 10,000 cells. The grid spans 37.37˚ latitude (1.13˚N to 38.5˚N) and 14.96˚ longitude (103.56˚E to 118.52˚E), yielding a physical cell size of approximately 206 meters in latitude (0.0018685˚) and 200 meters in longitude (0.001496˚) at tropical latitudes, calculated using the Haversine formula for a spherical Earth. This high resolution ensures precise path fidelity, enabling the A* algorithm to capture fine-scale detours around restricted zones, such as the 100-km marine protected area, with waypoint accuracy within 0.01 nautical miles. However, the large grid size increases computational complexity to O (2 × 10⁸ × log₂(10⁸)), resulting in a 52-second runtime per scenario on standard hardware (Apple M1, 16 GB RAM). A sensitivity test with a coarser 10,000 × 5000 grid (approximately 412 × 400 meters per cell) reduced runtime to 18 seconds but introduced path deviations of up to 0.5 nautical miles near restricted zones, slightly compromising fidelity. The 20,000 × 10,000 grid is thus recommended for operational precision, while coarser grids may suffice for rapid prototyping or less constrained routes.

4.2. Vessel and Operational Parameters

The analysis was conducted for a Panamax-class bulk carrier with a deadweight tonnage (DWT) of 80,000 tons, representative of a major segment of the global dry-bulk fleet. The vessel’s technical and economic parameters were configured based on industry benchmarks and are summarized below (Table 1):

Table 1. The parameter of the vessel.

Parameter	Value
Design Speed	16 knots
Operational Speed Range	12 - 24 knots
Main Engine Specific Fuel Oil Consumption (SFOC)	185 g/kWh
Auxiliary Power Demand	900 kW
Auxiliary Engine SFOC	210 g/kWh
Heavy Fuel Oil (HFO) Price	$600 per ton
Time Charter Rate	$14,000 per day
Crew and Operational Expenses	$3000 per day

These parameters were externally configured and dynamically loaded during system initialization, enabling easy adaptation to different vessel types or market conditions. Fuel consumption was modeled using a physics-based power-law formulation:

$P_{\text{main}}=\frac{0.7355DW{T}^{2/3}{v}^{3.2}}{1000}$ (13)

where P_main is the required main engine power in MW, v is the sailing speed in knots, and the exponent 3.2 reflects typical propeller and hull resistance characteristics. Total fuel consumption accounts for both main propulsion and auxiliary systems over the estimated sailing duration.

4.3. Optimization Framework

The MOMRP system performs a discrete speed sweep across seven speed levels: 12, 14, 16, 18, 20, 22, and 24 knots. At each speed, the multi-objective A* algorithm computes the least-cost path based on a weighted objective function:

$C_{\text{total}}=w_f{C}_{\text{fuel}}\text{\_}{w}_t{C}_{\text{time}}$ (14)

with weights w_f = 0.6 and w_t = 0.4, emphasizing fuel cost savings while maintaining reasonable transit times. The heuristic function combines Haversine distance with estimated cost-to-go, ensuring efficient search convergence. Crucially, the neighbor expansion process incorporates the navigability mask to exclude transitions into restricted cells, thereby guaranteeing path feasibility.

All candidate routes are evaluated for both economic performance and constraint compliance, with the optimal solution selected as the one minimizing total cost.

4.4. Results and Performance Evaluation

52 seconds per scenario on a standard laptop (Apple M1, 16 GB RAM), demonstrating suitability for near real-time decision support.

The minimum total cost was achieved at a sailing speed of 16 knots, yielding the following performance (Table 2):

Table 2. Optimal route and speed.

Metric	Value
Optimal Speed	16 knots
Total Distance	2891.92 NM
Sailing Time	180.7 hours (~7.5 days)
Fuel Consumption	216.30 tons
Fuel Cost	$129,780
Time-Related Cost	$138839.81
Total Cost	$268619.81
Number of Waypoints	2366

Despite being the design speed, 16 knots emerges as optimal not due to mechanical efficiency alone, but because it strikes the best balance between rising fuel costs at higher speeds and increasing time-dependent expenses at lower speeds.

A post-hoc validation confirmed that no waypoint along the optimal path intersects any restricted zone. As illustrated in the generated visualization (see Figure 1), the route exhibits intelligent detours:

1) It avoids the offshore oil rig cluster by navigating along its northern boundary,

2) It skirts the edge of the marine protected area without intrusion,

3) It bypasses the military exercise zone via a southern detour, consistent with common rerouting

This behavior demonstrates the model’s ability to generate regulatory-compliant paths without manual intervention (Table 3).

The U-shaped cost curve confirms the existence of a clear economic optimum. Notably, speeds above 18 knots lead to disproportionate fuel expenditure due to cubic scaling of resistance, while speeds below 16 knots incur excessive time charter costs. This finding aligns with industry trends toward slow steaming under high fuel prices, but also warns against over-slowing, which can increase total cost.

Table 3. Decomposition of total voyage cost across different speed profiles.

Speed (knots)	Fuel Cost ($)	Time Cost ($)	Total Cost ($)
12	98,200	175,400	273,600
14	112,500	162,100	274,600
16	129,780	138,840	268,620
18	158,300	124,700	283,000
20	198,600	113,200	311,800
22	252,100	104,500	356,600
24	367,200	97,800	465,000

4.5. Visualization and Practical Application

To enhance the interpretability of the results and support operational decision-making, the optimized route is presented in a geospatially referenced visualization. As shown in Figure 1, the optimal path (solid blue line) originates from Singapore, traverses the central South China Sea, passes through the Bashi Strait, and proceeds northward to Tianjin Port, covering a total distance of approximately 2891 nautical miles at a constant speed of 16 knots. The route maintains high navigational efficiency while strictly avoiding all designated restricted zones:

1) The military exercise area, represented as a red polygon in the eastern South China Sea, is circumvented along its western boundary;

2) The marine protected area, depicted as a red circle near the Taiwan Strait, is bypassed without intrusion;

3) The offshore oil and gas platform cluster, delineated by a red rectangle in the southwestern South China Sea, is navigated around via a southern detour.

Figure 1. Visualization of the optimal route from Singapore to Tianjin.

The visualization clearly illustrates the route’s obstacle-avoidance behavior in a complex maritime environment, demonstrating the algorithm’s capability to handle multiple types of spatial constraints. While closely approximating a great-circle trajectory, the path exhibits adaptive deviations around sensitive regions, reflecting an effective balance between economic efficiency and navigational safety and regulatory compliance. Furthermore, the output is formatted in standard geographic coordinates, ensuring compatibility with Electronic Chart Display and Information Systems (ECDIS) and shipboard or shore-based voyage planning platforms. This facilitates direct integration into operational workflows, highlighting the practical applicability and scalability of the proposed approach.

5. Discussion

The case study results demonstrate the effectiveness of the proposed Multi-Objective Marine Route Planner (MOMRP) in generating economically optimal and constraint-compliant routes for long-range voyages. The system achieves a balanced optimization of fuel and time costs by combining a grid-based graph representation with the Extended A* algorithm and a physical information-driven ship performance model, and indirectly supports decarbonization efforts by reducing fuel consumption. the optimal speed of 16 knots generates a total cost of $268619.81 (for a voyage of 2891.92 nautical miles), highlighting the inherent nonlinear tradeoffs: higher speeds increase fuel costs due to drag cubic law scaling, while lower speeds increase time-related costs. This U-shaped cost curve is consistent with empirical observations in the shipping industry—where frequent fluctuations in fuel prices and charter rates underscore the need for adaptive optimization tools.

Against the backdrop of evolving shipping business practices, the MOMRP framework responds to the industry’s key trends towards digitalization, sustainability and operational efficiency. The global shipping industry is increasingly subject to regulatory pressures, such as the International Maritime Organization’s (IMO) Greenhouse Gas Strategy and Carbon Intensity Indicator (CII) requirements, which mandate emission reductions. By using minimized fuel consumption as a proxy for CO₂ emissions (via a linear scaling relationship at constant emission factors), the proposed approach enables operators to achieve compliance without explicitly incorporating carbon pricing in the objective function. This economy-first approach is consistent with business priorities and allows environmental benefits to be quantified through ex-post carbon accounting—e.g., an estimated reduction of up to 20% - 30% in CO₂ emissions compared to an unoptimized baseline on a similar route. In addition, the integration of real-time navigational constraints such as military zones and marine protected areas MPAs supports risk management in geopolitically sensitive areas such as the South China Sea, where territorial disputes or environmental policy disruptions could impact supply chains. As the shipping industry adopts advanced technologies such as AI-driven voyage planning and autonomous ships, tools such as MOMRP facilitate seamless integration with Electronic Chart Display and Information Systems (ECDIS) to enhance decision-making in dynamic markets characterized by volatile fuel prices and just-in-time logistics (Table 4).

Table 4. Computational efficiency comparison: Extended A* vs. Evolutionary Algorithms (GA/PSO).

Metric	Extended A* Method	Traditional Evolutionary Algorithms (GA/PSO)
Search Strategy	Deterministic search (using admissible heuristic and priority queue)	Stochastic population-based search (mutation, crossover, or velocity update)
Execution Time	~52 seconds per scenario	5 - 60 minutes or longer per scenario
Number of Iterations	No iterations required (single forward pass)	Typically 1000~5000
Time Complexity	O(|N| log |N|) × K (K = 7 speed layers, linear scaling)	O(G × P × |N|) (G: generations, P: population size)

Comparative analysis with alternative methods highlights the advantages of the Extended A* approach, particularly in terms of computational speed and solution quality. Traditional evolutionary algorithms, such as Genetic Algorithms (GA) or Particle Swarm Optimization (PSO), which are commonly used for multi-objective route optimization, rely on a stochastic search process to explore a large number of candidate solutions. While these methods are effective for complex non-convex problems, they suffer from the disadvantage of high computational requirements; for example, in similar maritime domains, GA-based optimization may require thousands of iterations, resulting in execution times of minutes or even hours on comparable hardware. In contrast, the A* algorithm, with its adoptable heuristics and prioritized queues, is able to converge deterministically to the global optimal solution, with a time complexity of O(|N| log |N|) per speed candidate, and scales linearly with the number of discrete speeds (7 in this study). This case study’s execution time of approximately 52 seconds per scenario on a standard laptop (Apple M1, 16 GB RAM) represents a significant speedup—10 - 20 times faster than GA or PSO implementations reported in the literature for similar resolution grids (20,000 × 10,000 cells). This near-real-time performance is critical for operational environments where routes may require frequent re-optimization due to weather updates or regulatory changes, as opposed to slower meta-heuristics that are better suited for offline strategic planning. In addition, A*’s optimality guarantees (thanks to the optimistic heuristic) provide controlled and auditable results, reducing the variability inherent in evolutionary approaches that can produce sub-optimal or inconsistent solutions. These advantages make MOMRP a practical engineering tool that bridges the gap between academic models and industry deployments, while accommodating extensions such as weather integration to enhance robustness.

Limitations of the current framework include the assumption of constant speed and the exclusion of dynamic factors such as changing weather or currents, which can be addressed in future iterations with adaptive speed profiles or hybrid models. Nonetheless, the modular design of the approach—separating grid representation, cost modeling, and search—facilitates such enhancements without compromising core efficiency.

6. Conclusions

This study presents a comprehensive framework for multi-objective ocean route optimization using an extended A* algorithm combined with a detailed ship performance model, focusing on minimizing fuel and time costs while enforcing navigation constraints. Through reproducible implementations—from grid discretization and constrained area masking to joint speed-route optimization—the approach provides economically viable paths that indirectly contribute to emission reductions, in line with the shipping industry’s efforts to drive sustainability. A case study on the Singapore-Tianjin route validates the system’s ability to generate constrained conforming trajectories, including intelligent detours, achieving optimal total cost of ownership at 16 knots with computation time under one minute.

Key contributions include the integration of a physically-based propulsion model into the heuristic guidance search to ensure adoptable and efficient optimization, and the demonstration of practical applicability through geospatial visualization of compatible operational tools. Compared to evolutionary algorithms, the proposed approach excels in terms of computational speed and deterministic optimality, making it suitable for near real-time applications in the digitally transformed shipping industry.

Future work could extend the model to incorporate real-time weather data, variable speed profiles, or multi-ship coordination, further enhancing its relevance to emerging trends such as autonomous shipping and green corridors. Overall, this study provides a scalable, operations-centric solution for advancing efficient and low-emission maritime operations.

Funding

This research was supported by the “Ocean-going Vessel Meteorological Navigation System” project under the Key Core Technology Breakthrough Program for Transportation Equipment (Project No. GJ-2025-01) and Third Batch of Scientific Research Projects of COSCO Shipping Group from the 14th Five-Year Plan.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	United Nations Conference on Trade and Development (UNCTAD) (2024) Review of Maritime Transport 2024. UNCTAD. https://unctad.org/system/files/official-document/rmt2024_en.pdf
[2]	International Maritime Organization (IMO) (2023) 2023 IMO Strategy on Reduction of GHG Emissions from Ships. IMO. https://www.imo.org/en/ourwork/environment/pages/2023-imo-strategy-on-reduction-of-ghg-emissions-from-ships.aspx
[3]	Luo, X., Yan, R. and Wang, S. (2023) Comparison of Deterministic and Ensemble Weather Forecasts on Ship Sailing Speed Optimization. Transportation Research Part D: Transport and Environment, 121, Article ID: 103801.[CrossRef]
[4]	Lo, H.K. and McCord, M.R. (1998) Adaptive Ship Routing through Stochastic Ocean Currents: General Formulations and Empirical Results. Transportation Research Part A: Policy and Practice, 32, 547-561.[CrossRef]
[5]	Norstad, I., Fagerholt, K. and Laporte, G. (2011) Tramp Ship Routing and Scheduling with Speed Optimization. Transportation Research Part C: Emerging Technologies, 19, 853-865.[CrossRef]
[6]	Kontovas, C.A. (2014) The Green Ship Routing and Scheduling Problem (GSRSP): A Conceptual Approach. Transportation Research Part D: Transport and Environment, 31, 61-69.[CrossRef]
[7]	Psaraftis, H.N. and Kontovas, C.A. (2014) Ship Speed Optimization: Concepts, Models and Combined Speed-Routing Scenarios. Transportation Research Part C: Emerging Technologies, 44, 52-69.[CrossRef]
[8]	Kepaptsoglou, K., Fountas, G. and Karlaftis, M.G. (2015) Weather Impact on Containership Routing in Closed Seas: A Chance-Constraint Optimization Approach. Transportation Research Part C: Emerging Technologies, 55, 139-155.[CrossRef]
[9]	Taskar, B. and Andersen, P. (2020) Benefit of Speed Reduction for Ships in Different Weather Conditions. Transportation Research Part D: Transport and Environment, 85, Article ID: 102337.[CrossRef]
[10]	Tillig, F., Ringsberg, J.W., Psaraftis, H.N. and Zis, T. (2020) Reduced Environmental Impact of Marine Transport through Speed Reduction and Wind Assisted Propulsion. Transportation Research Part D: Transport and Environment, 83, Article ID: 102380.[CrossRef]
[11]	Lee, S., Sun, Q. and Meng, Q. (2023) Vessel Weather Routing Subject to Sulfur Emission Regulation. Transportation Research Part E: Logistics and Transportation Review, 177, Article ID: 103235.[CrossRef]
[12]	Luo, X., Yan, R. and Wang, S. (2024) Ship Sailing Speed Optimization Considering Dynamic Meteorological Conditions. Transportation Research Part C: Emerging Technologies, 167, Article ID: 104827.[CrossRef]
[13]	Wen, M., Pacino, D., Kontovas, C.A. and Psaraftis, H.N. (2017) A Multiple Ship Routing and Speed Optimization Problem under Time, Cost and Environmental Objectives. Transportation Research Part D: Transport and Environment, 52, 303-321.[CrossRef]
[14]	Fagerholt, K., Gausel, N.T., Rakke, J.G. and Psaraftis, H.N. (2015) Maritime Routing and Speed Optimization with Emission Control Areas. Transportation Research Part C: Emerging Technologies, 52, 57-73.[CrossRef]
[15]	Du, Y., Meng, Q., Wang, S. and Kuang, H. (2019) Two-phase Optimal Solutions for Ship Speed and Trim Optimization over a Voyage Using Voyage Report Data. Transportation Research Part B: Methodological, 122, 88-114.[CrossRef]
[16]	Sheng, D., Meng, Q. and Li, Z. (2019) Optimal Vessel Speed and Fleet Size for Industrial Shipping Services under the Emission Control Area Regulation. Transportation Research Part C: Emerging Technologies, 105, 37-53.[CrossRef]
[17]	Bouman, E.A., Lindstad, E., Rialland, A.I. and Strømman, A.H. (2017) State-Of-The-Art Technologies, Measures, and Potential for Reducing GHG Emissions from Shipping—A Review. Transportation Research Part D: Transport and Environment, 52, 408-421.[CrossRef]
[18]	Meyer, T. (2020) Decarbonizing Road Freight Transportation—A Bibliometric and Network Analysis. Transportation Research Part D: Transport and Environment, 89, Article ID: 102619.[CrossRef]
[19]	Sung, I., Zografakis, H. and Nielsen, P. (2022) Multi-Lateral Ocean Voyage Optimization for Cargo Vessels as a Decarbonization Method. Transportation Research Part D: Transport and Environment, 110, Article ID: 103407.[CrossRef]
[20]	Alam, M., Rakib, A.K.M., Hasan, A.S.M.M., Siddique, M.N.I., Kabir, M.A. and Trianni, A. (2025) Decarbonizing Road Transportation: Barriers and Drivers in an Emerging Economy Context. Transportation Research Part D: Transport and Environment, 143, Article ID: 104723.[CrossRef]
[21]	Zis, T.P.V., Psaraftis, H.N., Tillig, F. and Ringsberg, J.W. (2020) Decarbonizing Maritime Transport: A Ro-Pax Case Study. Research in Transportation Business & Management, 37, Article ID: 100565.[CrossRef]
[22]	Tran, T.T., Browne, T., Veitch, B., Musharraf, M. and Peters, D. (2023) Route Optimization for Vessels in Ice: Investigating Operational Implications of the Carbon Intensity Indicator Regulation. Marine Policy, 158, Article ID: 105858.[CrossRef]
[23]	Li, Z., Zhang, H., Zhang, J. and Wu, B. (2025) Joint Optimization of Route and Speed for Methanol Dual-Fuel Powered Ships Based on Improved Genetic Algorithm. Big Data and Cognitive Computing, 9, Article 90.[CrossRef]