Simulated Annealing for Optimal Ship Routing

1. Introduction

• Ship size, speed capability, cargo type, and vulnerability to adverse conditions inform route selection and surveillance.The passage says ship characteristics affect both pre-sailing route selection and monitoring underway.Source: §1 · p. 1
• Wind and waves affect ship speed and comfort, while fog and currents can also influence route selection and surveillance.Wave height is identified as a major factor affecting performance; fog avoidance can lengthen distance yet reduce transit time when visibility is poor.Source: §1 · p. 2
• The paper targets optimal ship routing using simulated annealing, focusing on wave height and direction.The introduction describes routing as allocating available resources to meet requirements.Source: §1 · p. 2
• The paper presents its problem formulation, discrete variational principles, algorithm, and simulated and real experiments in successive sections.Source: §1 · p. 3

2. Formulation of the problem

• The route is modeled as a smooth curve parameterized by arc length from the initial point, with ship velocity and wind and wave vectors specified.The passage identifies the ship’s velocity with the route’s time derivative.Source: §2 · p. 3
• Each route receives a scalar cost combining voyage time T and comfort C, with user-tunable weight α.The formulation states that α = 1 optimizes voyage time alone, while α = 0 optimizes crew comfort alone.Source: §2 · pp. 3–4
• For simplicity, the formulation sets F = 0 in the ship-speed expression, although F depends on ship characteristics, wind, waves, and movement direction.Source: §2 · p. 4

3. Discrete variational principles for mechanical problems

• The comfort function is treated as a variational minimization problem, with an integral made stationary under variations that vanish at fixed endpoints.The approach is compared with Hamilton’s principle and its Euler–Lagrange equations.Source: §3 · p. 5

3.1. Discretization of the initial ship’s route

• The route is approximated by a polygonal line, and small waypoint shifts are used to evaluate changes in route cost.The discrete route consists of edges between successive route points.Source: §3.1 · pp. 5–6

3.2. Searching using simulated annealing

• Simulated annealing accepts some cost-increasing moves early, then reduces their acceptance as temperature falls; continuous moves can still trap the search near an obstacle.The authors report this local-minimum case when the direct line between endpoints passes close to a small obstacle.Source: §3.2 · pp. 6–7
• Selecting waypoint variations parallel or antiparallel to wave propagation accelerates convergence by following the directions of maximum cost change.The direction is determined from the wave contribution to the cost function.Source: §3.2 · pp. 7–8

4. Description of the algorithm

• For routes with obstacles, initialization uses shortest paths for possible bypasses, and the algorithm checks all initial routes despite the added computation.With n obstacles, the passage gives 2n initial paths.Source: §4 · p. 8
• Waypoint spacing is adjusted toward the forecast mesh distance, balancing route fit against computation, crew actions, and forecast resolution.A waypoint is added when adjacent points are farther apart than DM and merged when closer than Dm.Source: §4 · pp. 8–9
• The algorithm randomly shifts an interior waypoint, accepts the change according to the Boltzmann probability, adjusts nearby waypoint spacing, and lowers the temperature.The procedure repeats until the termination condition is met.Source: §4 · p. 9

5.1. Constant wave field

• In uniform and direction-reversing wave fields, waypoints shift to maximize |u · w|, where perpendicular waves develop higher moments around the ship’s axis.The direction reverses once and twice in the piecewise-uniform cases.Source: §5.1 · p. 10

5.2. The effect of parameter α

• As α decreases, routes become longer and align with the wave field as comfort contributes more and voyage time contributes less to total cost.At α = 1, voyage time alone is optimized, yielding the largest circle joining the endpoints.Source: §5.2 · p. 10

5.3. Field test

• The Thessaloniki–Ag. Nikolaos field test uses forecast data and multiple initial routes because islands double the number of possible routes.The reported wave directions shift from north near Thessaloniki to north-east in the middle region and south-west near Ag. Nikolaos.Source: §5.3 · pp. 10–11
• The field-test routes differ only near the voyage’s beginning, and their total-cost difference is negligible.The initial mismatch is attributed to the proposed route’s continuous-transformation constraint.Source: §5.3 · p. 11

• The key result accelerates the search by restricting route variations to directions parallel or antiparallel to wave propagation.Field tests compare the proposed algorithm’s calculated routes with those from exhaustive, time-consuming genetic algorithms.Source: §6 · p. 11