The impact of fuel supply strategies on the routes of grain fleets is investigated, considering the specificity of grain transportation by sea and the spatiotemporal variations in fuel prices at supply ports. In order to minimize the operational costs of grain fleets, the relationship between fuel prices and supply quantity at fuel supply ports was analyzed, as well as the association between the average fuel price at fuel supply ports and port usage fees. A mixed integer programming model was constructed using the selection of fuel supply ports, fuel supply quantity, and vessel navigation routes as decision variables, based on the transport characteristics of grain fleets. The model was solved using the Gurobi solver, and its effectiveness was verified using a grain transportation fleet under a certain international dry bulk shipping company. The results suggested that grain fleets could reduce fuel costs by selecting fuel supply ports near vessel routes with lower fuel prices, except when loading and unloading cargo. Moreover, as fuel prices increased, grain fleets could optimize vessel transportation routes and selected more fuel supply ports for refueling to lower the average fuel supply price, ultimately achieved cost reduction.