A nonlinear integer programming model on cruise service planning is proposed. Constraints on the availability of berths at each port are considered. Two linearization methods are developed for the model. Some properties are proved by using the dynamic programming and heuristics. The proposed model demonstrates robustness and can obtain near-optimal plans.