Journal of Computer Applications ›› 2025, Vol. 45 ›› Issue (5): 1387-1394.DOI: 10.11772/j.issn.1001-9081.2024060882

• China Conference on Data Mining 2024 (CCDM 2024) • Previous Articles    

Improvement method of heuristic vehicle routing algorithm based on constrained spectral clustering

Meng LUO1, Chao GAO2(), Zhen WANG3   

  1. 1.School of Mechanical Engineering,Northwestern Polytechnical University,Xi'an Shaanxi 710072,China
    2.School of Artificial Intelligence,Optics and ElectroNics,Northwestern Polytechnical University,Xi'an Shaanxi 710072,China
    3.School of Cybersecurity,Northwestern Polytechnical University,Xi'an Shaanxi 710072,China
  • Received:2024-07-03 Revised:2024-07-28 Accepted:2024-08-02 Online:2024-12-04 Published:2025-05-10
  • Contact: Chao GAO
  • About author:LUO Meng, born in 2000, M. S. candidate. His research interests include multi-objective optimization, evolutionary computing.
    GAO Chao, born in 1980, Ph. D., professor. His research interests include multimodal cognitive computing, group intelligent decision-making.
    WANG Zhen, born in 1986, Ph.D., professor. His research interests include multimodal cognitive computing, group intelligent decision-making.
  • Supported by:
    National Key Research and Development Program of China(2022YFE0112300);National Natural Science Foundation of China(62025602)

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

罗蒙1, 高超2(), 王震3   

  1. 1.西北工业大学 机电学院,西安 710072
    2.西北工业大学 光电与智能研究院,西安 710072
    3.西北工业大学 网络空间与安全学院,西安 710072
  • 通讯作者: 高超
  • 作者简介:罗蒙(2000—),男,陕西汉中人,硕士研究生,CCF学生会员,主要研究方向:多目标优化、进化计算
    高超(1980—),男,辽宁鞍山人,教授,博士,CCF会员,主要研究方向:多模态认知计算、群智能决策
    王震(1986—),男,山西高平人,教授,博士,CCF会员,主要研究方向:多模态认知计算、群智能决策。
  • 基金资助:
    国家重点研发计划项目(2022YFE0112300);国家自然科学基金资助项目(62025602)

Abstract:

Aiming at the poor initial solution quality of existing heuristic algorithms in solving large-scale Multi-Depot Vehicle Routing Problems (MDVRPs), an improvement method of heuristic vehicle routing algorithm based on Constrained Spectral Clustering (CSC) was proposed. Firstly, the geographical and demand information feature matrices of delivery points were generated according to the geographical location and demand quantities of the customers to be served. Secondly, the constraint matrix with CSC was generated according to these feature matrices to perform clustering operations. Finally, the spectral clustering results were used to generate the initial solutions of the heuristic algorithms, and the appropriate heuristic algorithms were selected to solve the Vehicle Routing Problems (VRPs). Experimental results on 21 benchmark instances demonstrate that compared with Self-Constrained Spectral Clustering (SCSC), CSC achieves 18.75% and 31.18% improvements in Normalized Mutual Information (NMI) and Fowlkes-Mallows Index (FMI), respectively. In vehicle routing tasks, the heuristic algorithm initialized with CSC obtains the shortest path on 16 of 21 different sized instances while reducing runtime by 13.05% compared with SCSC-based initialization. Experimental results indicate that CSC can effectively improve the clustering accuracy of customer points, thereby improving both solving speed and solution quality for VRPs.

Key words: spectral clustering, Vehicle Routing Problem (VRP), Multi-Depot Vehicle Routing Problem (MDVRP), heuristic algorithm, Normalized Mutual Information (NMI), Fowlkes-Mallows Index (FMI)

摘要:

针对现有启发式算法在解决大规模多车场车辆路径规划问题(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指数

CLC Number: