交通网络最优路径搜索的蚁群算法

摘要

针对交通网络中最优路径搜索问题，本文提出一种基于蚁群算法的新的求解方法。首先从剖析最优路径问题的求解要求出发，探讨蚁群算法求解的优势，由于其并行性、正反馈、协作性等特点，能在较短的时间内发现较优解。然后，根据交通网络的特性，在基本蚁群算法的基础上，引入信息素限定规则，采用平滑机制进行局部更新，改进了全局更新模型等，使该算法更能满足交通系统最优路径的求解要求，降低了路径选择的复杂性，从而提高计算效率。对改进的模型进行的模拟实验和比较分析表明，该模型与算法的效果良好。该研究为交通系统最优路径问题开创了一条新的途径，同时显示出蚁群算法在交通分配中的良好使用前景。%In the study a new method of the ant colony optimization (ACO) algorithm was used for solving the problem of choosing the optimal path in a traffic network. To fit the solving requirements, ACO can be considered as the important algorithm for its advantages of parallelism, positive feedback and collaboration. In addition, this algorithm can also be taken advantage to improve the collaboration between different units and find a better solution in a shorter time. The authors improved the basic ACO in many aspects, including introducing the limiting rules for pheromone, using smoothing mechanism to local update, and improving the global update model, so that the algorithm can better solve the optimal path of the transportation system and decrease the complexity of routing choice. An extensive numerical experiment was performed on a traffic network problem. It is found that ACS gives better results compared with the other existed algorithms. Hence, this algorithm is a new way for solving the problem of optimal routing in transportation and illustrates bright application prospect of ACO in traffic assignment.