With increasing concerns on environmental issues, recent research on Vehicle Routing Problems (VRP) has added new factors such as greenhouse gas emissions and alternative fuel vehicles into the models. In this report, the authors consider one such promising alternative fuel vehicle, Compressed Natural Gas (CNG). However, due to the limited number of available fueling stations and small fuel tank capacity, CNG trucks face several challenges on their way to replacing traditional diesel trucks. Even though CNG trucks have advantages on less greenhouse gas emissions and cheaper fuel cost, the detours to the fueling station may increase the total travel distance. The authors introduce the CNG Truck Routing Problem with Fueling Stations (CTRPFS) to model decisions to be made with regards to the vehicle routes including the choice of fueling stations. Moreover the authors consider load capacity, fuel tank capacity and the driver’s daily traveling distance limitation. The authors develop a Mixed Integer Programming (MIP) model with preprocessing and valid inequalities to solve the problem optimally. A hybrid heuristic method is also proposed to solve this problem, which combines an Adaptive Large Neighborhood Search (ALNS) with a local search and a MIP model.
