An Effective Ship Berthing Algorithm

Abstract

Singapore has one of the busiest ports in the world. Ship berthing is one of the problems faced by the planners at the port. In this paper, we study the ship berthing problem. We first provide the problem formulation and study the complexity of the problem with different restrictions. In general, the ship berthing problem is NP-complete, although, some of its variants may be solved quickly. While a geometrical model is intuitive, the model cannot be easily extended to handle clearance constraints and berth restriction. Rather than solving the problem geometrically, we transform the problem into the problem of fixing directions of edges in graph to form directed acyclic graph with minimal longest path. Since the problem is NPcomplete, solving the problem exactly in polynomial time is highly unlikely. As a result, we devise a fast and effective greedy algorithm to can generate good solutions. The greedy method together with a tabu search like post optimization algorithm is able to return optimal or near optimal solutions.