《《公交网络路径算法研究(最短最优)》 (1)-公开DOC·毕业论文》由会员分享，可在线阅读，更多相关《《公交网络路径算法研究(最短最优)》 (1)-公开DOC·毕业论文（40页珍藏版）》请在金锄头文库上搜索。
1、精品题 目： 公交网络路径算法研究 摘 要 城市公交查询系统为乘客提供了优化、及时的信息服务，通过合理的引导，很大程度上方便了他们的出行，同时减少了不必要的交通流量，提高了整个公交网络的运行效率和城市信息服务化水平。在公交查询系统中，最关键的问题就是出行路径的选择问题。为了帮助乘客方便地选择出行路径、换乘路线等，本文对公交网络路径算法进行了如下研究。首先分析了现有的几种的公交查询算法，并通过比较，确定了本文的研究思路，归纳出本文工作需要解决的关键问题。在此基础上，本文研究了国内公交网络的主要特点，以及乘客的出行心理，建立了多目标规划的数学模型。最后在上述数学模型基础上，提出了一种最优公交网络路
2、径算法，该算法以广度优先遍历为基础，是一种优化的公交网络路径算法。本文在基于J2EE的环境下，实现了一个具有一定通用性的公交线路查询系统，在此系统下验证了算法的可行性和高效性。关键词：J2EE；最短路径算法；公交网络；线路查询ABSTRACTUrban public transport inquiry system provides the optimizated and quick information service to facilitate passengers travel in a large extent though a reasonable guide. And at sa
3、me time, this kind of system can reduce the unnecessary traffic flow and improve operation efficency of entire public transportation network and the level of urban information services. In public transport inquiry system，the key problem is travel path selection problem. In order to help passengers c
4、onveniently select travel path and transfer route ,the paper researched the public transport algorithm.Firstly, several existing public transport inquiry algorithms including their superiority and inferiority are analyzed in the paper. Secondly the key problems that need to be solved in this work ar
5、e also concluded. On this basis, a multi-objective programming mathematical model of public transport inquiry is established. Finally，on the ground of above mathematical model，a kind of optimization algorithm about public transport inquiry is proposed. The algorithm is based on breadth-first travers
6、al which is a kind of optimization algorithm about public transport inquiry.In the J2ME environment, the paper implements a Public Transport Inquiry System in which the feasibility and efficiency of the algorithm is verified.Key words：J2EE; Shortest path algorithm; Public transport network; Inquiry
7、of route目 录第一章 绪论11.1 研究背景11.2 项目的主要研究工作11.3开发环境2第二章 理论基础32.1 概念32.2 J2EE的结构32.3 J2EE的容器类型42.4 J2EE的体系与模式4第三章 公交网络分析与模型建立53.1 基础理论53.2 公交网络53.2.1 公交网络的特点63.2.2 公交网络的表示73.3 公交出行心理研究83.4公交网络数学模型建立93.4.1数学模型描述103.5 小结11第四章 最短路径问题及公交查询算法124.1 最短路径问题124.2 公交查询算法比较134.2.1 迪杰斯特拉算法134.2.2 A*算法154.2.3 扩散法164
8、.3 小结17第五章 基于广度优先遍历的最短路径算法185.1广度优先遍历的概念185.2图的建立过程185.3最短路径算法原理描述20第六章 最短路径算法在公交查询系统中的实现226.1公交查询系统的需求描述226.2公交查询系统的功能226.3 公交查询系统的数据库设计226.3.1 E-R图226.3.2 数据库表设计246.4公交查询系统的设计与实现266.4.1创建管理员登录的Servlet266.4.2创建用户登录的Servlet276.4.3车次信息查询286.4.4站点信息查询286.4.5两个站点间的信息查询296.4.6公交系统管理模块296.5系统测试与分析326.6小结
9、33结束语34致 谢35参考文献36精品第一章 绪论1.1 研究背景随着人民生活水平的提高和城市的发展，人们出行的次数和范围都在增加，作为城市主动脉的公共交通承担着越来越繁重的运输任务。与此相对应，公交的线路数量和投入运营的车辆数量也在迅猛增加，公交的服务时间延长、服务范围扩大、服务质量提高，对人们的吸引力也在增强。在油价上涨和能源短缺的今天，人们的出行将越来越依赖公共交通。一般意义上，完整的出行问题是解决出发点到目的地的路径选优问题。随着人们活动范围的扩大，乘公交出行往往也不可能一车到达，乘客从某一起点，可能需要一次或多次换乘才能到达目的地。因此，如何选择最优的出行路线，即如何换乘、换乘几次
10、、时间金钱花费，成为人们出行首要考虑的问题。 目前，我国众多大城市普遍存在交通拥挤，延误人们平时上班时间。甚至影响了城市旅游业经济的可持续发展。所以为了切实的改善公交车内拥挤状况，适当增加发车次数以缩短乘客等车时间，但是能够准确为人们提供最短的乘车线路才是得到解决的最好办法，这样大大的缩短了人们的乘车时间。本项目研究的基于J2EE的公交查询系统，让人们通过互联网很快的查出该城市任意两站点之间的最短乘车路线。1.2 项目的主要研究工作本系统是从城市交通现状出发，根据人们的出行规律，设计了一个完整的基于J2EE体系的公交车查询系统。该系统可以进行车次查询，站点查询，站站查询，解决了市民出行乘坐公交
11、车时经常遇到的困难。本系统模型构架分为下面四层结构，如下：1. J2EE应用程序组件J2EE应用程序是由组件构成的1。J2EE组件是具有独立功能的软件单元，它们通过相关的类和文件组装成J2EE应用程序，并与其他组件交互。本系统包括如下组件：应用客户端程序及J2EE服务器；Java Servlet和JavaServer Pages（JSP）Web组件及JavaBean。2. WEB层组件J2EE web层组件包含JSP页面或Servlet。按照J2EE规范，还包含某些JavaBean对象来处理用户输入，并把输入发送给运行在业务逻辑层上的组件来进行处理。3. 客户层组件基于WEB方式的静态HTML
12、页面或是Applet客户端的小应用程序。4. 最短路径算法编写最短路径算法，解决完成站点之间的最短乘车路径查询。1.3 开发环境开发平台：MyEclipse。开发工具包：JDK 1.6.0_24。Web服务器：Tomcat 6。数据库：MicroSoft SQL Server 2000。操作系统：Windows 7。浏览器：IE 6.0 以上。第二章 理论基础2.1 概念1. J2EE概念J2EE是一种利用Java 2平台来简化企业解决方案的开发、部署和管理相关的复杂问题的体系结构。J2EE技术的基础就是核心Java平台或Java 2标准平台。J2EE不仅巩固了标准版中的许多优点，例如“编写一
13、次、随处运行”的特性、方便存取数据库的JDBC API、CORBA技术以及能够在Internet应用中保护数据的安全模式等等，同时还提供了对EJB（Enterprise JavaBeans）、Java Servlet API、JSP（Java Server Pages）以及XML技术的全面支持2。其最终目的就是成为一个能够使企业开发者大幅缩短投放市场时间的体系结构。2. JSP的概念JSP程序是一个服务端页面脚本程序，可以在这个脚本中直接编写客户端浏览器需要显示的HTML文档内容，当然也可以依照JSP规范将Java程序代码嵌入脚本。JSP脚本规范提供了若干内部对象来简化JSP程序和浏览器之间的
14、输入输出处理。由于JSP程序是从HTML页面添加Java动态处理代码而来，因此，JSP程序又称为动态JSP页面。3. Java Bean的概念JavaBean是一种JAVA语言写成的可重用组件，用户可以使用JavaBean将功能、处理、值、数据库访问和其他任何可以用java代码创造的对象进行打包，并且其他的开发者可以通过内部的JSP页面、Servlet、其他JavaBean、applet程序或者应用来使用这些对象。用户可以认为JavaBean提供了一种随时随地的复制和粘贴的功能，而不用关心任何改变。这个对J2EE业务逻辑层处理具有相当重要的部分。4. Java Servlet的概念Java S
15、ervlet使用的是一种请求/响应机制，也就是说通过特定的Java程序设计技术，由该Servlet动态产生的响应向某一特定的请求做出响应。Servlet所能应用的请求/响应场合很多，但常用的还是在Web应用程序中用于产生超文本传输协议响应（HTTP）。据此，Servlet可能取代其他类型的HTTP请求/响应机制，譬如通用网关接口（CGI）脚本。5. Session对象Session对象是类javax.servlet.Httpsession的一个对象，是用来保存每个用户信息（以会话的形式直接保存在WEB服务器端），以便跟踪每个用户的操作状态。2.2 J2EE的结构J2EE结构具有一个很大的特点，就是与平台无关性的J2EE结构。所开发出来的程序可以在任何操作系统下运行。这样就使得J2EE程序的编写变得十分简单，因为业务逻辑被封装成可以复用的组件，
