基于带约束谱聚类的启发式车辆路径规划算法优化方法

来源：计算机应用杂志2025年第5期北京时间：

作者：罗蒙, 高超, 王震

单位：1.西北工业大学 机电学院，西安 710072；2.西北工业大学 光电与智能研究院，西安 710072；3.西北工业大学 网络空间与安全学院，西安 710072

摘要：针对现有启发式算法在解决大规模多车场车辆路径规划问题（MDVRP）时存在的初始解质量较差的缺点，提出一种基于带约束谱聚类（CSC）的启发式车辆路径规划算法优化方法。首先，根据待配送客户点的地理位置和需求量生成配送点的地理信息特征矩阵和需求信息特征矩阵；其次，根据地理信息特征矩阵和需求信息特征矩阵生成CSC的约束矩阵，并完成聚类操作；最后，使用谱聚类的结果生成启发式算法的初始解，选择合适的启发式算法完成车辆路径规划问题（VRP）的求解。在标准数据集的21个算例上的实验结果显示，CSC相较于SCSC（Self-Constrained-Spectral-Clustering）在标准化互信息（NMI）和Fowlkes-Mallows指数（FMI）上分别提升了18.75%和31.18%；在车辆路径规划任务中，使用CSC进行初始化的启发式算法在21个不同规模算例中的16个算例上求得了最短路径，并且启发式算法的运行时间相较于使用SCSC缩短了13.05%。实验结果表明，CSC能够有效提高客户点的聚类精度，进而能够有效提高VRP的求解速度和解的精度。

关键词：谱聚类,车辆路径规划问题,多车场车辆路径规划问题,启发式算法,标准化互信息,Fowlkes-Mallows指数

基金资助：国家重点研发计划项目(2022YFE0112300);国家自然科学基金资助项目(62025602)