Time-dependent Multi-depot Green Vehicle Routing Problem with Time Windows Considering Temporal-Spatial Distance

Abstract Reducing distribution costs is one of the effective ways for logistics enterprises to improve their core competitiveness. Aiming at the multi-depot vehicle routing problem under the time-varying road network, this paper proposes an integer programming model with the minimum total costs by comprehensively considering the fixed costs of vehicles, penalty costs on earliness and tardiness, fuel costs and the effects of vehicle speed, load and road gradient on fuel consumption. A hybrid genetic algorithm with variable neighborhood search is developed to solve the problem. In the algorithm, the temporal-spatial distance is introduced to cluster the customers to generate an initial population to improve the quality of the initial solution. Adaptive neighborhood search times strategy and simulated annealing inferior solution acceptance mechanism are used to balance the diversification and exploitation in the algorithm iteration process. Numerical results show that the model and algorithm we proposed are rather effective. The research results not only deepen and expand the vehicle routing problem (VRP) theory research, but also provide a scientific and reasonable method for logistics enterprises to make the vehicle scheduling plan.