Ship route schedule based interactions between container shipping lines and port operators

This chapter examines a practical tactical liner ship route schedule design problem, which involves the interaction between container shipping lines and port operators. When designing the schedule, the availability of each port in a week, i.e., port time window, is incorporated. As a result, the designed schedule can be applied in practice without or with only minimum revisions. We assume that each port on a ship route is visited only once in a round-trip journey. This problem is formulated as a nonlinear non-convex optimization model that aims to minimize the sum of ship cost, bunker cost and inventory cost. In view of the problem structure, an efficient dynamic-programming based solution approach is proposed. First, a lower bound of the number of ships is determined, and then we enumerate all possible numbers of ships. Given the number of ships, we can construct a space-time network that discretizes the time and represents the design of schedule. The optimal schedule in such a space-time network can be obtained by dynamic programming. The algorithm stops when the lower bound is not smaller than the optimal total cost of the best solution obtained. The proposed solution method is tested on a trans-Pacific ship route.