A Hybrid Algorithm Based on Improved K-means Clustering and Genetic Algorithm for Heterogeneous Vehicle Routing Problem
The single vehicle distribution model leads to low transportation efficiency,while integrating dif-ferent models of vehicles can better adapt to the size,weight and volume of various goods,so as to maximize the vehicle loading capacity and transportation efficiency,and reduce distribution costs.Compared with the traditional vehicle routing problem,the heterogeneous vehicle routing problem(HVRP)is more relevant in practice.In this paper,we focused on the heterogeneous fixed fleet vehicle routing problem(HFFVRP).According to whether there is time window constraint,we established two mathematical models with minimum total distribution costs as the objective function.Using the improved the K-means clustering algorithm and the genetic algorithm(GA),we proposed a hybrid algorithm to solve the models.The main research contents of this paper are as follows:(1)Considering the constraints of a fixed number of vehicles and a flexible time window,we constructed the HFFVRPTW model with the goal of minimizing the total distribution costs.(2)We designed a hybrid algorithm to solve the HVRP.In view of the use of heterogeneous vehicles for distribution in the HVRP model,we calculated a fixed value K using the sum of the loading capacity of the largest vehicle type and the customer site demand,and allocated appropriate vehicle types to each cluster,so as to improve the K-means clustering algorithm making it more suitable for solving the HVRP.Seeing that the improved K-means clustering algorithm could provide a better initial population for GA,we combined it with GA to propose a hybrid algorithm for the HVRP.(3)We verified the effectiveness of the hybrid algorithm and analyzed the simulation results.First,we pre-liminarily verified the effectiveness of the hybrid algorithm without considering the time window.Then,we selected small scale and large scale examples with time window in the Solomon benchmark database and compared the results with those of other algorithms to further prove the effectiveness of the hybrid algorithm.The research result shows that the hybrid algorithm proposed has higher solving efficiency than other algo-rithms,and can provide better distribution routes of heterogeneous vehicles with lower distribution costs.
NETL
NSTL
万方数据
