In this thesis, we consider the stowage planning problem of arranging containers on board the containership in the maritime transportation system. In the stowage planning, it is important to minimize handling costs and the containership operation costs as well as to maintain the stability of ships. Since containers are accessible only from the top of the stack, undesirable additional handling such as shifting (temporary unloading and reloading of containers) is unavoidable if containers are stored on the container required to be unloaded at the current port. The main objective of stowage planning is to minimize the number of shifting for a tour of a containership. We decompose the stowage planning problem into two subproblems, assignment of container groups into decks and determination of loading patterns of containers in decks. For the first subproblem, we formulate a mathematical model to minimize the number of shifting and the crane movement time in ports, and suggest a greedy algorithm based on the primal network algorithm to solve the fixed charge transportation problem. For the second subproblem, we suggest a tree search method. To see the performance of the suggested algorithm, computation experiments are carried out on randomly generated problems based on real situation of an ocean container liner in Korea. Results showed that the suggested algorithm gave good solutions compared wit the solution of simplified model of Botter and Brinati solved by CPLEX 4.0, a commercial package to solve mixed integer programs.
본 논문은 해상수송에서 컨테이너 선박의 컨테이너 적재위치 결정에 관한 연구이다. 컨테이너 선박에서 컨테이너의 적재 위치를 결정하는 것을 적부 계획(Stowage Planning)이라고 한다. 적부 계획 시 가장 중요하게 고려되는 것은 선박의 안정성을 유지하면서 컨테이너 취급 비용을 최소화하고, 컨테이너선의 운영 비용을 최소화하는 것이다. 컨테이너 적재 시에 먼 항구를 향하는 컨테이너가 가까운 항구를 향하는 컨테이너의 상단에 적재되어 있으면 아래의 컨테이너를 하역하기 위해 상단의 컨테이너를 임시로 하역하고 재적재하는 불필요한 작업이 필요하게 된다. 이를 shifting이라고 하며 이를 최소화하는 것이 적부 계획의 주요한 목표이다. 본 논문에서는 적부 계획 문제를 2단계로 나누어 접근한다. 첫 단계에서 목적지, 크기 및 무게별로 묶인 컨테이너 그룹을 각 deck와 hold에 할당하고, 두 번째 단계에서 각 deck와 hold들에 대해 할당되어진 컨테이너 그룹간의 적재형태를 결정한다. 첫 단계의 문제에 대해 shifting의 횟수와 크레인의 움직임을 최소화하는 fixed charge transportation problem형태의 수리적 모형을 제시하고, 이를 풀기 위하여 primal network algorithm을 기반으로 한 greedy algorithm을 제시하였다. 두 번째 단계를 위해서는 tree search 방법을 제시하였다. 그리고, 위 두 단계를 반복적으로 수행함으로써 해의 개선을 시도하였다.
제시한 알고리즘을 평가하기 위하여, 실제 선사의 자료를 바탕으로 수행도 평가를 해 보았다. Botter와 Britani가 제시한 모형을 단순화한 모형을 CPLEX 4.0을 이용하여 푼 해와 비교한 결과 본 논문에서 제시한 방법이 비교적 우수한 결과를 내었다.
