Equitable use of fuel products must be carried out by the Indonesian government, especially for the eastern region of Indonesia where most of the natural conditions are in the form of the sea. Since consumer requests on the islands come in at different times, fuel product deliveries are made in response to local demand, and occasionally the cargo hauled is not entirely full. Another challenge in shipping by ship is crew costs and the increase of fuel prices, thus making the company try different operational strategies. In addition, the open water conditions around September to early March are in choppy conditions, making the company spend more fuel costs, and of course it will require more costs as well. The company that distributes fuel products to consumers has three depots, twenty consumers, and twenty vessels with different capacities. Under these conditions, the problem will be solved by using a multi-depot vehicle routing problem using a heterogeneous fleet and binary integer programming. At the initial stage, the solution to the routing problem is expected to get the smallest distance, determine the ship that will carry out the transportation and determine the customers to be served. The purpose of the study is to meet consumer demand with minimum transportation costs and calculate the amount of emissions caused by the distribution of fuel based on routes and sea conditions. This study resulted in 13 of 20 vessels owned by the company assigned to the delivery of fuel. When sailing in choppy sea conditions, the transportation cost increase by 16.70 percent, and emissions CO2 increase by an average 17.28 percent when compared with calm water conditions.