선박 도착시간의 불확실성에 강건한 선석 계획
Robust Berth Planning under Uncertain Vessel Arrival
Article information
Abstract
본 연구의 목적은 선석 계획 수립 시에 선박 도착시간의 불확실성에 따른 피해를 대비할 수 있는 방법론을 개발하는 데에 있다. 세계적으로 수입량과 수출량이 급증하면서 컨테이너 터미널 선석 계획의 효율화가 더욱 중요해졌다. 선석 계획은 컨테이너 터미널의 처리용량을 결정하기 때문에 선박 사이의 시간과 공간적 간격을 최소화하여 선석 활용도를 극대화하는 것이 중요하다. 실제 선석을 운영할 때에는 여러 불확실한 요소로 인해서 선박이 예정보다 늦게 도착하는 경우 기존의 선석 계획이 틀어지게 되면서 터미널이 큰 피해를 입게 된다. 이러한 피해를 방지하기 위해 본 논문에서는 기존의 문헌들을 조사하여 완충 시간을 도입하는 방법을 제안한다.
Trans Abstract
The purpose of this study is to develop a proactive methodology for disruption due to uncertainty in vessels’ arrival time. As worldwide imports and exports increased rapidly, the importance of berth planning in container terminals has increased accordingly. Since the berth plan determines the capacity of the container terminal, it aims to maximize efficiency by minimizing the time and space gap between the vessels. In reality, several uncertainties disrupt the initial berth plan resulting in economic losses. In this study, we propose a robust berth plan for preventing disruption.
1. 서 론
4차 산업혁명의 제조방식이 도입됨에 따라 수요 예측의 정확도가 높아졌고, 생산방식이 다품종 소량에서 다품종 대량으로 변화하고 있다. 수입량과 수출량이 급증함과 동시에 항만 시설의 중요성이 대두되었다. 특히, 컨테이너 터미널의 처리 용량을 결정하는 선석 계획의 운영 방식은 선사를 유치하기 위한 컨테이너 터미널의 중요 경쟁 요인이다.
선석 계획(Berth planning)은 Fig. 1과 같은 시간 축과 공간 축으로 이루어진 2차원 평면 내에 존재하는 여러 선박의 접안 위치(Berthing position)와 접안 시간(Berthing time) 그리고 안벽 크레인(Quay crane)의 할당 수를 결정한다. 선석 계획을 수립함에 있어서 선박 사이의 시간 및 공간적 간격을 최소화하여 효율을 극대화하는 것이 중요하지만 여러 가지 불확실한 요인들로 인해 어려움을 겪는 것이 현실이다.
Time-space diagram
Source : Busan Port Terminal Corp, 2020
선박이 이전 터미널에서의 작업 상황 또는 해양 상태에 따라 예정 도착시간보다 늦게 도착하는 경우 기존의 선석 계획이 틀어지게 되는 문제가 발생하는데 이는 뒤의 선석 계획까지 영향을 끼쳐 터미널에 큰 손실을 초래할 수 있다. 이에 선석 계획 시 완충 시간을 도입하여 선박이 늦더라도 어느 정도 초기 계획을 지킬 수 있는 강건한 선석 계획을 수립하는 방법론이 등장하였다. 이는 초기 선석 계획 시 선박과 선박 사이에 완충 시간을 부여하는 것인데 완충 시간을 부여하다 보니 계획상에서 공간적으로 발생하는 손실과 불확실성의 위험에 따른 손해를 감소시키는 득실을 비교하여 비용 효율적인 계획을 수립하는 것이다.
본 논문에서는 불확실한 상황 속에서 선박이 늦게 도착하는 경우 기존의 선석 계획이 틀어지는 문제를 해결하기 위하여 효과적인 완충 시간을 도입하는 방안을 제시하고, 기존의 선석 계획을 효과적으로 유지할 수 있는지 실험을 통하여 분석하고자 한다. 본 논문의 구성은 다음과 같다. 우선 2절에서는 선석 계획과 완충 시간에 관한 기존의 연구를 조사한다. 3절에서는 수리적인 모델을 설명하고 4절에서는 완충 시간을 도입한 선석 계획의 효과를 여러 상황에서 시뮬레이션 실험을 통하여 기존의 선석 계획과 비교해 본다. 5절에서는 실험결과에 대하여 논할 것이며 마지막으로 연구의 결과를 요약한다.
2. 문헌 조사
선석 계획은 1990년대부터 수많은 연구가 진행되어 왔으며, 과거에는 이산형과 연속형에 따른 부두의 구조에 대한 연구가 많았다(Lai and Shih, 1992; Imai et al., 2001). 2000년대에 들 어서면서 선석 계획을 수립함에 있어 동적인 환경을 고려하는 연구가 급증하였다. 동적인 환경에는 선박의 도착시간과 안벽 크레인의 생산성이 가장 큰 불확실한 요소로 고려된다. 이러한 동적인 환경에 대처하기 위한 방법에는 두 가지가 있다. 문제가 발생하였을 때 문제가 발생하기 이전의 상태로 회복하기 위한 선석 계획을 수립하는 대응형 계획과 완충 시간을 통해 문제에 대한 준비를 할 수 있는 선석 계획을 수립하는 대비형 계획이 있다(Clausen et al., 2001). 본 논문에서는 이러한 불확실성을 고려한 연구에 중점을 두고 조사하였다.
2.1 Reactive planning(대응형 계획)
Zeng et al.(2011), Li et al.(2015)은 기상, 이전 터미널에서의 생산성 등의 요인으로 선박이 예상 도착시간보다 늦게 도착하였을 때, 이에 대응하여 계획을 재수립하는 방법론에 대해 연구하였다. 각 선박에 대한 최적의 접안 위치가 존재한다고 가정하고, 선박의 출발 지연을 최소화하여 선석 계획을 재 수립하고 안벽 크레인을 재할당하는 모델을 제시하였다. Umang et al.(2017)은 아랍에미리트의 Ras Al Khaimah 항만을 대상으로 선박이 예상 도착시간과 다르게 도착하였을 때, Set partitioning과 Greedy algorithm을 활용하여 선박을 재배치하는 연구를 하였다. Xiang et al.(2018)은 이산형 선석 구조(Discrete berth space)를 가정하고, 컨테이너 터미널의 형태를 2가지로 나누어 선석 계획을 수립했다. 선박의 도착시간의 편차, 안벽 크레인의 작업시간의 편차, 계획되지 않은 선박의 접안, 안벽 크레인의 고장에 대한 시나리오를 통해 모형의 성능을 평가하였다.
2.2 Proactive planning(대비형 계획)
Xu et al.(2012), Rodriguez-Molins et al.(2014)은 선박 사이에 완충 시간을 부여함으로써 선박의 도착시간과 안벽 크레인의 생산성의 불확실성에 대비하여 강건한 선석 계획을 수립하는 방법론에 대해 연구하였다. 선사에게 제공하는 서비스 수준과 선석 계획의 강건함의 균형을 이루기 위해 최적의 완충 시간을 도출하는 모델을 제시하였다. Golias et al.(2014)은 이산형 선석 구조와 선박의 도착시간과 안벽 크레인의 생산성의 불확실성을 가정하고 총 서비스 시간의 평균과 범위를 최소화하는 방법론에 대해 연구하였다. 본 모형은 다목적 최적화 문제로, 유전 알고리즘(Genetic algorithm)을 통해 해를 도출하였다. Du et al.(2010)은 선박 도착시간의 불확실성에 대비한 강건한 초기 선석 계획을 도출하고, 선박이 도착할 때마다 각 선박에 대한 완충 시간을 조절하여 계획을 재수립하였다. 이러한 피드백 절차와 과거 데이터를 활용하여 선박별로 최적의 완충 시간을 도출할 수 있고 플래너가 강건한 계획을 세우는 데 도움이 될 것으로 기대하였다.
3. 수리 모델
3.1 Notation
수리적 모델에 사용될 Notation을 아래와 같이 설정하였다.
입력변수(I nput Variable)
i: 선박의 인덱스
t: 계획 기간의 인덱스
ni: 선박 i에 할당 가능한 안벽 크레인 개수
L: 선석의 총 길이
N: 선박 i의 총 개수
T: 계획 기간 t의 총 길이
Q: 안벽 크레인의 총 개수
ETAi: 선박 i의 예상 도착시간
ETDi: 선박 i에 요구되는 출발시간
li: 선박 i의 길이
ri: 선박 i의 선적/양하 작업에 요구되는 안벽 크레인의 수
h: 선박 간의 최소한으로 요구되는 시간 간격
e: 선박 간의 최소한으로 요구되는 물리적 간격
θi: 선박 i의 완충 시간
C1i: 선박 i의 예상 전배발생비용
C2i: 선박 i의 위치이동비용
wi: 선박 i의 초기 계획 시 접안 위치
δi: 선박 i의 예상 도착시간(ETAi)에 비해 늦은 시간
M: 임의의 큰 양수
결정변수(Decision Variable)
bi: 선박 i의 접안 시간
di: 선박 i의 출발시간
yi: 선박 i의 접안 위치
qitni: 선박 i에 t시점에 ni개의 안벽 크레인이 작업하면 1, 그렇지 않으면 0
3.2 수리적 모델
본 연구는 계약상의 출발시간보다 늦어진 출발시간에 대한 선박별 비용을 최소화하는 초기 선석 계획 모델과 이를 통해 얻은 계획에서 선박의 지연이 발생하였을 때 다시 계획을 수립하는 모델을 수립하고, 완충 시간의 유무에 따른 초기 선석 계획 대비 시간적, 물리적 이탈성 정도를 비교하고자 한다.
3.2.1 초기 선석 계획 모델
(1)은 선석 계획 시 선박의 출발 예정 시간을 최대한 지키기 위한 목적식이다. (2)는 선박의 도착 예정 시간의 이후에 접안하기 위한 제약이며, (3), (4)는 선박 접안 시 부두 범위 내에 위치하기 위한 제약이다. (5)-(7)은 선석 계획 시 선박과 선박 사이의 시간적, 물리적 계획 충돌을 방지한다. (8)-(10)은 안벽 크레인의 할당 시작과 끝 시간을 각각 선박의 접안과 출발시간이 되도록 결정변수들을 서로 결부시킨다. (11)은 선박의 선적 및 양하 물량에 따라 필요한 안벽 크레인 개수를 보장한다. (12)는 항상 터미널이 보유한 안벽 크레인 개수 이내에서 할당되도록 제한한다. (13)은 안벽 크레인의 할당 개수를 정의하며, (14)는 각 선박이 접안하고 있는 동안 연속적인 안벽 크레인 작업을 보장한다. 마지막으로, (15)는 음이 아닌 실수의 결정변수, (16)은 0 또는 1의 값을 가지는 이진 결정변수를 나타낸다.
3.2.2 선석 계획 재수립 모델
선박이 지연되었을 때 계획을 재수립하는 모델은 위의 모델에서 아래의 내용을 변경한다.
우선 (1)의 목적식을 (17)의 목적식으로 바꾼다. (17)은 선박이 계약상의 출발시간을 맞추지 못했을 때 발생하는 비용과 초기 선석 계획 대비 접안 위치의 변화에 따른 비용의 합을 최소화하는 목적식이다.
다음으로 (2)의 제약식을 (18)의 제약식으로 변경한다. (18)은 계획을 재수립할 때, 예상보다 지연된 선박의 도착시간에 따라 그 이후에 선박이 접안할 수 있다는 조건을 나타낸다.
4. 수치시뮬레이션
본 실험은 Intel(R) Core(TM) i7-7700HQ 2.80GHz RAM 16.0GB에서 Gurobi 8.0.1 solver를 사용하였으며, 사용된 데이터는 부산항의 컨테이너 터미널의 데이터를 활용하였다. 선석의 길이는 1200m, 선박의 개수는 20개, 안벽 크레인의 개수는 12개, 선박 간의 요구되는 물리적, 시간적 간격은 각각 34.5m와 2시간으로 한다. 선박의 예정 도착시간과 계약 출발시간, 지연 시간, 선박의 길이 모두 실제 데이터를 정수로 변환하여 사용하였다. 선박의 초기 선석 계획 대비 위치 변동에 따른 비용은
4.1 완충 시간 도입에 따른 효과
실험의 구조는 아래 Fig 2와 같다. 모델 1과 모델 3은 3.2.1에서 설명한 초기 선석 계획 모델인데 둘의 차이는 완충 시간의 유무이다. 모델 1은 완충 시간을 고려하지 않았고 모델 3은 완충 시간을 고려하였다. 이 때 완충 시간은 0, 3, 6의 세 가지 경우에 대해 모든 선박에 동일하게 부여하여 실험하였다. 이후 선박의 지연이 발생하였을 때 계획을 재수립하는 모델이 모델 2와 모델 4이다. 이를 통해 완충 시간이 있을 때와 없을 때 기존 계획에서 어느 정도의 변동이 생겼는지를 파악할 수 있고 모델 2와 모델 4의 목적식 값의 비교를 통해 어느 쪽이 결과적으로 비용이 적게 발생했는지 확인하여 완충 시간의 효과를 검증한다.
The framework of simulation
Table 1을 보면 초기 선석 계획의 목적식 값은 완충 시간이 0일 때와 3일 때는 0으로 동일하고 완충 시간이 6일 때는 커졌으나 재수립 계획에서 목적식 값은 완충 시간이 커질수록 크게 감소한 것을 확인할 수 있다. Fig. 3, Fig. 5, Fig. 7을 보면 실제 초기 계획에 따른 전체 운영시간은 최대 122-124로 비슷하다. 즉, 초기 선석 계획을 수립함에 있어 완충 시간을 사용하더라도 전체적인 계획 기간은 유사하지만 지연 시간에 따라 재수립하면서 발생하는 비용이 감소한다.
Result of simulation
Initial berth plan(buffer time=0h)
Rescheduled berth plan(buffer time=0h)
Initial berth plan(buffer time=3h)
Rescheduled berth plan(buffer time=3h)
Initial berth plan(buffer time=6h)
Rescheduled berth plan(buffer time=6h)
4.2 데이터 기반의 차등적 완충 시간 도입에 따른 효과
본 실험은 과거의 지연 시간 데이터를 기반으로 선박별로 차등적인 완충 시간을 부여하여 효과를 확인한다. Table 2와 같이 선박의 지연 시간 데이터를 통해 각 선박별로 분포를 도출하였다. 각각의 분포를 통해 무작위로 500개의 표본을 추출하여 선박별로 평균적인 지연 시간을 도출한다.
Distribution of delay time
이러한 평균 지연 시간에 따라 차등적인 완충 시간을 부여한다. 실험은 4.1 절에서 선박별로 3과 6으로 균일하게 완충 시간을 부여하였을 때와 동일한 환경 하에 비교하기 위하여 차등적으로 완충 시간을 부여하되 그 평균이 각각 3과 6이 되도록 하였다.
Table 3을 보면 평균 완충 시간에 따라 선박별로 차등적인 완충 시간을 부여하였을 때, 6시간의 완충 시간을 고려한 초기 선석 계획은 다른 선석 계획에 비해 목적식 값이 크지만 실제 지연이 발생하여 재수립계획을 수립함으로써 발생하는 비용이 크게 감소한 것을 확인할 수 있다.
Result of simulation for buffer time based on data
Initial berth plan based on data (average buffer time=3h)
Rescheduled berth plan based on data (average buffer time=3h)
Initial berth plan based on data (average buffer time=6h)
Rescheduled berth plan based on data (average buffer time=6h)
또한, Table 4를 보면 완충 시간을 균등하게 도입할 때보다 데이터에 기반하여 차등적으로 부여할 때, 재수립 계획에서의 비용이 감소한 것을 확인할 수 있다. 이를 통해 단순히 완충 시간을 균등하게 도입하는 것보다 과거의 지연 데이터를 통해 차등적으로 완충 시간을 도입하는 것이 더욱 효과적임을 확인할 수 있다.
The experiment results of the test problems
5. 결 론
여러 가지 불확실한 요소로 인해 선박이 늦게 도착할 경우 초기 선석 계획이 틀어지면서 발생하는 손실이 매우 크다. 이를 방지하기 위해 본 연구에서는 완충 시간을 도입하는 방안을 제시한다.
본 연구에서는 초기 선석 계획을 수립하는 모델과 선박이 예상 도착시간보다 늦게 도착할 때 계획을 재수립하는 모델을 개발하였다. 실제 데이터를 기반으로 완충 시간의 유무에 따른 효과에 대한 모델의 검증을 위해 수치적 실험을 진행하였다. 완충 시간이 커질수록 선박의 지연이 발생하였을 때, 초기 선석 계획이 틀어지면서 발생하는 손실을 더 많이 줄일 수 있었다. 또한 선박별로 과거 데이터를 분석하여 지연 시간의 분포에 따라 차등적인 완충 시간을 도입하였고, 균등하게 완충 시간을 도입하였을 때보다 손실을 더 줄여 효과적임을 확인할 수 있었다.
본 연구에서 데이터 기반의 완충 시간을 도입하는 것이 효과적임을 입증하였지만 현실에 적용하기 위해서는 좀 더 다양한 상황에서의 추가적인 실험이 필요하며 나아가 해양 상태, 선박 운항 정보 등의 다양한 요소를 추가적으로 고려하여 최적의 완충 시간을 도입하는 기준에 대한 세밀한 연구가 필요하다.
Acknowledgements
본 연구는 한국해양과학기술원 부설 선박해양플랜트연구소의 주요연구사업 “스마트 해양안전 및 기업지원을 위한 오픈 플랫폼 기술개발(PES4070)”의 연구결과 중 일부임을 밝힌다.