基于电子地图的改进蚁群算法及其车辆路径寻优

Improved ant colony algorithm based on electronic map and vehicle routing optimization

路径优化研究中以目标节点的线性距离之和最短作为最优路径的求解结果难以运用于实际.文中提出了结合电子地图API的改进蚁群算法,首先得到各个节点之间的实际道路导航距离,然后对基本蚁群算法进行改进.在节点选择策略上采用了轮盘选择策略;在算法的不同时期对信息素挥发系数ρ进行调整;计算目标节点距离时去掉节点间直线距离,而采用从电子地图获取的实际导航距离;最后获取电子地图数据,用于改进后的蚁群算法,进行最优路径求解.实验结果分析表明,算法改进前后求得的直线最短路程分别为64.526、62.598 km,验证了改进后算法的有效性,实际道路导航最短路程为89.378 km,说明文中提出的最优路径求解方式更切合实际,实用性更高.

In the research of vehicle routing optimization,the minimum of the sum of the linear distances of the target nodes is usually used as the solution to the optimal path,which is difficult to be applied in practice.This paper proposes an improved ant colony algorithm combined with the electronic map API.Firstly,the actual road navigation distance between each node is obtained through the corresponding API interface provided by the electronic map,and then the basic ant colony algorithm is improved.Roulette selection strategy is adopted as the node selection strategy,the value of the pheromone volatilization coefficient ρ is adjusted at different stages of the algorithm,and the actual navigation distance is provided by the electronic map when the target node distance is calculated and the linear distance between the nodes is removed.Finally,the data obtained by the electronic map is used to solve the optimal path by the improved ant colony algorithm.The experimental results show that the shortest distances of the straight lines before and after the improvement of the algorithm are 64.526 km and 62.598 km.The effectiveness of the improved algorithm is verified.The shortest path of the actual road navigation is 89.378 km.It shows that the optimal path solution proposed in this paper is more practical.