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

摘要

针对现有中国邮递员问题求解方法在大规模稀疏路网图上求解效率的瓶颈，提出一种在可接受时间范围内求得可行解的基于蚁群优化的快速求解方法.该方法针对Euler回路求解的奇偶点图上作业法的第二阶段，采用蚁群算法进行求解，同时根据大规模稀疏路网图的特性基于密度峰值聚类算法对方法进行改进：首先在蚁群算法求解前对大规模稀疏路网图进行聚类分割；其次根据邻近节点覆盖率对分割后的节点群进行合并；最后通过改变部分节点所属聚类使各节点群内部节点个数均为偶数.实验结果表明：在奇偶点图上作业法所能支持的节点规模下，该方法可求得与确定性算法相同的最优解，并在运算时间上达到约10倍的效率优化；且该方法在大规模稀疏路网图下可有效提高计算效率，并在可控时间范围内得到优化的可行解，针对5 000个节点规模的路网图最快可在60 s内完成求解.

关键词

中国邮递员问题 / 蚁群优化 / 密度峰值聚类 / Euler图