Branch-and-Price Algorithm For The Multi-Depot Green Vehicle Routing Problem With Time Windows

With the deepening of globalization and the strengthening of supply chain management,logistics transportion plays an increasingly irreplaceable role in the current social and economic activies.However,emission from a large number of logistics activities have also raised concerns about air colution.In order to reduce the negative impact of logistics on the environment,scholars have 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,the logistics system in today’s society often involves multiple distribution centers,so the multi-deport GVRP has become a subject worth studying.This project aims to achieve the goal of minimizing the total carborn emission by constructing the appropriate driving route from each depot.In this paper,we propose the exact algorithm of MDGVRP with time windows(MDGVRPTW),which aims to provide another way to solve the MDGVRPTW.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 propose the branch-and-price algorithm to solve the MDGVRPTW.(2)In order to reduce the redundancy of the sub-problem of MDGVRPTW,a multi-depot aggregation labeling algorithm is proposed.The algorithm solves the sub-problem under certain conditions is aggregated from mutilple times to one time,which effectively avoids the redundancy in the soving process and reduces the computation time.(3)In order to futher accelerate the solution of the sub-problem of MDGVRPTW,a multidepot approximate labeling algorithm is proposed.The algorithm can effectively reduce the calculation times in the solution of the sub-problem,thus reducing the calculation time and improving the efficiency of the algorithm.(4)We use different scales of date to verify the applicability of the algorithms.We propose the branch-and-price algorithm and these two proved Branch-and-price algorithms can solve large,medium and small-scale instances.The results show that the branchand-price algorithm with the multi-depot aggregation labeling algorithm can solve small and medium-scale instances more efficiently.The branch-and-price algorithm with the multi-depot approximate labeling algorithm futher accelerate the subproblem solving and has better performance.We then compare the experimental results of multi-depot with the results of single-depot.The results show that multi-depot conditions can effectively reduce carbon emission.