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

菜单

1 绪论城市立体交通问题已经关系到了国民经济的方方面面，而对于优化技术处理的选择等此类问题，对于提高系统的效率、缓解能源供需的不平衡状况和提高经济效益都有非常明显的效果。自20世纪90年代以来，城市立体交通的各种问题就表现出非线性和不确定性的新特点。而对于一般的优化方法也开始无法解决这类问题了。此时，改进的优化方法以其灵活、稳定和效率高的优点得到了许多研究学者的青睐，双向Dijkstra算法是优化算法大家庭的一位重要成员。本论文着重于城市立体交通道路的交通网络，对最短路径问题的Dijkstra算法进行研究和验证，并对改进后的双向Dijkstra算法的可行性和正确性进行了实验研究。65219

1 绪论 5

1．1 城市立体交通中的最经典问题和解决的措施 5

1．2 研究现状和意义 6

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

2 最短路径问题分析 9

2．1最短路径问题的分类和特点[19] 9

2．2最短路径的搜索策略： 10

2．2．1深度优先搜索： 10

2．2．2广度优先搜索 11

2．2．3启发式搜索 11

2．3 典型Dijkstra算法 12

2.4 本章小结 14

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

4 总结与展望 22

4．1总结 22

4．2展望 231．1 城市立体交通中的最经典问题和解决的措施

自21世纪以后，我们的国家经济不断地发展，所以随着城市居民的生活节奏继续地加快，社会活动的持续增多，城市交通运输方面的压力也越来越大，许许多多的城市都存在着非常严重的的交通问题。尽管政府已经开始着手于改善城市的交通情况，可是城市的交通仍然是大问题。而产生这个问题的主要的原因有以下几点：

首先，城市的交通运输负担不了巨大的人口的流动。况且我们的国家是一个人口超级大国，不仅人口的基数比较大，而且还有居高不下的人口新增长率，根据科学的研究表明，在不久之后的十年，我们的国家人口数量将会以一年几百万的数量每年增加，城市的人口密度也将继续变大，这当然无疑给管理城市交通带来了巨大的困难。

其次，随着人民的生活的水平的提升，机动车的数量，特别是私家车的数量迅速增加。当然随着不断大众化的交通工具增多，城市交通的统一管理也开始遇到了困难，随之给公共交通安全增加了很大的隐患。其次，道路的设计也有存在比较不合理的地方。即使政府在不断持续的修筑新的道路，或者加大城市道路的宽度，可是仍然无法避免交通拥堵和事故的发生。就比如，如果已经损坏了的道路不能及时的去修理，或者存在未分清机动车道的道路规划，非机动车道和人行横道，那么在人们上班和下班高峰期或者法定节假日时，会带来非常严重的交通堵塞和增加发生交通意外的频率。

最后，由于城市交通问题的不断产生，随之而来能源问题和环境问题也将会是一个大问题。至今为止，我国机动车仍然以汽油作为主要燃料，随着不断增加的交通能源需求，也在不断增加的油耗量。排放的汽车尾气等等一直以来都是城市环境问题的主要内容，而如今已经比较不好的交通问题无疑使这个问题变得越来越严峻了。为了解决综上所述的一系列问题和交通压力的缓解，现在也产生了很多新解决措施。例如，北京开始实行单双号的出行；开发更多的线路，开发新能源和道路单行线设置；并且我们国家大力发展了城市公共交通事业；更多的城市不断开通地铁线路来对付行车高峰带来的拥堵问题。还有，我们的国家在铁路事业上加大投资，并且开通城间动车组，开通速度越来越快的城际高铁，这些解决方案都在改善交通问题发挥了很大的作用，例如通过增加城市立体交通的线路来改善当前交通拥堵问题。