Robust Metaheuristics under Uncertainty for Berth Allocation and Quay Crane Assignment: A Review
arXiv:2608.192142026-08-21
A review of algorithms that keep port ship-and-crane schedules from falling apart when things go wrong
This paper reviews population-based metaheuristics (algorithms that evolve many candidate solutions at once, like genetic algorithms) built to handle uncertainty in the Berth Allocation and Quay Crane Assignment Problem (BACAP), which decides when and where ships dock and how crane resources are assigned at container terminals. The authors organize prior work into five design areas: how solutions are represented and decoded, how uncertainty is captured for evaluation, how robustness is scored and used for selection, how search behavior adapts to robustness, and how constraint violations are repaired. They also release a benchmark suite and baseline results comparing nine combinations of three algorithms (GA, ACO, PSO) with three robustness strategies (MMRO, ERO, TSRO).
What they did
BACAP jointly decides ship berthing time/position and quay crane assignment, and this review focuses on making such schedules resilient to arrival delays, handling-time fluctuations, and equipment disruptions
Existing methods are organized into five mechanisms: solution representation/decoding (direct, indirect, hybrid, constructive), uncertainty information (fuzzy, set-based, scenario-based, distributional, distributional-ambiguity), robust evaluation and selection, robustness-guided search dynamics, and feasibility recovery
A literature screening from 2008 through recent years found metaheuristic-based studies make up 33.9% of the field, versus 25.2% for heuristic-based studies
Nine algorithm-strategy combinations (GA/ACO/PSO x MMRO/ERO/TSRO) were run 25 times each on a 100-vessel benchmark; PSO-based combinations often achieved lower average port time, while ACO-based combinations were competitive on robustness in some cases
The paper flags open challenges: extending benchmarks toward real terminal data, designing search operators that are explicitly robustness-aware, handling robustness over an evolving time horizon, and coping with uncertainty whose statistical properties change over time
Figure 1: BACAP literature identification and landscape analysis using a PRISMA-style screening procedure. (a) Annual trend of metaheuristic-based studies on uncertain BACAP. (b) Distribution of algorithm families in the included studies. Records from 2008–May 2026 were retrieved from Google Scholar using BACAP-, uncertainty-, and robustness-related keywords. After duplicate removal, title/abstract screening, and full-text eligibility assessment, studies were retained if they addressed uncertain berth allocation, quay crane assignment, or integrated BACAP with metaheuristic, population-based, stochastic, or robust solution methods. Deterministic-only, irrelevant, duplicate, incomplete, or methodologically insufficient studies were excluded.
TABLE I: Parameters and decision variables for a representative deterministic BACAP formulation.
Sets and indices
𝒱={1,…,n}
Set of vessel indices
𝒬={1,…,m}
Set of QC indices
𝒯={0,…,H−1}
Set of discrete time periods
i,j∈𝒱
Vessel indices
k,ℓ∈𝒬
QC indices
t∈𝒯
Time-period index
Parameters
ai∈{0,…,H}
Nominal arrival time of vessel i
li∈(0,L]
Length of vessel i
pi>0
Handling workload of vessel i
μ>0
Handling productivity of one QC per time period
[t¯g,t¯g]⊆[0,H]
The g-th tidal time window
L>0
Total quay length
b≥0
Minimum safety distance between simultaneously operating QCs
1≤q¯i≤q¯i≤m
Minimum and maximum numbers of QCs assignable to vessel i
M>0
A sufficiently large constant
Decision and auxiliary variables 𝐗
xi∈[0,L−li]
Berthing position of vessel i
si∈{0,…,H}
Service start time of vessel i
di∈{0,…,H}
Completion time of vessel i
zi,t∈{0,1}
Equals 1 if vessel i is under service during time period t, and 0 otherwise
yi,k,t∈{0,1}
Equals 1 if QC k serves vessel i during time period t, and 0 otherwise
qi,t∈{0,…,m}
Number of QCs assigned to vessel i during time period t
αi,j∈{0,1}
Equals 1 if vessel i is spatially before vessel j, and 0 otherwise
βi,j∈{0,1}
Equals 1 if vessel i is temporally before vessel j, and 0 otherwise
γi,j∈{0,1}
Equals 1 if vessels i and j are separated in space, and 0 if they are separated in time
ci,k,t∈[0,L]
Position of QC k when assigned to vessel i during time period t
((b))
TABLE II: Taxonomy of representation and encoding strategies for BACAP.
Figure 2: Conceptual framework of robust population-based metaheuristics for uncertain BACAP. The central port scenario illustrates vessel-arrival uncertainty, handling-duration uncertainty, and QC-availability uncertainty, while the surrounding modules summarize how representation, uncertainty information, robust evaluation, search dynamics, and feasibility recovery jointly shape robust executable berth–QC schedules.
TABLE III: Taxonomy of uncertainty information representations for BACAP search evaluation.
Representation type
Representative references
Fuzzy or imprecise representation
[71][72][73][98]
Set-based representation
[76][77][78][99][100]
Scenario-based representation
[7][40][81][82][83][101][102]
Distributional representation
[61][64][65][84][85][87][88] [103]
Distributional-ambiguity representation
[93][94][95][96] [97]
TABLE IV: Robust evaluation, ranking, and selection mechanisms for uncertain BACAP.
Mechanism
Representative references
Expected-performance evaluation
[64][81][104][103][116][117]
Worst-case evaluation
[38][76] [78] [99][105] [118][119][120]
Risk-, regret-, and stability-aware evaluation
[7] [49][77][100][116] [121][122]
Distributionally robust evaluation
[90] [93] [94] [95] [96] [97]
Recourse-aware and time-adaptive evaluation
[17][53] [69][83] [112] [113]
TABLE V: Robustness-guided search dynamics in BACAP metaheuristics.
TABLE VI: Constraint-handling mechanisms for robust BACAP.
Mechanism
Representative references
Penalty-based feasibility pressure
[87][100][103] [118][138][143][154]
Repair-based feasibility restoration
[53][83] [148][149] [150] [155]
Model- and representation- integrated preservation
[49][58][137][138][156][157][158]
Robust feasibility coordination
[17][7][39][76][96][112] [113][159]
TABLE VII: Benchmark cases constructed from four arrival patterns and four uncertainty scenarios.
Cases C1–C8
Cases C9–C16
ID
Pattern
US
ID
Pattern
US
C1
Uniform
US1
C9
Uniform
US3
C2
Gaussian
C10
Gaussian
C3
Chaotic
C11
Chaotic
C4
Periodic
C12
Periodic
C5
Uniform
US2
C13
Uniform
US4
C6
Gaussian
C14
Gaussian
C7
Chaotic
C15
Chaotic
C8
Periodic
C16
Periodic
TABLE VIII: Baseline results (mean ± std) of average port time and survival-time robustness for nine robust population-based metaheuristics under the 100-vessel setting.
Cases
Metric
Value
GA-MMRO
GA-ERO
GA-TSRO
ACO-MMRO
ACO-ERO
ACO-TSRO
PSO-MMRO
PSO-ERO
PSO-TSRO
C1
T¯port
Mean
3.14E+01
3.08E+01
3.08E+01
2.90E+01
2.85E+01
2.88E+01
2.83E+01
2.76E+01
2.71E+01
Std
1.35E+00
7.00E-01
7.90E-01
9.80E-01
1.04E+00
9.90E-01
1.36E+00
1.03E+00
1.02E+00
σ¯
Mean
7.10E+00
7.02E+00
7.02E+00
7.14E+00
7.01E+00
7.03E+00
7.13E+00
7.22E+00
7.05E+00
Std
3.70E-01
3.50E-01
3.50E-01
3.40E-01
2.90E-01
2.60E-01
3.20E-01
4.40E-01
3.80E-01
C2
T¯port
Mean
3.19E+01
3.09E+01
3.12E+01
2.92E+01
2.87E+01
2.85E+01
2.86E+01
2.74E+01
2.82E+01
Std
1.21E+00
7.90E-01
9.10E-01
7.10E-01
9.00E-01
8.50E-01
1.39E+00
9.50E-01
8.20E-01
σ¯
Mean
7.09E+00
6.97E+00
6.95E+00
7.03E+00
7.05E+00
7.10E+00
6.91E+00
7.16E+00
6.97E+00
Std
3.80E-01
4.10E-01
3.70E-01
3.30E-01
3.30E-01
4.30E-01
4.00E-01
3.90E-01
3.20E-01
C3
T¯port
Mean
3.57E+01
3.53E+01
3.55E+01
3.42E+01
3.36E+01
3.33E+01
3.30E+01
3.19E+01
3.21E+01
Std
7.90E-01
7.60E-01
7.60E-01
8.40E-01
7.30E-01
6.30E-01
1.60E+00
1.23E+00
1.11E+00
σ¯
Mean
6.95E+00
7.05E+00
7.09E+00
6.93E+00
6.93E+00
7.00E+00
7.06E+00
6.96E+00
6.93E+00
Std
3.80E-01
4.40E-01
3.80E-01
2.90E-01
3.00E-01
3.50E-01
3.70E-01
4.10E-01
3.50E-01
C4
T¯port
Mean
3.59E+01
3.54E+01
3.50E+01
3.39E+01
3.35E+01
3.34E+01
3.38E+01
3.32E+01
3.29E+01
Std
1.11E+00
8.90E-01
1.10E+00
7.30E-01
6.80E-01
8.40E-01
1.03E+00
7.80E-01
8.60E-01
σ¯
Mean
6.93E+00
7.01E+00
7.11E+00
7.08E+00
7.01E+00
7.14E+00
6.77E+00
6.93E+00
6.96E+00
Std
3.30E-01
3.70E-01
3.00E-01
3.30E-01
3.90E-01
2.80E-01
4.00E-01
4.60E-01
3.30E-01
C5
T¯port
Mean
3.32E+01
3.24E+01
3.23E+01
3.06E+01
2.97E+01
2.99E+01
3.00E+01
2.86E+01
2.85E+01
Std
8.80E-01
1.00E+00
1.10E+00
9.20E-01
8.80E-01
8.80E-01
1.57E+00
1.01E+00
1.18E+00
σ¯
Mean
7.34E+00
7.37E+00
7.38E+00
7.49E+00
7.48E+00
7.45E+00
7.50E+00
7.52E+00
7.54E+00
Std
4.40E-01
3.70E-01
3.20E-01
3.20E-01
3.80E-01
2.50E-01
3.10E-01
3.20E-01
3.40E-01
C6
T¯port
Mean
3.30E+01
3.19E+01
3.21E+01
3.06E+01
3.01E+01
3.01E+01
2.98E+01
2.84E+01
2.88E+01
Std
1.08E+00
8.00E-01
7.30E-01
9.10E-01
8.70E-01
9.70E-01
1.13E+00
1.13E+00
8.70E-01
σ¯
Mean
7.37E+00
7.39E+00
7.44E+00
7.43E+00
7.60E+00
7.47E+00
7.43E+00
7.39E+00
7.44E+00
Std
4.20E-01
3.30E-01
3.90E-01
2.30E-01
3.50E-01
3.70E-01
3.90E-01
2.90E-01
3.40E-01
C7
T¯port
Mean
3.49E+01
3.44E+01
3.41E+01
3.35E+01
3.27E+01
3.24E+01
3.36E+01
3.15E+01
3.15E+01
Std
8.00E-01
1.05E+00
9.00E-01
1.03E+00
6.90E-01
7.60E-01
1.10E+00
8.40E-01
9.80E-01
σ¯
Mean
7.30E+00
7.30E+00
7.29E+00
7.45E+00
7.24E+00
7.35E+00
7.28E+00
7.28E+00
7.26E+00
Std
4.40E-01
3.80E-01
4.00E-01
3.90E-01
3.70E-01
4.60E-01
4.50E-01
3.50E-01
4.80E-01
C8
T¯port
Mean
3.22E+01
3.13E+01
3.16E+01
3.11E+01
3.06E+01
3.05E+01
3.16E+01
3.03E+01
3.04E+01
Std
9.40E-01
8.30E-01
8.00E-01
6.60E-01
9.10E-01
6.80E-01
9.40E-01
7.20E-01
8.70E-01
Why it matters
Real ports rarely run on schedule, so knowing which optimization strategies actually hold up under delays and disruptions matters directly for terminal efficiency and cost. The released benchmark and code give researchers a shared, reproducible testbed to fairly compare new robust scheduling algorithms instead of relying on scattered, proprietary datasets.
Terms in this paper
BACAP · the problem of jointly deciding ship berth position/timing and quay crane assignment at a container port
population-based metaheuristic · a search algorithm that evolves a group of candidate solutions together, e.g. genetic algorithms
MMRO (min-max robust optimization) · optimizing for the worst-case outcome across possible uncertain conditions
TSRO (two-stage robust optimization) · planning a first-stage decision then allowing adjustments once uncertainty is revealed
ambiguity set · a set of plausible probability distributions used when the true distribution of uncertainty is unknown
Original abstract (English)
The berth allocation and quay crane assignment problem (BACAP) is a representative port-terminal scheduling problem in maritime transportation and freight logistics, where vessel arrivals, berth positions, service durations, and quay?crane availability are tightly coupled. Under uncertainties such as arrival deviations, handling-time fluctuations, and resource disruptions, schedules optimized under nominal assumptions may become fragile during execution, motivating the study of robust metaheuristic optimization for BACAP in port-terminal operations. Although population-based metaheuristics have been widely used for BACAP and related port-scheduling problems, existing studies remain fragmented in their uncertainty repre?sentations, robustness criteria, search mechanisms, and empir?ical evaluation protocols. To the best of our knowledge, this paper provides the first focused review dedicated to robust population-based metaheuristics for BACAP under uncertainty. We first summarize uncertainty sources and information repre?sentations in BACAP, and then organize existing methods from a mechanism-oriented perspective, covering solution representation and decoding, robust evaluation and selection, robustness-guided search dynamics, and feasibility preservation and recovery. We further present a benchmark suite for uncertain BACAP to support controlled empirical comparison and report illustrative baseline results by combining representative metaheuristics with different robustness strategies. Finally, we identify open chal?lenges related to benchmark extension, robustness-aware search design, time-adaptive robustness, and non-stationary uncertainty.
