[논문]컨테이너 터미널의 불확실한 환경 하에서의 ALV 주행 계획 수립방안

김정민; 이동균; 류광렬

doi:10.5394/kinpr.2014.38.5.493

컨테이너 터미널의 불확실한 환경 하에서의 ALV 주행 계획 수립방안
Routing of ALVs under Uncertainty in Automated Container Terminals 원문보기

한국항해항만학회지 = Journal of navigation and port research, v.38 no.5, 2014년, pp.493 - 501

김정민 (부산대학교 대학원) , 이동균 ((주)싸이버로지텍 Core Asset 팀) , 류광렬 (부산대학교 정보컴퓨터공학부)

초록
AI-Helper

무인 자가 운반 하역차량(Automated Lifting Vehicle, ALV)은 자동화 컨테이너 터미널에서 컨테이너를 수송하는 무인 차량의 하나로 자가 하역 및 수송 능력을 가지고 있다. 여러 대의 ALV를 이용해 컨테이너를 효율적으로 수송하기 위해서는 ALV가 컨테이너의 이송작업을 시작할 때마다 최소 시간에 주행이 가능한 경로를 실시간으로 찾을 수 있어야 한다. 또한 차량 간의 충돌 및 교착 상태 발생 시 스스로 해결이 불가능한 무인 차량의 특성 상 이러한 충돌 및 교착을 막을 수 있도록 차량이 목적지까지 가기 위해 점유해야 하는 점유 영역과 그 점유 시간을 결정하여 이를 겹치지 않도록 주행 계획을 수립하여야 한다. 하지만 주행 계획 수립을 위한 ALV의 점유 영역에서의 점유 시간 계산은 교통 상황에 따른 주행 시간의 변화나 주행 경로 상에 작업을 수행하는 크레인의 작업 상황의 불확실성 때문에 정확한 추정이 어렵다. 본 논문에서는 개미 집단 최적화 기법을 기반으로 이러한 ALV 도착 시간의 불확실성을 고려한 ALV 주행 계획 수립방안을 제안한다. 시뮬레이션 실험을 통해 제안 방안이 불확실한 환경에서 효율적으로 좋은 경로를 찾아냄을 확인하였다.

Abstract ▼ AI-Helper

An automated lifting vehicle(ALV) used in an automated container terminal is a type of unmanned vehicle that can self-lift a container as well as self-transport it to a destination. To operate a fleet of ALVs efficiently, one needs to be able to determine a minimum-time route to a given destination whenever an ALV is to start its transport job. To find a route free from any collision or deadlock, the occupation time of the ALV on each segment of the route should be carefully scheduled to avoid any such hazard. However, it is not easy because not only the travel times of ALVs are uncertain due to traffic condition but also the operation times of cranes en route are not predicted precisely. In this paper, we propose a routing method based on an ant colony optimization algorithm that takes into account these uncertainties. The result of simulation experiment shows that the proposed method can effectively find good routes under uncertainty.

주제어

AI 본문요약
AI-Helper

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

문제 정의

향후 연구로는, 앞서 본 논문에서는 불확실한 요소를 고려하여 정차기점의 예약기간을 추정하기 위해서 두 가지 설정변수를 사용하는데, 컨테이너 터미널의 상황 변화를 감지하여 유동적으로 이 설정변수 값을 재 변경하는 방안에 대한 연구가 필요하다. 그리고 본 논문에서는 주행경로를 결정하기 위해서 미시적 관점으로 자신의 주행시간이 최소가 되는 경로를 탐색한다. 하지만 이는 거시적인 관점에서 보면 오히려 성능에 안 좋은 영향을 미칠 수도 있다.
본 논문에서는 자동화 컨테이너 터미널에서 ALV가 안벽과 장치장 사이를 오가며 컨테이너를 운반하는 에이프런 영역을 노드와 에지를 가지는 그래프 형태로 일반화 하여 표현한다.
본 장에서는 3장에서 제안한 ALV의 주행방안의 성능을 시뮬레이션 기반의 비교실험을 통해 확인하고자 한다.
본 절에서는 주행네트워크 상에서 ACO(Ant Colony Optimization) 알고리즘과 교착상태 회피 개념을 적용하여 교착상태를 회피하면서, 최소시간으로 목적 TP에 이르는 주행경로를 결정하는 방법에 대해서 살펴본다.
첫 번째 실험은 불확실성을 고려하여 정차지점의 예약기간을 추정한 방안의 유용성을 검증하기 위한 실험이다. 본 실험에서는 A^*알고리즘과 휴리스틱 함수로 식 (2)의 h(l)을 적용해 최소시간 주행경로를 결정하였고 주행경로 탐색에 소요되는 시간은 없다고 가정한다.

가설 설정

첫 번째 실험은 불확실성을 고려하여 정차지점의 예약기간을 추정한 방안의 유용성을 검증하기 위한 실험이다. 본 실험에서는 A^*알고리즘과 휴리스틱 함수로 식 (2)의 h(l)을 적용해 최소시간 주행경로를 결정하였고 주행경로 탐색에 소요되는 시간은 없다고 가정한다. 주행시간 추정의 상하한 값을 계산하기 위해서 사용되는 파라미터 α와 β는 α의 값이 작고 β의값이 크면 TP 점유시간이 늘어나면서 평균 TP 대기시간이 점차 길어지고, α와 β의 값이 비슷할수록 대기시간이 짧아지지만 리라우팅 빈도가 높아지는 경향이 있어 실험을 통해서 각각 1.
예약기간이 겹치는 경우에는 다른 ALV가 정차지점을 해지하는 시간을 기준으로 해당 정차지점의 예약기간을 다시 계산하고, 겹치지않는 경우에는 원래의 예약기간을 그대로 사용한다. 정차지점의 예약기간은 이전 정차지점을 떠나는 시간부터 현재 정차지점에 도착하는 시간으로 가정한다.

제안 방법

하지만 이때, 어느 시간이 최적의 설정 값인지 알 수 없으므로 본 논문에서는 ALV가 30대 운행하는 환경에서 0.5초부터 5초까지 주행경로 탐색시간을 변경해가며 최적의 탐색시간을 찾았다.
본 논문에서는 자동화 컨테이너 터미널에서 ALV가 주행계획 수립을 위해 Choe et al.(2013)의 충돌 및 교착 방지를 위한 주행 계획 수립 방안을 기반으로 컨테이너 터미널의 불확실한 요소를 감안하여 정차지점의 예약기간을 추정하는 방안을 제안하였다. 그리고 ACO 알고리즘을 적용하여 최소시간 주행경로를 결정하는 방안에 대해서 제안하였다.
앞선 3. 3 절에서 추정된 정차지점의 예약스케줄이 주행 도중 어긋나면서 교착상태가 발생 할 수 있고, 이를 해결하기 위해서 정차지점의 예약 스케줄과 어긋나게 정차지점이 예약되어 있는 경우 주행 중인 모든 ALV의 경로를 다시 설정하는 방법을 소개하였다. 하지만 이러한 방안은 주행 중인 모든 ALV의 주행경로를 다시 변경하는데 많은 계산비용이 소요된다.
이 방법은 교착상태를 사전에 회피하는 방안과 회피가 불가능한 교착 상태의 경우 교착 상태를 감지하여 이를 해소하는 방안으로 구성되어 있다. 교착상태를 회피하는 방안은 차량이 정차지점을 예약한 순서에 따라 정차지점의 예약기간을 설정하면서 먼저 예약한 차량의 예약 기간과 겹치지 않는 경우에만 예약을 허용하는 것이다. 교착 상태 해소 방안으로는 만일 작업의 불확실성으로 인해 예약 스케줄이 어긋나면서 차량 사이에 교착 상태에 빠진 경우에는 차량이 이동하고자 하는 목적지에 따른 의존관계를 계산하여 사이클이 발생하는 경우 사이클에 들어 있는 모든 차량의 주행 경로를 다시 결정한다.
(2013)의 충돌 및 교착 방지를 위한 주행 계획 수립 방안을 기반으로 컨테이너 터미널의 불확실한 요소를 감안하여 정차지점의 예약기간을 추정하는 방안을 제안하였다. 그리고 ACO 알고리즘을 적용하여 최소시간 주행경로를 결정하는 방안에 대해서 제안하였다.
두 알고리즘의 성능비교는 탐색 시간을 주행시간에 포함하지 않은 경우와 포함한 경우로 나누어 실험하였다. 그리고 두 알고리즘 모두 불확실성을 고려하여 정차지점의 예약기간을 계산하였다. A^*알고리즘의 경우 휴리스틱 함수로 식 (2)의 h(l)을 적용하였고, ACO의 경우 Table 7과 같이 설정 값을 적용하였다.
ALV의 수는 12대에서 30대까지 6대씩 변화시켜 가며 각각 실험하였다. 그리고 매 실험 마다 3000번의 랜덤 주행을 실시한 후, 10회씩 반복한 결과의 평균을 구하였다.
두 번째 실험은 ACO 알고리즘과 최소시간 주행경로를 찾는 A*알고리즘의 성능을 비교 분석한다. 두 알고리즘의 성능비교는 탐색 시간을 주행시간에 포함하지 않은 경우와 포함한 경우로 나누어 실험하였다. 그리고 두 알고리즘 모두 불확실성을 고려하여 정차지점의 예약기간을 계산하였다.
또한, 뒤에 주행한 ALV에 의해서 앞서 주행한 ALV가 불필요하게 우회해서 목적 TP로 주행하는 경우가 발생 할 수 있다. 따라서 본 논문에서는 Fig. 5와 같이 정차지점을 예약하는 시간의 상한 값과 정차지점을 떠나는 시간의 하한 값을 추정하여 보다 길게 정차지점의 예약기간을 구함으로써 예약 스케줄이 조금 어긋나더라도 교착 상태에 빠지지 않게 만든다.
반면에, ACS는 개미가 이동경로를 결정하면 지역적으로 방문한 경로에 대해서 페로몬의 양을 변경하여 나중에 지나가는 개미가 다른 이동경로로 방문할 수 있게 하므로 다양한 경로를 탐색 할 수 있어 AS에 비해 지역 최적화에 빠질 확률이 낮다. 본 논문에서는 ACS 알고리즘을 적용하여 ALV의 주행경로를 결정한다.
본 논문에서는 제안한 주행방안의 성능을 확인하기 위해서 시뮬레이션 실험을 수행하였다. ALV의 수는 12대에서 30대까지 6대씩 변화시켜 가며 각각 실험하였다.
여유시간이 충분치 못하면 경로계획을 전반적으로 다시 수립해야 하는 경우가 자주 발생하여 계산 부담이 가중되는 반면 여유시간이 너무 길어지면 재계획을 거의 하지 않게 되는 대신 다른 차량들의 주행을 지나치게 막음으로써 전체 수송 효율이 떨어지게 된다. 본 연구에서는 적절한 여유시간을 실험적으로 결정하였다.
, 2005)을 이용하여 주행 경로를 탐색한다. 불확실성에 대처하는 방안으로는 주행 경로 상의 단위영역이나 TP를 예약하는 시간에 적절한 여유를 두는 방안을 제안한다. 여유시간이 충분치 못하면 경로계획을 전반적으로 다시 수립해야 하는 경우가 자주 발생하여 계산 부담이 가중되는 반면 여유시간이 너무 길어지면 재계획을 거의 하지 않게 되는 대신 다른 차량들의 주행을 지나치게 막음으로써 전체 수송 효율이 떨어지게 된다.
주행시간 추정의 상하한 값을 계산하기 위해서 사용되는 파라미터 α와 β는 α의 값이 작고 β의값이 크면 TP 점유시간이 늘어나면서 평균 TP 대기시간이 점차 길어지고, α와 β의 값이 비슷할수록 대기시간이 짧아지지만 리라우팅 빈도가 높아지는 경향이 있어 실험을 통해서 각각 1.5와 3.0으로 정하였다.
차량이 정차지점에서 떠나는 시간은 교착상태회피 개념을 적용하여 계산된다. 즉, 해당 정차지점의 예약기간을 추정한 후, 우선적으로 해당 정차지점을 예약 할 수 있는 다른 ALV의 예약기간과 겹치는지를 파악한다. 예약기간이 겹치는 경우에는 다른 ALV가 정차지점을 해지하는 시간을 기준으로 해당 정차지점의 예약기간을 다시 계산하고, 겹치지않는 경우에는 원래의 예약기간을 그대로 사용한다.
차량의 교착상태 및 충돌을 방지하기 위한 방안으로 그래프의 노드 형태에 따라 서로 다른 충돌 및 교착상태 방지 알고리즘을 적용한다. 그래프를 구성하는 노드 중 주행레인에 해당하는 노드에 대해서는 Bae et al.

대상 데이터

본 논문에서는 제안한 주행방안의 성능을 확인하기 위해서 시뮬레이션 실험을 수행하였다. ALV의 수는 12대에서 30대까지 6대씩 변화시켜 가며 각각 실험하였다. 그리고 매 실험 마다 3000번의 랜덤 주행을 실시한 후, 10회씩 반복한 결과의 평균을 구하였다.

데이터처리

두 번째 실험은 ACO 알고리즘과 최소시간 주행경로를 찾는 A*알고리즘의 성능을 비교 분석한다. 두 알고리즘의 성능비교는 탐색 시간을 주행시간에 포함하지 않은 경우와 포함한 경우로 나누어 실험하였다.

이론/모형

그래프를 구성하는 노드 중 주행레인에 해당하는 노드에 대해서는 Bae et al.(2011)의 방법을 적용하였다. 점유 영역 기반의 이 방법에서는 차량의 궤적을 바탕으로 점유 영역을 생성한 후 점유 영역 별 점유 시간을 관리한다.
그래프를 구성하는 노드 중 정차지점에 해당하는 노드에는 Choe et al.(2013)이 제안한 방법을 적용한다. 이 방법은 교착상태를 사전에 회피하는 방안과 회피가 불가능한 교착 상태의 경우 교착 상태를 감지하여 이를 해소하는 방안으로 구성되어 있다.
본 논문에서는 제한된 시간 내에 비교적 최적에 가까운 경로를 탐색할 수 있는 개미 집단 최적화(Ant Colony Optimization, ACO) 기반의 주행경로 탐색 방안(Chen et al., 2009; Montemanni et al., 2005)을 이용하여 주행 경로를 탐색한다. 불확실성에 대처하는 방안으로는 주행 경로 상의 단위영역이나 TP를 예약하는 시간에 적절한 여유를 두는 방안을 제안한다.

성능/효과

실험을 통해 확인 한 바로는 주행경로 탐색에 최고 561초까지 소요되는 것을 확인하였다. 결론적으로 주행경로 탐색시간도 주행시간에 포함되는 실제 환경에서는 본 논문에서 ACO를 이용하여 주행경로를 탐색하는 것이 효과적임을 확인 할 수 있다.
시뮬레이션을 이용한 비교실험 결과 불확실성을 고려한 정차지점의 예약을 통해 정차지점을 보다 정확하게 예약하고 보다 최소시간으로 목적지에 이르는 주행경로를 설정한다는 것을 확인 하였다. 그리고 ALV가 정차지점을 예약하는 과정에서 어떠한 교착상태도 발생하지 않음을 확인하였다.
마지막으로 본 논문에서는 위의 모든 실험을 수행하면서 단 한 번의 교착상태도 발생하지 않았음을 확인하였다.
시뮬레이션을 이용한 비교실험 결과 불확실성을 고려한 정차지점의 예약을 통해 정차지점을 보다 정확하게 예약하고 보다 최소시간으로 목적지에 이르는 주행경로를 설정한다는 것을 확인 하였다. 그리고 ALV가 정차지점을 예약하는 과정에서 어떠한 교착상태도 발생하지 않음을 확인하였다.
ACO의 탐색시간은 Table 8에서 가장 좋은 성능을 보인 1초로 설정 하였다. 실험 결과, 12대에서 18대까지는 두 알고리즘의 평균주행시간이 비슷하나 24대부터는 평균주행시간이 A^* 알고리즘에 비해 짧아지면서 30대에서는 A^* 알고리즘에 비해 약 5% 정도 평균 주행시간의 단축을 확인하였다.
ACO 알고리즘은 주행경로 탐색시간을 1초로 정하면 탐색지연 시간이 일정한 반면, A* 알고리즘은 탐색시간의 제한이 없어 최적 주행경로 탐색에 많은 시간이 소요되는 경우가 있다. 실험을 통해 확인 한 바로는 주행경로 탐색에 최고 561초까지 소요되는 것을 확인하였다. 결론적으로 주행경로 탐색시간도 주행시간에 포함되는 실제 환경에서는 본 논문에서 ACO를 이용하여 주행경로를 탐색하는 것이 효과적임을 확인 할 수 있다.
Table 4는 ALV의 수를 12대에서 30대까지 6대씩 증가시켜 나가면서 평균주행시간을 측정한 결과를 나타낸다. 제안방안인 Strict reservation이 비교방안들 보다 주행 시간 단축에 유리한 것을 확인할 있다. Table 5는 차량이 TP에서 대기한 평균 시간을 나타내고 Table 6은 평균 주행거리를 나타낸다.

후속연구

향후 연구로는, 앞서 본 논문에서는 불확실한 요소를 고려하여 정차기점의 예약기간을 추정하기 위해서 두 가지 설정변수를 사용하는데, 컨테이너 터미널의 상황 변화를 감지하여 유동적으로 이 설정변수 값을 재 변경하는 방안에 대한 연구가 필요하다. 그리고 본 논문에서는 주행경로를 결정하기 위해서 미시적 관점으로 자신의 주행시간이 최소가 되는 경로를 탐색한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	ACO란 무엇인가?	ACO는 실제 개미들이 집에서 먹이까지 가장 짧은 경로를 찾는 방식을 모방하여 그래프 상에서 최적 경로를 찾는 알고리즘이다. 개미들은 먹이를 향해 가는 동안 자신이 지나간 각 경로에 페로몬을 분비하고 나중에 지나가는 개미들은 경로에 남아 있는 페로몬 양을 가지고 먹이까지의 이동경로를 결정한다.
	자동화 컨테이너 터미널에서 무인 자가 운반 하역차량은 어떤 역할을 담당하는가?	자동화 컨테이너 터미널에서 무인 자가 운반 하역차량(Automated Lifting Vehicle, ALV)은 안벽 크레인(Quay Crane, QC)과 장치장의 자동화 크레인(Automated Stacking Crane, ASC) 간의 컨테이너 운반을 담당한다. 적하 작업 시 ALV는 ASC가 장치장에서 집어낸 컨테이너를 지정된 QC까지 운반하고, 양하 작업 시에는 QC가 선박에서 내린 컨테이너를 지정된 장치장의 ASC까지 운반하여 전달한다.
	ACS 알고리즘의 주행경로 탐색과정은 어떤 작업으로 나눌 수 있는가?	ACS 알고리즘은 정해진 시간 동안에만 주행경로를 탐색한다. 주행경로 탐색과정은 후보 해를 생성 하는 작업과 페로몬을 갱신하는 작업으로 나눌 수 있다. 먼저 해를 생성하는 작업은 현재 노드와 이웃 노드들 중에서 이동 가능한 노드들을 선별하는 작업과 선별된 노드들 중에 페로몬과 휴리스틱 정보를 이용해서 확률적으로 다음에 이동 할 노드를 선택하는 작업으로 나누어진다.

참고문헌 (12)

Bae, H. Y., Choe, R., Park, T. J. and Ryu, K. R.(2011), "Comparison of Operations of AGVs and ALVs in an Automated Container Terminal", Journal of Intelligent Manufacturing, Vol. 22, No. 12, pp. 413-426.

상세보기
Chen, P, Huang. H and Dong, X.(2009). "An Ant Colony System Based Heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pickup", Computers and Operation Research, Vol. 36, No. 12, pp. 3215-3223.

상세보기
Choe, R., Lee, D. G. and Ryu, K. R.(2013), "Routing method for automated lifting vehicles considering the reservation schedule of transfer points", The International Conference on Tourism, Transport, and Logistics 2013
Gawrilow, E., Kohler, E., Mohring, R., and Stenzel, B.(2008), Mathematics - Key Technology for the Future, Springer Berlin Heidelberg Press, pp. 165-177.
Imai, A., Nishimura, E. and Current, J.(2007), "A Lagrangian relaxation-based heuristic for vehicle routing with full container load", European Journal of Operational Research, Vol. 176, pp. 87-105.

상세보기
Jin, G. G., So, M. O. and Lee, H. S.(2005), "Job Deployment and Dynamic Routing for Container AGVs", Journal of the Korean Society of Marine Engineering, Vol. 29, No. 3, pp. 369-376.
Ko, K. C. and Egbelu, P. J.(2003), "Unidirectional AGV Guidepath Network Design: A heuristic Algorithm", International Journal of Production Research, Vol. 41, No. 10, pp. 2325-2343.

상세보기
Krishnamurthy, N., Batta, R. and Karwan, M.(1993), "Developing Conflict-Free Routes for Automated Guided Vehicles", Operations Research, Vol. 41, pp. 1077-1090.

상세보기
Mohring, R., Kohler, E., Gawrilow, E., and Stenzel, B.(2005), Conflict-free Real-time AGV Routing. Operations Research Proceedings 2004 SE - 3, Springer, pp. 18-24.
Montemanni, R., Gambardella, L. M., Rizzoli, A. E. and Donati, A. V.(2005), "An ant colony system for Dynamic vehicle routing problem", Journal of Combinatorial Optimization, Vol. 10, No. 4, pp. 327-343

상세보기
Moorthy, R.L., Wee, H. G. and Ng, W. C.(2003), "Cyclic deadlock prediction and avoidance for zone-controlled AGV system", International Journal of Production Economics, Vol. 83, March, pp. 309-324.

상세보기
Taubin, A., Kondratyev, A., and Kishinevsky, M.(1998), "Deadlock Prevention using Petri Nets and Their Unfoldings", International Journal of Advance Manufacturing Technology, Vol. 14, No. 10, pp. 750-759.

상세보기

저자의 다른 논문 :

표제어: 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

연합인증