(精品论文)最优公交线路查询的设计与实现本科生毕业论文(设计)

本科生毕业论文（设计）开题报告题 目: 最优公交线路查询的设计与实现 姓 名: 学 院: 理学院 专 业: 信息与计算科学 班 级: 学 号: 指导教师: 职称: 大学教务处制本课题的意义：随着城市的发展和人民生活水平的提高，人们出行的次数和出行的路程都在增加，作为城市枢纽的公共交通承担着越来越重的运输任务。同时，公交线路的条数和公交车数量也在迅速增多，公交的服务时间在延长，到站路程在扩大，服务质量在提高，给人民的日常生活带来了很多便利。在油价上涨和能源短缺的今天，人们的出行将更多的依赖公共车。然而，随着人们所到目的地范围扩大，出行往往需要转乘多辆公交车才能到达目的地，如何在短时间、换乘次数最少、成本最低的情况到达目的地，是人们所关注的问题。因此，我们的课题运用计算机及网络技术，结果国内外先进的数学计算方法，设计一套能够方便人们通过多种网络查询模式，查询到出行时所需的最佳公交换乘方法，给人们出行节约更多的时间和金钱。国内外研究概况：随着运筹学，图论等学科的不断发展，在1959年，荷兰计算机科学家艾兹格迪科斯彻发现了Dijkstra算法，该算法在公交路线查询中是一种比较常用、方便的算法，但它的复杂度为结点数平方的数量级。当网络模型中结点数和边数较多的情况下，算法的计算量较大，时间花费较多。因此，Dijkstra 算法在理论上是正确的，但在实际应用中不尽人意。1968年人们开发出A*算法，该算法是一种启发式搜索方法，它特别适用于公交查询等统，它是利用已有的一些先验知识来对解空间进行搜索。由于已经有了问题的一些先验知识，因此A*算法往往比一些遍历搜索方法在计算时间上要快得多，但它不能像Dijkstra算法一样搜索到的一定是最短的路径，只能是相对短的路径。之后，在20世纪90年代初意大利学者M Dorigo ，V Maniezzo ，A Colorni等通过模拟蚂蚁搜索路径的行为，发明出蚂蚁算法。该算法可以带记忆功能，选择某路径的次数越多，说明此路径是比较优的路径，其信息素的值也越大，为以后选择路径提供必要的信息。系统使用的时间越长，为乘客提供的信息越全面，越准确，系统也越智能化。应用前景：基于网络环境下的B/S公交换乘系统将是今后几年内城市公交建设发展和研究的方向，在该项查询技术成熟并运用的很短时间内，亦可以在B/S公交换乘系统的基础上设计出实时路况系统。为人们出行提供便利，对人们了解交通现状和城市道路发展规模提供了必不可少的平台。研究的内容：1 调查出行者在出行时以哪些因素为首要考虑因素？2 了解并分析目前公交网络的设计以何种理论为依托？3 思考如何才是公交换乘最短路概念？4 了解、并分析国内外目前已有公交路线查询系统的理论及设计方法。5 如何将集合，广度和深度优先搜索的思想应用于B/S模式下公交换乘系统中去？6 结合传统的公交查询方法和国内外先进的公交路线算法理论，设计出一套适用于我国城市的最佳公交换乘路线查询系统。研究的目标：采用国内外先进的设计算法原理，结合JSP语言开发出基于B/S模式下的公交查询系统。拟解决的关键问题：1、 如何收集齐全所有城市的公交线路信息？2、 根据实际调查和理论分析，归纳出公交换乘最短路概念。3、 分析、对比、总结出最少换乘路径的最优算法。4、 在进行系统设计时，需对运筹学、图论、概率论、离散数学、数据结构、java语言等多门复杂学科进行深入了解。5、 如何运用MVC、连接池、ajax等先进的程序设计技术来优化系统查询功能。研究方法、实验方案：本课题的研究方法主要综合分析法，包括对各类文献、书本的分析等。1、上网浏览法.通过浏览大量关于公交路线查询的网络资源的文章、开发文档、B/S软件实例2、分析比较法：对1中的同类软件进行分类和比较，指出同类软件在建设上的优缺点。3、研究开发法：最后，采用JSP语言开发系统一套。技术路线：学习传统查询理论和方法分析目前查询系统的优缺点 总结 归纳尝试更高效、准确的算法优化算法软件开发完善各种文档撰写论文可行性分析：1. 目前，国内外已有公交查询系统的雏形，但不完善和全面。2. 公交算法理论在国内外有较完善的理论基础。3. 通过多种调查方法的结果显示，人们对在什么地点和时间等环节进行公交换乘还不是很熟悉，需要一套较智能和便利的查询系统来为他们提供所需的最佳换乘方案。特色或创新之处：1、 通过网络终端（电脑，手机,掌上电脑等），即可快速查询到所查城市公交信息及出行换乘方案。2、目前国内无完善和全面的公交换乘自动生成系统。3、本系统基于JAVA环境，系统使用越频繁，查询效率越高。研究计划及预期进展：2006年9月至2007年1月，做初步的调查，论证其可行性，确定研究详细内容，完成开题报告2007年1月15日至2007年2月28日，收集材料，研究算法，优化算法2007年3月1日至2007年3月15日 系统设计研究制作，完成中期检查报告2007年3月15日至2007年3月20日，整理资料分析材料。2007年3月20日至2007年3月30日，撰写论文初稿。已具备的条件、尚缺少的条件和拟解决的途径（包括利用教学实验中心、科研实验室、实习基地、校外其它企事业单位等条件的计划与落实情况）已具备条件：1. 基础文献的收集工作已经完成2. 对一些关于路径搜索的算法有一定的研究3. 有关于软件工程的思想4. 有开发软件的能力尚缺少的条件：1. 各城市公交路线的数据2. 缺少一定的权威性著作，尤其是国外的文献，还有待于收