An adaptive large neighborhood search for the discrete and continuous Berth allocation problem

• We propose an Adaptive Large Neighborhood Search (ALNS) heuristic for both discrete and continuous cases of the Berth Allocation Problem.
• A very broad set of instances were used and our heuristic provided good solutions within low computational time.
• A sensitivity analysis was reported by changing the number of ships and berths.
• Statistical tests were performed over the obtained results.
• Our ALNS produced high quality results and was superior to the competing algorithms on most instances.

The Berth Allocation Problem (BAP) consists of assigning ships to berthing positions along a quay in a port. The choice of where and when the ships should move is the main decision to be made in this problem. Considering the berthing positions, there are restrictions related to the water depth and the size of the ships among others. There are also restrictions related to the berthing time of the ships which are modeled as time windows. In this work the ships are represented as rectangles to be placed into a space ×time area, avoiding overlaps and satisfying time window constraints. We consider discrete and continuous models for the BAP and we propose an Adaptive Large Neighborhood Search heuristic to solve the problem. Computational experiments indicate that the proposed algorithm is capable of generating high-quality solutions and outperforms competing algorithms for the same problem. In most cases the improvements are statistically significant.