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

Geraldo Regis Mauri, Glaydston Mattos Ribeiro, Luiz Antonio Nogueira Lorena, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

88 Citations (SciVal)

Abstract

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.

Original languageEnglish
Pages (from-to)140-154
Number of pages15
JournalComputers and Operations Research
Volume70
DOIs
Publication statusPublished - 1 Jun 2016

Funding

This research was partly supported by the National Council for Scientific and Technological Development – CNPq (Processes 476862/2012-4 , 303052/2013-9 , 313408/2014-9 and 454569/2014-9 ), the Espírito Santo Research Foundation – FAPES (Process 67627153/2014 ) and the Canadian Natural Sciences and Engineering Research Council under grant 39682-10 . This support is gratefully acknowledged. The authors thank Eduardo Lalla Ruiz from Universidad de La Laguna for kindly providing second data set used in this paper. Thanks are due to the Editor and to the referees for their valuable comments.

Keywords

  • Adaptive large neighborhood search
  • Berth allocation problem
  • Metaheuristic

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'An adaptive large neighborhood search for the discrete and continuous Berth allocation problem'. Together they form a unique fingerprint.

Cite this