Robust Metaheuristics under Uncertainty for Berth Allocation and Quay Crane Assignment: A Review
arXiv:2608.192142026-08-21
항구에서 배와 크레인 일정을 짜는 알고리즘들이 '변수'에 얼마나 강한지 정리한 리뷰
이 논문은 컨테이너 항구에서 배를 어디에 몇 시에 접안시키고 크레인을 어떻게 배정할지 정하는 문제(BACAP)를, 도착 지연이나 작업시간 변동 같은 불확실성 속에서도 잘 버티도록 푸는 '집단 기반 메타휴리스틱' 알고리즘들을 처음으로 체계적으로 정리한 리뷰다. 해를 어떻게 표현하고 해독하는지, 불확실성을 어떤 정보로 다루는지, 해를 어떻게 평가·선택하는지, 탐색 과정을 어떻게 조정하는지, 제약 위반을 어떻게 복구하는지 다섯 가지 축으로 기존 연구를 정리했다. 또한 저자들은 자체 벤치마크(비교용 표준 시험 문제 세트)를 만들어 GA, ACO, PSO 세 알고리즘에 세 가지 강건화 전략을 조합한 9가지 방법의 기초 성능을 비교해 공개했다.
무엇을 했나
항구에서 배 접안 위치·시간, 크레인 배정을 동시에 정해야 하는 BACAP 문제를, 도착 지연·작업시간 변동·장비 고장 같은 불확실성 상황에서 풀리게 만드는 강건한 알고리즘들을 조사했다
해를 표현하는 방식(직접/간접/혼합/구성적 표현), 불확실성을 다루는 정보 형태(퍼지, 구간, 시나리오, 확률분포, 분포 모호집합), 해를 평가하고 고르는 방법, 탐색 중 강건성을 반영하는 방식, 제약 위반 복구 방법 등 다섯 갈래로 기존 연구를 분류했다
2008년부터 최근까지 문헌을 체계적으로 수집해 분석한 결과 메타휴리스틱 기반 연구가 전체의 33.9%로 휴리스틱 기반(25.2%)보다 많았다
GA, ACO, PSO 세 알고리즘에 최악상황대비 최적화(MMRO), 기대값 기반 최적화(ERO), 2단계 강건 최적화(TSRO)를 조합한 9가지 방법을 배 100척 규모에서 25회씩 반복 실행해 비교했고, PSO 계열이 평균 운항시간(port time) 면에서, ACO 계열이 일부 상황에서 강건성 면에서 경쟁력을 보였다
벤치마크 확장, 강건성을 반영한 탐색 연산자 설계, 시간에 따라 변하는 강건성 관리, 시간에 따라 성질이 바뀌는 불확실성 대응을 앞으로의 연구 과제로 제시했다
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
왜 중요한가
항구 운영은 실제로는 계획대로 배가 오지 않고 작업시간도 들쭉날쭉한데, 이 리뷰는 그런 현실적 불확실성을 감안해 일정을 짜는 방법들을 한눈에 비교할 수 있게 정리해 연구자와 항만 운영자 모두에게 참고 지도 역할을 한다. 또한 저자들이 공개한 벤치마크와 코드는 앞으로 새 알고리즘을 만들 때 공정하게 성능을 비교할 수 있는 공통 시험대를 제공한다.
이 논문의 용어
BACAP · 선박 접안 위치·시간과 부두 크레인 배정을 함께 정하는 항구 일정 문제
메타휴리스틱 · 정확한 최적해 대신 실용적으로 좋은 해를 빠르게 찾는 탐색 알고리즘 기법
집단 기반(population-based) 알고리즘 · 여러 후보 해를 동시에 유지하며 발전시키는 탐색 방식(예: 유전 알고리즘)
min-max 강건 최적화(MMRO) · 가장 나쁜 상황에서도 성능이 보장되도록 최적화하는 방법
2단계 강건 최적화(TSRO) · 먼저 큰 틀의 계획을 세우고 불확실성이 실현된 뒤 세부 조정을 허용하는 최적화 방식
모호집합(ambiguity set) · 정확한 확률분포를 모를 때 가능한 여러 확률분포들의 집합으로 불확실성을 표현하는 방법
논문 원문 초록 (영문)
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.
