详情

原文传递改进的城市公交查询算法研究

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