Because of the harmful effects of greenhouse gas (GHG) emitted by petroleum-based fuels, the adoption of alternative green fuels such as biodiesel and compressed natural gas (CNG) is an inevitable trend in the transportation sector. However, the transition to alternative fuel vehicle (AFV) fleets is not easy and, particularly at the beginning of the transition period, drivers may be forced to travel long distances to reach alternative fueling stations (AFSs). In this paper, the utilization of bi-fuel vehicles is proposed as an operational approach. We present a mathematical model to address vehicle routing problem (VRP) with bi-fuel vehicles and show that the utilization of bi-fuel vehicles can lead to a significant reduction in GHG emissions. Moreover, a simulated annealing algorithm is adopted to solve large instances of this problem. The performance of the proposed algorithm is evaluated on some random instances.