（计算机软件与理论专业论文）公交最优路径算法研究及基于数字家庭短信平台的应用.pdf

公交最优路径算法研究及基于数字家庭短信平台的应用 摘要 论文题目：公交最优路径算法研究及基于数字家庭短信平台的应用 专业：计算机软件与理论 硕士生：陈偬 指导教师：罗笑南教授 摘要 随着计算机技术的发展与3 c 产品的融合，数字家庭为人们提供了方便、智 能、高效的数字化生活，成为人们关注的焦点。城市公交覆盖面广、经济快捷， 目前是大多数出行者的首选方式。在数字家庭中实现公交查询服务，为用户提供 高效、准确的公交乘坐方案，将极大方便他们的出行和生活。公交最优路径算法 作为公交查询系统的核心，决定着系统运行的效率及查询结果的准确性。短信作 为当前最便捷的通信方式之一，是发布查询结果的理想媒介。因此，在对公交最 优路径算法研究的基础上，设计并实现数字家庭短信发布公交查询系统，通过数 字家庭短信平台提供公交查询服务，具有重要的研究意义和应用前景。 本文首先对公交出行相关理论及典型公交最优路径算法进行研究，分析了几 种典型算法的特点和不足，在此基础上，提出了基于公交集合的最少换乘改进算 法，对该算法的基本思想、步骤及实现进行阐述，并根据实验数据进行分析。该 算法以换乘次数最少的公交线路作为最优方案，能处理现实中公交线路存在单行 线的情况，具有算法效率高，查询结果准确的优点。然后，本文对该算法进行应 用研究，设计了数字家庭短信发布公交查询系统。系统运行s e r v l e t 响应客户端 请求，查询结果通过本文设计实现的数字家庭短信平台进行发布。该平台使用终 端方式进行短信发送，采用r m l 分布式计算技术和p d u 短信编码模式。最后，本 文实现了数字家庭短信发布公交查询系统，该系统基于i p a n e l 中间件进行开发， 采用基于公交集合的最少换乘改进算法，以短信方式发布查询结果。本文的研究 成果实现了在数字家庭中高效、准确、便捷地为用户提供公交查询服务的功能， 有良好的应用价值。 关键词：数字家庭、公交查询、最优路径算法、最少换乘、短信平台 r e s e a r c h o fb u so p t i m a lp a t ha l g o r i t h ma n di t sa p p l i c a t i o nb a s e do nd i g i t a lh o m es m sp l a f f o f m a b s t r a c t t i t l e ：r e s e a r c ho fb u so p t i m a lp a t ha l g o r i t h ma n di t sa p p l i c a t i o n m a j o r ： n a m e ： b a s e do nd i g i t a lh o m es m sp l a t f o r m c o m p u t e rs o f t w a r ea n dt h e o r y s ic h e n s u p e r v i s o r ：p r o f x i a o n a nl u o a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n dt h ef u s i o no f3 cp r o d u c t s ， d i g i t a lh o m eb r i n g st op e o p l ec o n v e n i e n t , i n t e l l i g e n ta n de f f i c i e n tl i f e b u sc o v e r s w i d e l ya n dc o s t sl i t t l e ，w h i c hi st h ef k s tc h o i c eo fm o s tc i t i z e n s d i g i t a lh o m e w i l l i m p r o v eu s e r s l i f ec o n v e n i e n c eb yp r o v i d i n gt h ee f f i c i e n ta n da c c u r a t eb u sr o u t e q u e r ys e r v i c e a st h ec o r eo f t h eb u sr o u t eq u e r ys y s t e m ，b u so p t i m a lp a t ha l g o r i t h m d e t e r m i n e st h ee f f i c i e n c yo ft h es y s t e ma n dt h ea c c u r a c yo ft h eq u e r yr e s u l t s m si s o n eo ft h em o s tw i d e l y u s e dc o r n r n u n i c a t i o n sm e t h o d sa n dt h e r e f o r ei st h ei d e a l m e d i af o rs e n d i n gt h er e s u l t d e s i g n i n ga n di m p l e m e n t i n gt h ed i g i t a lh o m eb u sr o u t e q u e r ys y s t e mw i t hs m ss e n d i n g b a s e do nt h er e s e a r c ho fb u so p t i m a lp a t ha l g o r i t h m h a sr e s e a r c hs i g n i f i c a n c ea n da p p l i c a t i o np r o s p e c t t h et h e s i sb e g i n s 、析t ht h er e s e a r c ho fb u s r e l a t e dt h e o r ya n dt h et y p i c a lb u s o p t i m a lp a t ha l g o r i t h m b ya n a l y z i n gt h ec h a r a c t e r i s t i c sa n dd i s a d v a n t a g e so ft h e t y p i c a la l g o r i t h m s ，t h et h e s i sp r o p o s e st h el e a s tt r a n s f e ri m p r o v e da l g o r i t h mb a s e d o n b u ss e t t h eb a s i ci d e aa n ds t e p 舔w e l la st h ei m p l e m e n t a t i o no ft h ea l g o r i t h ma r e d e s c r i b e di nd e t a i l t h e nt h et h e s i sa n a l y s e st h ee f f i c i e n c ya n da c c u r a c yo ft h e a l g o r i t h ma c c o r d i n gt ot h ee x p e r i m e n t a ld a t a t h ea l g o r i t h ma d o p t st h eb u sl i n ew i t h t h el e a s tt r a n s f e ra st h eb e s ts o l u t i o na n di sa b l et oh a n d l et h es p e c i a ls i t u a t i o no f s i n g l eb u sl i n e t h ea l g o r i t h mh a st h ea d v a n t a g eo fh i g he f f i c i e n c ya n da c c u r a c y i n t h en e x tt h et h e s i sr e s e a r c h e st h ea l g o r i t h mi na p p l i c a t i o na n dd e s i g n st h ed i g i t a l h o m eb u sr o u t eq u e r ys y s t e m t h es y s t e mu s e ss e r v l e tt or e s p o n dt ot h er e q u e s tf r o m r e s e a r c ho fb u s o p t i m a lp a t ha l g o r i t h ma n d i t sa p p l i c a t i o nb a s e do nd i g i t a lh o m es m sp l a t f o r m c l i e n te n da n dr e l e a s e st h eq u e r yr e s u l to nt h ed i g i t a lh o m es m sp l a t f o r m t h e p l a t f o r mi sd e v e l o p e di nt e r m i n a lm o d e ，a d o p t sr m it oa c t u a l i z er e m o t ei n v o c a t i o n a n du s e sp d um o d ea st h es m sc o d i n gm o d e f i n a l l y , t h et h e s i si m p l e m e n t st h e d i g i t a lh o m e b u sr o u t eq u e r ys y s t e m t h es y s t e mi sd e v e l o p e do ni p a n e lm i d d l e w a r e a n da d o p t st h el e a s tt r a n s f e ri m p r o v e da l g o r i t h mb a s e do nb u ss e t t h er e s e a r c hr e s u l t o ft h et h e s i sr e a l i z e st h ef u n c t i o no fp r o v i d i n gb u sr o u t eq u e r ys e r v i c et ot h eu s e r si n d i g i t a lh o m ee f f i c i e n t l ya n da c c u r a t e l y , w h i c hi sv a l u a b l ef o rp r a c t i c a la p p l i c a t i o n k e yw o r d s ：d i g i t a lh o m e ，b u sr o u t eq u e r y , o p t i m a lp a t ha l g o r i t h m ，l e a s tt r a n s f e r , s m s p l a t f o r m i 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 学位论文使用授权声明 隘丝1 2 汐驴9 乒i 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：醑腮 日期：2 0 0 l 年箩月z 1 日 导师魏r 旬 日期：二嘶年乡月2 午日 公交最优路径算法研究及基于数字家庭短信平台的应用第1 章综述 第1 章综述 随着计算机技术的发展与3 c 产品的融合，数字家庭产业呈现蓬勃发展的形 势。“广东省数字家庭行动计划 创新提出岭南式的数字家庭发展模式，通过增 值服务方式为家庭提供电子政务、电子商务、家居控制、医疗保健、社区服务等 各种全新的互动服务。目前，城市公交以其覆盖面广、经济快捷的特点，是绝大 多数出行者的首选方式，公交查询服务具有广大的用户需求。通过对公交最优路 径算法的研究，在数字家庭中实现公交查询系统，以数字家庭短信平台为依托发 送查询结果，为大量数字家庭用户提供高质量的公交查询服务，具有广阔的应用 前景和重要的研究意义。 1 1 研究背景及意义 目前，公交是我国城市交通的主要方式，为城市的大部分居民提供经济、便 捷的出行机会，在国际大城市中，公交出行比例已经达到了6 0 甚至8 0 ，是 城市中绝大多数人选择的出行方式哪。随着城市建设步伐的加快，城市公共交通 也得到了迅速发展，公交线路越来越多，极大地方便了市民和外地游客。如果能 够提供一种服务，为市民提供方便、快捷、经济、高效的公交线路的方案，将方 便他们的出行和生活，解决乘客出行过程中遇到的实际困难，提高乘客的出行效 率，同时减少不必要的交通流量，提高交通运输的效率，对于推广公交优先政策、 确定科学合理的公交管理体系和提高公交系统的效率也具有重要作用。美国、日 本等西方国家在城市公交网络系统上投入了极大的财力，构建了利用计算机网络 和先进的通信系统的智能交通系统( i t s ，i n t e l l i g e n tt r a n s p o r t a t i o i ns y s t e m ) ，从而 实现了大范围内全方位发挥的实时、准确、高效的运输综合管理，使人、车、路 密切配合，大大改善了交通环境固。 北京的选择：优先发展公共交通，h t t p ：w w w c h i n a b u s e s c o r n r o a d 2 0 0 7 0 9 1 8 0 1 5 h t m 国外智能交通系统介绍，h t t p ：w w w m o h u r d g o v e n i c p r o d u c t f i l e 0 0 4 h t m l 公交最优路径算法研究及基于数字家庭短信平台的应用 第1 章综述 智能交通系统是利用交通信息系统、通讯网络、定位系统和智能化分析与选 线的交通系统的总称。它将先进的信息技术、数据通信传输技术、电子控制技术、 传感器技术、自控控制理论、运筹学、人工智能以及计算机处理技术等有效地综 合运用于交通运输，建立起一种在大范围内、全方位发挥作用的实时、准确、高 效的交通综合管理系统【l 】。智能交通系统通过对有关交通信息的实时采集、传输 和处理，把握当前交通运行状况以及预测未来的交通状况，借助多种手段和设备 对各种交通情况进行处理。通过有力的信息交流手段，使用户迅速获知交通信息， 从而有效地提高交通效率和安全，并使交通设施得到充分利用，实现交通系统的 集约式发展。国内在这方面的起步较晚，但是各地政府都给予了极大的重视， 相继建立了一些智能交通系统。南京市建立了公共交通基础信息系统，该系统以 v i s u a lb a s i c 为基本编程工具，以a c c e s s 为数据库管理软件，以m a p l n f o 的m a p x 为空间管理工具，对南京市公交网络的服务水平进行了科学地评估，找出了公交 网络中服务水平薄弱环节，为南京市的公交系统的发展起到了重要的作用。重庆 市研究开发了“重庆市公共交通管理信息系统 。该系统已实现了公交线路、公 交站点等基础地理信息设施的静态查询。北京市建立了“北京市公交查询系统。 该系统实现了公交站点、公交线路、两地之间等不同形式的查询，但该系统所返 回的查询信息仅仅是以文本的形式给出的，并没有实现有关图形信息的显示，缺 乏直观性。杭州市应用g i s 和g p s 技术，实现对车辆的动态调度和实时监控， 并对公交车辆的运行情况，提供电子站牌实时显示车辆位置。其中g i s 系统负责 接收车辆定位数据，完成车辆信息的地图映射，功能包括地理信息和数据信息的 输入输出、地图的显示和编辑以及空间数据查询等【2 】。 作为智能交通系统的重要组成部分，公交查询系统能为乘客提供准确、及时 的公交信息服务，同时能提高公共交通系统的效率。目前建立的一些公交查询系 统，效果不甚理想，主要存在以下一些问题： ( 1 ) 大多数系统基于点对点的查询，智能化程度较差； ( 2 ) 采用预先编排数据库的方式查询，不能满足城市交通网络的变化要求； ( 3 ) 查询结果显示方式差，不便于了解线路状况； ( 4 ) 咨询方式单一，没有充分利用现有的各种通信资源。 信息技术在城市公共交通系统中的应用。h t t p ：w w w c m o c o m c r d 0 5 0 3 m l i t s j 2 0 0 5 0 3 2 h u n 2 。交最优路径算* 研究& 基f 数字家廛短信平台的应用第1 章综述 近些年来，随着互联网技术的不断发展国内出现了很多提供公交查询的网 站，如8 6 8 4 全国公交查询网”、坐车网。等，已经可以为出行者提供丰富的出行 信息，包括公交出行方案、某条公交线路的具体停靠站点、公交站点信息等。在 这些功能中，对乘客最有意义的是根据起点站和终点站给出公交乘坐方案，在实 际应用中，由于系统采用的算法不同，同样的出行问题在不同系统得到的结果也 不同，而且有些查询结果明显不合理。 # 日，女0 女p 珊舳m n ；自t i i l * 目ol - 】f # # ) 【* 鞠j m 1 8 墼”m 陛! 塑j t n l0 自* 0 & # ? j n h 月 # * ：镕j e0 洲目， i # 图卜1 提供公交盎询服务的网站 2 0 0 6 年毫u ，广东省发改委、省信产厅、省科技厅、省广电局、省质监局和 省通信管理局等六个部门联合制定的“东省数字家庭行动计划”作为重点工作 被列入省政府工作报告和省“十一五”发展规划中任务。广东省数字家庭以数字 电视平移为契机，以独具特色的岭南式数字家庭发展模式为导向，按照“统技 术体系、全省互通互联、分级设置前端、共享频道资源、合理分配收益”的原则， 推进数字家庭试点_ 丁作，推动数字电视与数字家庭产业的发展口】。目前，广东省 数字家庭产业发展已形成有丰富软硬件资源的数字家庭产、l k 孵化平台和环境，具 有整合各家标准并实现产业化的应用基础，并有着庞大的潜在用户群体和市场。 所谓数字家庭，是指将各种家庭通信产品、计算机产品、消费类电子产品 ( 3 c ) ，按照各类家庭数字化需求，形成家庭网络，通过与社会全方位的信息交互， 组成家庭信息、娱乐、控制服务和信息功能系统，使家居生活更加舒适、安全、 智能化，开刨一种全新的生活方式。数字家庭将改变人们的生活方式，为人们 提供方便、安全、智能、高效、舒适的数字化生活，使每个家庭的生活、娱乐和 08 6 8 4 全国。交查询日。h t 。“8 6 8 4c r f f 坐车喇，h 呻丹一删o c h c 吖 黄选人枝企联合携手数字家庭，h t i p ：g 1 7 t c c hc o r t 咖洲“2 0 0 8 舛2 4 3 4 8 4 9s h t m l r 东艋功“数字家庭”行动计划，h u p ：w w wg d d h o m cc o m m e w “m f o a 辨x l d - 3 8 7 3 。交矗优路径算法m 究& 基干数字家庭短信平台的应用 第1 章综* 信息活动在一系列数字化产品的支持下，更节省时间和成本，取得更佳效果。 人们足不出户就可以更加方便快捷地获取信息，从而极大提高人类居住的舒适性 和娱乐性。通过构建数字家庭标准体系和专利池，形成适台我国国情的数字家 庭产品和技术应用规范标准，可吼促进以平板显示产品为代表的3 c 产品制造业 发展，也可以促进以数字家庭为基础的我国信息化的发展。数字家庭代表着信 息技术和产业应用的发展方向是现代信息服务业未来在家庭应用上的具体体现， 与平板显示产业、现代信息服务业的发展一并成为广东省信息产业转变增长_ 方 式、推动产业结构优化升级的重要举措。抓住数字家庭产、l p 发展的机遇，以互动 应用为纽带，可以实现电了信息产业的跨越式发展，带动芯片- 器件- 整机软件一 内容一服务一运营整个产业链的发展。数字家庭公共资源平台如图1 - 2 所示。 詈、 磊护? 露 皤烂 剥+ + ! 巴 载案嬲- 尹? 寸椠 觏 墨苎璧垮。冀墓鐾1 槲 稠磐i * ，、稽， 个恻 共冁 图卜z 广东数字家庭公共资源平台l 广东省数字家庭中自j 件以用户早已熟悉的遥控器操作方式为基础，结合了互 联网等目前流行的互动交互技术，为用户提供了即熟悉又新颖的互动体验频道， 同时为运营商、内容制作商提供了数字家庭互动业务的平台。数字家庭中间件位 于s t b 的操作系统之上，运行于多个s t b 硬件和o s 平台，提供跨网络、跨硬 件和跨o s 平台的透明性应用或服务的交互功能，能支持标准的协议和标准的接 口，管理计算资源和网络通讯。广东省数字家庭采用的中叫件主要有s d f 中间 蓦；：韪；：；i ；空；蓍! ：；：翌：嚣黧。：。 “数字家庭计划”助推广东产业甜级，h 呻：，p d c 1 1 4n e t j g , 4 a , 3 5 4 5 7 0 2h t m l 4 雪 螬蘑 公交最优路径算法研究及基于数字家庭短信平台的应用第1 章综述 件和i p a n e l 中间件。i p a n e l 中间件是专为数字电视业务开发的机项盒客户端软件， 将互联网技术应用于数字电视，提供全新的频道管理方式，给用户提供新的电视 收看模式，让用户以网页互动方式操作电视，为运营商开展、运营数字电视业务 提供平台。s d f 中间件作为数字家庭互动服务平台使用的中间件，是基于场景描 述文件s d f ( s c e n ed e s c r i p t i o nf i l e ) ，专为数字家庭互动服务扩展的软件。s d f 中间件通过整合i p a n e l 中间件，可以实现更强大的功能。在电视功能上，s d f 中间件支持高清、标清视频点播以及各种d v b c 业务；在互动平台功能上， s d f 中间件支持视频通信、视频点播、智能家居、数字医疗、远程教育等功 能：在系统功能上，s d f 中间件支持3 c 设备接入、终端p o s 业务、j p g g i f 动态g i f p n g 等图片格式、f l a s h 、j a v a s c r i p t 、h t m l 语言、s d f 协议语言 及国笔智能输入法w 。 广东省数字家庭为用户提供了舒适、安全、便捷的生活服务，电影点播、电 子政务、远程医疗、智能家居、三农服务等与用户日常生活息息相关的服务已经 得到了广泛的应用，推进了数字家庭产业的发展。提供更多的具有广大用户需求 的数字家庭服务有着巨大的现实应用价值。 目前，由于存在大量的用户需求，公交查询系统在互联网中得到了广泛的应 用。而在数字家庭中实现公交查询系统，为数字家庭用户提供准确高效的公交查 询服务，这方面的研究和应用远远落后于互联网上的公交查询系统。随着数字电 视的推广，数字电视必然会成为一种新的通讯和消费的媒体，数字家庭短信发布 公交查询系统正是借助该媒体，为市民出行提供高效便捷的公交查询服务。作为 当前最为简单和方便的数据通信方式之一，短信拥有广大的用户规模，是数字家 庭公交查询系统发布查询结果的理想媒介，同时以短信为核心的增值业务因其广 阔的市场前景和巨大的商业价值而备受人们的青睐。因此，在数字家庭短信发布 公交查询系统的实现过程中，研究作为公交查询核心部分的公交最优路算法，同 时开发数字家庭短信平台，以该平台为依托发布查询结果，在数字家庭中高效、 准确、便捷地为用户提供公交出行乘坐方案，具有广阔的应用前景和重要的研究 意义。 参考互动服务平台中间件介绍 5 公交最优路径算法研究及基于数字家庭短信平台的应用 第1 章综述 1 2 公交最优路径算法国内外研究现状 公交最优路径算法实现对公交出行最优路径的选择，根据输入的出行起点站 和终点站，输出最优的公交乘坐方案。对于道路交通网络两点间最短路径的搜索， 目前已有上百种成熟的算法，其中最著名的就是d i j k s t r a 算法。但现有的最短路 径算法一般不能直接运用于公交网络的路径选择中，因为公交乘客在出行的过程 中不仅要考虑出行距离，还要考虑换乘次数、出行时间、出行费用等其它因素。 国外对公交最优路径算法的研究伴随公交客流分配的研究而发展。n i c h o l a s k o n c z 等提出了公交网络多路径优选的算法，并以换乘次数为主要约束条件进行 路径选择研究，该算法只搜索二次换乘以下的情况，而不处理二次换乘以上的情 况【5 】；s n g u y e n 等结合出行策略理论、有效路径算法和超级网络理论，发展了基 于超级路径和策略优化理论的公交网络有效超级路径搜索算法，该方法不需要枚 举所有的出行策略，同时能够生成多条优选路径，但当两点距离较远时，该方法 产生的“有效”路径过多，而且其中很大部分是基本不被乘客考虑的路径【6 j ；j a n e z 研究了用二重图表示公交网络中换乘情况的简化模型【7 】；p h lb o v y 等研究了在 多模式运输网络中乘客选择出行路径的行为特征1 8 】；l o z a n oa 与s t o r c h ig 研究 了换乘方式选择中的行为问题f 9 】。 随着一些城市公交乘客信息系统的建立，国内一些学者也开始对公交最优路 径算法进行研究。张国伍在对f l o y d 算法进行扩展的基础上，提出了公交网络多 条最短路径算法，该算法一次可以搜索出所有的站点间的多条最短路径，但在只 需选择两点问路径的情况下应用效率较低【1 0 】；王祖祥等研究了公交网络中乘客在 换乘次数最小约束下的最短路径算法，并给出了多条路径集的生成技术【l l j ；杨新 苗等进行了公交乘客出行心理的调查研究，提出了以d i j k s t r a 算法为基础，以换 乘次数最少为主要目标，以出行距离最短为次要目标的出行路径选择模型，但是 对于影响公交出行的其它因素并未进行研究【1 2 】；赵巧霞等建立了以最少换乘次数 为第一目标，最少途经站数为第二目标的公交出行最优路径模型，并提出了可行 路径的最少换乘次数动态规划算法f 1 3 】；周文峰等通过建立直达综合费用矩阵和使 用修改的最短路径算法求出满足不同需求的最优公交出行路线【1 4 1 。近年来一些学 者将现代启发式优化算法引入到该类问题的研究中来，例如李文勇等使用蚂蚁算 6 公交最优路径算法研究及基于数字家庭短信平台的应用第1 章综述 法求解公交出行路径选择问题，但该研究只是以最少换乘次数作为约束，并没有 综合考虑影响乘客出行的其它因素【1 5 1 。 对于公交网络中两点间最优路径的选择是公交查询研究的难点。由于公交乘 客出行路径选择心理具有复杂性和多样性，往往单一的乘车路径并不能满足所有 乘客的需要。例如，一些乘客希望选择换乘次数最少的乘车路径，而另外一些乘 客则倾向于选择出行距离最短的乘车路径。公交乘客出行选择路径时考虑的因素 主要有换乘次数、出行距离、出行时间、出行费用、乘坐安全性和舒适性等。 在目前的公交最优路径算法的研究方面，存在的主要问题是以d i j k s t r a 及其 改进算法为主，该算法执行速度较慢，而且在运行过程中只是考虑路径最短，而 不能考虑换乘次数，通常会出现两点间需要换乘很多次才能到达的结果，而多次 换乘在实际应用中是没有意义的。 1 3 研究内容及主要创新点 如前所述，在数字家庭中实现高效便捷的公交查询互动服务有良好的应用价 值。公交最优路径算法是公交查询系统的核心部分，对系统的运行效率和查询结 果的准确性起着重要作用。本文依托国家科技支撑计划“数字家庭与数字电视技 术应用与示范 项目中的课题“数字家庭互动频点服务及试点应用示范，在阅 读大量文献和积累项目经验的基础上，深入研究公交最优路径算法，通过分析几 种典型公交最优路径算法的特点和不足，提出适用于数字家庭应用需求的基于公 交集合的最少换乘改进算法。同时开发数字家庭短信平台，以该平台为依托设计 并实现数字家庭短信发布公交查询系统。本论文的主要创新点如下： ( 1 ) 在研究公交出行相关理论以及典型公交最优路径算法的基础上，分析 几种典型算法的特点和不足，并提出基于公交集合的最少换乘改进算法。对该算 法的基本思想、步骤和实现进行阐述，并根据实验数据与原算法进行比较对算法 进行分析。该算法以换乘次数最少的公交线路作为最优方案，能处理现实中公交 线路存在单行线的情况，算法效率高，查询结果准确，能满足数字家庭公交查询 的应用要求。 ( 2 ) 在研究g s m 系统短信发送技术的基础上，设计并实现数字家庭短信 7 公交最优路径算法研究及基于数字家庭短信平台的应用 第1 章综述 平台，实现对数字家庭短信发布公交查询系统的查询结果进行短信发布的功能。 该平台采用终端方式进行短信发送，使用r m l 分布式计算技术和p d u 短信编码 模式，为数字家庭互动服务提供短信发送的功能，能满足数字家庭中以短信为核 心的增值业务的发展要求。 ( 3 ) 设计并实现了数字家庭短信发布公交查询系统。该系统基于数字家庭 i p a n e l 中间件进行开发，实施本文提出的基于公交集合的最少换乘改进算法，并 通过数字家庭短信平台发布查询结果。系统中的公交查询服务器采用m v c 模式， 运行s e r v l e t 响应公交查询请求。该系统实现了在数字家庭中高效、准确、便捷 地为用户提供公交乘坐方案的互动服务。 1 4 论文组织与结构 本文的章节结构主要安排如下： 第l 章是本文的综述，主要介绍本文的研究背景与意义，综述公交最优路径 算法的研究现状，介绍本文的研究内容及主要创新点。 第2 章对公交最优路径算法进行研究。在分析公交网络的基础上对典型公交 最优路径算法进行研究，分析了d i j k s t r a 算法、o l 矩阵最少换乘算法、公交查 询蚁群算法、基于直达矩阵的公交查询算法的特点和不足。 第3 章提出了基于公交集合的最少换乘改进算法。在对乘客出行选择影响因 素及对基于公交集合的最少换乘算法进行分析的基础上，对算法进行改进。对改 进算法的基本思想、具体步骤及实现进行详细阐述。根据实验数据，通过与原算 法比较，对改进算法的效率及输出结果的准确性进行分析。 第4 章设计并实现了数字家庭短信发布公交查询系统，对第3 章提出的基于 公交集合的最少换乘改进算法进行应用。对数字家庭短信发布公交查询系统进行 系统总体设计和公交信息数据库的设计，确定了系统结构。在设计与实现数字家 庭短信平台的基础上，基于i p a n e l 中间件实现了数字家庭短信发布公交查询系 统，并对系统运行情况进行分析。 第5 章是结论与建议。总结和评价本文所做的研究工作和相关研究成果，并 展望下一步的工作，提出改进建议。 8 公交最优路径算法研究及基于数字家庭短信平台的应用 第2 章公交最优路径算法分析 第2 章公交最优路径算法分析 本章对公交最优路径算法进行研究。首先对公交网络进行分析；在此基础上， 分析当前的几种典型公交最优路径算法。公交最优路径算法实现对公交出行最优 路径的选择。在当前提出的公交最优路径算法中，最优的指标选取没有绝对的标 准，有的算法以出行距离最短作为最优目标，有的算法以换乘次数最少作为最优 目标，有的算法以经过的站点数最少作为最优目标，还有的算法综合考虑了换乘 次数、出行距离、出行时间等因素，通过建立出行决策模型提供最优出行方案。 研究者从不同角度提出了算法，其中大多数算法都通过建立最短路径模型来解决 公交查询问题【1 6 】。目前，比较典型的公交最优路径算法有d i j k s t r a 算法、o - 1 矩 阵最少换乘算法、蚁群算法、基于直达矩阵的公交查询算法等。本章对这些典型 算法进行研究，分析其特点和不足。 2 1 公交网络分析 城市公交网络包含的两个最基本元素是线路和站点。线路和站点之间的关系 具有如下基本特征：每个站点包含若干条线路，站点内这些线路用名字唯一标识； 每条线路由一系列站点组成，并且按照一定的次序经过这些站点，一条线路上的 站点都可以用名字唯一标识。 在现实中，公交线路是比较复杂的，一般分为以下三类【1 7 】： ( 1 ) 完全的双向线路。如图2 1 所示，这种线路在起点站与终点站之间双向 行车，而且两个方向上的行车路线是对称的，经过相同的站点序列和街 道序列，线路上名字相同的站点分列街道两旁，只是经过同名站点的顺 序相反。 a 1b 1c 1 d 1 a 2 b 2c 2d 2 图2 - 1 完全的双向线路 9 公交最优路径算法研究及基于数字家庭短信平台的应用第2 章公交最优路径算法分析 ( 2 ) 环形线路。如图2 2 所示，这种线路起点站也就是终点站。行车线路是 单向环形的。 图2 2 环形线路 ( 3 ) 部分路段是单行线的线路。如图2 3 所示，有些在两个端点站之间双向 行车的线路，在个别比较窄或者比较拥挤的路段会实行单向行车，而在 其他的路段跟完全的双向线路一样，因此在这样的线路中两个方向的站 点序列和街道序列会有部分不同。这种类型的公交线路在现实中普遍存 在。如在广州市公交线路中，8 0 以上的公交线路存在部分路段是单行 线的情况。 a 1b 1c 1d 1 e 图2 - 3 部分路段是单行线的线路 在公交网络中，公交站点抽象成图的结点，公交线路抽象成连接各结 点的有向边。以上三类公交线路可以抽象如下【1 8 1 ： ( 1 ) 完全的双向线路。公交车在两端点之间双向行车，以不同方向经过相同 站点，可以抽象成各结点由双向边连接的有向图。如图2 - 4 所示。 a bc d e f _ i 卜_ o h 图2 - 4 双向线路的抽象 ( 2 ) 环形线路。这种行车线路起点终点重合，以单一固定的方向经过相同站 点，形成闭环，可以抽象成一个单向环形。如图2 5 所示。 图2 - 5 环形线路的抽象 ( 3 ) 部分路段是单行线的线路。这种线路部分路段是单向行车的，部分路段 l o 公交最优路径算法研究及基于数字家庭短信平台的应用第2 章公交最优路径算法分析 是双向行车的。可以抽象成有向图，图中存在单向边和双向边。如图 2 - 6 所示。 图2 6 部分路段是单行线的线路的抽象 2 2 d i j k s t r a 算法 d i j k s t r a 算法是由荷兰计算机科学家艾兹格迪科斯彻于1 9 5 9 年提出的。算法 解决的是有向图中任意两个顶点之间的最短路径问题。它是一个适用于所有弧 的权为非负的最短路径算法，也是目前公认的求解最短路径问题的最经典的算 法。 2 2 1 d i j k s t r a 算法基本思想 d i j k s t r a 算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为 止。d i j k s t r a 算法可以给出从某定点到图中其它所有顶点的最短路径的最优解， 通过求出单源最短路径，然后逐个节点利用d i j k s t r a 算法就可以求出整个网络的 节点之间的最短路径。但由于它遍历计算的节点很多，虽然可以适用于大型网络， 但是效率较低1 9 1 。 设图g 的所有顶点组成集合v ，d i j k s t r a 算法基本思想是，设置顶点集合s 并不断地作贪心选择来扩充这个集合。一个顶点属于集合s 当且仅当从源到该顶 点的最短路径长度已知。初始时，s 中仅含有源。设u 是g 的某一个顶点，把从 源到u 且中间只经过s 中顶点的路径称为从源到u 的特殊路径，并用数组d i s t 记录当前每个顶点所对应的最短特殊路径长度。d i j k s t r a 算法每次从v - s 中取出 具有最短特殊路径长度的顶点u ，将u 添加到s 中，同时对数组d i s t 作必要的修 改。一旦s 包含了所有v 中顶点，d i s t 就记录了从源到所有其它顶点之间的最短 路径长度 2 0 1 。 百度百科一艾兹格迪科斯彻，h t t p ：b a i k e b a i d u c o r n v i e w 2 7 7 6 1 0 h t m l l 公交最优路径算法研究及基于数字家庭短信平台的应用第2 章公交最优路径算法分析 2 2 2 d i j k s t r a 算法的不足 d i j k s t r a 最短路径算法由于其稳定性、能适应网络拓扑的变化，因而在计算 网络拓扑路径选择以及g i s 中得到广泛的应用口1 1 。但是对公交网络来说，d i j k s t r a 在公交线路查询中具有以下不足： ( 1 ) 算法时间开销大。在实际应用中，需要计算的公交网络规模通常都较大， 而在d i j k s t r a 算法中，核心步骤是从v - s 中取出具有最短特殊路径长度的顶点u ， 这是一个循环比较的过程，在大数据量的情况下，计算速度收到很大制约。以广 州市公交为例，公交站点构成的结点数有2 0 0 0 多个，对一般计算机来说，计算 速度极慢。 ( 2 ) d i j k s t r a 算法得到的最优路径可能在实际中没有参考价值。d i j k s t r a 算法 得到的最短路径没有考虑换乘次数，不一定能满足公交查询的要求。根据d i j k s t r a 算法计算出的起点站和终点站之间含有n 个站点的最短路径中，最少的换乘次数 是0 次，最多的换乘次数是n 次，平均换乘次数是n 2 次。例如，用d i j k s t r a 算 法计算乘客从a 站到b 站的最短距离，只要两个顶点之间有边存在，它就会进 行搜索，而不考虑换乘代价，这就可能造成从a 站到b 站的距离是最短的，但 需要转乘很多次车才能到达，即它重点考虑的是公交路径的距离或经过的公交站 点数，而忽略了换乘次数，这样的结果对乘客来说并不是最佳的选择，有时甚至 毫无意义。 ( 3 ) 算法的利用率较低。对由n 个结点构成的公交网络，d i j k s t r a 算法能够计 算出起点到其他n - 1 个点的最短路径，而实际上用户需要的只有起点到终点的最 短路径，这样造成了搜索其余路径结果的浪费，使得算法利用率低。 因此，基于经典d i j k s t r a 算法的公交最优路径算法在实际应用中存在算法时 间开销大，可能得到没有实际参考价值的最短路径、算法利用率低的不足，其算 法效率、查询结果的有效性和算法利用率都不能很好地满足应用需求。 2 30 - 1 矩阵最少换乘算法 o 1 矩阵最少换乘算法【2 2 】【2 3 1 以换乘次数最少作为最优目标，使用o 1 矩阵来 表示公交站点和公交线路的关系，通过对o 1 矩阵的查找判断得出换乘次数最少 1 2 公交最优路径算法研究及基于数字家庭短信平台的应用第2 章公交最优路径算法分析 的公交出行方案。 0 1 矩阵最少换乘算法根据城市公交线路和公交站点的关系创建线路一站点 表，对每个公交线路，若经过某站点，则用“l 表示，否则用“0 表示。这样， 公交线路和公交站点的关系可以通过o 1 矩阵来表示，现假设公交网络中公交线 路和站点的关系简单如表2 1 所示。 表2 - 1 公交网络线路一站点表 s ls 2s 3s 4 s 5 s 6 s ， s 8 s 9s l o s n $ 1 2$ 1 3$ 1 4$ 1 5 l l 10lol0o0l0oo1o0 l 2 o00 lo 0l o lol0ooo l 3 lll ol 00 l olo lo 1l l 4o00l1o000ool100 l 5 0lo0o01l1000o 1 o l 6 o00ol1o000o0100 l 110ll0olol0olooo l s 0000l00ool0o0ll l 9 olo00l0o00looo1 l i o o0 0 0o o1 0o0lol l l l 1 1 0o o oo 01 00olo1 1 l l i 2 0l o 01 ll 0000l0 l l 表中l i 表示公交线路，s j 表示公交站点，其中公交线路与公交站点的关系构 成o 1 矩阵w 。矩阵元素w i ，i 为o 或1 ，w i j = 0 代表公交线路l i 不经过公交站点 s j ，w i , j - - 1 代表公交线路l i 经过公交站点s j 。如表2 1 中，w 1 1 = 1 ，表示公交 线路l l 经过站点s l ；w 1 2 = o 表示公交线路l 1 不经过站点s 2 。 对于起点站s i ，终点站s j ，算法按以下步骤得到换乘次数最少的公交方案： ( 1 ) 搜索集合 l 1 ，l 2 ，l f ) ，判断是否存在l k l i ，l e 9o 9 l f ，使得w l 【i = w 幻= 1 。 若存在，说明无需换乘就可到达目的地，乘车路线为：s i 生b s j ，其中l k 满 足w k i = w i ( i j = 1 。 ( 2 ) 若不存在满足上述条件的l k l l ，l e ，l f ，则说明到达目的地需进行换乘。 搜索集合s s i = l i ，l 2 ，l f ，s s 2 = s