城市立体交通网络求最短路径的Dijkstra算法求解及其优化(2)

菜单

最短路径问题的研究是运筹学、计算机科学和地理信息科学等学科的一个热点。对于城市立体交通最短路径的问题，国内外大量该方面的专家也深入的研究了此类问题。目前有许多国内外大量的学者对这一问题进行了非常深入且取得很多成效的研究。其中，着重于研究当下的最短路径的改进和优化比较多。而求城市立体交通的最短路径问题，也成为求最短路径问题。而采用贪心启发策略的Dijkstra算法是目前理论上已知的最完善的经典的最短路径算法，而所谓的Dijkstra(迪杰斯特拉)算法是经典的单源最短路径算法[20]，用于计算一个开始节点到其他所有任何节点的最短路径问题。主要特点是以起始点为中心向外层不断的层扩张，直到扩张到终点为止。Dijkstra算法是最基本的的最短路径算法，在很多专业课程中都当做基本内容且写出了详细的介绍，如数据结构、图论、运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式[19]，一种是用OPEN, CLOSE表的方式。但由于城市立体交通网络复杂化，越来越多的地理节点数，而Dijkstra算法只能给出无负权边权重的最短路径问题的解答，而意大利学家Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents”中提出蚁群算（Ant Colony Optimization, ACO），又称蚂蚁算法，是一种几率型的用来在电子图里寻找优化路径的智能算法。它的灵感被发现于蚂蚁在找寻食物过程中寻找路径的行为方式。蚁群算法是一种基本的模拟生物智能的一种算法,初步的研究表明该算法具有很多比较优秀的性质.针对PID控制器参数问题优化方案,将蚁群算法设计的结果与遗传算法设计的结果相比较,依据数值仿真结果发现,蚁群算法具有一种新的模拟智能优化方法的有效性和实用价值[22]。如今经过了这几年的研究，蚂蚁算法开始慢慢进化，越来越多的已经应用在城市立体交通网络道口中，也大量的应用在导航、路由等对实时性要求较高的场合的情况下。论文网

对于基准抽象的网络图之中的最短的路径问题(shortestPath Problem，简称为sPP) 的解决方案，由于多种应用的需求指向通信、交通、计算机网络、运筹、管理等多门学科中，多年以来越来越受到人们关注并取得了许多比较成功的研究成果。而交通道路设计的基础是最短路径算法的选择与实现,最短路径算法是计算机科学与地理信息科学等领域的研究热点，很多网络相关问题都可以划入最短路径问题的范畴之中。经典的图论与计算机数据结构的不断发展和完善和完美结合的算法使得新的最短路径优化算法不断出现[1]。

1．3 论文的主要研究内容

面对当今社会日益严重城市立体交通问题，讨论如何在最快的时间里选择最为合理的路线，也是改善城市立体交通问题的焦点所在。本论文在分析讨论最短路径问题的基础上，给出了传统最短路径算法，特别是对采用贪心策略的Dijkstra算法的详细介绍。为了充分研究算法的可行性和实用性，本论文第一步选取了南京市某区地图进行网络拓扑结构的构建，并在该平台上实现了Dijkstra算法的优化算法。而针对经典Dijkstra算法已经存在的收敛速度慢，遍历的节点较少，对于多节点情况效率低下，易陷入局部最优的缺点，本论文还在基本的算法参数下，选择引入双向的查找规则对典型的Dijkstra算法作了改变。依据平台的实验结果发现，改进的双向Dijkstra算法优化在收敛速度和搜索精度方面都较基本的Dijkstra算法有比较显著的提高。但根据有随时性变化的城市立体交通状况，如果在某一时刻堵塞，下一时刻却比较畅通的情形，本论文还讨论了交通堵塞时的最短路径问题，设计了Dijkstra算法的优化方案，并根据已知的实验数据得知，新的优化方案能很好地解决了交通拥塞带来的求最短路径的困难问题。