基于聚类的LNS算法求解异构VRP问题  

LNS Algorithm Based on Clustering for Solving HVRP

作　　者：赵雄 李琳 ZHAO Xiong;LI Lin(School of Science,Shenyang Aerospace University,Shenyang 110136,China)

机构地区：[1]沈阳航空航天大学理学院,辽宁沈阳110136

出　　处：《计算机技术与发展》2023年第9期98-104,共7页Computer Technology and Development

基　　金：国家自然科学基金项目(61403260);辽宁省自然科学基金项目(2020-MS-233);辽宁省兴辽英才计划项目(XLYC2002017)。

摘　　要：该文研究了异构车辆路径问题(heterogeneous fleet vehicle routing problem,HVRP),在经典HVRP模型的基础上,设计了结合均值漂移聚类算法及大邻域搜索算法的混合求解算法(mean shift-large neighborhood search,MS-LNS)。该算法通过均值漂移聚类算法对客户集进行分类,达到减少计算量、加快算法收敛速度的效果。算法使用单链设计,结合swap邻域变换及insert邻域变换产生新式邻域变换方法,使邻域变换方法可以随机处理路径间与路径内变换。新增redistribution邻域变换,在变换后对新解检测是否存在不满足车辆载重利用率的子路径,并将其删除,达到提高车辆利用率的目的。3组仿真实验使用9组算例:实验一比较了异构与同构车辆的配送效果,验证结果表明异构车辆配送方案成本较低;实验二验证了聚类算法在不同规模客户数据中的有效性;实验三使用MD-LNS算法计算了4组算例,并与4种算法的结果进行比较,验证了在得出相近最优解的前提下,该算法能够减少算法的总体运行时间。仿真实验结果验证了模型的合理性及算法的有效性。We mainly study the heterogeneous fleet vehicle routing problem(HVRP).Based on the classical HVRP model,a mean shift large neighborhood search(MS-LNS)algorithm,which combined with the mean shift clustering algorithm and large neighborhood search algorithm,was proposed.The customer data was divided by classifying the customer set,so as to reduce the amount of calculation and accelerate the convergence speed of the algorithm.The use of single chain design,combined with the swap and insert neighborhood search,the new neighborhood search was produced,which can randomly handle the neighborhood search between paths and one path.In addition,a new neighborhood search named redistribution was used to detect whether there is a sub path that does not meet the vehicle load utilization rate for the new solution after the neighborhood search,and delete it to improve the vehicle utilization rate.Nine numerical examples were used to set up three groups of experiments.Experiment one compares the distribution effects of heterogeneous and homogeneous vehicles,and the verification results show that the cost of heterogeneous vehicle distribution scheme is low.Experiment two verifies the effectiveness of clustering algorithm in different scales of customer data.Experiment three uses MD-LNS to calculate four examples and compare with the four algorithms.It is verified that the algorithm proposed can reduce the overall running time on the premise of obtaining similar optimal solutions.Simulation results verify the rationality of the model and the effectiveness of the algorithm.

关 键 词：异构车辆路径问题 均值漂移聚类算法 大邻域搜索算法 单链设计 redistribution邻域变换 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]