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

doi:10.1016/j.cor.2016.01.002

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 journal › Article › peer-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 language	English
Pages (from-to)	140-154
Number of pages	15
Journal	Computers and Operations Research
Volume	70
DOIs	https://doi.org/10.1016/j.cor.2016.01.002
Publication status	Published - 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

Access to Document

10.1016/j.cor.2016.01.002

Cite this

@article{3910a3a5d03344daac4ce192887c53bc,

title = "An adaptive large neighborhood search for the discrete and continuous Berth allocation problem",

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.",

keywords = "Adaptive large neighborhood search, Berth allocation problem, Metaheuristic",

author = "Mauri, {Geraldo Regis} and Ribeiro, {Glaydston Mattos} and Lorena, {Luiz Antonio Nogueira} and Gilbert Laporte",

year = "2016",

month = jun,

day = "1",

doi = "10.1016/j.cor.2016.01.002",

language = "English",

volume = "70",

pages = "140--154",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Mauri, Geraldo Regis

AU - Ribeiro, Glaydston Mattos

AU - Lorena, Luiz Antonio Nogueira

AU - Laporte, Gilbert

PY - 2016/6/1

Y1 - 2016/6/1

N2 - 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.

AB - 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.

KW - Adaptive large neighborhood search

KW - Berth allocation problem

KW - Metaheuristic

UR - http://www.scopus.com/inward/record.url?scp=84955460964&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2016.01.002

DO - 10.1016/j.cor.2016.01.002

M3 - Article

AN - SCOPUS:84955460964

SN - 0305-0548

VL - 70

SP - 140

EP - 154

JO - Computers and Operations Research

JF - Computers and Operations Research

ER -

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

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this