Paper Info
Title
Algorithms for solving the ship berthing problem
Abstract
The Ship Berthing Problem (SBP) is one of the many problems faced by a port in its daily execution. Ships arriving at the port will have to be assigned specific berthing location based on certain constraints arising from the ship's cargo or physical characteristics. SBP can be solved as a minimization problem, in which the aim is to assign all ships in an arrangement that would result a minimum wharf length. The SBP can be represented using a Directed Acyclic Graph (DAG) where vertices represents ships and edges represent the contemporary relationship between ships. Two ships are contemporary if they are both required to be berthed at a particular instance. The direction of the edges determines the relative positions of the ships and hence the resulting required wharf length. For the ease of manipulation, the DAG is represented by an acyclic list where each node in the list represents a vertex and the relative positions of the nodes reflects the direction of edges in the DAG. A Greedy Local Search (GLS) algorithm is proposed to solve the SBP. The idea is to constantly displace nodes in the acyclic list as long as the resulting required berth length is reduced. A Tabu-Search (TS) post-optimization technique is proposed to improve the result of the GLS, here, a potentially 'bad' displacement is allowed in hope that the move would result in an escape from the local optimal, the performance of the TS can be varied by specifying the maximum number of consecutive 'bad' displacement allowed. Two displacement techniques with different local search neighbourhood were proposed. The initial solution in which the GLS is performed can be obtained by using a Greedy Heuristic, alternatively, a randomly generated initial solution can be used. A different approach in solving the SBP is the use of Genetic Algorithm (GA). Due to the unique nature of the acyclic list, common crossover reproductive methods cannot be used, instead three reproductive methods that would not corrupt the acyclic list were proposed. The performance of the G A can be configured by using a decline factor on the fitness measure, a high decline factor would give rise to a more stringent natural selection by modifing the fitness measure as the generation progresses. The roulette selection method is used to ensure that the solution would not be moving towards the local optimal all the time. We have experimented with a total of 22 different variants of the GLS, TS and GA and found that all techniques possess variants that produces good results for solving the SBP.
Year
DOI
Venue
2000
10.1007/3-540-44533-1_86
PRICAI
Keywords
Field
DocType
different local search neighbourhood,berth length,local optimal,fitness measure,initial solution,relative position,different variant,different approach,acyclic list,g a,tabu search,local search,greedy heuristic,directed acyclic graph,genetic algorithm,natural selection
Computer science,Artificial intelligence,Roulette,Genetic algorithm,Mathematical optimization,Crossover,Vertex (geometry),Algorithm,Greedy algorithm,Directed acyclic graph,Local search (optimization),Machine learning,Wharf
Conference
ISBN
Citations 
PageRank 
3-540-67925-1
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Kai Song Goh1282.15
Andrew Lim237321.86