Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem

The vehicle routing problem (VRP) has been addressed in many research papers. Only a few of them take time-dependent travel speeds into consideration. Moreover, most research related to the VRP aims to minimize total travel time or travel distance. In recent years, reducing carbon emissions has become an important issue. Therefore, fuel consumption is also an important index in the VRP. In this research a model is proposed for calculating total fuel consumption for the time-dependent vehicle routing problem (TDVRP) where speed and travel times are assumed to depend on the time of travel when planning vehicle routing. In the model, the fuel consumption not only takes loading weight into consideration but also satisfies the "non-passing" property, which is ignored in most TDVRP-related research papers. Then a simulated annealing (SA) algorithm is proposed for finding the vehicle routing with the lowest total fuel consumption. An experimental evaluation of the proposed method is performed. The results show that the proposed method provides a 24.61% improvement in fuel consumption over the method based on minimizing transportation time and a 22.69% improvement over the method based on minimizing transportation distances. (C) 2010 Elsevier Ltd. All rights reserved.