The distribution process or activities is one of the most important aspects in ensuring the energy demand fulfillment in every country. This study opts for the case of Liquified Natural Gas (LNG) distribution in supporting the sustainable energy demand fulfillment in Indonesia, especially at the Bali-Nusa Tenggara cluster. Indonesia is the biggest archipelago in the world where shipment through the ocean is the most prominent transportation mode. This study implements model fleet size and mixed vehicle routing problem (FSMVRP) combined with mixed-integer linear programming (MILP) to solve the stated problem by performing distribution route optimization. The constraints of this study consist of the fleet specification acceptance toward each terminal, and also the consideration LNG Terminal at Benoa and Makassar as only the warehousing area. Other than the distribution route, the FSMVRP and MILP model can be utilized to model the required fleet number and its utilization that has the minimum cost. This study is expected to enrich the energy distribution optimization literature and the FSMVRP and MILP combination literature in solving distributions problem that has a very strategic influence on the decision making.