一种大规模稀疏中国邮递员问题快速求解方法  

A Fast Solution Method for Large-Scale Sparse Chinese Postman Problem

作　　者：唐继州 何丽莉[1] 白洪涛[1] TANG Jizhou;HE Lili;BAI Hongtao(College of Computer Science and Technology,Jilin University,Changchun 130012,China)

机构地区：[1]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（理学版）》2024年第2期311-319,共9页Journal of Jilin University:Science Edition

基　　金：国家重点研发计划项目(批准号:2022YFF06069003)。

摘　　要：针对现有中国邮递员问题求解方法在大规模稀疏路网图上求解效率的瓶颈,提出一种在可接受时间范围内求得可行解的基于蚁群优化的快速求解方法.该方法针对Euler回路求解的奇偶点图上作业法的第二阶段,采用蚁群算法进行求解,同时根据大规模稀疏路网图的特性基于密度峰值聚类算法对方法进行改进:首先在蚁群算法求解前对大规模稀疏路网图进行聚类分割;其次根据邻近节点覆盖率对分割后的节点群进行合并;最后通过改变部分节点所属聚类使各节点群内部节点个数均为偶数.实验结果表明:在奇偶点图上作业法所能支持的节点规模下,该方法可求得与确定性算法相同的最优解,并在运算时间上达到约10倍的效率优化;且该方法在大规模稀疏路网图下可有效提高计算效率,并在可控时间范围内得到优化的可行解,针对5000个节点规模的路网图最快可在60 s内完成求解.Aiming at the bottleneck of solving efficiency of existing Chinese postman problem solving methods on large-scale sparse road network graph,we proposed a fast solution method based on ant colony optimization to obtain feasible solutions in an acceptable time range.This method used ant colony algorithms to solve the second stage of the odd even point graph operation method for Euler’s loop solution.At the same time,we improved the method based on density peak clustering algorithm according to the characteristics of large-scale sparse road network graph.Firstly,we clustered and segmented the large-scale sparse road network graph before using the ant colony algorithm to solve the problem.Secondly,we merged the segmented node groups according to the coverage of adjacent nodes.Finally,by changing the clustering of some nodes,the number of internal nodes in each node group was even.The experimental results show that:under the node size supported by the homework method on the odd even point graph,the proposed method can obtain the same optimal solution as the deterministic algorithm and achieve the efficiency optimization of about 10 times in the operation time.The proposed method can effectively improve computational efficiency in large-scale sparse road network graphs and obtain optimized feasible solutions within a controllable time range.When facing road network graphs with a scale of 5000 nodes,the fastest solution can be completed within 60 s.

关 键 词：中国邮递员问题 蚁群优化 密度峰值聚类 EULER图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]