基于改进K-means聚类和遗传算法的混合算法求解异构车辆路径问题
A Hybrid Algorithm Based on Improved K-means Clustering and Genetic Algorithm for Heterogeneous Vehicle Routing Problem
吴麟麟 1吕一鸣 1何美玲 1韩珣2
作者信息
- 1. 江苏大学 汽车与交通工程学院,江苏 镇江 212013
- 2. 智能警务四川省重点实验室,四川 泸州 646000;四川警察学院 道路交通管理系,四川 泸州 646000
- 折叠
摘要
由于目前单一车型配送存在资源浪费和效率低下等问题,选取确定数量的不同车型对各客户点进行配送服务往往可以得到更优的配送路径方案.针对这一点,描述了一种异构车辆路径问题,并建立了具有固定车辆数且考虑固定成本、可变成本以及时间窗惩罚成本的混合整数规划模型.同时,提出了一种基于改进K-means聚类和遗传算法的混合算法对模型进行求解.实验仿真先求解不考虑时间窗的问题初步证明混合算法的有效性,再在带时间窗的问题中求解不同规模算例的单一及异构车型结果,以证明异构车型配送更优.最后,对该混合算法的求解结果与其他混合算法的求解结果进行对比分析,证明了混合算法的优越性.研究结果表明:该混合算法求解的异构车型结果优于单一车型,并且比其他混合算法求解的异构车型结果更优,异构车辆配送使用的配送车辆数更少,总成本也更低,该混合算法具有更好的效率和性能.
Abstract
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.
关键词
异构车辆路径问题/改进K-means聚类算法/遗传算法/混合算法Key words
heterogeneous vehicle routing problem/improved K-means clustering algorithm/genetic al-gorithm/hybrid algorithm引用本文复制引用
出版年
2024
NETL
NSTL
万方数据