A MEMETIC ALGORITHM FOR A CONTINUOUS CASE OF THE BERTH ALLOCATION PROBLEM

This work presents a Memetic Algorithm heuristic to solve a continuous case of the Berth Allocation Problem (BAP). The BAP deals with programming and allocating ships to berthing areas along a quay. In general, the continuous case considers that ships have different lengths and can moor anywhere along the quay. However, we consider a quay divided in berths that have limited areas and different equipments to handle the ships. So, we must to assign the ships to berths and determine the berthing time and position for each ship. We treat the ships as rectangles to be placed into a space x time area avoiding overlaps and satisfying time window constraints. Our MA uses a Simulated Annealing (SA) as the local search mechanism, and SA is also applied in a stand alone way to solve the BAP. A two-phase heuristic is also presented to compute the berthing time and position for all of ships during MA and SA execution. Computational results are performed on a set of instances proposed in the literature and new best-known solutions are presented.