routing problem

traveling salesman problem

neighborhood search

Journal of Cleaner Production

Global warming is a serious problem presently faced by human society, and CO 2 is a major concern as a greenhouse gas (GHG), especially as the amount of atmospheric CO 2 has been steadily increasing in recent years. Multi-depot model of vehicle routing has sparked widespread interest among researchers as an effective means of reducing cost comprising carbon emissions , fuel consumption, vehicles rental, and driver salaries. In this paper, we developed an improved adaptive large neighborhood search (ALNS) algorithm to efficiently solve large-scale instances of the multi-depot green vehicle routing problem with time windows (MDGVRPTW), based on the characteristics of the multi-depot model, and the formulation of carbon emissions from customers. For the destroy operation, three problem-specific destroy operators that took advantage of the structure of the multi-depot model and the calculation formula of carbon emissions, were deliberately tailored for the MDGVRPTW. The operators could rapidly remove customers causing significant carbon emissions, which enabled these customers to be better positioned in future repair operations. For the repair operation, a noise-greedy repair operator was proposed to enhance the diversification capabilities of the ALNS. Additionally, two methods for speeding up the repair process were proposed to improve computational time. Computational experiments revealed that the proposed ALNS algorithm exhibited a significant improvement in calculation speed and accuracy compared with existing algorithms. • Multi-depot green VRPTW (MDGVRPTW) to reduce emissions and economic cost is studied. • Improved adaptive large neighborhood search (ALNS) is devised for larger-scale MDGVRPTW. • Three novel destroy operators and two speeding-up repair methods are developed. • Accuracy is improved by 17.94% on average compared to classic ALNS.

An adaptive large neighborhood search for the larger-scale multi depot green vehicle routing problem with time windows