This paper studies the joint optimization problem of vessel scheduling and refueling strategy for container liner shipping with cooperative agreements signed by the container terminal operators and the shipping company with multiple vessel arrival time windows, multiple start and end times, and multiple handling rates. A non-linear mixed integer programming model for vessel scheduling and refueling strategy problem of liner shipping is established considering fuel price difference and discount factors at different refueling ports, which aims to minimize the total cost of liner shipping service. A set of discretization and linearization technique is applied to the original model in accordance with the vessel navigation controlling practice. Taking the AEX1 route served by China COSCO Shipping Corporation Limited as an example, a large number of simulation verifications are conducted. The results of numerical examples show that the joint optimization of vessel scheduling and refueling strategy helps shipping companies to flexibly adjust vessel sailing speed. It can significantly reduce the total cost of liner shipping service. The sensitivity analysis indicates that the total cost of liner shipping service and the vessel refueling volume in a voyage will reduce with the expansion of time window of vessel arrival at port in the cooperative agreement. No matter how the fuel price changes, the joint optimization of vessel scheduling and refueling strategy can effectively reduce the total cost of liner shipping service.