분할 납품이 가능한 근거리 배선계획에서의 효율적인 선박 운용 경로 결정 방법

Abstract

The purpose of this thesis is to present and solve a ship routing problem called split delivery ship routing problem with time windows (SDSRPTW). The problem has time window constraints and allows split delivery as well as merge delivery. Split and merge delivery can be more economical especially when the unloading ports are far away from the loading ports and there is dead freight fare, which is additional cost incurred when the loads on the ship is less than adequate quantity. However, split and merge delivery make ship routing problem more complex and finding the optimal routes with minimum cost is hard. In this thesis, we handle a real-world practical problem situation with two loading ports and limited number of allowable unloading ports within routes. We develop exact mathematical models for the problem and prove that the problem is NP-hard by restriction it into the bin-packing problem. Then, we propose an insertion based construction algorithm, 2-opt algorithm and multi start 2-opt improvement algorithm (MS2-opt) to generate near optimal solutions quickly. The computational experiments show that the proposed algorithms generate reasonable solutions quickly. The efficiency of split delivery is also analyzed by comparing the cost of non-split case and the split case.