Abstract: In order to improve and optimize a liner shipping system and to meet the requirements of liner service with fixed schedules, a mixed-integer nonlinear model for fleet planning was established based on the multi-call liner route pattern. The objective of the model is to maximize the discounted cash flow of fleet operation during the planning period. Based on the characteristics of the model, a Lagrangian relaxation heuristic algorithm was developed to solve it. A liner fleet of shipping company was taken as an example to demonstrate the model, and the optimal solution including ship allocation, sail frequency and fleet development for multi-route, multi-ship, large-scale fleet planning is obtained by using the proposed heuristic algorithm. The simulation results indicate that the model is able to synthetically take into account many factors such as the forecasted flow of commodity, deadweight utilization and chartering in and out of vessels during fleet planning. Therefore, the model can be applied to the typical liner operation pattern with the same type of ships deployed on the same route, providing decision support for liner fleet planning.