Institute of Transportation, MOTC

　　Ship routing is essential to a liner carrier’s operation. In the past, carriers in Taiwan usually plan their routing manually, which was inefficient to their operations. This research attempts to develop a model and solution algorithm that could help liner carriers in container ship routing so that their operations can be improved. The model, on the basis of carrier’s perspective considering planning practices without capacity constraint, is formulated as an integer linear program that is characterized as an NP-Hard problem. Two heuristic methods, based on the Clarke-Wright Savings method, the node exchanging technique, the threshold accepting algorithm and the great deluge algorithm, are developed to solve for near-optimal solutions. In order to evaluate the model and solution algorithm in practice, a case study concerning the operation of a major Taiwan liner carrier is performed.