Good short-term ship scheduling and container shipment planning are very important for liner operations; however, in Taiwan, most such carriers currently utilize a trial-and-error process. In this study, we employ network flow techniques to construct a model for such activities. A solution algorithm, based on Lagrangian relaxation, a subgradient method, and a heuristic for the upper-bound solution, is developed to solve the model. To demonstrate and to test how well the model and the solution algorithm apply in the real world, we performed a case study using operating data from a major Taiwanese marine shipping company. The test results show that the model and the solution algorithm could be useful references for ship scheduling and container shipment planning.
