Tackling the Berth Allocation Problem via Harmony Search Algorithm

Abstract

Berth Allocation Problem (BAP) is a renowned difficult combinatorial optimization problem that plays a crucial role in maritime transportation systems. BAP is categorized as non-deterministic polynomial-time hard (NP-hard) problems, that is very tough to resolve for optimality within an acceptable timeframe. Many metaheuristic algorithms have been suggested to tackle this problem, and yet, most of these algorithms have some drawbacks such as they have a weak ability to explore the solution space (they struggle escaping from local minima) and they face the difficulties to operate on different datasets. Consequently, the need to either enhance the existing algorithms or utilize a new algorithm is still necessary. Harmony Search Algorithm (HSA) is one of the recent population-based optimization methods which inspired by modern-nature. HSA has confirmed its ability to tackle various difficult combinatorial optimization problems like vehicle routing, exam timetabling to name a few. However, as far as we are concerned, it has never been applied to tackle the BAP problem. The primary objective of this article is to examine the effectiveness of HSA in solving BAP by identifying suitable values for the parameters of the HSA and then applying HSA to tackle BAP. Therefore, in this article, the basic HSA is proposed to tackle the BAP. The suggested HSA is tested on BAP benchmark (I3 dataset) and compared the results with other latest algorithms found in the literature. The trial outcomes evidenced that the HSA is promising, competitive, and that it has surpassed some other algorithms that have solved the same dataset, and the results were very near to the best-known results. Experimental results also prove the suitability and applicability of HSA in tackling the BAP.

Keywords

• Berth allocation problem
• combinatorial optimization problems
• harmony search algorithm
• metaheuristic algorithms