Route Optimization Engines

Two complementary graph-search algorithms for weather-aware maritime route optimization with configurable safety–fuel trade-off

Abstract

WindMar provides two independent route optimization engines that attack the weather routing problem from different angles. The A* engine operates on a 0.5° spatial grid with eight-connected adjacency and uses the classical A* algorithm with an admissible fuel-based heuristic to find the minimum-cost path. It excels at short-to-medium routes where fine-grained coastal navigation and high spatial resolution matter. The VISIR-style engine, inspired by the VISIR model (Mannarini et al., 2016), builds a time-expanded graph on a coarser 1° grid with 3-hour discrete time steps. This allows it to account for weather evolution over the voyage duration — a vessel that departs during a storm may find calmer conditions 12 hours later. The VISIR engine also implements voluntary speed reduction (VSR), automatically evaluating multiple candidate speeds per edge and selecting the cheapest safe option. Both engines share a configurable safety weight parameter that continuously interpolates between pure fuel minimization and full weather avoidance, enabling the Pareto analysis mode to reveal the cost of safety.

1. Introduction

Weather routing aims to find the vessel trajectory that optimizes a given objective — typically fuel consumption or voyage time — subject to environmental forcing and safety constraints. The problem is computationally challenging because the cost of traversing an ocean segment depends on wind, waves, and currents that vary in both space and time. A route that is optimal at departure may become suboptimal as weather systems evolve.

Two broad families of algorithms dominate the literature: isochrone methods, which propagate equal-time wavefronts from the departure point (Hagiwara, 1989; Mannarini et al., 2016), and graph search methods, which discretize the ocean into a weighted graph and apply shortest-path algorithms like Dijkstra or A* (Vettor & Guedes Soares, 2016; Szlapczynska, 2015). WindMar implements one engine from each family:

• A* Search — a pure spatial graph search that queries weather at the estimated arrival time of each edge. Best for routes where weather does not change drastically during transit.
• VISIR-style Dijkstra — a time-expanded graph search where each node carries a time coordinate. Weather is sampled at the node’s actual time, capturing the evolution of conditions across the voyage.

Running both engines on the same voyage produces two independent solutions. The user can compare the routes to understand trade-offs and build confidence in the result. When the engines agree, the solution is likely robust; when they disagree, the differences highlight sensitivities to grid resolution, weather timing, or coastal constraints.

2. A* Engine — Graph Construction

The A* engine discretizes the ocean surface into a regular latitude–longitude grid at a configurable resolution (default 0.5°, approximately 30 nautical miles at the equator). The grid is bounded by a configurable margin around the great-circle path between origin and destination, keeping the search space manageable.

Land cells are excluded using a high-resolution global land mask. Each edge between adjacent ocean cells is additionally checked for land crossings via ray–casting, ensuring that routes do not cut across peninsulas or narrow isthmuses. The fine 0.5° resolution allows the A* engine to navigate through straits and along coastlines where the coarser VISIR grid cannot.

3. A* Engine — Cost Function

The cost of traversing an edge from cell \(i\) to cell \(j\) is computed by the full hydrodynamic vessel model, incorporating calm-water resistance, wind resistance, wave-added resistance, and the effect of ocean currents on speed over ground. The result is the actual fuel consumption in metric tonnes for the leg at the given speed and weather conditions.

To prevent the optimizer from exploiting slow-steaming (reducing speed to save fuel per mile at the cost of excessive voyage time), a time-value penalty \(\lambda_t\) is added. This penalty is calibrated as the fuel consumed by one hour of steaming at the user’s calm-water speed:

where:

• \(\text{fuel}(i,j)\) is the fuel consumption for the leg (mt)
• \(\phi_{\text{safety}}\) is the dampened safety penalty (see Section 8)
• \(\phi_{\text{zone}}\) is the regulatory zone penalty
• \(\lambda_t\) is the time-value penalty (mt/hour)
• \(t(i,j)\) is the transit time for the leg (hours)

When the optimization target is time rather than fuel, the cost simplifies to \(C(i \to j) = t(i,j) \cdot \phi_{\text{safety}} \cdot \phi_{\text{zone}}\).

3.1 Variable-Speed Optimization

After A* finds the minimum-cost path at the user’s calm-water speed, a post-processing step re-evaluates each leg at multiple candidate speeds (8–18 kts in 0.5-knot increments) to find the per-leg optimal speed. The function _find_optimal_speed selects the speed that minimizes the combined fuel + time-value cost for each leg, incorporating the safety weight penalty. This captures situations where a headwind makes it cheaper to slow down on one leg while a following current makes it efficient to speed up on another.

4. A* Search Algorithm

A* is a best-first graph search that uses an admissible heuristic \(h(n)\) to guide exploration toward the goal. The heuristic must never overestimate the true cost to reach the destination. WindMar’s heuristic is based on the great-circle distance to the destination, the maximum attainable speed, and a conservative fuel rate:

where \(d_{\text{gc}}\) is the great-circle distance in nautical miles and the minimization finds the speed with the lowest cost-per-mile in calm conditions. This is admissible because weather can only increase cost, never decrease it below the calm-water optimum.

The algorithm maintains a priority queue ordered by \(f(n) = g(n) + h(n)\), where \(g(n)\) is the cost from origin to node \(n\). At each step, the node with the lowest \(f\)-score is expanded, and its 8 neighbours are evaluated via the cost function. The search terminates when the destination cell is popped from the queue, guaranteeing optimality.

For typical Mediterranean routes, the heuristic prunes 60–80% of the grid, reducing solve times to 0.5–2 seconds.

5. Route Smoothing

The raw A* path follows the discrete grid, producing staircase-like waypoints at 0.5° intervals. Post-processing applies Douglas–Peucker simplification (Douglas & Peucker, 1973) to reduce waypoint density while preserving the route’s shape. Each candidate simplification is checked for land crossings — if the straight-line shortcut crosses land, the original waypoints are retained.

After smoothing, the route typically has 10–30 waypoints instead of 50–200 grid cells, making it practical for navigation and display. The final statistics (fuel, time, distance) are recomputed along the smoothed path to ensure accuracy.

6. VISIR Engine — Time-Expanded Graph

The VISIR-style engine extends the spatial grid with a time dimension, creating a 3-D graph where each node is identified by the tuple \((\text{row},\, \text{col},\, \text{time\_step})\). This allows the algorithm to query weather conditions at the actual time the vessel would arrive at each cell, rather than assuming static weather as a spatial-only grid does.

The time-expanded structure means that two nodes at the same spatial location but different time steps are distinct. A vessel arriving at cell (5, 10) at hour 6 encounters different weather than one arriving at hour 12. This is the key advantage of the VISIR approach for long ocean crossings where weather systems move and evolve during transit.

7. VISIR Engine — Dijkstra Search

Despite using Dijkstra’s algorithm as its foundation, the VISIR engine incorporates an admissible heuristic (A*-guided Dijkstra) to focus exploration toward the destination. The heuristic is the same great-circle-based minimum cost-per-mile estimate used by the A* engine:

The heuristic is computed once per spatial cell and cached, since it depends only on distance to the destination and calm-water fuel rates. This dramatically reduces the number of nodes explored compared to pure Dijkstra, especially on long routes.

7.1 Isochrone Expansion

The search proceeds in an isochrone-like fashion: when a node at time step \(k\) is expanded, each spatial neighbour is evaluated at multiple candidate speeds. The travel time determines the time step of the resulting neighbour node:

where \(\Delta t\) is the temporal resolution (default 3 hours). This maps continuous travel times onto the discrete time grid while ensuring monotone progress through time. The algorithm naturally handles the coupling between speed choice and weather exposure: a slower speed means the vessel arrives later, potentially encountering different (better or worse) conditions.

7.2 Time-Value Penalty

Both engines use the same time-value penalty \(\lambda_t\) to prevent the optimizer from gaming voyage time. Each extra hour of transit is penalized by the fuel that would be consumed during one hour at the user’s calm-water speed. This anchors the optimizer’s time preferences to a physically meaningful scale and produces routes whose total voyage time remains within a reasonable margin (typically 15–30%) of the direct great-circle transit.

7.3 Voluntary Speed Reduction

A distinguishing feature of the VISIR engine is voluntary speed reduction (VSR). At each edge, the algorithm evaluates 3 candidate speeds linearly spaced between 10 kts and the vessel’s service speed (+2 kts margin). For each candidate speed, the safety constraints are checked:

• If the safety factor is \(\infty\) (dangerous conditions), that speed is skipped — a hard constraint that applies regardless of optimization settings.
• If all candidate speeds are unsafe, the entire edge is blocked, forcing the route to detour around the hazardous area.
• Otherwise, the cheapest safe (speed, cost) pair is selected, potentially choosing a lower speed to stay within safety limits.

VSR faithfully models real-world slow-steaming in bad weather. A ship master facing heavy head seas will reduce speed to limit slamming and parametric roll. The VISIR engine captures this decision automatically during the graph search.

8. Shared Components — Vessel Model

Both engines use the same VesselModel instance to compute fuel consumption for each leg. The model implements the full propulsion chain described in the Hydrodynamics & RAO article:

• Calm-water resistance — Holtrop–Mennen regression
• Wind resistance — Fujiwara wind loading model
• Wave-added resistance — STAWAVE-2 method (ITTC, 2014)
• Current effects — Speed over ground adjustment
• SFOC curve — Engine-specific fuel consumption

The vessel model is configured once with ship particulars (length, beam, draft, displacement, block coefficient) and the loading condition (laden or ballast). Each cost function call queries the model with speed, weather, and distance, receiving back the fuel consumption in metric tonnes.

9. Shared Components — Safety Assessment

The seakeeping safety model evaluates each leg for six operational criteria:

Each criterion returns a multiplicative safety factor. Below the threshold, the factor is 1.0 (no penalty). Above the threshold, the factor grows with severity. At extreme conditions, the factor becomes \(\infty\), representing a hard constraint that blocks traversal regardless of optimization settings.

The safety model produces the same factors for both engines, ensuring that their route comparisons are driven by algorithmic differences rather than different safety evaluations.

10. The Safety Weight Mechanism

Both engines accept a safety weight parameter \(w \in [0, 1]\) that controls how much influence the safety factor has on the cost function. The raw safety factor \(S_f\) from the seakeeping model is dampened by raising it to the power of \(w\):

This formulation has several desirable properties:

• At \(w = 0\) — the dampened factor is always 1.0. Safety has zero influence on the cost function. The optimizer finds the pure fuel-optimal path. Hard constraints (\(S_f = \infty\)) still apply, blocking dangerous conditions.
• At \(w = 1\) — the full safety factor is applied. Routes actively avoid areas with elevated safety factors, even at the cost of extra fuel and time.
• At \(0 < w < 1\) — a continuous interpolation between fuel-optimal and safety-optimal behavior. The exponent dampens large safety factors sublinearly: a factor of 4.0 at \(w = 0.5\) becomes \(4.0^{0.5} = 2.0\), halving the penalty.
• Hard constraints always apply — regardless of \(w\), conditions that exceed the dangerous threshold (\(S_f = \infty\)) always block traversal. This ensures that no optimization strategy can route through truly dangerous seas.

11. Optimization Strategies

WindMar exposes the safety weight through three named strategies in the user interface:

The default strategy is Fuel Optimal. In this mode, the optimized route should consume less fuel than the direct (great-circle) route, since the optimizer can exploit favourable currents and avoid headwinds while incurring no safety penalties for mild-to-moderate weather.

12. Pareto Analysis

The Pareto strategy runs 6 independent optimizations: each of the 2 engines at safety weights \(w \in \{0.0,\, 0.5,\, 1.0\}\). All 6 requests execute in parallel, producing a matrix of results:

The Pareto table in the UI shows the original (direct) route alongside the three solutions for each engine, with colour-coded fuel deltas: green when the optimized route saves fuel, amber when it costs more. A safety icon summarizes the worst-case condition along each route.

This gives the operator a clear picture of the cost of safety. For example, if the Fuel Optimal route saves 3% fuel but has weather warnings, while the Safety route costs 8% more fuel but avoids all warnings, the operator can make an informed trade-off based on the specific voyage requirements.

13. Engine Comparison

14. When to Use Which Engine

Both engines run automatically on every optimization request, so the user always has both results to compare. However, each engine has characteristics that make it better suited to certain route profiles:

14.1 A* Engine Strengths

• Coastal and confined waters — The fine 0.5° grid resolves narrow straits, island passages, and coastal features that the VISIR engine’s 1° grid cannot navigate.
• Short routes — When transit time is under 24 hours, weather evolution is minimal and the static-weather assumption is reasonable.
• Speed — Fewer dimensions mean faster solve times, typically under 1 second for Mediterranean routes.

14.2 VISIR Engine Strengths

• Long ocean crossings — On multi-day voyages, weather systems move and evolve. The time-expanded graph captures this, potentially finding routes that “wait out” a storm by choosing a longer but calmer path.
• Rapidly changing weather — When forecast fields show significant weather evolution (e.g., a developing low-pressure system), the VISIR engine can exploit temporal windows that the A* engine misses.
• Speed adaptation — VSR is integrated into the search, automatically reducing speed in heavy seas rather than treating it as a post-processing adjustment.

References

1. Mannarini, G., Pinardi, N., Coppini, G., Oddo, P. and Iafrati, A. (2016). “VISIR-I: Small Vessel — Least-Time Nautical Routes Using Wave Forecasts.” Geoscientific Model Development, vol. 9, pp. 1597–1625.
2. Hart, P.E., Nilsson, N.J. and Raphael, B. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107.
3. Dijkstra, E.W. (1959). “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik, vol. 1, pp. 269–271.
4. Hagiwara, H. (1989). “Weather Routing of (Sail-Assisted) Motor Vessels.” PhD Thesis, Delft University of Technology.
5. Szlapczynska, J. (2015). “Multi-objective Weather Routing with Customised Criteria and Constraints.” Journal of Navigation, vol. 68, no. 2, pp. 338–354.
6. Vettor, R. and Guedes Soares, C. (2016). “Development of a Ship Weather Routing System.” Ocean Engineering, vol. 123, pp. 1–14.
7. Douglas, D.H. and Peucker, T.K. (1973). “Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature.” Cartographica, vol. 10, no. 2, pp. 112–122.
8. ITTC (2014). “Recommended Procedures and Guidelines: Prediction of Power Increase in Irregular Waves from Model Tests.” ITTC 7.5-02-07-02.2.