여유시간을 고려한 다수 자동화 야드 크레인의 이적작업 일정계획
Remarshalling Planning for Multiple Automated Yard Cranes Considering Slack Time
Article information
Abstract
최근 컨테이너 터미널에서는 야드 장비의 자동화 및 환적화물의 증가로 인하여 터미널내의 이적작업이 증가하고 있으며 이에 따라 터미널 운영자들은 효율적인 이적작업 계획을 수립하고자 노력하고 있다. 보통 자동화 컨테이너 터미널에서는 장치장에 다수의 자동화된 야드 크레인을 사용하여 컨테이너를 취급하고 있으며 선적작업의 효율을 높이기 위하여 여유시간대를 이용하여 이적작업을 수행하고 있다. 본 연구 는 블록 내에서 다수의 자동화 야드 크레인이 운영되고 있는 경우의 이적작업 계획을 다루고 있으며 혼합정수계획법을 이용하여 주어진 여유 시간을 고려하여 작업효율을 최대화하는 각 크레인 별 최적 이적작업 계획을 수립하는 수리모형을 제시하였다. 또한 컨테이너 터미널 현장에 서 쉽게 적용할 수 있도록 빠른 시간 안에 이적작업계획을 수립할 수 있는 작업 할당규칙을 찾기 위하여 다섯 가지 대표적인 할당규칙에 대하 여 수치 실험을 통하여 유용성을 분석하였다. 수치 실험 결과 작업할당 규칙 중에서 MR규칙과 MW규칙이 다수 자동화 야드 크레인의 이적작 업 할당규칙으로 좋은 성능을 발휘하는 것으로 나타났다.
Trans Abstract
Recently, container terminal operators have made efforts to develop an efficient remarshalling plan in response to the increase in automation of equipment handling and transport of containers in the terminals. Usually, containers are handled by multiple AYCs(automated yard cranes) in-yard in an automated container terminal, and terminal operators establish a remarshalling plan using slack time to increase the efficiency of ship operation. This study develops the optimal mathematical model through mixed integer programming as a solution to the problem of dispatching multiple AYCs. Considering the difficulty of direct application to the field due to computation time, we analyze the five prototypical dispatching rules for real world adaptation. A numerical experiment found that the maximum weight ratio (MR) rule and the maximum weight (MW) rule are the ideal dispatching solutions to the multiple AYCs dispatching problem.
1. 서 론
최근 우리나라 항만에서는 중국의 경제성장으로 인한 물동 량의 지속적인 증가와 세계 선사들의 허브항을 통한 컨테이너 운송 전략에 따라 국내 터미널의 환적화물 컨테이너가 꾸준히 증가하고 있다. 이로 인하여 컨테이너 터미널에서는 효율적인 이적작업 방안에 대한 관심이 증가하고 있다. 또한 주요 항만 들의 하역장비 자동화가 지속적으로 이루어짐에 따라 효율적 인 하역장비 운영에 대한 요구도 더욱 증대되고 있다. 본 연 구에서는 컨테이너 터미널에서 증가하는 이적작업에 대하여 여유시간을 활용하여 장치장에서 주요 하역장비인 다수의 자 동화 야드 크레인(AYC, Automated Yard Crane)의 효율적인 이적작업 일정계획을 수립하는 연구를 수행하였다. 보통 자동 화 컨테이너 터미널에서는 선적작업을 하지 않는 야간 시간대 나 휴일 등 주간의 특정시간대에 대하여 블록내 이적작업을 수행하고 있다. 따라서 이적작업은 작업가용시간 한도 내에서 효과적인 이적작업이 가능하도록 작업계획을 수립하여야 한 다.
2. 컨테이너 터미널의 이적작업
2.1. 문헌연구
관련 연구 분야로는 컨테이너 터미널의 크레인 작업일정계 획, 작업 재배치 및 이적계획, 크레인 작업할당 등이다. Kim et al.(1998)은 컨테이너 터미널에서 수출 컨테이너의 재배치 에 관한 문제를 다루었으며 작업배분과 이송장비 및 취급장비 의 작업순서 문제로 분할하여 해법을 제시하였다. Yun et al.(2003)은 자동화 컨테이너 터미널의 이적작업에 대하여 무 작위(random) 할당방법과 DOS(Duration of stay) 할당방법을 적용하여 양하작업과 반출입 작업에서 AYC의 작업시간 변화 를 비교하였다. 그러나 이는 운영규칙에 한 비교연구로서 구 체적인 이적작업 계획을 다루지는 않았다. Kim et al.(2004)은 선석에서의 하역장비인 컨테이너 크레인에 대하여 간섭을 고 려한 작업일정계획 문제를 다루었으며 혼합정수계획법을 이 용한 수리모델을 제시하고 분지한계법을 이용한 작업일정계 획을 제시하였다. Kang et al.(2005)은 휴리스틱을 이용하여 적하작업 과정에서 재취급이 발생하지 않게 컨테이너들을 이 적할 수 있는 컨테이너 이동 순서를 찾는 방안을 제안하였다. 또한 시뮬레이션을 통하여 제안 방안이 다양한 환경에서 컨테 이너 이동 순서를 실시간에 생성할 수 있음을 보였다. Oh et al.(2005)는 이적작업시간이 충분하게 주어진 경우에 교차가 불가능한 크레인들 간의 간섭을 고려하여 목적 베이에서 재취 급이 최소화되도록 개별 컨테이너를 취급할 크레인을 선정하 고 컨테이너의 장치위치를 결정하는 휴리스틱을 제안하였다. Bae et al.(2008)은 자동화 컨테이너 터미널에서 수출 컨테이 너의 시간 가치를 고려한 이적작업 계획을 다루었다. 이들은 적하작업의 효율성을 높이도록 장치장의 공간을 고려하여 이 적계획을 수립하는 방법을 제시하였지만 이적작업 시간이 충 분하게 주어진 경우를 가정하고 이적계획을 다루었다. Bae et al.(2011)은 컨테이너 터미널에 반입되는 수출 컨테이너에 대 하여 작업순서와 장치위치를 동시에 결정하는 문제에 대한 혼 합정수 모형과 휴리스틱 방법을 제안하였다. Bae et al.(2012) 은 작업가능시간이 한정되어 있는 경우 이적작업의 효과를 최 대화하기 위해 가능한 이적작업 중에서 효율적인 이적작업을 선정하고 이들의 작업순서를 정하는 것으로 혼합정수계획법 을 활용하여 수리모형을 개발하고 5가지 휴리스틱기법을 제 시하여 그 성능을 비교하였다. 이 연구의 제한점으로는 야드 의 블록 내에서 작업하는 AYC가 1대 인 것으로 가정하였다 는 점이다. 이는 야드 운영이 자동화된 터미널에서는 블록 내 에서 실제로 다수의 AYC가 운영되고 있는 것을 고려하지 못 한 제한점이 있다고 볼 수 있다. 본 연구에서는 Bae et al.(2012)의 연구와 유사한 문제를 다루고 있지만 야드의 블록 내에서 작업하는 다수 AYC의 이적작업 계획을 다루었다는 점에서 차이점이 있다. 또한 단일 AYC 작업과는 달리 다수의 AYC 작업을 고려할 때에는 반드시 AYC 간의 간섭도 함께 고려하여 주어진 시간 내에 효과적인 이적작업 계획을 수립해 야 한다. Kim et al.(2003)은 다수 크레인의 이적작업 계획과 유사한 문제에 대한 관련 연구를 수행하였는데 컨테이너 터미 널과 같은 동적 환경에서는 전체 작업일정을 계획하는 것 보 다는 바로 작업해야 하는 작업을 선택하는 작업할당 규칙이 오히려 우수한 해를 제공하기도 함을 보였다. 따라서 본 연구 에서는 여유시간 내에서 가능한 이적작업 중 효과적인 작업을 수행할 수 있는 작업할당 규칙을 다루고자 한다.
2.2. 문제정의
본 연구는 수직배치형 자동화 컨테이너 터미널의 장치장에 서 작업을 수행하는 자동화 야드 크레인인 AYC의 이적작업 결정 문제를 다루었다. Fig. 1과 같은 수직배치형 자동화 컨테 이너 터미널에서 일반적으로 장치장은 여러 개의 블록(Block) 으로 구성되어 있으며 하나의 블록은 여러 개의 베이(Bay)로 구성되어 있고 한 블록 안에는 다수의 AYC가 하역작업을 수 행하고 있다.
Automated yard cranes in container terminal yard
수직배치형 자동화 컨테이너 터미널의 장치장에서는 선박 에 컨테이너를 실거나 내리는 본선 작업요청과 게이트를 통한 트럭의 반출입 작업요청이 무작위로 발생한다. 또한 효율적인 본선 작업과 반출입 작업 수행을 위하여 컨테이너를 육측이나 해측 TP(Transfer Point)에 가까운 위치로 재배치하는 이적작 업이 필요하며 보통 야드 크레인의 여유시간을 활용하여 이적 작업을 수행하게 된다. 이때 여유시간이 충분히 많은 경우에 는 이적작업을 모두 처리할 수 있지만 본 연구에서와 같이 여 유시간이 한정된 경우에는 여러 가지 이적작업 중에서 선별적 으로 작업을 수행하여야 한다. 이런 경우에는 본선 작업의 임 박정도나 선사의 긴급 반출입 작업요청 여부 등과 같이 이적 작업의 가중치를 고려하여 이적작업 대상을 결정하여야 한다. 본 연구는 장치장내 하나의 블록 내에서 이적작업을 수행할 수 있는 AYC가 여러 대인 경우 각 AYC에 이적작업 대상과 이적작업 순서를 결정하는 문제를 다루었다. Fig. 1과 같이 장 치장에는 하나의 블록에 동일한 크기의 여러 대의 AYC가 작 업하는 경우를 다루고 있기 때문에 원활한 작업계획을 수립하 기 위해서는 AYC간의 간섭고려가 반드시 필요하다. AYC간 의 간섭은 크게 두 가지로 구분할 수 있다. 첫 번째는 AYC가 서로 가까운 곳에서 작업을 수행해야 하는 경우 안전상의 문 제가 발생하기 때문에 인접하여 작업하는 AYC는 일정거리 만큼 떨어져 있어야 한다는 것이다. 두 번째로는 작업해야하 는 작업의 위치가 이웃하는 AYC보다 더 먼 곳에 있어서 이 웃 AYC를 지나가야 하는 작업 불가능한 상황이 발생한다. 본 연구에서는 블록 내에서 다수의 크레인이 이적작업을 수행하 는 경우 두 가지 종류의 AYC 간섭이 발생하지 않도록 주어 진 여유시간 내에서 다수 AYC에 대한 이적작업 계획을 수립 하는 문제를 다루었다.
3. 혼합정수모형
수직배치형 자동화 컨테이너 터미널에서 하나의 블록 내에 다수의 AYC가 운영되는 경우 여유시간 내에서 최적 이적작 업 계획 수립을 위한 혼합정수모형을 제시하였으며 모형에 사 용된 입력변수 및 의사결정변수는 다음과 같다.
c : AYC c = 1, 2 ..., C. 증가 순으로 정렬되어있다.
S, T : 가상의 초기 작업(S) 및 가상의 마지막 작업(T).
Ai : 작업 i의 현재장치위치.
Ri : 작업 i의 재취급 위치.
Tpd : 야드 크레인의 하차 및 장치작업시간.
Tb : 야드 크레인이 1 베이를 이동하는데 소요되는 시간(부하, 무부하 동일하게 가정).
T max : AYC의 최대 작업가능시간(여유시간).
Lc : 야드크레인 c의 초기 및 최종 위치.
wi : 작업 i에 대한 가중치, 즉 본선 작업의 긴급도나 이적작업 긴급 요청에 따른 작업의 중요도.
Θ : 작업의 안전상 동시 작업이 불가능한 작업들(
Yc : AYC의 작업 종료시간(의사결정변수).
Ti : 작업 i의 완료시간(의사결정변수).
yij : 작업 i가 끝 난 후에 작업 j를 시작하면 1 아니면 0(의사결정변수).
이적 작업을 수행할 수 있는 여유시간(Tmax)이 제한되어 있는 경우 다수 AYC의 효과적인 이적작업계획을 수립하는 혼합정 수모형은 다음의 식(1)-(13)과 같다.
식 (1)은 목적함수로서 컨테이너 이적작업에 대한 작업효과 를 최대화하는 것이다. 여기서 wi는 이적작업의 효과를 의미 하는 가중치로서 Bae et al.(2008)과 Bae et al.(2012)의 연구에 서 제시한 바와 같이 이적작업과 관련된 본선 작업의 긴급도 나 선사 등의 긴급 반출입 작업요청을 고려하여 이적작업의 가중치를 산정할 수 있다. 따라서 식 (1)은 여유시간 내에서 다수의 크레인을 이용하여 가능한 가중치가 크면서 이동 및 작업에 필요한 시간이 작아 상대적으로 이적작업의 효과가 큰 이적작업을 우선적으로 수행하고자 함이다. 식 (2)는 작업을 시작하는 가상의 첫 작업을 나타내며 식 (3)은 가상의 마지막 작업을 의미한다. 식 (4)는 컨테이너에 대한 이적작업은 최대 한번 수행되어야 함을 의미하고 식 (5)는 작업의 흐름균형을 나타내는 제약이다. 식 (6)은 작업순서 및 작업위치에 따른 작 업 수행완료(장치)시간을 의미한다. 식 (7)은 변수 yij의 값이 1인 경우에 작업 완료시간과의 관계를 나타내고, 식 (8)은 작 업의 안전상 동시 작업 수행이 불가능한 작업들에 대한 제약 을 나타낸다. 즉 동시에 작업이 수행되면 안 되는 작업들에 대해서는 둘 중 하나는 반드시 작업이 끝난 후에 다른 작업이 시작되어야 함을 나타낸다. 식 (9)는 동일 선상에서 작업을 수 행하는 AYC의 특성을 고려하여 AYC에 의해 동시에 작업이 이루어지는 작업들은 AYC들의 간섭이 발생하지 않도록 하는 것이다. 식 (10)은 각 AYC의 마지막 작업의 완료시간은 주어 진 여유시간 내에 완료되어야 함을 의미한다. 식 (11)은 각 크 레인의 마지막 작업 수행 시 해당 작업의 완료시간을 결정한 다. 식 (12)와 식 (13)은 각 변수들이 값을 가질 수 있는 범위 를 나타내고 있다.
Table 1은 Bae et al.(2012) 연구에서 사용된 단일 AYC의 이적작업 결정에 사용된 데이터를 이용하여 블록내 작업 AYC가 두 대인 경우의 이적작업 일정계획을 수립하였다. AYC의 이동과 관련된 Tb는 0.5단위시간(왕복 1단위시간), 인 출 및 장치와 관련된 Tpd는 1단위시간으로 설정하였다.
Remarshalling operations requested from planning
두 AYC의 초기위치는 양끝쪽 이송지점인 TP(0, G)에 위치 하는 것으로 가정하였다. 실험 결과 Table 2에서 보는 바와 같이Tmax값이 증가할수록 목적함수의 값과 수행시간 둘 다 증가함을 알 수 있다. Table 2에서 Tmax가 30단위시간 이상인 경우 수행시간이 감소한 이유는 예제에서 작업에 필요한 시간 에 비해 작업 여유시간이 충분히 많은 경우로서 작업순서와 무관하게 모든 작업을 수행할 수 있으므로 프로그램 수행시간 이 줄어든 경우이다.
The optimal remarshalling schedule
4. 작업 할당규칙
본 연구에서는 작업 할당문제에서 짧은 시간에 좋은 성능 의 해을 찾기 위하여 많이 사용되고 있는 규칙들로서 이전 Bae et el.(2012) 연구에서 사용된 할당규칙들을 간섭을 고려 하여 수정하여 적용하였다. Bae et al.(2012)의 연구는 블록내 단일 AYC에 대한 이적작업 할당규칙에 대하여 다음의 5가지 할당규칙을 검토하였는데 본 연구에서는 블록내 다수의 AYC 가 운영되는 경우 두 종류의 간섭 현상을 고려하여 간섭이 발 생하지 않는 작업을 대상으로 이적작업 할당 규칙을 적용하여 분석하였다. 이전에 적용된 5가지 할당규칙을 소개하면 다음 과 같다.
① Shortest Processing Time rule(SPT) : AYC의 현 위치에 서 주어진 시간을 고려하여 처리 가능한 작업 중에서 가장 빨 리 완료할 수 있는 이적작업을 선택하여 수행한다.
② Maximum Weight rule(MW) : AYC의 현 위치에서 처리 가능한 이적작업 중에서 가중치(wi)가 가장 큰 이적작업을 선 택하여 수행한다.
③ Maximum weight Ratio rule(MR) : AYC의 현 위치에서 처 리 가능한 작업 중에서 작업시간당 가중치(wi)가 가장 큰 이적 작업을 선택하여 수행한다.
④ Largest Processing Time rule(LPT) : AYC의 현 위치에서 처리 가능한 작업 중에서 작업시간이 가장 큰 이적작업을 선택 하여 수행한다.
⑤ Minimum Empty Travel distance rule(MET) : AYC의 현 위치에서 처리 가능한 작업 중에서 빈 이동시간이 가장 작은 (가장 가까운) 이적작업을 선택하여 수행한다.
이적 작업수 n이 10개, 50개, 100개이며 각각 Tmax가 30, 60, 120 단위시간인 세 가지 종류에 대하여 각각 10개씩 총 30 가지 문제를 무작위로 입력 자료를 생성하여 다섯 가지 작업 할당 규칙에 대하여 비교실험을 수행하였다.
Table 3은 작업 수 n이 10이고 최대 작업가능시간 Tmax가 30 단위시간인 10가지 예제에 대한 할당규칙의 적용결과를 보 여주고 있다. 10가지 예제에 대하여 할당규칙을 적용한 결과 할당규칙 중 MR규칙이 7가지 예제에서 성능이 가장 좋은 것 으로 나타났으며, MW규칙도 3가지 예제에서 성능이 가장 우 수한 것으로 나타났다. 또한 10개 예제에 대하여 LINDO 프로 그램을 이용하여 최대 700,000 Iteration을 시행하여 하한값 (LB)과 상한값(UB)구하였으며 UB와 할당규칙 중 가장 좋은 규칙의 목적함수 값과의 성능비(UB/OV)를 구한 결과 평균 1.27, 최대 1.41로 나타났으며 제시된 할당규칙은 모두 1초 이 내의 짧은 수행시간을 보여 비교적 좋은 성능을 발휘하는 것 으로 판단된다.
The result of dispatching rules for 10 examples (Tmax =30 for n=10)
Fig. 2는 n이 10인 10가지 예제에 대한 각 할당규칙의 목적 함수 값을 보여주고 있다. 앞서 설명한 바와 같이 MR규칙과 MW규칙, MET규칙이 우수한 성능을 나타내며 LPT규칙이 가장 성능이 낮은 것으로 분석되었다.
Objective values of dispatching rules(Tmax=30, n=10)
Fig. 3은 각 할당규칙에 대한 최대 작업가능시간의 활용정 도를 보여주고 있는데 LPT규칙이 활용도가 가장 높으며 MR 규칙과 MW규칙도 활용도가 상당히 높은 것으로 나타났다.
The average time usage rate of dispatching rules(Tmax=30, n=10)
Fig. 4는 각 할당규칙에 대한 여유시간내의 평균작업처리 개수를 보여주고 있는데 LPT규칙이 작업처리 개수가 가장 적 고 MR규칙과 MET규칙이 가장 많은 이적작업을 처리함을 알 수 있다.
The average number of completed job of dispatching rules(Tmax=30, n=10)
Fig. 5는 작업수가 50개이고 Tmax가 60단위시간인 10가지 예제에 대한 각 할당규칙의 목적함수 값을 보여주고 있다. 작 업개수가 10개인 경우와 마찬가지로 MR규칙과 MW규칙이 우수한 성능을 나타내는 것으로 분석되었다.
Objective values of dispatching rules(Tmax=60, n=50)
Fig. 6은 각 할당규칙에 대한 최대 작업가능시간(여유시간) 의 활용정도를 보여주고 있는데 작업개수가 10인 경우와 달리 작업개수 50개인 경우에는 모두 90%이상으로 각 할당규칙들 간의 활용도의 차이가 크지 않은 것으로 나타났다.
The average time usage of dispatching rules(Tmax=60, n=50)
Fig. 7은 작업수가 100개이고 최대 작업가능시간(여유시간) Tmax가 120단위시간인 10가지 예제에 대한 각 할당규칙의 목 적함수 값을 보여주고 있다. 또한 작업개수가 10개, 50개 인 경우와 마찬가지로 작업수가 100개 인 경우에도 프로그램 수 행시간은 1초 이내로 나타났으며 MR규칙이 가장 우수하고 MW규칙과 MET규칙이 그다음으로 좋은 성능을 나타내는 것 으로 나타났다.
Objective values of dispatching rules(Tmax=120, n=100)
Fig. 8은 각 할당규칙별 평균작업처리 개수를 보여주고 있 는데 모든 규칙이 100개의 작업 수에 대하여 50%이하로 처리 하고 있으며 그중에서 MR규칙과 MET규칙이 가장 많은 이적 작업을 처리하고 있으며 LPT규칙이 가장 적은 작업을 처리함 을 알 수 있다.
The average number of completed job of dispatching rules(Tmax=120, n=100)
5. 결 론
본 연구는 수직배치형 자동화 컨테이너 터미널의 장치장 에서 하나의 블록에 다수의 AYC가 작업을 수행하는 경우 한 정된 여유시간을 활용한 다수 AYC의 이적작업 일정계획 문 제를 다루었다. 혼합정수모형을 이용한 수리모델을 제시하였 으며 LINDO 프로그램을 이용하여 간단한 문제에 대한 최적 해를 제시하였다. 실제 현장에서 이적작업 시 활용할 수 있는 간단한 작업할당 규칙을 제시하여 작업수가 적은 경우에 대하 여 그 성능을 수리모델 결과와 비교분석하였다. 또한, 작업수 가 10개, 50개, 100개인 세 가지 종류 각각 10개씩, 총 30가지 문제에 대하여 다섯 가지 작업할당 규칙을 실험하여 분석한 결과 MR규칙과 MW규칙이 이적작업의 효과도가 높고 이적 작업 처리 개수에서도 좋은 결과를 나타내어 다수 AYC의 이 적작업 할당 규칙으로 적합한 것으로 분석되었다. 이적작업의 가중치를 고려한 MR규칙과 MW규칙이 효과적이라는 연구결 과는 한정된 여유시간 내의 이적작업은 본선 작업이 임박하여 빠른 이적작업이 요구되거나 선사의 긴급 반출입 작업요청 등 과 같이 이적작업의 가중치가 큰 작업을 우선적으로 수행하는 것이 더욱 효과적임을 나타내고 있다. 향후 연구 분야로 복잡 하지 않으면서도 MR규칙보다 이적 작업 효과가 높은 작업규 칙을 개발하는 것과 블록 내 이적작업 뿐만 아니라 블록 간 이적작업이 가능한 수평배치형 자동화 컨테이너 터미널에 대 한 이적작업 규칙 연구가 필요한 것으로 생각된다.