듀얼모드 안벽 크레인의 스케줄링 문제를 위한 동적계획법 기반의 알고리즘 연구

• 영문명: A Study on the Dynamic Programming-based Algorithm for the Dual-spreader Quay Crane Scheduling
• 발행기관: 한국물류학회
• 저자명: 공인택(Gong, In-Taek) 김동윤(Kim, Dong-Yun) 김무영(Kim, Moo-Young) 민윤홍(Min, Yun-Hong)
• 간행물 정보: 『물류학회지』제32권 제4호, 1~9쪽, 전체 9쪽
• 주제분류: 경제경영 > 무역학
• 파일형태: PDF
• 발행일자: 2022.08.31

국문 초록

메가 컨테이너선의 도입으로 컨테이너 수송에서 규모의 경제가 극대화됨에 따라 항만과 터미널에서도 컨테이너 처리량의 증가에 대비하기 위하여 큰 노력을 기울이고 있다. 이러한 노력 중 하나가 한 번에 두 개 이상의 컨테이너를 동시에 양·적하할 수있는 안벽 크레인을 사용하는 것이다. 이러한 안벽 크레인은 작동 모드에 따라 하나 또는 그 이상의 컨테이너를 양·적하할 수있다. 하지만 스케줄링 관점에서는 한 번에 양·적하할 수 있는 컨테이너의 중량 제한, 작동 모드 변경 시 필요한 셋업 시간 등을고려해야 하므로 기존 안벽 크레인의 스케줄링보다 더 복잡하다. 이미 선행연구에서 이 문제의 중요성을 언급하고 이를 위한 해법을 제시하였지만, 그 수가 많지 않아 다양한 접근방법에 대한 검증이 필요한 상황이다. 본 논문은 최대 두 개의 컨테이너를 동시에 양·적하할 수 있는 듀얼-스프레더(dual-spreader) 안벽 크레인의 스케줄링 문제를 다룬다. 본 논문에서는 이 문제에 대한 마르코프 결정 프로세스(MDP) 모형을 제시하고 해를 얻는 데까지 걸리는 계산 시간을 줄이기 위해 완전한 동적 계획법을 사용하는대신, 해 탐색에 사용하는 일부 상태와 전이 함수를 부분적으로만 고려하는 휴리스틱을 제안하였다. 이 휴리스틱은 MDP 모형에서일부 상태와 전이 함수만을 고려하기 때문에 항상 최적해를 도출하는 것을 보장하지는 못하지만 비교적 작은 문제에 대해서는 최적해와 근접한 해를 도출한다는 것을 확인하였다. 큰 문제에 대해서는 상용 소프트웨어가 한 시간 동안 최적해를 찾지 못하였지만본 휴리스틱은 해를 도출하였고, 이 해가 상용 소프트웨어가 한 시간 동안 찾은 해보다 더 좋은 해 품질을 갖는다는 것을 확인하였다.

영문 초록

As economies of scale in container transport are maximized with the introduction of mega container ships, ports and terminals are also making great efforts to prepare for an increase in their capacities. One example of such efforts is the use of a new type of quay crane that can simultaneously lift more than one container at a time. This quay crane can lift one or more containers depending on its lifting mode. However, scheduling of this crane is more complicated than scheduling of existing quay cranes because it is necessary to consider the weight limit of containers to be lifted, and the set-up time required for changing the lifting mode. Previous study has already mentioned the importance of this problem and suggested solutions for it, but since there are not many, verification of various approaches is necessary. This paper addresses the scheduling problem of dual-spreader quay crane that can lift up-to two containers at a time. We propose a Markov decision process (MDP) model for the problem. In order to reduce the computation time required to obtain a solution, instead of applying dynamic programming, we propose a heuristic that only considers a subset of states and transition functions used for searching solutions. Since this heuristic does not consider all possible states and transition functions, it cannot guarantee that an optimal solution is derived. However, as confirmed through experiments, it finds a solution close to the optimal solution for relatively small-sized instances. And, for larger-sized instances, while commercial software did not find an optimal solution for one hour, this heuristic can find a solution. Moreover, the solution from the proposed heuristic has better quality than the solution found by commercial software for one hour.

목차

Ⅰ. 서 론

Ⅱ. 문헌연구

Ⅲ. 문제정의

Ⅳ. 방법론

Ⅴ. 실 험

Ⅵ. 결 론

참고문헌

키워드

듀얼 스프레더 크레인 안벽크레인 스케줄링 동적 계획법 휴리스틱 자원 스케줄링 Twin-spreader Crane Quay Crane Scheduling Dynamic Programming Heuristic Resource Scheduling