改进的城市公交查询算法研究

论文摘要

城市公交查询系统为乘客提供了优化、及时的信息服务,通过合理的引导,很大程度上方便了他们的出行,同时减少了不必要的交通流量,提高了整个公交线网的运行效率和城市信息服务化水平。本文对城市公交查询算法进行了深入的研究,主要做了如下工作:首先,分析了现有的几种的公交查询算法,并通过比较,进行了优劣性总结,确定了本文的研究思路,归纳出本文工作需要解决的关键问题。在此基础上,本文研究了国内公交网络的主要特点,以及乘客的出行心理,建立了以换乘次数,时间花费和经济开销为最优的城市公交查询的多目标规划的数学模型。针对城市公交线路错综复杂、部分线路往返线路不一致等特点,提出了一种基于双邻接表的存储策略,避免了传统的存储方法不利于乘车线路搜索的问题,在上述数学模型的基础上,提出了一种基于线路优先的层次搜索公交线路查询算法,引入偏好系数,综合考虑了换乘次数、时间花费、经济开销等优化目标,分析和仿真表明,新的算法能满足不同乘客的实际需要,具有较高的精确度和良好的实用性。针对便携设备的运算速度较低的特点,在上述数学模型基础上,提出了一种公交线路查询快速算法,该算法将换乘次数为优化目标,经济开销和时间花费弱化为约束条件,并抑制无效换乘运算提高响应速度。分析和仿真表明,与已有的算法相比,新的算法在保证查询结果的质量的同时,具有较短的查询响应时间,是一种更适合便携设备的查询算法。最后,本文在J2ME Wireless Toolkit环境下,实现了一个适合不同城市、任意两地间,具有一定通用性的公交线路查询原型系统,测试结果表明,我们所提出的算法能满足不同乘客的需要,具有较好的通用性,同时具备良好的性能。

论文目录

• 摘要
• ABSTRACT
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 研究背景
• 1.2 智能公交系统
• 1.2.1 概述
• 1.2.2 发展及研究意义
• 1.3 相关研究现状
• 1.3.1 国外研究现状
• 1.3.2 国内研究现状
• 1.4 基于便携设备的公交查询
• 1.5 本文的研究内容和章节安排
• 第2章 最短路径问题及公交查询算法
• 2.1 最短路径问题
• 2.2 公交查询算法比较
• 2.2.1 迪杰斯特拉算法
• 2.2.2 A*算法
• 2.2.3 Moore-pape 算法
• 2.2.4 扩散法
• 2.2.5 其他算法
• 2.3 小结
• 第3章 公交网络分析与模型建立
• 3.1 基础理论
• 3.2 公交网络
• 3.2.1 公交网络的特点
• 3.2.2 公交网络的表示
• 3.3 公交出行心理研究
• 3.4 公交网络数学模型建立
• 3.4.1 数据说明
• 3.4.2 站点的抽象
• 3.4.3 数学模型描述
• 3.5 小结
• 第4章 一种基于线路优先的层次搜索算法
• 4.1 相关工作
• 4.2 公交网络存储结构设计
• 4.3 基于线路优先的层次搜索算法
• 4.4 实验比较
• 4.5 小结
• 第5章 一种公交线路查询快速算法
• 5.1 相关工作
• 5.2 存储结构设计
• 5.3 算法描述
• 5.4 实验比较
• 5.5 小结
• 第6章 快速算法在公交线路查询系统中的实现
• 6.1 系统工作环境
• 6.2 系统主要功能
• 6.3 系统设计
• 6.3.1 地名模糊查询
• 6.3.2 站点定位
• 6.3.3 设置换乘代价
• 6.3.4 最佳公交线路查询
• 6.3.5 指定站点和线路查询
• 6.4 小结
• 结论及进一步研究的方向
• 参考文献
• 致谢
• 附录 攻读硕士学位期间发表的学术论文