Multi-Depot Low-Carbon Vehicle Routing Problem With Time Windows

The traditional vehicle routing problem (VRP) considers mostly economic benefits, and aims to minimize travel distance or logistics cost. However, the related research considering the impact of transportation on environment is much fewer. Logistics and transportation has become one of the main source of carbon emissions, which is one of the important field to carry out the energy-saving and emission reduction. Under the constrains of capacity, time window, route duration, the number of vehicles of each depot and multi-depot, a new variant of VRP——the multi-depot low-carbon vehicle routing problem with time windows (MDLCVRPTW) is studied. The problem is an extension of traditional multi-depot vehicle routing problem with time windows (MDVRPTW), in which the objective is the environmental benefits. Through the reasonable arrangement of vehicle routing, energy consumption and carbon emissions can be reduced.Based on the historically statistical data and existing research, the macro statistical model of vehicle energy consumption and CO2 emissions is established, considering distance and the weight affecting carbon emissions. And then, a mathematical optimization model is formulated with the minimum carbon emissions. Because MDLCVRPTW is NP-hard problem, the hybrid genetic algorithm with adaptive heuristic mutation is proposed. The generation of the initial solution based on the rule of roulette is designed; the tournament selection and OX cross is adopted; mutation with adaptive choice of neighborhoods search is proposed. Finally, population diversity is kept through the population management.To assess the effectiveness of the proposed algorithm, firstly, it is tested on the benchmark MDVRPTW instances proposed by Cordeau. The computational results show that the method performs impressively in the aspects of solution quality and algorithm stability and convergence time. Secondly, comparison between MDLCVRPTW model and MDVRPTW model shows that the travel distance of the former is increased by an average of 1.65%, but its carbon emission is decreased by an average of 0.90% than that of the latter. This shows that appropriate increase travel distance can reduce carbon emissions during small quantity and multi-batch distribution; Meanwhile, it will not benefit energy-saving and emission reduction only considering the travel distance. Finally, the proposed model and algorithm are applied to SuGuo distribution problem, and the reasonable routing arrangements are given.This paper extends the research of vehicle routing problem, which can provide important decision support for low-carbon transportation.