Improved Nearest Neighbor Algorithm for Multi Depot Vehicle Routing Problem
LI Yan
PAN Dazhi
Abstract：In this paper,an improved nearest neighbor algorithm is proposed to solve the multi depot vehicle routing problem(MDVRP)In order to effectively control the solution space of the problem.This paper integrates the advantages of the nearest neigh-bor algorithm and K-means algorithm to allocate more reasonable parking lots for customers,and decomposes the multi parking lot vehicle routing problem into multiple single parking lot vehicle routing subproblems.In the solution phase of the subproblems,a cod-ing and decoding rule is proposed.Based on the improved utilization of vehicle loading,the length of parking lot vehicle routing is reduced,and a global optimization strategy is designed.Based on the customer access sequence inside the vehicle and the change of path length caused by the change of customers between vehicles,a local optimization strategy is designed,and a search strategy that changes with the number of customers served by the vehicle is proposed,which improves the operation efficiency of the algorithm.The effectiveness of the proposed algorithm is verified on problems of different scales and simulation experiments.
Keywords：vehicle routing problemmulti depotnearest neighbor algorithmK-means algorithm
Publication Date：2024-09-20
Online Publishing Date：2025-08-15(First online date of this platform, not the publication date of the document)
Pages：6( 2634-2639 )