[논문]장치장 블록의 작업부하를 고려한 안벽크레인 작업계획

이승환; 최이; 박태진; 김갑환; 류광렬

장치장 블록의 작업부하를 고려한 안벽크레인 작업계획
Quay Crane Scheduling Considering the Workload of Yard Blocks in an Automated Container Terminal 원문보기

지능정보연구 = Journal of intelligence and information systems, v.14 no.4, 2008년, pp.103 - 116

이승환 (부산대학교 컴퓨터공학과) , 최이 (부산대학교 컴퓨터공학과) , 박태진 (부산대학교 컴퓨터공학과) , 김갑환 (부산대학교 산업공학과) , 류광렬 (부산대학교 컴퓨터공학과)

초록
AI-Helper

본 논문은 컨테이너 터미널에서 장치장의 작업부하가 고르게 분산되도록 안벽크레인의 작업을 계획함으로써 장치장의 컨테이너 처리능력을 최대로 활용할 수 있는 두 가지 알고리즘을 제안한다. 두 제안방안 모두 선적 작업을 진행하는 동안 안벽크레인의 컨테이너 반출 요청이 특정 블록에 집중 되지 않고 전체 블록에 고르게 분산될 수 있도록 안벽크레인이 작업할 선박 베이(ship bay)의 순서를 결정한다. 첫 번째 제안 방안은 장치장 블록의 작업부하의 엔트로피(entropy)를 계산하여 이를 최대화하도록 다음에 작업할 베이를 결정하는 휴리스틱(heuristic)알고리즘이다. 두 번째 방안은 유전 알고리즘(genetic algorithm, GA)을 이용하여 최적의 선박 베이 작업순서를 탐색한다. 유전 알고리즘의 각 염색체(chromosome)의 적합도(fitness)를 계산하기 위해 장치장의 작업부하 분포를 고려하여 안벽크레인의 작업시간을 계산하는 알고리즘을 고안하였다. 제안한 두 가지 방안으로 선박 베이 작업순서를 조정한 안벽크레인 작업계획과 기존 작업계획을 비교 실험한 결과 선박의 총 적하 시간이 단축되는 것을 확인하였다.

Abstract ▼ AI-Helper

This paper proposes quay crane (QC) scheduling algorithms that determine the working sequence of QCs over ship bays in a container vessel in automated container terminals. We propose two scheduling algorithms that examine the distribution of export containers in the stacking yard and determine the sequence of ship bays to balance the workload distribution among the yard blocks. One of the algorithms is a simple heuristic algorithm which dynamically selects the next ship bay based on the entropy of workloads among yard blocks whenever a QC finishes loading containers at a ship bay and the other uses genetic algorithm to search the optimal sequence of ship bays. To evaluate the fitness of each chromosome in the genetic algorithm, we have devised a method that is able to calculate an approximation of loading time of container vessels considering the workloads among yard blocks. Simulation experiments have been carried out to compare the efficiency of the proposed algorithms. The results show that our QC scheduling algorithms are efficient in reducing the turn-around time of container vessels.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

추정치의 오차를 줄이기 위해 QC의 작업을 정밀한 시뮬레이터로 시뮬레이션 하면 실제 소요시간과 가까운 값을 얻을 수 있으나 정교한 시뮬레이션일수록 시간비용이 크므로 실제 운영 시스템에 적용 가능한 실시간 탐색이 어려워진다. 따라서 본논문에서는 선박의 총 적하작업시간을 간단한 수식을 통해 추정하는 방안을 고안하였다.
본 논문에서는 장치장 내의 적하 컨테이너들의 분포를 고려하여 각 안벽크레인의 컨테이너 반출 요청이 특정 블록에 집중되지 않도록 고르게 분산하는 안벽크레인 작업계획을 도출하는 두 가지 알고리즘을 제안한다. 제안방안은 단시간에 안벽크레인의 작업계획을 도출하기 위해 안벽크레인의 작업계획을 선박 베이의 작업순서 결정과 선박 베이 내에서 컨테이너의 작업순서 결정으로 구분하고 선박 베이의 작업순서를 결정한다.
본 논문에서는 장치장 블록의 작업부하를 고려 하여 특정 장치장 블록에 작업부하가 집중 되지 않도록 QC의 선박 베이 작업순서를 결정하는 두가지 방안을 제안하였다. GAQS는 유전알고리즘을 이용하여 최적 작업계획을 탐색을 통해 도출하며, EHQS는 장치장 블록의 작업부하의 엔트로피를 이용하여 QC의 작업이 완료될 때마다 다음에 작업할 선박 베이를 동적으로 결정하는 휴리스틱 방안이다.
본 논문에서는 효과적인 QC의 작업계획을 수립하기 위해 엔트로피 계산에 기반한 휴리스틱 QC 작업계획 방안(entropy-based heuristic QC scheduling, EHQS)과 유전알고리즘에 기반한 QC 작업계획 방안(genetic algorithm-based QC scheduling, GAQS)의 2가지 QC 작업계획 알고리즘을 제안한다.
제안방안을 설명함에 앞서 대상문제의 이해를 돕기 위해 QC 작업계획 시 장치장의 작업부하가 고르지 못해 작업에 지연이 발생하는 경우를 의 예로 살펴보자.

가설 설정

제안방안의 성능을 평가하기 위하여 시간 당 20 박스의 컨테이너 처리능력을 보유한 QC 3대와 시간 당 20박스의 컨테이너를 처리할 수 있는 7개의 장치장 블록으로 구성 된 컨테이너 터미널에서 70 개의 베이를 보유한 선박 1척을 대상으로 적하작업을 수행하는 상황을 가정하였다. <표 1>과 같은 시스템 환경에서 알고리즘을 구현 및 실험하였으며, 작업 선박 베이와 적하 컨테이너 수를 <표 2>와 같이 실험 1, 2, 3으로 구분하여 실험하였다.
적하계획 전에 적하계획을 수립하는데, 적하계획이란 컨테이너 단위의 양, 적하작업 순서를 수립하는 것이며 수립절차는 적부도 제작, 크레인 스플릿, QC의 작업계획 수립 순으로 이루어지는데, 본 논문에서는 QC의 선박 베이 작업순서 결정에 초점을 두고 QC 작업계획을 수립한다. 크레인 스플릿과 적부 도는 선박 베이 작업순서 결정 이전 단계에서 이 미 수립 되었다고 가정한다.

제안 방법

EHQS 방안에서는 다음 작업 선박 베이 결정 시에 QC의 이동시간을 고려하지 않았으며 컨테이너의 적하작업을 장치장 블록 단위로 고려하였다. 성능의 추가 개선을 위해서는 QC의 이동을 고려하고 컨테이너 적하작업을 그룹 단위로 결정하는 방안에 대한 연구가 필요하다.
QC의 작업시간 추정은 총 3 단계로 이루어지는 데, QC가 장치장 블록에 컨테이너를 요청하는 적하 컨테이너 요청률(QC request rate)을 계산하고, 장치장 블록이 해당 QC가 작업 중인 선박 베이에 지원하는 컨테이너의 양(yard block service rate)을 계산한다. 계산된 요청률과 지원량을 이용하여총 적하 작업시간을 계산한다.
QC의 작업시간 추정은 총 3 단계로 이루어지는 데, QC가 장치장 블록에 컨테이너를 요청하는 적하 컨테이너 요청률(QC request rate)을 계산하고, 장치장 블록이 해당 QC가 작업 중인 선박 베이에 지원하는 컨테이너의 양(yard block service rate)을 계산한다. 계산된 요청률과 지원량을 이용하여총 적하 작업시간을 계산한다.
과 같은 시스템 환경에서 알고리즘을 구현 및 실험하였으며, 작업 선박 베이와 적하 컨테이너 수를 와 같이 실험 1, 2, 3으로 구분하여 실험하였다.
제안방안중 하나는 각 블록의 작업부하의 엔트로피를 이용하는 휴리스틱(heuristic) 규칙을 이용하여 작업 계획을 수립하며 나머지 한 방안은 유전알고리즘 (genetic algorithm, GA)을 이용하여 안벽크레인의 최적 선박 베이 작업순서를 탐색한다. 또한 유전알고리즘의 염색체의 적합도 평가를 위해 선박 베이 작업순서를 바탕으로 장치장 작업부하를 고려하여 안벽크레인의 작업시간을 계산하는 알고리즘을 제안한다.
비교방안으로는 순차적 QC 작업계획(각 QC가 맡은 선박 베이에서 가장 왼쪽부터 순차적으로 작업)과 본 논문에서 제안하는 GAQS, EHQS, 무작위 순서로 작업, 총 4가지 방법으로 적하작업을 수행하고 작업소요시간을 비교하였다. 작업시간은 제 3.
위의 방법으로 QC의 요청률과 장치장 블록의 지원율을 계산하며, 이를 바탕으로 다음과 같이 작업시간을 계산하고 잔여물량을 갱신 한다.
본 논문에서는 장치장 내의 적하 컨테이너들의 분포를 고려하여 각 안벽크레인의 컨테이너 반출 요청이 특정 블록에 집중되지 않도록 고르게 분산하는 안벽크레인 작업계획을 도출하는 두 가지 알고리즘을 제안한다. 제안방안은 단시간에 안벽크레인의 작업계획을 도출하기 위해 안벽크레인의 작업계획을 선박 베이의 작업순서 결정과 선박 베이 내에서 컨테이너의 작업순서 결정으로 구분하고 선박 베이의 작업순서를 결정한다. 제안방안중 하나는 각 블록의 작업부하의 엔트로피를 이용하는 휴리스틱(heuristic) 규칙을 이용하여 작업 계획을 수립하며 나머지 한 방안은 유전알고리즘 (genetic algorithm, GA)을 이용하여 안벽크레인의 최적 선박 베이 작업순서를 탐색한다.
제안방안은 단시간에 안벽크레인의 작업계획을 도출하기 위해 안벽크레인의 작업계획을 선박 베이의 작업순서 결정과 선박 베이 내에서 컨테이너의 작업순서 결정으로 구분하고 선박 베이의 작업순서를 결정한다. 제안방안중 하나는 각 블록의 작업부하의 엔트로피를 이용하는 휴리스틱(heuristic) 규칙을 이용하여 작업 계획을 수립하며 나머지 한 방안은 유전알고리즘 (genetic algorithm, GA)을 이용하여 안벽크레인의 최적 선박 베이 작업순서를 탐색한다. 또한 유전알고리즘의 염색체의 적합도 평가를 위해 선박 베이 작업순서를 바탕으로 장치장 작업부하를 고려하여 안벽크레인의 작업시간을 계산하는 알고리즘을 제안한다.

대상 데이터

본 논문은 자동화 컨테이너 터미널에서 사용하는 안벽크레인의 작업계획 문제를 대상으로 한다. 자동화 컨테이너 터미널에서는 터미널 내부의 컨테이너 운반을 위해 무인이송차량(automated guided vehicle, AGV)과 자동화 장치장크레인(automated transfer crane, ATC)과 같은 무인장비를 사용한 다.

이론/모형

염기의 중복을 방지하기 각각의 QC 별로 ‘1/염색체 길이’의 확률로 돌연변이 연산이 발생할 때 해당 QC영역내의 다른 염기와 교환하는 방식을 취하면 돌연변이 연산 후에도 지역 최적해(local optimum)을 빠져 나오지 못하는 문제점이 있다. 따라서 본 논문에서는 역전(inverse) 돌연변이 연산을 적용한다(Goldberg, 1989). 역전돌연변이 연산은 OX 교차연산과 마찬가지로 2개의 단절점을 임의로 지정하고 지정된 단절점 사이의 염기들을 <그림 8>과 같이 뒤집어 배치하여 돌연변이를 만든다.
부모 선택 단계에서 적합도 계산 단계에서 계산한 작업시간을 이용하여 토너먼트 선택을 통해 작업시간이 적은 개체가 선택된다. 부모 사이의 교차연산은 순서계획 문제에 적합한 OX 교차연산을 사용한다(Oliver et al., 1987). OX 교차연산은 다음과 같이 진행된다.
비교방안으로는 순차적 QC 작업계획(각 QC가 맡은 선박 베이에서 가장 왼쪽부터 순차적으로 작업)과 본 논문에서 제안하는 GAQS, EHQS, 무작위 순서로 작업, 총 4가지 방법으로 적하작업을 수행하고 작업소요시간을 비교하였다. 작업시간은 제 3.3절의 장치장 작업부하를 고려한 작업시간 계산 알고리즘으로 계산하였다. <표 3>은 GAQS의 탐색 알고리즘인 GA의 설정이다.

성능/효과

EHQS는 QC의 이동시간 계산은 포함 되어 있으나 QC의 이동시간을 선박 베이 결정 시 고려하지 않았다. EHQS는 근시안적인 방법으로 최적의 결과를 내놓지 못했지만 계산시간이 짧은 장점이 있어 탐색시간이 소요되는 GAQS보다 실시간 적용에 보다 적합하며, 엔트로피 계산이 적하작업 도중 동적으로 수행되므로 QC의 작업시작시간이 서로 다른 경우와 적하 도중 적부도의 수정에도 크게 영향을 받지 않고 유연하게 계산 할 수 있다는 장점이 있다.
본 논문에서 제안한 GAQS는 빠르게 수렴하여 최적의 작업 순서를 탐색하였고, 기존의 방법보다약 13%(3～5시간)의 작업시간을 절약하였다. 엔트로피 계산을 통해 장치장 블록의 작업부하가 균등화 되도록 다음 선박 베이를 결정하는 EHQS는 적하 컨테이너 수가 증가하고 작업대상 선박 베이 수가 늘어날수록 GAQS과 근접한 성능을 보였다.
실험 결과 본 논문에서 제안한 두 가지의 방안 으로 도출된 QC 작업계획으로 적하작업을 수행하 였을 때 선박의 적하소요시간이 감소하는 것을 확인하였다. 실험에서 EHQS는 작업 선박 베이 수와 적하 컨테이너 물량이 늘어나 대상 문제가 어려워 질수록 GAQS와 근접한 성능을 보였으며 QC 작업시간에 불확실성이 존재하는 경우 EHQS 방법이 더 효과가 좋을 것으로 예상된다.
실험 방법에서 작업시간의 최대 상한과 비교하기 위해 최대의 작업시간이 걸리는 최악의 경우를 탐색을 통해 유추하였고, 무작위 작업계획은 임의의 순서로 결정한 QC 작업계획으로 적하작업을 수행한 결과이다. GAQS와 무작위 작업계획은 각각 10번 실험하여 평균한 값이다.
실험결과에서 QC 작업계획이 없는 순차적인 적하작업은 QC의 이동시간은 최소인데 반해, 장치장 블록의 작업 부하는 고려되지 않으므로, QC의 유휴 시간의 발생으로 인해 작업시간에 지연이 발생하였다. 무작위 작업계획 또한 이와 대동소이한 결과를 보였다.
실험 결과 본 논문에서 제안한 두 가지의 방안 으로 도출된 QC 작업계획으로 적하작업을 수행하 였을 때 선박의 적하소요시간이 감소하는 것을 확인하였다. 실험에서 EHQS는 작업 선박 베이 수와 적하 컨테이너 물량이 늘어나 대상 문제가 어려워 질수록 GAQS와 근접한 성능을 보였으며 QC 작업시간에 불확실성이 존재하는 경우 EHQS 방법이 더 효과가 좋을 것으로 예상된다.
본 논문에서 제안한 GAQS는 빠르게 수렴하여 최적의 작업 순서를 탐색하였고, 기존의 방법보다약 13%(3～5시간)의 작업시간을 절약하였다. 엔트로피 계산을 통해 장치장 블록의 작업부하가 균등화 되도록 다음 선박 베이를 결정하는 EHQS는 적하 컨테이너 수가 증가하고 작업대상 선박 베이 수가 늘어날수록 GAQS과 근접한 성능을 보였다. EHQS는 QC의 이동시간 계산은 포함 되어 있으나 QC의 이동시간을 선박 베이 결정 시 고려하지 않았다.
적하작업시간 계산을 통한 실험 결과, QC 작업 계획 방법에 따라 적하작업시간의 현격한 차이를 보였고 본 논문에서 제안한 두 가지의 방안으로 도출된 QC 작업계획으로 적하작업을 수행한 결과 작업효율이 향상된 것을 확인하였다.

후속연구

EHQS 방안에서는 다음 작업 선박 베이 결정 시에 QC의 이동시간을 고려하지 않았으며 컨테이너의 적하작업을 장치장 블록 단위로 고려하였다. 성능의 추가 개선을 위해서는 QC의 이동을 고려하고 컨테이너 적하작업을 그룹 단위로 결정하는 방안에 대한 연구가 필요하다. 또한, 한 선박 베이의 작업을 완료한 뒤 다음 선박 베이로 이동하는 대신, 필요한 경우 한 베이에서 작업하는 중에도 유동적으로 다른 선박 베이로 이동하여 작업을 수행하도록 계획을 수립하는 방안도 고려할 수 있다.

질의응답

핵심어	질문	논문에서 추출한 답변
	자동화 컨테이너 터미널에서는 터미널 내부의 컨테이너 운반을 위해 어떤 무인장비를 사용하는가?	본 논문은 자동화 컨테이너 터미널에서 사용하는 안벽크레인의 작업계획 문제를 대상으로 한다. 자동화 컨테이너 터미널에서는 터미널 내부의 컨테이너 운반을 위해 무인이송차량(automated guided vehicle, AGV)과 자동화 장치장크레인(automated transfer crane, ATC)과 같은 무인장비를 사용한 다. 이와 같은 자동화 장비의 사용으로 인해 자동화 터미널 운영은 기존 재래식 터미널에 비해 많은 차이가 있다.
	본선작업은 어떻게 구분되는가?	본선작업의 총 작업시간은 컨테이너 터미널의 중요한 생산성 지표이다. 본선작업은 크게 양하와 적하의 두 가지 작업으로 구분되며, 양하작업은 컨테이너선으로부터 수입 컨테이너를 하역하여 장치장에 장치하는 작업이며 적하작업은 장치장에 보관중인 수출컨테이너를 반출하여 선박에 싣는 작업이다. 이러한 양적하작업은 안벽크레인(quay crane, QC)이 수행하며, 따라서 안벽크레인의 작업효율이 전체 컨테이너 터미널의 생산성에 가장 중대한 영향을 미친다(Moccia et al.
	장치장의 컨테이너 처리능력을 최대로 활용할 수 있게 제안한 두 가지 알고리즘은 무엇인가?	두 제안방안 모두 선적 작업을 진행하는 동안 안벽크레인의 컨테이너 반출 요청이 특정 블록에 집중 되지 않고 전체 블록에 고르게 분산될 수 있도록 안벽크레인이 작업할 선박 베이(ship bay)의 순서를 결정한다. 첫 번째 제안 방안은 장치장 블록의 작업부하의 엔트로피(entropy)를 계산하여 이를 최대화하도록 다음에 작업할 베이를 결정하는 휴리스틱(heuristic)알고리즘이다. 두 번째 방안은 유전 알고리즘(genetic algorithm, GA)을 이용하여 최적의 선박 베이 작업순서를 탐색한다. 유전 알고리즘의 각 염색체(chromosome)의 적합도(fitness)를 계산하기 위해 장치장의 작업부하 분포를 고려하여 안벽크레인의 작업시간을 계산하는 알고리즘을 고안하였다. 제안한 두 가지 방안으로 선박 베이 작업순서를 조정한 안벽크레인 작업계획과 기존 작업계획을 비교 실험한 결과 선박의 총 적하 시간이 단축되는 것을 확인하였다.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증