Branch-and-Price Algorithm For Heterogeneous Fleet Green Vehicle Routing Problem With Time Windows

The negative impact of air pollution on the global environment is increasing,and the exhaust emissions constitute a large part of transportation.In order to improve logistics efficiency and reduce the negative impact of logistics activities on the environment,the academic community has proposed the Green vehicle routing problem(GVRP).The GVRP aims to reduce carbon emissions as much as possible with respecting the customer demands and other constraints.At the same time,considering the fact that some organizations and enterprises not only use a single type vehicle when taking logistics and transportation services,our research focus on reducing the carbon emissions of Heterogeneous fleet GVRP(HFGVRP).Under the condition of heterogeneous fleet vehicles,those vehicles are used to serve customers,which can avoid the waste of vehicle capacity resources and effectively reduce the carbon emissions during transportation.Up to now,related HFGVRP researches are based on heuristic algorithm,and there is no corresponding accurate algorithm research.In this paper,we propose the exact algorithm of HFGVRP with time windows(HFGVRPTW),which aims to provide another way to solve the HFGVRPTW.It is also the exploration and development of related research in this field.The main research contents of this paper are as follows:(1)We studied the HFGVRP and its carbon emission calculation method,and then propose the Branch-and-price algorithm to firstly solve the problem.We then compare the experimental results of heterogeneous fleet vehicles with the results of homogenous fleet vehicles.(2)To speed up solving the pricing problem,we develop a multi-vehicle approximate dynamic programming(MVADP)algorithm based on labeling algorithm.The MVADP algorithm reduces labels by integrating the calculation of pricing problems of all vehicle types.(3)Additionally,to quickly get a tighter upper bound,we propose an integer branch method.For each branch,we solve master problem with the integer constraint by CPLEX using the columns produced by column generation.We retain the smaller one of the obtained integer solution and the current upper bound,thus the branches are reduced significantly.(4)Extensive computational experiments were performed on the Solomon benchmark instances.The results show the branches and computing time were reduced significantly by our proposed BP algorithm.