컨테이너 터미널의 해측 생산성 극대화를 위한 YT 배차 전략 최적화

Optimization of YT Dispatching Policy for Maximizing Quay Side Productivity in Container Terminals

Article information

J Navig Port Res. 2020;44(3):227-234
* 부산대학교 대학원 박사과정생 kimt86@pusan.ac.kr 051)510-3531
부산대학교 전기컴퓨터공학과 교수
김 태광*, 류 광렬
* Student, Graduate School of Pusan National University, Busan 46241, Korea kimt86@pusan.ac.kr 051)510-3531
Professor, Department of Electrical and Computer Engineering, Pusan National University, Busan 46241, Korea
Corresponding author: 종신회원, krryu@pusan.ac.kr 051)510-2453
Received 2020 March 12; Revised 2020 April 18; Accepted 2020 April 25.

Abstract

컨테이너 터미널에서 가장 중요한 운영 목표 중 하나는 각 선박에 대한 서비스 시간을 최소화함으로써 안벽의 생산성을 극대화하 는 것이다. 선박에 대한 서비스 시간을 최소화하기 위해서는 선박에 컨테이너를 싣고 내리는 해측의 안벽 크레인(QC: Quay Crane) 작업이 지연 없이 계속되어 그 효율이 극대화되어야 한다. 본 논문은 장치장과 QC 간 컨테이너 운반을 담당하는 트럭인 YT(Yard Tractor)의 운영 을 효율화함으로써 QC가 YT를 기다리게 되는 지체 상황을 최소화할 수 있도록 해 주는 전략 기반의 YT 배차 방안을 사용할 것을 제안한다. 특히 본 논문에서는 실제 컨테이너 터미널에의 적용을 위해 기존에 제안된 전략을 수정 보완하고, 실제 터미널 데이터를 이용한 시뮬레이션 실험을 통해 그 효과를 검증한다.

Trans Abstract

One of the most important operational goals in container terminals is to maximize the quay side productivity by minimizing the turnaround times of the vessels, for which the operations of the quay cranes (QC) to load/unload containers onto/ from the vessels should be conducted efficiently without delays. This paper suggests using a policy-based dispatching method for YTs (Yard Tractor) that deliver containers between QCs and the storage yard. The goal of using such a dispatching policy is to maximize the efficiency of the YT operation and accordingly to minimize the QC delays because of late arrivals of the YTs. In particular, in this paper, we modified the previously proposed policy for its application to real container terminal and verified the effect through simulation experiments using real terminal data.

1. 서 론

컨테이너 터미널에서는 선박에 컨테이너를 싣거나(적하) 내리기(양하) 위해 여러 대의 안벽 크레인(QC: Quay Crane) 과 수십 대의 운반용 트럭(YT: Yard Tractor)이 사용된다. 특 히, 선박에 대한 서비스 시간을 최소화하여 생산성을 극대화 하기 위해 QC 작업의 지연을 줄이는 것은 터미널의 중요한 운영 목표 중 하나이다. QC 작업이 지연되는 주요 요인은 크 게 두 가지로서, 첫째는 컨테이너의 임시 저장소인 장치장에 서 해당 컨테이너들에 대한 처리가 지연됨으로써 그 효과가 QC 지연으로 나타나는 것이고, 둘째는 장치장과 QC 사이에 서 컨테이너를 운반하는 YT의 운영이 원활하지 못해서 QC가 YT를 기다리게 되는 상황이 발생하는 것이다. 본 논문에서는 이 중 후자와 관계되는 YT의 운영 효율화를 통하여 QC의 생 산성을 극대화하는 것을 대상 문제로 한다.

선박의 하역 작업을 지연 없이 처리하려면 QC와 YT 간의 긴밀한 상호협동이 필요한데, 이를 위해서는 적절한 YT가 적 시에 적절한 작업을 하도록 작업을 배정하는 것이 매우 중요 하다. YT 작업 배정에 흔히 쓰이는 가장 간단한 방법은 휴리 스틱 배차(heuristic dispatching)이다. 이 방안은 대기 중인 운 반작업 중 가장 긴급한 작업을 우선으로 선택하거나, 혹은 현 재 YT의 위치에서 가장 가까운 작업을 우선으로 선택하는 등 의 간단한 규칙에 따라 작업을 배정한다(Egbelu and Tanchoco, 1984; Yamashita, 2001; Briskorn et al., 2006). 구 현이 쉽고 간단하며 계산 비용이 낮아 실시간에 사용하기 좋 다는 장점이 있으나 미래 작업을 고려하지 못해 근시안적이라 는 한계를 지닌다. 이러한 한계를 극복하기 위해 최적 계획을 수립하여 작업을 배정하는 방안이 연구되었다(Kim and Bae, 1999; Kim and Bae, 2004; Nguyen and Kim, 2009). 이들 방 안은 일정 시간(horizon) 내의 미래 작업을 대상으로 최적화 알고리즘 등을 통해 최적의 배차 계획을 수립한 뒤, 이 계획에 따라 YT에 작업을 배정한다. 하지만 동원되는 장비의 수가 많거나 horizon이 길어질수록 최적 계획을 수립하는데 드는 계산 비용이 기하급수적으로 늘어나 실시간 적용이 어렵게 된 다. 이에, 근시안적이지 않으면서도 실시간 적용이 용이한 전 략(policy) 기반의 작업 배정 방안이 제안되었다(Park et al., 2011; Kim et al., 2013; Kim et al., 2014). 이 방안은 여러 가 지 평가 기준을 가지고 후보작업들의 점수를 계산하여 취합한 뒤 점수가 가장 좋은 것을 선택하여 작업을 배정하는 방식으 로, 단순한 규칙으로 작업을 배정하는 휴리스틱 배차 방법보 다 성능적으로 더 효과적일 뿐만 아니라 계산 부담도 거의 없 어 실시간 적용에도 문제가 없다는 장점을 지닌다.

본 논문에서는 기존에 제안된 전략 기반의 작업 배정 방식 을 이용하되 실제 컨테이너 터미널에의 적용에 문제가 없도록 평가 기준들을 수정 보완하였으며, 그 효과를 검증하기 위해 실제 터미널 데이터를 이용하여 시뮬레이션 실험을 수행하였 다. 실험 결과, 새로 제안된 전략 기반의 배차 방식이 터미널 에서 사용하고 있는 기존 배차 방식에 비해 더 높은 운영효율 을 보임을 확인하였다. 특히 제안 방안을 도입할 경우, 기존 배차 방식을 따랐을 때의 해측 생산성을 능가하면서도 YT 투 입 대수를 크게 줄일 수 있어서 상당한 운영비용 절감 효과도 기대할 수 있는 것으로 나타났다.

본 논문의 구성은 다음과 같다. 2장에서는 YT 운영 문제를 상세히 설명하고 YT 배차와 관련된 기존 연구를 소개한다. 3 장에서는 본 논문에서 제안하는 YT 배차 방안을 제시하고 4 장에서는 제안 방안의 성능 검증을 위해 여러 가지 방안들과 비교한 실험 결과를 살펴본다. 마지막으로 5장에서 결론을 내 린다.

2. YT 운영 문제 및 관련 연구

본 장에서는 YT 운영 문제를 소개한 후 YT 작업 배정에 관한 과거 연구를 살펴본다.

2.1 YT 운영 문제

컨테이너 터미널은 Fig. 1에서 보듯이 크게 나누어 선박이 접안하는 안벽(quay)과 컨테이너가 임시로 저장되는 장치장 (yard) 및 배후지(hinterland)의 세 영역으로 구분된다. 안벽에 설치된 QC는 선박으로부터 수입 컨테이너를 양하하거나 수출 컨테이너를 선박으로 적하하는 대형 크레인이다. 컨테이너에 는 20ft와 40ft의 두 가지 크기가 있다. 일반적으로 40ft 컨테 이너는 QC가 한 번에 하나씩을 처리하지만, 20ft 컨테이너는 소위 twin 작업이라 하여 QC가 한꺼번에 2개를 동시에 처리 함으로써 생산성 향상을 시도하는 경우가 많다. YT는 수출입 컨테이너를 안벽과 장치장 간에 운반하는 역할을 한다. 보통 YT는 한 번에 20ft 컨테이너 2개 또는 40ft 컨테이너 1개를 운반 할 수 있으며, QC로부터 수입 컨테이너를 받아 장치장 크레인(YC: Yard Crane)에 전달해 주거나 YC로부터 수출 컨 테이너를 받아 QC에게 전달한다. QC가 선박의 컨테이너를 양하 및 적하하는 작업은 사전에 수립된 계획에 따라 순서대 로 처리된다. 양하 계획은 보통 작업 편의성을 고려하여 선박 내 위쪽에 적재된 컨테이너들을 먼저 내리는 방식으로 순서를 부여한다. 그러나 적하 계획에서는 목적항이 먼 컨테이너일수 록 선박의 아래쪽으로 실어야 한다거나 중량이 무거운 컨테이 너를 가벼운 것보다 가능한 아래쪽에 두어 선박의 안정성을 확보해야 한다는 등의 복잡한 제약들을 고려하여 작업 순서가 결정된다. 특히 적하 작업의 경우 계획된 순서와 다르게 컨테 이너를 선박에 실을 수 없기 때문에, YT 배차가 잘못되어 QC 가 YT를 기다리게 되거나 아니면 YT가 QC 아래에서 대기해 야 하는 일이 없도록 주의해야 한다.

Fig. 1

Container terminal layout

YT 운반작업은 보통 무부하 주행, 컨테이너 싣기, 부하 주 행, 컨테이너 내리기의 4단계를 거쳐 수행된다. 무부하 주행 단계는 YT가 컨테이너를 싣지 않고 크레인으로부터 컨테이 너를 받을 위치까지 공차 상태로 주행하는 단계이다. 컨테이 너 싣기 단계는 YT가 무부하 주행을 완료하고 크레인으로부 터 컨테이너를 받는 핸드오버(handover) 단계이다. 부하 주행 단계는 YT가 컨테이너를 싣고 컨테이너를 건네줄 크레인으 로 주행하는 단계이며 컨테이너 내리기 단계는 상대 크레인이 YT가 싣고 온 컨테이너를 집어 내리는 핸드오버 단계이다. 그러나 YT가 twin 작업을 할 때는 작업의 수행 단계가 더 늘 어나게 된다. 장치장의 YC가 QC와는 달리 20ft 컨테이너 2개 를 한꺼번에 처리할 수 없기 때문이다. YT가 수입 컨테이너 2개를 동시에 운반하는 twin 작업 처리 단계를 예로 들어 보 겠다. YT는 먼저 QC로 무부하 주행 후 그 QC로부터 컨테이 너 2개를 한 번에 받는다. 그 다음 이것들을 싣고 첫 목표 YC 로 부하 주행한 후 그 YC에 컨테이너 하나를 건네준다. 그리 고 남은 컨테이너를 장치할 다음 YC로 부하 주행을 한 후 그 YC에 컨테이너를 넘겨주면서 twin 작업이 완료된다. 물론 두 컨테이너 모두를 같은 YC가 처리하는 경우 마지막 부하 주행 단계는 생략된다. 즉, 수입 twin 작업의 경우 보통의 4단계 후 에 부하 주행과 컨테이너 내리기 단계가 추가되고 수출 twin 작업의 경우 원래의 무부하 주행 및 컨테이너 싣기 단계 후에 부하 주행과 컨테이너 싣기 단계가 추가되는 것이다. 이처럼 twin 작업은 일반 작업과는 달리 더 복잡한 처리 과정을 거치 므로 효율적인 YT 작업 배정을 하려면 보다 면밀한 주의가 필요하다.

해측 생산성 극대화를 위해서는 QC가 양적하 작업 중 YT 를 기다리게 되는 일이 없도록 YT의 운반작업이 이루어져야 한다. 이를 위해서는 위에서 언급한 QC의 양적하 순서에 따 라 어김없이 YT가 QC의 작업을 뒷받침해 줄 수 있어야 한다. 이런 이유로 YT의 배차는 양적하 순서상 앞쪽의 작업들을 일 단 후보로 삼은 다음 그중 작업 효율 상 가장 유리하다고 판 단되는 것을 선택하는 방식으로 결정된다. 운반작업의 효율은 어떤 YT가 어떤 컨테이너를 운반하는가에 따라 달라질 수 있 고 그에 따라 해측 생산성도 달라지게 된다. 예를 들어 당장 하역이 급한 QC의 컨테이너를 운반하는 작업을 위해서는 대 상 QC로부터 멀리 떨어진 YT보다는 가까이 위치한 YT를 투 입하는 것이 그 QC의 지연을 줄이는 데 도움이 될 것이다. YT의 작업 배정 방식은 크게 두 가지로 나누어진다. 작업이 발생할 때마다 그 작업이 적절한 차량을 선택하도록 하는 작 업 발주(job-initiative) 방식과 배정된 작업을 완료한 차량이 다음에 수행하기에 가장 적절한 작업을 선택하게 하는 차량 발주(vehicle-initiative) 방식이 있다. 본 논문의 제안 방안은 차량 발주 방식을 따르고 있다.

운반작업 배정 범위의 관점에서 볼 때 YT의 운영 방식은 크게 local pooling 방식과 global pooling 방식으로 나눌 수 있다. 국내 대부분의 컨테이너 터미널에서는 선박별로 그 선 박의 양적하 작업들을 전담하는 YT 조를 구성하여 운반을 담 당하게 하는 local pooling 방식을 사용하고 있다. 이 방식에 의하면 각 YT가 자신이 담당하는 선박의 작업만 수행하면 되 므로 운영 계획이 간단하고 쉬운 대신 작업 배정의 유연성이 떨어진다는 한계를 지니고 있다. 대표적인 문제로는 소위 말 하는 dual cycle이 어려워진다는 점을 들 수 있다. Dual cycle 이란 어떤 YT가 한 작업을 완료한 후 이어서 바로 인접한 위 치의 작업을 다음 작업으로 선택함으로써 공차주행을 줄이는 것을 말한다. Dual cycle 작업을 하게 되면 작업 효율 측면에 서 훨씬 유리하지만 local pooling 방식에서는 자기 조에 속한 작업이 아니면 인접 작업이라 하더라도 수행할 수 없기 때문 에 문제가 된다. 보다 구체적인 예로서, 어떤 YT가 한 선박의 QC로 적하 컨테이너를 가져다준 뒤 후속 작업으로 바로 이웃 선박을 서비스하는 인접 QC의 양하 컨테이너를 운반하게 된 다면 공차주행 거리를 줄이는 효과를 볼 수 있겠지만, local pooling 방식에서는 이웃 선박의 작업을 수행하는 것이 허용 되지 않아서 이러한 dual cycle 작업이 불가능하게 된다. 그럼 에도 불구하고 실제 현장에서 local pooling 방식이 많이 채택 되고 있는 이유는, YT 운영이 아직 시스템에 의해서 이루어 지기 보다는 현장 전문가의 수작업 계획에 의존하여 이루어지 고 있기 때문으로 보인다. 본 논문에서 채택하는 YT 운영 방 식은 모든 YT가 모든 QC를 상대로 서비스할 수 있게 하는 global pooling 방식이다.

2.2 관련 연구

서론에서 YT 작업 배정에 많이 적용되는 방안으로 휴리스 틱 규칙, 최적화 계획, 전략 기반 방안을 소개하였다. 본 절에 서는 각 방안의 대표적인 기존 연구들을 살펴본다.

휴리스틱 규칙 방안은 주로 도메인 지식을 활용하여 간단 하게 후보작업 중 하나를 선택하는 규칙을 만든 후, 이를 이용 하여 수행할 작업을 결정하는 방법이다. YT 작업 배정을 위 한 규칙의 예로는 이미 언급했듯이 작업 마감시간이 제일 급 한 작업을 선택한다든지, YT로부터 가장 가까이에 있는 작업 을 선택하는 등의 규칙이 있을 수 있다. Egbelu and Tanchoco(1984)는 자동화공장의 AGV(automated guided vehicle) 시스템을 대상으로 EDF(earliest due-time first), STD/T(shortest travel distance/time first) 등의 배차 규칙의 성능을 비교한 바 있으며 Yamashita, H.(2001)Briskorn et al.(2006) 또한 AGV에 작업 배정을 위해 다양한 휴리스틱 규 칙을 이용하였다. 이러한 휴리스틱 방안은 단순하고 계산 비 용이 적어 실시간에 적용이 쉬운 데다가 현장 전문가의 도메 인 지식을 잘 활용하면 그 성능 또한 우수하다. 하지만 규칙의 성능이 전문가의 역량에 따라 좌지우지된다는 점과 EDF 및 STD/T와 같이 단일 평가 기준으로 설계된 규칙의 경우 근시 안적인 의사결정으로 그 효율이 떨어질 수 있다는 점을 한계 점으로 들 수 있다.

최적화 계획 방안은 근시안적인 의사결정을 피하고자 일정 범위의 미래 작업에 대해 최적의 계획을 수립하고 이 계획에 따라 수행할 작업을 배정하는 방법이다. Kim and Bae(1999, 2004)Nguyen and Kim(2009)의 연구에서는 AGV 및 ALV(automated lifting vehicle)와 같은 자동화 이송 차량의 작업 배정을 위한 혼합정수계획(MIP) 모델을 제시하고 이 모 델의 최적 해를 계산하여 계획을 수립하였다. 하지만 이러한 MIP 모델의 최적 해를 계산하는 비용은 계획 대상 장비와 작 업 수가 늘어날수록 기하급수적으로 늘어나므로 문제 규모가 조금만 커져도 실시간 적용이 어렵다는 한계가 있다. 예를 들 어 Nguyen and Kim(2009)의 연구를 보면, QC 2대에 대한 작 업을 8대의 차량에 배정하는 문제를 풀 때 각 QC의 작업 12개 까지를 대상으로 최적 계획을 수립하는 데 35분이 소요되었다.

전략을 기반으로 한 방안은 다양한 평가 기준으로 일정 기 간 내에 해야 할 작업을 평가하며 그 평가값의 가중 합을 이 용하여 우선 할 작업을 선택한다. 여기서 가중치 조합이 달라 지면 그에 따라 선택되는 작업이 달라지므로 이들 평가값의 가중치 조합을 전략으로 볼 수 있으며, 탐색 알고리즘 등을 이 용하여 가중치 조합을 최적화한 전략을 작업 배정에 사용한 다. Kim et al.(2013)은 자동화 컨테이너 터미널의 AGV 작업 배정을 위해 유전 알고리즘으로 최적화한 전략을 사용하였다. Kim et al.(2014) 또한 비슷한 방식으로 최적 전략을 사용하여 터미널 YC에 작업을 배정하였으며 Park et al.(2011)은 장치 장에서 컨테이너를 적재할 최적의 위치를 결정하기 위해 전략 을 사용한 바 있다. 이처럼 컨테이너 터미널 운영 문제를 전략 최적화를 통해 해결하려는 시도가 많이 있어왔는데, 전략은 다양한 평가 기준을 이용하여 작업을 다각적으로 평가하므로 효율적일 뿐 아니라 다양하고 장기적인 작업 시나리오를 이용 한 시뮬레이션을 통하여 최적화됨으로 인해 근시안적인 의사 결정 또한 피할 수 있다는 장점이 있기 때문이다.

Kim et et al.(2013)의 전략 기반 작업 배정 방안은 수직형 자동화 컨테이너 터미널의 AGV를 대상으로 제안되었으며 운 반작업 평가를 위해 9가지의 기준을 도입 사용하였다. 그러나 이들 중 몇 가지는 본 연구가 대상으로 하는 보통의 수평형 컨테이너 터미널에 적용하기 어려운 데다가 twin 작업을 고려 하는 평가 기준이 없어 실제로 현장에서 사용하기는 어렵다는 한계가 있다. 이에 본 논문에서는 이 전략을 기반으로 하되 실 제 현장에 적용할 수 있도록 평가 기준을 수정 및 보완한 작 업 배정 방안을 제안한다.

3. YT 배차 전략

본 장에서는 제안 방안인 YT 배차 전략에 대해 설명한다. 먼저 3.1절에서 YT 후보작업과 그 마감시간을 산정하는 방법 에 대해 알아보고 3.2절에서 배차 전략에 대해 상세히 설명한 다. 3.3절에서는 유전 알고리즘을 이용하여 전략을 최적화하는 방법에 대해 살펴본다.

3.1 후보작업과 마감시간

YT 배차는 각 QC별로 미리 사전에 계획된 양적하 작업들 이 그 순서대로 지연 없이 수행될 수 있도록 이루어져야 한다. 본 논문에서 사용하는 배차전략은 어떤 YT가 작업을 마칠 때 마다 여러 기준으로 후보작업들을 평가해보고 가장 적합한 것 을 선택하여 그 YT에 배정한다. 본 연구에서는 각 QC별로 YT 배정이 이루어지지 않은 첫 작업부터 시작하여 계획된 순 서 상 연속된 6개까지를 후보작업으로 하고 있다. 이렇게 하 면 실제 현장에서 흔히 하는 방식처럼 QC당 최대 6대까지 YT를 투입하더라도 작업을 할당받지 못하는 YT가 생기는 일 이 없다.

Fig. 2(a)의 예는 어떤 한 QC에 대해 순서가 가장 앞선 6개 의 작업이 후보로 선정된 모습을 보이고 있다. Fig. 2(b)는 이 들 중 가장 앞선 J1이 YT에 배정된 후 J7이 새로 후보에 추가 된 상태를 나타낸다. 그러나 Fig. 2(c)에 보인 것처럼 이어서 J3가 YT에 배정된 다음에는 새 후보작업이 추가되지 않는다. 마지막 후보작업인 J7이 아직 YT 배정이 이루어지지 못한 후 보작업 중 가장 앞선 J2로부터 계획 상 여전히 6번째 작업이 기 때문이다. 이 상태에서 J2가 YT에 배정되면 이번에는 Fig. 2(d)와 같이 두 개의 작업 J8J9이 후보작업으로 추가된다. Fig. 2(c)의 예에서 본 것처럼, 계획된 순서 상 연이은 6개의 작업 중 첫 작업 외의 작업에 YT가 배차되더라도 후보작업을 6개로 유지하기 위해 새 작업을 추가하지 않는 이유는, 새 후 보를 추가할 경우 가장 급한 작업이 (본 예에서는 작업 J2) 계 속 YT 배정을 받지 못하게 될 위험이 있기 때문이다.

Fig. 2

Configuration of YT candidate jobs

YT의 후보작업이 구성되고 나면 각 후보작업별로 YT가 대상 컨테이너를 픽업해야 할 마감시간을 계산해야 한다. 배 차 전략을 적용하여 작업을 선택하기 위해서는 각 후보작업의 평가 점수를 계산해야 하는데 이 때 이 마감시간이 필요하기 때문이다. YT 마감시간은 YT가 무부하 주행을 마치고 컨테 이너를 받을 준비가 완료되는 시점으로 하되 QC의 양적하 마 감시간이 지연되지 않게 정해져야 한다. Fig. 3(a)는 양하 작 업을 수행하는 YT의 타이밍 다이어그램이다. QC의 지연이 없으려면 양하 계획 상 QC가 컨테이너 하나를 내려서 YT에 상차할 준비가 완료되는 시점이 t2 시점과 일치해야 하며 이 시점이 YT 마감시간이 된다. Fig. 3(b)는 적하 작업을 수행하 는 YT의 타이밍 다이어그램이다. QC가 지연 없이 목표 컨테 이너를 적재할 수 있으려면 적하 계획 상 t9에 YT가 그 컨테 이너를 QC에게 넘길 준비를 완료해야 한다. 그러기 위해서는 주행 소요 시간 등을 감안하여 t7까지는 YT가 컨테이너를 받 기 위해 장치장의 해당 YC 아래에 도착해야 하고 이 시점이 YT 마감시간이 된다. 본 연구에서 YT의 주행 소요 시간은 목표 지점까지의 최단 거리를 평균 주행 속도로 나누어 추정 하였다.

Fig. 3

YT timeline for discharging/loading job

그런데 대부분의 터미널에서는 양적하 작업계획 시 작업의 순서만 결정하지 컨테이너 하나하나에 대한 QC 작업 마감시 간을 미리 정하지는 않는다. 본 연구에서는 QC가 평균적으로 작업 하나를 처리하는 데 걸리는 시간인 QC cycle time을 사 용하여 QC 마감시간을 계산하였다. 예를 들어 QC cycle time 이 90초이고 어떤 QC가 작업을 9시부터 시작해야 한다고 하 면 그 QC의 작업 처리 순서대로 첫 번째 작업은 9시 1분 30 초, 두 번째 작업은 9시 3분, 세 번째 작업은 9시 4분 30초와 같은 식으로 마감시간을 계산할 수 있다. 이렇게 계산된 마감 시간은 또한 주기적으로 갱신되어야 하는데, 그 이유는 QC의 작업 진척이 상황에 따라 계속해 변할 수 있기 때문이다. 예를 들어 한 컨테이너의 적하가 장치장에서의 예상치 못한 지연으 로 예정보다 5분 늦어졌다고 하자. 이럴 경우 이후의 적하작 업들에 대해서는 그 마감시간을 모두 5분 늦추어 주어야 한 다. QC의 cycle time이 갑자기 변하지 않는 한 그 후속 작업 들을 원래의 마감시간 내에 완료할 방법이 없기 때문이다. 만 약 그럼에도 불구하고 후속 작업들의 마감시간을 조정해 주지 않는다면, 그 작업들이 필요 이상으로 급한 것으로 취급되면 서 YT 배차가 과도하게 이루어져 전체적 운영 효율이 떨어지 게 된다. 본 연구에서는 QC가 작업을 하나 처리할 때마다 QC 작업 마감시간 및 그에 따른 YT 작업 마감시간을 갱신하고 있다.

3.2 배차 전략

YT 배차 전략은 앞서 설명했듯이 다양한 평가 기준을 사 용하여 각 후보작업의 점수를 계산하고 그 중 가장 좋은 점수 를 얻은 작업을 YT에 배정한다. 평가 기준 C1, C2, …, Cn이 주어졌을 때 YT y가 수행할 후보작업 j의 점수를 계산하는 함수 S는 식(1)과 같다.

(1) S(y,j)=iwiCi(y,j)

여기서 wi는 0과 1 사이의 실수로서 평가기준 Ci의 중요도를 나타내는 가중치다. YT y에 작업 j를 배정하는데 대한 평가값 Ci(y, j)는 평가 기준 Ci가 어떤 것인가에 따라 그 값의 크기 규모가 많이 달라질 수 있으므로 표준화(standardization)가 필요하다. 본 연구에서는 현장의 작업할당 방법을 모사한 local pooling 방식으로 YT 운영 시뮬레이션을 수행하여 각 Ci(y, j)의 값들을 수집한 후 각각 평균이 0이면서 분산이 1이 되도록 표준화하여 사용하였다.

본 논문에서 제안하는 평가 기준은 Table 1에 보인 10개로 서, 이들 평가값은 낮을수록 해당 작업이 선호되게 되어있다. 평가 기준 C1은 YT y가 작업 j를 시작하기 위해 무부하 주행 을 마친 시각과 작업 마감시간과의 차이를 계산한다. 이 값이 작을수록 y의 입장에서는 급하게 수행해야 할 작업이므로 우 선 할당되어야 한다. 이 평가 기준을 중요하게 볼수록 YT가 마감시간을 지키게 될 것이므로 QC가 YT를 기다리는 시간이 줄어드는 효과를 기대할 수 있다.

Evaluation criteria for YT dispatching

평가 기준 C2는 YT y가 자기 외의 다른 YT y’보다 작업 j 의 컨테이너 위치까지 얼마나 더 일찍 도착할 수 있는지를 계 산한다. 즉, y가 무부하 주행을 마친 시각과 y’ 중 가장 빨리 무부하 주행을 마치는 시각과의 차이를 계산하는 것이다. 이 값이 작을수록 y가 다른 YT보다 그만큼 더 먼저 작업 j를 시 작할 수 있음을 의미한다.

평가 기준 C3는 작업 j의 컨테이너에 대해 현재 시점으로부 터 YT y가 크레인과 핸드오버를 시작할 수 있는 시점까지 남 은 시간을 계산한다. 이 시간을 계산하기 위해서는 YT와 크 레인의 핸드오버 준비 완료 시각이 필요한데, 두 장비가 모두 준비되어야 핸드오버를 시작 할 수 있으므로 이 두 시각 중 더 늦은 시각이 곧 핸드오버를 시작하는 시각이 된다. YT의 핸드오버 준비 완료 시각은 YT의 무부하 주행 완료 시각이 며, 크레인의 핸드오버 준비 완료 시각은 크레인이 작업 j를 시작하기 전까지 처리해야 할 작업을 모두 완료하는 시각이 될 것이다. 이때 크레인이 작업 j를 시작하기 전까지 처리해야 할 남은 작업을 모두 완료하는 시간은 남은 작업의 수에 크레 인의 cycle time을 곱하여 추정할 수 있다.

평가 기준 C4는 작업 j가 양하 작업이면 1, 적하 작업이면 -1의 평가값을 부여한다. 그 이유는 양하 작업의 경우 작업 시작을 위해 YT가 바로 QC로 가면 되지만 적하 작업인 경우 에는 장치장 YC로부터 컨테이너를 받아서 QC로 가야 하므로 마감시간이 같다면 YT가 양하 작업보다 적하 작업을 더 중요 하게 보도록 해야 하기 때문이다.

평가 기준 C5C6는 YT의 주행 거리에 대한 것으로, C5는 YT y가 작업 j를 위해 무부하 주행을 하는 거리를 계산한다. 무부하 주행거리가 짧은 작업을 선호하도록 하기 위함인데 이 평가 기준을 중요하게 생각할수록 YT가 dual cycle 작업을 할 확률이 높아진다. 평가 기준 C6은 YT y가 작업 j를 위해 부하 주행을 하는 거리의 음수 값을 계산한다. 부하 주행거리 가 긴 작업을 선호하도록 하기 위함인데 부하 주행거리가 긴 작업은 처리 시간이 더 많이 소요되므로 다른 작업보다 먼저 선택되어야 하기 때문이다.

평가 기준 C7C8은 각각 작업 j를 처리하는 QC와 YC에 할당된 YT 수를 계산한다. 이는 YT 할당이 적게 된 크레인 의 작업에 YT를 우선 배정하게 해서 어느 한 크레인에 너무 많은 수의 YT가 쏠리는 현상을 방지하기 위함이다.

평가 기준 C9는 YT y가 작업 j를 완료한 후, 그 자리에서 바로 다음 작업으로 dual cycle을 할 수 있는 작업을 선택할 가능성을 계산하여 가능성이 있다면 –1을, 그렇지 않다면 1 의 값을 부여한다. 이는 dual cycle을 많이 하도록 유도하여 작업 효율성을 높이기 위함이다. Dual cycle 가능성을 따지는 방법은 다음과 같다. j가 양하 작업인 경우, y는 YC와 핸드오 버를 하고 작업을 완료한 후 그 YC에게 곧바로 적하 작업의 컨테이너를 받아야 dual cycle이 이루어진다. 이렇게 되려면 YT의 후보작업 중에 그 YC가 해야 하는 적하 작업이 존재해 야 한다. 즉, YT 후보작업 중 작업 j를 수행하는 YC의 적하 작업이 존재하면 dual cycle의 가능성이 있다고 보는 것이다. j가 적하 작업인 경우도 이와 같은 원리로, YT 후보작업 중 작업 j를 수행하는 QC의 양하 작업이 존재하면 dual cycle의 가능성이 있다고 본다. 본 연구에서는 인접한 두 QC를 거쳐 야 만들어지는 dual cycle을 직접적으로 장려하기 위한 평가 기준을 두지 않고 있다. 두 QC가 얼마나 가까워야 dual cycle 로 인정할 수 있는지를 비롯하여 여러 가지로 명확한 기준 설 정이 어려웠기 때문이다. 그러나 실험적 연구 결과, 공차 주행 을 줄이는 C5의 도입만으로도 인접 QC 간의 dual cycle이 촉 진되는 효과가 있음을 확인하였다.

마지막으로 평가 기준 C10은 twin 작업을 고려한 기준으로 일반 작업보다 twin 작업이 더 선호되도록 설계되었다. Twin 작업은 앞에서 언급했듯이 20ft 컨테이너 2개를 동시에 운반 하는 작업이다. 각각의 컨테이너는 서로 다른 위치에 장치될 수 있으므로 어느 컨테이너를 먼저 운반하느냐에 따라 YT의 주행거리가 달라질 수 있다. 즉 twin 작업은 그 운반 순서가 두 가지이므로 이 둘을 구분해서 운반 효율상 더 유리한 방법 의 twin 작업을 YT에 배정할 수 있어야 한다. 이를 위해 C10 은 두 가지 방법의 twin 작업 중 짧은 동선을 가진 twin 작업 에 –1의 값을 부여하고 긴 동선의 twin 작업이나 일반 작업 에는 1의 값을 부여하여 YT가 동선이 짧은 twin 작업을 선호 할 수 있도록 한다.

3.3 전략 최적화

식(1)의 가중치 wi의 조합에 따라 YT에 배정되는 작업의 양상이 달라지므로 wi의 조합이 바로 배차 전략이라 볼 수 있 다. 3.2절에서 언급한 바와 같이 wi는 0과 1 사이의 실수로서 그들의 조합이 무한하므로 이 중 해측 생산성을 극대화하는 최적의 전략을 찾는 것은 상당히 어려운 문제이다. 본 논문에 서는 최적의 전략을 탐색하기 위해 유전 알고리즘을 사용하였 다. 유전 알고리즘은 다수의 후보 해로 이루어진 집단을 구성 하고 후보 해를 평가하여 적합도를 계산한 후 진화 연산을 통 해 집단 내 개체들을 교체하는 과정을 반복하면서 최적의 적 합도를 가진 해를 탐색한다. 본 논문에서는 집단 내의 다양성 유지를 통해 좋은 품질의 해를 효율적으로 찾아 주는 것으로 알려져 있는 RTS(Restricted Tournament Selection) 알고리 즘을 사용하였으며, 이를 통해 최적의 전략을 탐색하는 과정 을 Fig. 4에 나타내었다. 전략, 즉 가중치 벡터의 후보 해는 0 과 1 사이의 실수 배열로 표현되며 초기 집단은 임의로 생성 된 후보 해 100개로 구성된다. 각 후보 해의 평가는 그 후보 해의 전략대로 YT를 운영하는 시뮬레이션을 수행하여 QC의 평균 작업 처리 시간을 측정함으로써 이루어지며 그 값이 곧 후보 해의 적합도가 된다. 현실에 가까운 YT 운영 시뮬레이 션을 위해 현장으로부터 터미널 레이아웃, 크레인 및 YT의 성능 수치, 선박 작업 현황 등의 데이터를 받아 사용하였다. 후보 해가 평가되어 적합도가 계산되면 다음과 같은 진화 연 산을 통해 집단을 갱신한다. 먼저 집단 내에서 임의로 2개의 후보 해(부모)를 선택한 후 교배 및 돌연변이 연산을 통해 2 개의 새로운 후보 해(자손)를 생성(reproduce)한다. 그리고 새 로 생성된 후보 해를 평가하여 적합도를 계산한 후, 집단에서 임의로 뽑은 50개의 후보 해 중 자신과 가장 비슷한 해의 적 합도와 비교하여 더 좋으면 새로 생성된 해가 기존 집단의 해 를 대체한다. 반대의 경우 새로 생성된 해는 폐기된다. 이와 같은 집단 갱신 과정을 정해진 평가 횟수를 채울 때까지 반복 한 후 최종 집단에서 가장 적합도가 좋은 후보 해를 최적 해 로 삼는다. 본 논문에서는 10,000번의 평가를 하였으며 교배 및 돌연변이 연산 방법으로는 실수 표현 개체들에 많이 사용 되는 simulated binary crossover와 non-uniform mutation 기 법을 사용하였다.

Fig. 4

Psedocode of RTS

4. 실험 및 결과

제안 방안의 성능을 검증하기 위하여 현장에서 흔히 사용 하는 local pooling 방식의 배차 방안과 2장에서 소개한 휴리 스틱 배차 방안을 대상으로 비교 실험을 수행하였다. 4.1절에 서 비교 대상 방안을 상세히 설명하고 4.2절에서는 실험 환경 을 살펴본 다음 실험 중 수집해야 할 성능 지표를 소개한다. 그 후 4.3절에서 방안별로 성능을 비교한 결과를 분석한다.

4.1 비교 대상 방안

본 실험에서는 제안 방안(PB: Policy Based)의 성능 검증을 위해 현장에서 쓰이는 local pooling 방식의 배차 방안(LP: Local Pooling)과 마감 시간 우선 휴리스틱 배차 방안(EDF: Earliest Due-time First)을 비교 대상 방안으로 선정하였다. LP 방안은 선박별로 YT 작업조를 구성하여 각 선박의 작업 을 전담 작업조의 YT에게만 배정한다. YT가 여러 QC의 작 업을 골고루 수행하도록 만들기 위해 QC 별로 YT 할당 하한 값을 설정하고 이 값보다 할당된 YT 수가 적은 QC의 작업만 후보작업으로 삼으며 이 중 마감시간이 가장 이른 작업을 YT 에 배정한다. 만약 모든 QC에 그 QC의 YT 할당 하한값보다 더 많은 수의 YT가 할당되어 있다면 모든 QC의 작업을 후보 작업으로 삼고 그중에 YT와 가장 가까운 위치에 있는 작업을 YT에 배정한다. QC의 YT 할당 하한값 크기는 해당 QC의 작 업 진척도에 따라 조정되는데 작업 진척도가 다른 QC에 비해 낮으면 그 값을 높이고 반대의 경우에는 낮춘다.

또 다른 비교 대상인 EDF는 후보작업 중 가장 마감시간이 이른 작업을 배정하는 단순 규칙을 이용하되 local pooling이 아 니라 global pooling 방식으로 YT에 작업을 배정한다. 이 방안 역시 YT가 각 QC의 작업을 어느 정도 고르게 수행하게 되도록 QC 별로 YT 할당 하한값을 설정하여 이 값보다 할당된 YT 수 가 적은 QC의 작업이 우선적으로 YT에 배정되도록 하였다.

4.2 실험 환경 및 성능 지표

각 방안의 성능은 테스트 시나리오에 대한 시뮬레이션 수 행을 통해 측정된 성능 지표로 평가하였다. 테스트 시나리오 는 현장의 선박 양적하 작업 기록 데이터 중 양적하가 골고루 이루어진 약 2일 간의 데이터를 추출하여 생성하였으며 작업 컨테이너의 총 개수는 약 8,000개이다. 또한, 공정한 검증을 위해 제안 방안의 전략을 최적화할 때 사용한 시나리오와는 다른 시나리오를 테스트 시나리오로 사용하였다. 시뮬레이션 시 투입되는 YT 수는 작업 중인 QC 수의 6배로 설정하였으 며 LP 방안 및 EDF 방안에서 각 QC의 YT 할당 하한값은 3 대로 설정하였다. 물론 LP 방안의 경우 이 값이 QC의 진척도 에 따라 조정된다.

시뮬레이션을 통해 측정되는 성능 지표는 해측 생산성과 YT 작업 효율에 관한 것으로, 해측 생산성에 대한 지표로는 QC의 시간당 컨테이너 처리량과 QC의 평균 작업 지연 시간 을 측정하였다. QC의 시간당 컨테이너 처리량이 많을수록, 평 균 작업 처리 소요 시간은 짧을수록 해측 생산성이 높다고 할 수 있다. 그리고 YT 작업 효율에 대한 지표로는 YT의 평균 주행거리와 YT의 dual cycle 작업 횟수를 측정하였다. YT의 평균 주행거리가 짧을수록 그리고 dual cycle 작업 횟수는 많 을수록 YT 작업 효율이 높다고 할 수 있다.

4.3 실험 결과

본 절에서는 비교 대상 방안인 LP 및 EDF와 제안 방안인 PB의 성능 지표를 비교한다. 각 방안의 성능 지표는 Table 2 에 나타내었다. 먼저 QC의 시간당 컨테이너 처리량과 평균 작업 지연 시간을 보면 PB, EDF, LP 순으로 시간당 컨테이너 처리량이 많고 평균 작업 지연 시간은 짧은 것을 확인할 수 있다. 즉, 제안 방안이 해측 생산성 측면에서 가장 성능이 좋 았다. 그리고 YT의 평균 주행거리와 dual cycle 작업 횟수를 비교해 보면 PB, EDF, LP 순으로 평균 주행거리는 짧고 dual cycle 작업 횟수는 많아 YT 작업 효율 측면에서도 제안 방안 의 성능이 가장 좋음을 확인하였다. 제안 방안이 작업을 할당 하는데 소요되는 시간은 작업 당 평균 0.0003초, 최대 0.04초 로 관찰되어 (Intel i7-8700 CPU 기준) 실시간 적용에 전혀 문 제가 없음을 확인하였다.

Performance comparison

LP 방안의 성능이 가장 나쁘게 나타나는 것은 아무래도 local pooling 방식이다 보니 dual cycle이 잘 이루어지지 못해 불리하기 때문으로 보인다. 실제로 세 방안 중 dual cycle 작 업의 횟수가 가장 적었으며 이에 따라 YT 평균 주행거리도 길어져서 YT 작업 효율이 상대적으로 다른 방안에 비해 낮은 것으로 분석된다. EDF 방안은 사용한 규칙이 단순한데 비해 높은 성능을 보이는 것을 확인 할 수 있다. 위에서 설명했듯이 본 논문에서 비교한 EDF 방안은 단순히 마감시간만 보는 것 이 아니라 QC 별 YT 할당 최소값을 이용하여 YT가 어느 정 도 골고루 QC에 배정되도록 한다. 이러한 운영 방법이 global pooling 방식과 시너지 효과를 일으켜 성능에 좋은 영향을 미 친 것으로 보인다. 또한, LP 방안과 비교해 dual cycle 횟수도 50번 이상 더 많아 YT 작업 효율도 좋게 나타났다. 본 논문에 서 제안하는 PB 방안은 해측 생산성 측면이나 YT 작업 효율 측면 모두에서 LP나 EDF 방안에 비해 더 좋은 성능을 보인 다. 특히 YT dual cycle 횟수는 다른 방안보다 약 2배 정도 많으며, YT 평균 주행거리 또한 가장 짧다. 이렇게 높은 YT 작업 효율은 곧 QC 작업 지연 시간의 단축으로 이어져 PB 방 안이 세 방안 중 시간당 가장 많은 컨테이너를 처리하는 모습 을 보여준다.

Table 3은 투입되는 YT 수를 QC 수의 6배에서 4배까지 점 차 줄일 경우 QC의 시간당 컨테이너 처리량이 어떻게 달라지 는지를 보여준다. 전반적으로 PB 방안이 일관성 있게 나머지 방안들보다 좋은 성능을 보임을 확인할 수 있다. 특히 주목할 점은 PB 방안의 경우 YT 투입 대수를 QC 수의 5배까지 줄이 더라도 6배일 때의 LP 방안 성능을 능가한다는 것이다. 이는 제안 방안이 현장에 도입될 경우 YT 대수를 15% 이상 줄일 가능성이 있음을 의미한다.

QC throughput per hour (box) with reduced number of YTs

5. 결 론

본 논문에서는 해측 생산성 극대화를 위한 YT 배차 방안 으로 전략 기반 방안을 사용할 것을 제안하였고 휴리스틱 기 반 방안 및 현장 방안과 비교하여 제안 방안의 성능이 더 우 수함을 보였다. 제안 방안은 Kim et al.(2013)이 수직형 자동 화 컨테이너 터미널을 대상으로 제안한 전략 기반 방안을 기 반으로 하되, 현장 적용이 가능하도록 몇 가지 평가 기준을 수 정 및 보완하였고 twin 작업을 고려한 평가 기준을 추가하였 다. 현장 데이터를 이용한 YT 운영 시뮬레이션을 통해 성능 비교 실험을 수행한 결과, 비교 대상 방안보다 제안 방안이 해 측 생산성 측면 및 YT 작업 효율 측면 모두에서 가장 좋은 성능을 보임을 확인하였다. 특히 제안 방안을 도입할 경우 투 입 YT 수를 15% 이상 줄이더라도 해측 생산성이 local pooling 방식보다 떨어지지 않는 모습을 보임으로써 운영비용 절감 가능성도 확인할 수 있었다. 그러나 보다 다양한 시나리 오를 이용하여 전략을 학습하고 그 성능을 검증하는 추가 실 험이 필요할 것으로 보인다. 전략 기반 방안의 한계 중 하나는 다양한 시나리오를 이용해 학습하더라도 그 모두에 평균적으 로 잘 동작하는 전략 하나를 얻을 수 있을 뿐이지 각 상황에 특화된 다양한 전략을 얻을 수 있는 것은 아니라는 점이다. 강 화학습 기법 등을 이용한 상황적응적 전략의 학습이 향후 매 우 중요한 연구 주제가 될 것으로 사료된다.

후 기

이 과제는 부산대학교 기본연구지원사업(2년)에 의하여 연 구되었음.

본 논문은 BK21플러스, IT기반 융합산업 창의인력양성사 업단에 의하여 지원되었음.

References

1. Briskorn, D.,, Drexl, A., Hartmann, S.. (2006;), "Inventory-based dispatching of automated guided vehicles on container terminals", OR Spectrum, Vol. 28, pp. 611-630. 10.1007/s00291-006-0033-8.
2. Egbelu, P. J., Tanchoco, J. M. A.. (1984;), "Characterization of automatic guided vehicle dispatching rules", International Journal of Production Research, Vol. 22, No. 3, pp. 359-374. 10.1080/00207548408942459.
3. Kim, J.,, Choe, R., Ryu, K. R.. (2013;), "Multi-Objective Optimization of Dispatching Strategies for Situation- Adaptive AGV Operation in an Automated Container Terminal", 2013 RESEARCH IN ADAPTIVE AND CONVERGENT SYSTEMS (RACS 2013). 10.1145/2513228.2513277.
4. Kim, K. H., Bae, J. W.. (1999;), "A Dispatching Method for Automated Guided Vehicles to Minimize Delays of Containership Operations", International Journal of Management Science, Vol. 5, No. 1, pp. 1-25.
5. Kim, K. H., Bae, J. W.. (2004;), "A look-ahead dispatching method for automated guided vehicles in automated port container terminals", Transportation Science, Vol. 38, No. 2, pp. 224-234. 10.1287/trsc.1030.0082.
6. Kim, T.,, Yang, Y.,, Bae, A., Ryu, K. R.. (2014;), "Optimization of Dispatching Strategies for Stacking Cranes Including Remarshaling Jobs", Journal of Korean Navigation and Port Research, Vol. 38, No. 2, pp. 155-162. 10.5394/KINPR.2014.38.2.155.
7. Nguyen, V. D., Kim, K. H.. (2009;), "A dispatching method for automated lifting vehicles in automated port container terminals", Computers & Industrial Engineering, Vol. 56, No. 3, pp. 1002-1020. 10.1016/j.cie.2008.09.009.
8. Park, T.,, Choe, R.,, Kim, Y. H., Ryu, K. R.. (2011;), "Dynamic adjustment of container stacking policy in an automated container terminal", International Journal of Production Economics, Vol. 133, No. 1, pp. 385-392. 10.1016/j.ijpe.2010.03.024.
9. Yamashita, H.. (2001;), "Analysis of Dispatching Rules of AGV Systems with Multiple Vehicles", IIE Transactions, Vol. 33, pp. 889-895. . 10.1080/07408170108936881.

Article information Continued

Fig. 1

Container terminal layout

Fig. 2

Configuration of YT candidate jobs

Fig. 3

YT timeline for discharging/loading job

Table 1

Evaluation criteria for YT dispatching

Fig. 4

Psedocode of RTS

Table 2

Performance comparison

Table 3

QC throughput per hour (box) with reduced number of YTs