Novel formulations and modeling enhancements for the dynamic berth allocation problem

Arthur Kramer, Eduardo Lalla-Ruiz*, Manuel Iori, Stefan Voß

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
1 Downloads (Pure)

Abstract

This paper addresses the well-known dynamic berth allocation problem (DBAP), which finds numerous applications at container terminals aiming to allocate and schedule incoming container vessels into berthing positions along the quay. Due to its impact on ports’ performance, having efficient DBAP formulations is of great importance, especially for determining optimal schedules in quick time as well as aiding managers and developers in the assessment of solution strategies and approximate approaches. In this work, we propose two novel formulations, a time-indexed formulation and an arc-flow one, to efficiently tackle the DBAP. Additionally, to improve computational performance, we propose problem-based modeling enhancements and a variable-fixing procedure that allows to discard some variables by considering their reduced costs. By means of these contributions, we improve the models’ performance for those instances where the optimal solutions were already known, and we solve to optimality for the first time other instances from the literature.

Original languageEnglish
Pages (from-to)170-185
Number of pages16
JournalEuropean journal of operational research
Volume278
Issue number1
Early online date28 Mar 2019
DOIs
Publication statusPublished - 1 Oct 2019

Fingerprint

Enhancement
Containers
Formulation
Modeling
Schedule
Container Terminal
Managers
Performance Model
Container
Vessel
Optimality
Arc of a curve
Optimal Solution
Allocation problem
Costs
Developer
Container terminal
Discards
Problem formulation
Optimal solution

Keywords

  • Dynamic berth allocation problem
  • Modeling enhancements
  • Novel formulations
  • OR in maritime industry

Cite this

@article{a3fd211831614043b6372ade3bd7103c,
title = "Novel formulations and modeling enhancements for the dynamic berth allocation problem",
abstract = "This paper addresses the well-known dynamic berth allocation problem (DBAP), which finds numerous applications at container terminals aiming to allocate and schedule incoming container vessels into berthing positions along the quay. Due to its impact on ports’ performance, having efficient DBAP formulations is of great importance, especially for determining optimal schedules in quick time as well as aiding managers and developers in the assessment of solution strategies and approximate approaches. In this work, we propose two novel formulations, a time-indexed formulation and an arc-flow one, to efficiently tackle the DBAP. Additionally, to improve computational performance, we propose problem-based modeling enhancements and a variable-fixing procedure that allows to discard some variables by considering their reduced costs. By means of these contributions, we improve the models’ performance for those instances where the optimal solutions were already known, and we solve to optimality for the first time other instances from the literature.",
keywords = "Dynamic berth allocation problem, Modeling enhancements, Novel formulations, OR in maritime industry",
author = "Arthur Kramer and Eduardo Lalla-Ruiz and Manuel Iori and Stefan Vo{\ss}",
year = "2019",
month = "10",
day = "1",
doi = "10.1016/j.ejor.2019.03.036",
language = "English",
volume = "278",
pages = "170--185",
journal = "European journal of operational research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

Novel formulations and modeling enhancements for the dynamic berth allocation problem. / Kramer, Arthur; Lalla-Ruiz, Eduardo; Iori, Manuel; Voß, Stefan.

In: European journal of operational research, Vol. 278, No. 1, 01.10.2019, p. 170-185.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Novel formulations and modeling enhancements for the dynamic berth allocation problem

AU - Kramer, Arthur

AU - Lalla-Ruiz, Eduardo

AU - Iori, Manuel

AU - Voß, Stefan

PY - 2019/10/1

Y1 - 2019/10/1

N2 - This paper addresses the well-known dynamic berth allocation problem (DBAP), which finds numerous applications at container terminals aiming to allocate and schedule incoming container vessels into berthing positions along the quay. Due to its impact on ports’ performance, having efficient DBAP formulations is of great importance, especially for determining optimal schedules in quick time as well as aiding managers and developers in the assessment of solution strategies and approximate approaches. In this work, we propose two novel formulations, a time-indexed formulation and an arc-flow one, to efficiently tackle the DBAP. Additionally, to improve computational performance, we propose problem-based modeling enhancements and a variable-fixing procedure that allows to discard some variables by considering their reduced costs. By means of these contributions, we improve the models’ performance for those instances where the optimal solutions were already known, and we solve to optimality for the first time other instances from the literature.

AB - This paper addresses the well-known dynamic berth allocation problem (DBAP), which finds numerous applications at container terminals aiming to allocate and schedule incoming container vessels into berthing positions along the quay. Due to its impact on ports’ performance, having efficient DBAP formulations is of great importance, especially for determining optimal schedules in quick time as well as aiding managers and developers in the assessment of solution strategies and approximate approaches. In this work, we propose two novel formulations, a time-indexed formulation and an arc-flow one, to efficiently tackle the DBAP. Additionally, to improve computational performance, we propose problem-based modeling enhancements and a variable-fixing procedure that allows to discard some variables by considering their reduced costs. By means of these contributions, we improve the models’ performance for those instances where the optimal solutions were already known, and we solve to optimality for the first time other instances from the literature.

KW - Dynamic berth allocation problem

KW - Modeling enhancements

KW - Novel formulations

KW - OR in maritime industry

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

U2 - 10.1016/j.ejor.2019.03.036

DO - 10.1016/j.ejor.2019.03.036

M3 - Article

AN - SCOPUS:85064507628

VL - 278

SP - 170

EP - 185

JO - European journal of operational research

JF - European journal of operational research

SN - 0377-2217

IS - 1

ER -