A Benders Decomposition Algorithm for the Berth Allocation Problem

• Type: Article in International Conference Proceedings Book
• Date: 2019

Authors

Flávia Barbosa (Author) Other; José Fernando Oliveira (Author) FEUP; Maria Antónia Carravilla (Author) FEUP; Eduardo Ferian Curcio (Author) Other

Conference proceedings International

Title: Springer Proceedings in Mathematics and Statistics

Pages: 29-41

19th Congress of APDIO, Portuguese Association of Operational Research, IO 2018

5 September 2018 through 7 September 2018

Indexing

Scopus - 1 Citation

Other information

Authenticus ID: P-00Q-HNG

DOI: 10.1007/978-3-030-10731-4_3

Abstract (EN): In this paper we present a Benders decomposition approach for the Berth Allocation Problem (BAP). Benders decomposition is a cutting plane method that has been widely used for solving large-scale mixed integer linear optimization problems. On the other hand, the Berth Allocation Problem is a NP-hard and large-scale problem that has been gaining relevance both from the practical and scientific points of view. In this work we address the discrete and dynamic version of the problem, and develop a new decomposition approach and apply it to a reformulation of the BAP based on the Heterogeneous Vehicle Routing Problem with Time Windows (HVRPTW) model. In a discrete and dynamic BAP each berth can moor one vessel at a time, and the vessels are not all available to moor at the beginning of the planning horizon (there is an availability time window). Computational tests are run to compare the proposed Benders Decomposition with a state-of-the-art commercial solver. © 2019, Springer Nature Switzerland AG.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13