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

摘要：

该文研究了异构车辆路径问题(heterogeneous fleet vehicle routing problem,HVRP),在经典HVRP模型的基础上,设计了结合均值漂移聚类算法及大邻域搜索算法的混合求解算法(mean shift-large neighborhood search,MS-LNS).该算法通过均值漂移聚类算法对客户集进行分类,达到减少计算量、加快算法收敛速度的效果.算法使用单链设计,结合swap邻域变换及insert邻域变换产生新式邻域变换方法,使邻域变换方法可以随机处理路径间与路径内变换.新增redistribution邻域变换,在变换后对新解检测是否存在不满足车辆载重利用率的子路径,并将其删除,达到提高车辆利用率的目的.3组仿真实验使用9 组算例:实验一比较了异构与同构车辆的配送效果,验证结果表明异构车辆配送方案成本较低;实验二验证了聚类算法在不同规模客户数据中的有效性;实验三使用MD-LNS算法计算了4 组算例,并与4 种算法的结果进行比较,验证了在得出相近最优解的前提下,该算法能够减少算法的总体运行时间.仿真实验结果验证了模型的合理性及算法的有效性.

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

所属期刊栏目：33

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金;辽宁省自然科学基金;辽宁省兴辽英才计划项目

在线出版日期：2023-09-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：98-104