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

来源：计算机技术与发展杂志2023年第09期北京时间：

作者：赵雄;李琳

单位：沈阳航空航天大学 理学院,辽宁 沈阳 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 种算法的结果进行比较,验证了在得出相近最优解的前提下,该算法能够减少算法的总体运行时间。 仿真实验结果验证了模型的合理性及算法的有效性。

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

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