Optimal ship navigation with safety distance and realistic turn constraints

An I., Aksakalli V., AYDOGDU V., Kum S.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol.229, no.3, pp.707-717, 2013 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 229 Issue: 3
  • Publication Date: 2013
  • Doi Number: 10.1016/j.ejor.2013.03.022
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.707-717
  • Keywords: Graph theory, Shortest path, Ship navigation, Turn-radius constraint, A* algorithm, SHORTEST-PATH PROBLEM, ALGORITHM, CURVATURE, AIRCRAFT, RISK
  • Istanbul Technical University Affiliated: Yes


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. (C) 2013 Elsevier B.V. All rights reserved.