论文部分内容阅读
在我国众多大城市普遍存在交通拥挤问题,造成交通拥挤的首要原因是城市交通基础设施的建设远远落后于城市交通需求的增长。大力发展公共交通是解决城市交通拥挤问题的首选措施。然而,通过对我国目前公共交通系统的分析,可以看出我国公共交通系统存在的一个普遍问题,就是乘客出行换乘比率高。另外,我们对公交乘客的出行心理也进行了调查分析,结果显示,乘客在选择出行路径时首先考虑的是换乘次数最少,其次是考虑时间最短。
针对目前这种形式,本文通过对于道路交通网络两点间最短路径的搜索算法进行研究,发现目前的很多种成熟算法在公交换乘网络的应用上都存在一定问题:Dijkstra算法是传统最短路径算法中最为常用的经典算法,但该算法的执行效率明显不足,它求解最短路径问题是基于网络的权矩阵,运用了关联矩阵、邻接矩阵和距离矩阵的概念,在存储图形数据和运算时需要定义n×n阶矩阵,其中n为网络的结点数。当网络的结点数较多时,其庞大的网络数据存储需求及算法的空间时间复杂度将占用大量的计算机内存,执行效率较低。目前还有许多基于Dijkstra算法的改进算法如:基于点——边拓扑关系的算法、优先搜索算法和采用动态数据串等方法。以上这些算法的研究目的都是为了提高运算的效率,但一般都还不能直接运用于公交网络的路径选择中,因为公交乘客在出行的过程中不仅要考虑出行距离,还要考虑换乘次数这一重要因素。
而近年来逐渐兴起的很多智能算法比如遗传算法、蚂蚁算法、神经网络等算法也开始应用于公交换乘的算法研究中,并在基于海量网络图中的最优路径问题求解中取得了较好的效果,但这些智能算法首先本质上还是一种随机搜索算法,有其自身不可避免的局限性,不可能达到全部网络路径的遍历求解,往往因为参数选取不当和公交网络图的表达问题造成得到的结果实际并不是最优解;其次,其算法的高效率主要体现在应用于超大海量网络图上,但实际应用中的城市交通网尤其是中小城市交通网络还远没有达到那样的复杂度,所以其实际运行效率不能得到很好的体现。
本文在分析和总结归纳以上算法的优缺点的同时,通过对公交网络的分析与研究,针对公交网络的特点,首先进行公交网络的抽象,建立换乘矩阵和权值矩阵,然后给出相应的算法实现,即根据公交车站路线表,依据该换乘矩阵和权值矩阵对应的值就可以计算出任意两站之间的最少换乘次数和出行方案。提出了以换乘次数最少为第一目标、经过的站数最少和时间最短为第二目标的城市公交查询系统的设计与实现方案。全文共分七章,第一章为绪论,为全文搭建一定的理论基础平台,并对论文的结构作整体的概述;第七章为结语,归纳全文主要结论和有待进一步研究的问题。
第二章、第三章,从现实中我国公共交通状况出发,分析我国公共交通系统的弊端,并对国外的智能交通系统的产生与发展进行详细背景研究。着重介绍了现阶段公交换乘系统的研究现状,并从问题类型、网络特征以及实现技术等几个方面对最优路径算法进行分类讨论;最后对经典的dijkstra算法和流行的智能算法如遗传算法、神经网络、蚂蚁算法等最新的公交换乘算法研究进展做了详细论述。第四章、第五章,论文的重点部分。利用Dijkstra基本思想和基于邻接矩阵的改进算法进一步对其优化、改进,直接将公交换乘矩阵中的换乘次数改为换乘方案字符串,同时对时间最短作为权值分析,将路程花费用公式转化合并入权值,并建立基于时间最短的网络矩阵序列,这样,将大部分换乘查询放在矩阵的生成阶段,在用户查询时只需要对换成矩阵和权值矩阵进行简单的取值、分解、计算即可得到最优路径的解。大大减少了用户查询时的反应时间。
第六章,结合克拉玛依电子地图实例,在WEBGIS环境下利用典型的客户机、地图应用服务器与Web服务器、数据库服务器的三层结构,实现了克拉玛依市的公交换乘模块并验证了其算法的高效和实用性。