多约束的城市道路交通信息的最优路径算法研究

最优路径算法一直是学者们关注和研究的热点，传统的最优路径算法主要是在静态网络下求解单一约束条件——结点之间路径长度下的最短路径，在算法求解之前该值是确定的，并且是可知的。在问题规模较小、网络较简单的情况下，传统的最优路径算法能够求解出较满意的结果。然而，现在的城市道路交通网络是复杂的、时刻变化的，结点数目比较多而且结点之间包含的信息不再是单一的、确定的，并且无法提前预知。现在出行者对最优路径的要求不再是路径最短，而希望是综合考虑了城市道路上的多个交通信息，得到更符合出行安全便捷目的的路径。在这种需求下，传统的最优路径问题就演变成为在多个约束条件下的相对最优路径问题。 蚁群算法是受蚁群觅食行为启发而提出的一类智能算法，该算法能有效地解决组合优化问题。在实际搜索过程中能对外界的变化动态的作出响应，在城市道路交通最优路径选择中具有可行性。本文正是利用了蚁群算法的优点，对基本蚁群算法进行改进。本文的内容主要包括以下几个方面： (1)从最优路径以及蚁群算法的研究现状出发，分析了现有研究中存在的问题；描述了最优路径问题以及多约束最优路径的模型；研究分析了传统最优路径算法的特点及使用范围。 (2)研究了城市道路中的交通信息参数，提出了参数的表示形式和存储结构。分析研究了城市道路网络的表示形式以及存储结构，提出了交通信息在城市道路网络中的表示方式。 (3)研究了蚁群算法的基本原理、流程以及模型，分析了算法中部分参数对算法性能的影响。在此基础上提出了具有多约束条件的算法MCACO(Mutil-Constrained Ant Colony Optimization)。将多个交通信息融入改进之后的算法中，仿真结果证明了改进算法MCACO能够用于求解多约束条件限制下的最优路径选择。 本论文得到了湖北省自然科学基金项目：基于无线传感器网络的出行者最优路径选择算法的研究(编号：2012FFB05006)的资助。