基于广度优先的公交换乘搜索算法

数学建模有关紧急调兵和最佳乘车路线问题(总11页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《数学模型与数学软件综合训练》论文训练题目：一紧急调兵问题二最佳乘车路线学号：06500125 姓名：刘永旺兰州理工大学计通院信息与计算科学专业2009年春季学期目录一前言.......................................................................................................... 错误!未定义书签。

二紧急调兵问题.......................................................................................... 错误!未定义书签。

1论文摘要............................................................................................... 错误!未定义书签。

2问题重述与分析................................................................................... 错误!未定义书签。

3假设与模型........................................................................................... 错误!未定义书签。

模型假设.............................................................................................. 错误!未定义书签。

模型建立.............................................................................................. 错误!未定义书签。

云南大学学报(自然科学版),2008,30(S2):219～222CN 53-1045/N ISSN 0258-7971Journa l of Yunna n Un iver sity基于Ar c I M S 和JSP 的公交查询系统设计与实现3陈志明,梁　虹,肖　琦,廖泽容(云南大学信息学院,云南昆明　650091)摘要:基于A rc I M S 和JSP 的WebGIS 二次开发技术,提出一种高效、实用的公交查询系统解决方案,基于昆明市公交线网,设计并实现昆明公交查询系统.阐述公交数据模型、换乘算法设计与实现,提出基于广度优先换乘算法的步行换乘及换乘策略优化方法,并采用AO 实现换乘组生成.关键词:A rc I M S;JSP;W ebGIS;公交查询系统;换乘算法中图分类号:TP 311 文献标识码:A 文章编号:0258-7971(2008)S2-0219-04 城市公交查询系统能够帮助出行者快速选择出行路径、换乘路线等,是提高出行效率、优化公交资源配置的有效方法和途径[1].由公交站点及公交线路构成的公交线网,是公交查询的基础,具有典型的空间分布特性.GI S 以其特有的空间数据存储、管理、空间可视化及空间分析功能,为开发公交查询系统提供了强有力的技术支持.随着W ebGI S 技术及应用的日趋成熟,开发基于B /S 结构、真正面向广大交通出行者的可视、高效、交互性好的城市公交查询系统,是城市公交管理部门和公交出行者的迫切需求.本文结合主流W ebGI S 产品及W eb 开发技术,提出一种公交查询系统的高效实用解决方案,重点阐述公交数据模型、步行换乘实现及换乘算法设计与实现.基于昆明市公交线网,设计并实现昆明公交查询系统.1　Arc I M S 及J SP 简介1.1　Ar c I M S 体系特点及结构　A r c I M S 是ESR I 公司出品的优秀W ebGI S 产品.它被专门设计用于基于W eb 的地图、数据和元数据的发布,它的设计使得创建地图、开发和地图交互的网页及管理地图站点更加容易[2].A rc I M S 由客户端和服务器端的部件组成,如图1所示.其中客户端浏览器主要有2种:H T ML V iewer 和Java V ie wer,可以根据需要灵活定制;服务器端主要由W eb 服务器�A r c I M S 连接器(Ar 2c I M S Connectors)、A r c I M S 应用服务器(Arc I M S Ap 2plication Server )和A rc I M S 空间服务器(A rc I M S S patial Server )组成.A rc I M S 连接器起到了连接W eb 服务器和应用服务器的作用.空间服务器是A rc I M S 的中枢,由I m ageSe r ver 、FeatureServe r 等组件构成,用于栅格或矢量数据的响应.A rcI M S 各组成部分之间依赖TCP /I P 协议通讯,且这种通讯以A rcX ML 格式进行[3].1.2　JSP 及其在W ebG IS 二次开发中的优势　JSP 是当前主流的动态网页标准之一,采用Java 作为脚本语言,代码编译为Servle t,并由Java 虚拟机执行.JSP 具有完全面向对象、平台无关、表现与逻辑分离、安全可靠等优点,同时有大量项目和开源产品的支持,是W eb 项目开发的利器.Esri 公司在A rc I M S4.0中引入了JavaConnec 2tor,使得开发人员可以使用JSP 定制A rc I M S 应用.利用JSP 技术对Arc I M S 发布程序进行二次开发,二者不仅运行在同一环境下,而其共同支持Java Servlet 技术和标准的X ML 标准,可以很好地将二3收稿日期　作者简介陈志明(　),男,云南人,硕士生,主要从事通信信号处理、地理信息系统方面的研究　通讯作者梁　虹(65　),女,云南人,教授,主要从事地理信息系统、空间数据库方面的研究:2008-10-08:1979-.:19-.次开发程序同A r c I M S 结合在一起[4].JSP 的优点使得A r c I M S 较强的功能得到更好的扩展和发挥.2　公交查询系统设计2.1　系统架构　公交查询系统采用三层结构体系,客户端为W eb 浏览器,服务器端采用W eb 服务器+Arc I M S 服务器+空间数据服务器的结构,其中空间数据服务器采用S QL Server +ArcS DE 建立,实现空间数据和属性数据的统一存储和管理,如图2所示.整个系统支持基于网络的分布式布署和管理,提供良好的负载均衡性和可维护性.对空间数据库中属性数据及关联表的访问可直接通过建立数据源访问S Q L Server .2.2　基于Geoda taBa se 的数据模型设计　公交数据库设计是整个系统的关键,直接决定了系统功能实现的效果.系统数据库采用Ge odatabase 建模.Geodatabase 是Esri 公司在A rcInf o 8中引入的全新的面向对象的数据模型,具有很强的空间数据建模能力,它能够很好的表达要素的自然行为以及这些行为的关联,并实现地理数据的统一存储管理[5].图1　Arc I M S 体系结构图Fig .1The a rchitecture of A rc I MS图　公交查询系统结构图F T f ff q y y 022云南大学学报(自然科学版) 第30卷2ig .2h e arch itectu re o the p ub lic tra ic in u ir s stem 公交查询空间数据库要能很好的支持公交空间信息和属性信息的查询与显示,以及公交换乘算法的实现.系统采用了公交站点(st opPoint )、公交线路(bus L ine )、公交线段(lineSec t )(两站点之间的线路路径)3个要素类及线路———站点关联(lineIncludeSt op )、线段———站点关联(sectI nclude 2Stop )2个关系类对公交网络建模,既能较好的支持系统功能,又做到了精简和易维护.数据结构如图3所示.其中,站点要素中的字段tr ansferGr oup 为换乘组,即该站点可步行换乘的站点集合,线路———站点关联中字段sequence 为站点在线路中的序号,并且线路要区分去程和回程.图3　公交网络模型数据结构Fig .3Data model of public traffic net work2.3　换乘算法及策略　换乘功能是公交查询系统的难点,也是系统实用的关键.本系统换乘算法结合昆明的城市公交状况,由基于广度优先的最少换乘次数算法改进而来.原始算法如下:(1)输入或由电子地图选择乘车始点A 、终点B .(2)求经过A 的线路s (I)(I =1,2,…,m )(m 为正整数),及经过B 的线路t (J )(J =1,2,…,n )(n 为正整数).(3)有s (I )=t (J )吗?若有,满足此条件的线路s (I )也即t (J )为A 到B 的直达车线路,输出结果,结束运算.若没有,往下执行.(4)求线路s (I )的站点E (I,U )(U =1,2,…,p,p 为正整数)及线路t (J )的站点F (J ,V )(V =1,2,…,q,q 为正整数).(5)有E (I,U )=F (J ,V )吗?若有满足此条件的线路s (I ),t(J )(可能不止1种),即为1次转车的线路,计算各种1次转乘方法的乘车路程,乘车路程最短转乘线路,再求转车地点,输出结果,结束运算若没有,往下执行(6)求经过站点(I ,U )的线路集合(K )(K=1,2,…,b)(b 为正整数),求经过站点F (J ,V)的线路集合z (X )(X =1,2,…,c )(c 为正整数).(7)有r (K )=z (X )吗?若有,则线路r (K )也即z (X )为2次换乘中的第2条乘车线路,计算各种2次转乘方法的乘车路程,乘车路程最短转乘线路,转车地点,输出结果.若没有,往下执行.(8)设定换乘次数的上界N ,然后可在不大于N 次换乘的某次循环中找到可行路径,若找不到则结束并提示.原始算法中未考虑步行换乘的问题,不符合实际的出行情况,同时换乘次数过大也不具有实际意义.改进后的算法有效解决了步行换乘问题,同时对换乘次数的限制及换乘策略的优化,既满足昆明的城市规模,又符合大多数出行者的情况,能为其提供最优的出行方案供选择.因此对算法进行改进,具体如下:(1)运算中加入步行换乘,即将站点E (I ,U )及F (,V )的换乘组站点也加入考虑()设定N =,即最多计算到次换乘因为已经考虑了步行换乘,所以完全能满足昆明的城市122第S2期 陈志明:基于Arc I M S 和JSP 的公交查询系统设计与实现..E r J .222.规模.(3)1次换乘为只有含步行换乘的情况下,计算并再提供不含步行的2次换乘方案(存在的情况下).(4)只有2次换乘的情况下,只计算并提供不含步行或步行次数最少的方案.3　系统功能与实现系统应用层配置为Apache2.0+Tom cat5.5+A rc I M S9.2,数据层为S QL Se r ver2005+A r cS DE9.2.公交网络数据库通过A r c I nfo9.2建立,并使用A rc I M S 功能组件建立昆明公交地图服务,然后以Java Connect or 提供的示例程序jspvie wer (一个用JSP 和JavaConnect or 标记实现的地图服务浏览器)为基础,在I DE 中新建项目,对公交查询功能进行二次开发和实现.另外,站点要素中换乘组(tr ans 2ferGr oup )在A rc Ma p 下通过AO (A r c O bjects )开发方式,定制相应缓冲分析功能模块对站点要素数据处理后生成,昆明公交查询系统中缓冲距离取200m.系统提供线路信息查询、站点信息查询及换乘查询三种功能及常用电子地图浏览工具.查询输入除提供传统的文本输入方式外,对后两种查询中站点的选择还提供基于电子地图的点击缓冲选择,查询结果既有地图信息也有相应文本信息.系统运行界面如图4.图4　昆明公交查询系统运行界面Fig .4The system interface of the public traffic i nquing syste m of Kun m ing4　结束语论文基于主流W ebGI S 产品及W eb 开发技术,提出一种公交查询系统的快速、高效解决方案.充分利用成熟G I S 平台的功能性,并且步行换乘及换乘算法的解决具有较强实用性.步行换乘的实现需要换乘组数据的支持,A r c I M S 具备一定的空间分析能力,但要其基于网络进行实时的大数据量的空间分析运算是不现实的,通过AO 方式对数据进行预处理,生成相应换乘组数据,充分利用了A r c Map 桌面系统的强大功能,很好的解决了这一矛盾.参考文献[]　吴永军,蔡永香,郭庆胜城市公交查询系统的设计与实现[J ].测绘信息与工程,2006,31(5):40242.[2]　ES R I .Arc I M S 9Arch itecture and Functi onality [EB /OL ].2006211225.htt p://ww w .e sri .co m /libra ry/whitepape rs/pdfs/a rc i m s92architecture .pdf .[3]　刘志勇,许晓宏,邵彦蕊.网络地图发布技术研究[J ].测绘与空间地理信息,2007,30(2):1122115.[4]　赵淑玲,曲鑫,张乐.WebGIS 二次开发中JSP 与ASP的比较[J ].测绘与空间地理信息,2007,29(1):61263.[5]　M ichael Zeil e r .Modeling Our World [M ].Amer i ca:ESR I Press,1999.(下转第225页)222云南大学学报(自然科学版) 第30卷:1.低通道数量的VoI P 解决方案,具有适应增加功能(例如音乐、视频和图像传输以及系统总控制)的处理余量.与智能家居相结合,将带给小区住户良好的生活体验.参考文献:[1]　沈鑫剡.多媒体传输网络与VoIP 系统设计[M ].北京:人民邮电出版社,2008.[2]　董琳媛.现代电子技术在智能小区中的应用[J ].北京石油化工学院学报,2004,12(4):61264.[3]　潘清艺.信息化智能住宅小区建设初探[J ].邮电企业管理,2001(4):21222.[4]　米良洲.智能小区管理网络系统的构成[J ].山西建筑,2005,31(22):28229.[5]　张鹏,马伟敏,唐棣芳.基于AR M 的嵌入式VoIP 终端的设计与实现[J ].电子技术,2008,45(2):52253.V isible talk 2back syste m app licati on research of VoIP in intelligent comm unityX UE J i 2liang,S HA N G Zhen 2hong(Sch ool of Infor m ation Enginee ri ng and Auto ma tion,Kun m i ng Uni ve rsity of Sc ience and T echn ology,Kun m ing 650051,China)Abstra ct:The traditi ona l si m ulated ta lk 2back is compa r ed with digital I P talk 2back .Foll owed by the anlysis and c ompa ris on of t wo of the most i mportant pr ot ocols in Vo I P .The pr ospect of Vo I P ’s app licati on in digitized and interconnected Inte lligence Comm unity is elaborated as we ll .Eventually,a feasible s oluti on is p r oposed accord 2ing to p r actical p r ojec ts .Key wor ds:intelligent co mm unity;visible talk 2back;Vo I P;SI P;H .322;SoC333333333333333333333333333333333333333333333(上接第222页)Desi gn and realizati on of public traffic inquiry system based on Arc I M S and JSPCHEN Zhi 2m ing,L I A NG Hong,XI AO Qi,L I A O Ze 2r ong(Sch ool of Infor m ati on Sc ience and Engineering,Yunnan University,K un m ing 650091,China )Abstra ct:B ased on the W ebG I S secondary devel opm ent technol ogy using A r c I M S and JSP,it is bringed upan ef ficient and prac tical solution of public traffic inquir y syste m ,de signed and realizes the public traffic inquiry syste m of Kunm ing based on the public traffic net wor k of Kunm ing .It is intr oduced the data mode l of public traf 2fic net work,the de sign and r ealizati on of the transfer a lgorithm ,especially sloved the wa lking transf e r pr oble m and op ti m izes the transfer strategy of the breadth 2first transf e r a lgorithm ,more over use s the AO m ethod t o create the transfer gr oup.Key wor ds:Arc I M S;JSP;W ebGI S;public traffic inquiry system;transfer a lgorithm522第S2期 薛继良等:VoIP 技术在智能小区可视对讲系统中的应用研究3。

p(i ) ,则一定能找 到一个 pim 就是终点 p hk ，也就是 pim 在 p h 中对应站点 p hk ，即 p hk 是 pi 和 p h 两条线路上共同经过的一站。 p(i )
为所求的最佳路径， 在实际情况中可以直接看公交车站点站 牌就可以判断出
pij 与 p hk 是否在同一路公交线路上，若存 在其他线路如 p ( d ) 等使 pij p ( d ) 且 p hk p (d ) ，则比 较各符合要求的线路的 p (i ) 和 p ( d ) ， 因此 选择 pij 与 p hk
公交车最佳乘车路径优化算法1对于情况1只要遍历p中pd则一定能找到一个p拥就是终点p从也就是p加在p中对应站点pm即p从是p和p两条线路上共同经过的一站?pi为所求的最佳路径在实际情况巾可以直接看公交车站点站牌就可以判断出ph与p从是否在同一路公交线路上若存在其他线路如pd等使ppd且pmpd则比较各符合要求的线路的pf和pd因此选择p与p址之间的公交车站点数最小即im一i的值最小的线路为所选择的最佳路径
大部分城市提出了“优先发展城市公共交通”的交通政 策，以缓解交通堵塞，能源紧张，废气污染等问题。为方便 乘客出行，交通部门大力发展完善公交服务系统，改善乘车 环境的同时，也努力为乘客的出行提供及时、准确、最佳的 公交信息查询服务。从现有网站看出，公交路线查询信息服 务很全面，从 A 地到 B 地给出了多种路线，建议哪条路线 是最佳路线并不多。 最佳路径是指乘客在乘车从起点到终点 的多条路径中，能最好满足乘客期望的线路，即出行效用最 大的线路。 2 公交乘客出行最佳路径的定义 确定公交出行最佳路径， 很重要的一点是通过对乘公交

p1n p 2n p sn
每个站点信息可以有两部分组成，站名和本站编号。 对于任意的起点 下几种： （1）起点 p ij 与终点 p hk 在同一线路上，即 i h ，可 -80-

２ ２ Ｄ ｊｓ ａ算 法 的 主要 思 路 及 其缺 陷 ． ｉ ｔ ｋｒ 目前 对 公 交 线 路 遍 历 查 询 应 用 的最 广 泛 的是 Ｄｊｓ ａ算 法 ，该 算 法 是 Ｅ Ｗ ｉ ｓ ａ于 ｉ ｔ ｋｒ ． Ｄｊ ｔ ｋｒ
１５ ９ ９年提 出 的一 个 按 照路 径 长 度 递 增 的次 序 产 生 最 短 路 径 的 算 法 ，此 算 法 是 已证 明 能 得 出
（ 雄 师 范 学 院 物 理 与 电 子 科 学 系 ，云 南 楚 雄 ６ ５ ０ 楚 ７ ０ ０）
摘 要 ：基 于 Ｗｅ Ｇ Ｓ的 交 通 信 息 发 布 系统 中 ，公 交 换 乘 算 法 是 近 年 研 究 的 主题 。也 是 目前 解 决 ｂＩ
城市 交 通 拥 挤 最 为 关 注 的课 题 之一 。本 文 依 据 传 统 公 交 网络 建 模 的基 础 上 ，通 过 研 究 传 统 的经 典 算 法不 足 之 处 ，结 合 ＧＩ Ｓ的相 关 技 术 ，运 用 了其 中空 间 数 据 的 分 析 功 能 ，提 出 了 公 交 步 行 换 乘 算 法 ， 结 合 Ｇ Ｓ的 强 大 的空 间数 据 存 储 以及 图 形 界 面 显 示 的 功 能 。 有 效 的 运 用 了 数 据 缓 冲 区分 析 以 及 Ｇ Ｓ Ｉ Ｉ 的桌 面 产 品 ＡＯ，从 而 形 成 了 昆 明 步 行 公 交 换 乘 系 统 。该 系统 在 交 通 网络 中 进 行 测 试 ，最 终 得 以 实 现 ，提 高 了算 法换 乘 的 时 间效 率 。 关 键 词 ：Ｗｅ ＧＩ ；公 交换 乘 ；步 行 换 乘 ；交 通 网络 ；Ａ ｂ Ｓ Ｏ
楚 雄 师 范 学 院 学 报
２ １年 第 ０１
３期
两个 方 向不 重 合 时 ，每个 节 点 只有 一 条 出边 或 者 一 条 入 边 。 如 果 一 个 节 点 是 多 条 公 交 线 路