[1]赵 雄,李 琳.基于聚类的 LNS 算法求解异构 VRP 问题[J].计算机技术与发展,2023,33(09):98-104.[doi:10. 3969 / j. issn. 1673-629X. 2023. 09. 015]
　ZHAO Xiong,LI Lin.LNS Algorithm Based on Clustering for Solving HVRP[J].,2023,33(09):98-104.[doi:10. 3969 / j. issn. 1673-629X. 2023. 09. 015]

点击复制

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

分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:

33

期数:

2023年09期

页码:

98-104

栏目:

人工智能

出版日期:

2023-09-10

文章信息/Info

Title:

LNS Algorithm Based on Clustering for Solving HVRP

文章编号:

1673-629X(2023)09-0098-07

作者:

赵 雄; 李 琳

沈阳航空航天大学 理学院,辽宁 沈阳 110136

Author(s):

ZHAO Xiong; LI Lin

School of Science,Shenyang Aerospace University,Shenyang 110136,China

关键词:

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

Keywords:

HVRP;  mean - shift clustering algorithm;  large neighborhood search algorithm;  single chain design;  redistributionneighborhood search

分类号:

TP301. 6

DOI:

10. 3969 / j. issn. 1673-629X. 2023. 09. 015

摘要:

该文研究了异构车辆路径问题( heterogeneous fleet vehicle routing problem,HVRP) ,在经典 HVRP 模型的基础上,设计了结合均值漂移聚类算法及大邻域搜索算法的混

合求解算法( mean shift-large neighborhood search,MS-LNS) 。 该算法通过均值漂移聚类算法对客户集进行分类,达到减少计算量、加快算法收敛速度的效果。 算法使用单链设计,结合 swap 邻域变换及 insert 邻域变换产生新式邻域变换方法,使邻域变换方法可以随机处理路径间与路径内变换。 新增 redistribution邻域变换,在变换后对新解检测是否存在不满足车辆载重利用率的子路径,并将其删除,达到提高车辆利用率的目的。 3组仿真实验使用 9 组算例:实验一比较了异构与同构车辆的配送效果,验证结果表明异构车辆配送方案成本较低;实验二验证了聚类算法在不同规模客户数据中的有效性;实验三使用 MD-LNS 算法计算了 4 组算例,并与 4 种算法的结果进行比较,

验证了在得出相近最优解的前提下,该算法能够减少算法的总体运行时间。 仿真实验结果验证了模型的合理性及算法的有效性。

Abstract:

We mainly study the heterogeneous fleet vehicle routing problem ( HVRP) . Based on the classical HVRP model,a mean shiftlarge neighborhood search ( MS -?

LNS) algorithm, which combined with the mean shift clustering algorithm and large neighborhoodsearch algorithm,was proposed. The customer data was divided?

by classifying the customer set,so as to reduce the amount of calculationand accelerate the convergence speed of the algorithm. The use of single chain design,　combined with the swap and insert neighborhoodsearch,the new neighborhood search was produced,which can randomly handle the neighborhood search between paths and one path. Inaddition,a new neighborhood search named redistribution was used to detect whether there is a sub path that does not meet the vehicleload utilization rate for the new solution after the neighborhood search, and delete it to improve the vehicle utilization rate. Ninenumerical examples were used to set up three groups of experiments. Experiment one compares the distribution effects of heterogeneousand homogeneous vehicles,and the verification results show that the cost of heterogeneous vehicle distribution scheme is low. Experimenttwo verifies the effectiveness of clustering algorithm in different scales of customer data. Experiment three uses MD-LNS to calculatefour examples and compare with the four algorithms. It is verified that the algorithm proposed can reduce the overall running time on thepremise of obtaining similar optimal solutions. Simulation results verify the rationality of the model and the effectiveness of the algorithm.

常用功能