基于改进蚁群算法的避免拥堵最优路径选择

作     者：胡昆 

作者单位：西南交通大学 

学位级别：硕士

导师姓名：景红

授予年度：2018年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：蚁群算法 拥堵 最优路径 

摘      要：近年来,随着经济的发展,人们生活水平的提高,有越来越多的人拥有自己的私家车辆。城市也在不断修建或者改善道路状况。车辆的增多,城市道路改建,加上其他许多因素,导致道路变得越来越拥堵,驾驶出行变得越来越困难,如何避免道路拥堵情况,然后以最理想的路径到达目的地,是人们自驾出行的迫切希望。国内外关于最优路径研究工作已取得许多成果,且多考虑的只是道路状况对出行的影响。而怎样将路径长度、交通限流、交通信号灯对道路拥堵造成的影响作为出行考虑的研究不多。因此,构建成数据模型去模拟交通拥堵是一个值得研究的问题,本文就此问题做了建模。蚁群优化算法已成功地应用于最优路径的选择,但上述约束的单独应用还未见研究,本文拟采用研究加入动态拥堵因素数据模型的改进蚁群算法来解决出行拥堵的问题。为此,本文提出了一种改进的蚁群算法,即避免拥堵的蚁群算法(Avoid Traffic Jam Ant Colony Optimization,简称ATJ-ACO),来寻找避免拥堵后找到的最优路径的问题。这个算法包含了几个适应问题的特殊机制:(1)一个启发函数改变规则,减少蚂蚁盲目搜索,加快算法收敛速度;(2)一个基于拥堵问题的信息素初始分布设计,根据路径存在是否拥堵以及拥堵的状况不相同来分布信息素,加快蚂蚁对畅通路径的寻找的效率,减少算法找到最优解的搜索时间;(3)一个基于拥堵问题的局部信息素更新,通过新的信息素局部更新方式使当前最优路径的局部路径信息变化能够迅速地表现在路径的信息素分布上,从而提高算法搜索的效率;(4)一个基于拥堵问题的全局信息素更新,根据拥堵状况进行全局信息素更新,使全局路径信息变化能够迅速地表现在路径的信息素分布上。通过这些有效的机制,ATJ-ACO算法能够结合全局和局部信息,充分构建出全局最优的解。本文用仿真实验验证改进的算法,然后在成都市部分地图上证明算法的有效性和实用性。并且,在进行的仿真实验中,本文提出的算法在效果上比其他算法表现更有效。