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

Abstract: 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 5 000 nodes, the fastest solution can be completed within 60 s.

Key words: Chinese postmen problem, ant colony optimization, density peak clustering, Euler diagram