TY - JOUR

T1 - Optimal ship navigation with safety distance and realistic turn constraints

AU - Ari, Ibrahim

AU - Aksakalli, Vural

AU - Aydoǧdu, Volkan

AU - Kum, Serdar

PY - 2013/9/16

Y1 - 2013/9/16

N2 - We consider the optimal ship navigation problem wherein the goal is to find the shortest path between two given coordinates in the presence of obstacles subject to safety distance and turn-radius constraints. These obstacles can be debris, rock formations, small islands, ice blocks, other ships, or even an entire coastline. We present a graph-theoretic solution on an appropriately-weighted directed graph representation of the navigation area obtained via 8-adjacency integer lattice discretization and utilization of the Aâ̂- algorithm. We explicitly account for the following three conditions as part of the turn-radius constraints: (1) the ship's left and right turn radii are different, (2) ship's speed reduces while turning, and (3) the ship needs to navigate a certain minimum number of lattice edges along a straight line before making any turns. The last constraint ensures that the navigation area can be discretized at any desired resolution. Once the optimal (discrete) path is determined, we smoothen it to emulate the actual navigation of the ship. We illustrate our methodology on an ice navigation example involving a 100,000 DWT merchant ship and present a proof-of-concept by simulating the ship's path in a full-mission ship handling simulator.

AB - We consider the optimal ship navigation problem wherein the goal is to find the shortest path between two given coordinates in the presence of obstacles subject to safety distance and turn-radius constraints. These obstacles can be debris, rock formations, small islands, ice blocks, other ships, or even an entire coastline. We present a graph-theoretic solution on an appropriately-weighted directed graph representation of the navigation area obtained via 8-adjacency integer lattice discretization and utilization of the Aâ̂- algorithm. We explicitly account for the following three conditions as part of the turn-radius constraints: (1) the ship's left and right turn radii are different, (2) ship's speed reduces while turning, and (3) the ship needs to navigate a certain minimum number of lattice edges along a straight line before making any turns. The last constraint ensures that the navigation area can be discretized at any desired resolution. Once the optimal (discrete) path is determined, we smoothen it to emulate the actual navigation of the ship. We illustrate our methodology on an ice navigation example involving a 100,000 DWT merchant ship and present a proof-of-concept by simulating the ship's path in a full-mission ship handling simulator.

KW - A algorithm

KW - Graph theory

KW - Ship navigation

KW - Shortest path

KW - Turn-radius constraint

UR - http://www.scopus.com/inward/record.url?scp=84877700225&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2013.03.022

DO - 10.1016/j.ejor.2013.03.022

M3 - Article

AN - SCOPUS:84877700225

SN - 0377-2217

VL - 229

SP - 707

EP - 717

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -