（系统工程专业论文）城市公交网络建模与最优路径搜索算法研究.pdf

华中科技大学硕士学位论文 摘要 j 最优路径搜索一直是g i s ( 地理信息系统) 和基于g i s 的i t s ( 智能交通系统) 的基本功能之一，也是g i s 算法研究的重点，它不仅仅是简单的数据查询和数据管理， 而是涉及到多目标决策和运筹学算法的综合数据处理过程。近年来数字城市成为g i s 研究和应用的一个热点，它的蓬勃发展大大方便了居住在城市中的人们在公务和休闲 时能够获取及时丰富的城市地理信息，充分享受信息化技术带来的生活便利。其中针 对城市公共交通网络的乘车线路搜索是人们对数字城市系统的一个基本需求，而这就 是一种典型的最优路径搜索问题，因此对这种乘车线路搜索问题的研究是很有意义 的。 本文对城市公交网络路径搜索设计了一套比较完整的解决方案，分析了网络系统 的软件模型、数学模型和数据库设计，并提出了一些提高网络路径搜索速度的优化算 法。软件模型运用了面向对象的设计模式，体现了良好的封装性和灵活性，做到了软 件设计与具体算法的隔离；选择了有向赋权图作为网络的数学模型，将最优路径搜索 问题转化为图的最短路径搜索问题，设计的重点在于图的边权值的设定，针对一些实 际情况提出了比较合理的权值计算公式。并且通过将实际的动态网络简化成大范围的 静态网络与小范围的局部动态网络叠加的模式，利用前期静态网络演算的最优路径结 果有效的提高了动态路径搜索的速度。最后构建了一个比较简单的但是能充分反映系 统特征的模拟网络来检验模型和算法的可行性。 关键词：城市公交系统路径搜索动态网络 i t sg i s 一- 一一一 华中科技大学硕士学位论文 = = = = ；j ；= = ；口= = = = # = = = = = = = = = = = ；= = = = = 一：= a b s t r a c t t h e o p t i m a l r o u t es e a r c hi s a l w a y st h e b a s i cf u n c t i o no ft h e g i s ( g e o g r a p h y i n f o r m a t i o ns y s t e m ) a n dt h ei 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 ns y s t e m ) b a s e do ng i s i ti s a l s ot h ef o c u so ft h ea l g o r i t h mr e s e a r c ho ft h eg i s i t sn o to n l yt h es i m p l eq u e r ya n d m a n a g e m e n tf o rd a t ab u tt h ec o m p r e h e n s i v ed a t ap r o c e s s m gt h a ti n v o l v et h em u l t i - o b j e c t d e c i s i o n sa n dt h ep r o g r a ma l g o r i t h m s t h e s ey e a r s ，t h ec y b e r c i t yh a sb e c a m et h ef o c u so f t h er e s e a r c ha n d a p p l i c a t i o nt og i s i t sl a r g ed e v e l o p m e n th a sc o n v e n i e n c e dt h er e s i d e n t s i nc i t i e st oo b t a i nt h ep l e n t yc i t yg e o g r a p h yi n f o r m a t i o ni nt i m ef o rb u s i n e s sa n d s p a r et i m e t h er o u t es e a r c ho fu r b a np u b l i cw a n s p o r tn e t w o r k s ，w h i c hi st h et y p i c a lp r o b l e mo ft h e o p t i m a lr o u t es e a r c i o ，i s o n eo ft h em a j o rr e q u e s t so ft h ec y b e rc i t y s y s t e m s s oi t h a s i m p o r t a n tm e a n i n g t or e s e a r c ht h i sk i n do f r o u t es e a r c h p r o b l e m t h i sp a p e rd e s i g n sa l li n t e g r a t e ds o l u t i o no ft h er o u t es e a r c ho fu r b a n p u b i ct r a n s p o r t n e t w o r k s ，a n da n a l y z e st h es o r w a r em o d e l ，t h em a t h e m a t i cm o d e la n dt h ed a t a b a s em o d e l o f t h i sk i n do f n e t w o r k s i ta l s om e n t i o n ss o m e o p t i m i z a t i o na l g o d t h i n si no r d e r t op r o m o t e t h es e a r c hs p e e d t h es o m a a r em o d e lu s e st h eo b j e c to r i e n tp r o g r a m p a t t e m 、析t ht h eg o o d e n c a p s u l a t i o na n df l e x i b i l i t yt oi s o l a t et h es o r w a r cd e s i g nf r o mt h ec o n c r e t ea l g o r i t h m s w eu s et h ed i r e c t i o n a lw e i g h t e d g r a p ha st h em a t h e m a t i cm o d e l ，s o t h a nw ec a nt r a n s f e rt h e o p t i m a lr o u t es e a r c ht ot h es h o r t e s tr o u t es e a r c ho i lt h eg r a p h t h ef o c u so f t h em a t h e m a t i c m o d e ld e s i g ni sh o wt os e tt h ee d 嚣sw e i g h to ft h eg r a p h w em e n t i o n e ds o m er e a s o n a b l e f o r m u l a st oc a l c u l a t et h ee d g e sw e i g h tu n d e rt h ep r a c t i c a lc o n d i t i o n a n dt h e nw es i m # f y 也ep m c d c a a 赳b 由m m i cn e t w o r kt ot h ec o m p o s i t eo ft h eg l o b a ls t a 6 cn e t w o r ka n dt h e l o c a ld y n a m i cn e t w o r k s ow ec a nm a k et h eu s eo ft h ep r e v i o u ss t a t i cr o u t es e a r c hr e s u l tt o p r o m o t et h ed 咄n i ci x ) u t e s e a r c hs p e e d a tl a s tw eb u i l das i m p l yb u tf u l l - c h a r a c t e r s e x a m p l e t oc h e c kt h ef e a s i b i l i t y o f t h em o d e l sa n dt h ea l g o r i t h m s k e y w o r d s ：u r b a np u b l i ct r a n s p o r ts y s t e m r o u t es e a r c h d y n a m i cn e t w o r k i t sg i s 华中科技大学硕士学位论文 = = = = ；= # = = ；= = ；= = = ；= = = = ；= = # = = = = 。= 一= 1 绪论 本系统属于城市智能交通系统( i t s ，i n t e l l i g e n t t r a n s p o r t a t i o n s y s t e m ) 的子系统， 近年来智能交通系统发展迅速，它是高效、综合地运用了信息技术、电子通信、自动 控制、传感器、运筹学、人工智能、计算机网络等诸多先进的最新科研成果，建立起来 的一种大范围、全方位、实时、准确、高效的交通运输综合管理和控制系统。智能运 输系统实质上就是利用高新技术对传统的运输系统进行改造而形成的一种信息化、智 能化、社会化的新型运输系统，其服务领域涉及先进的交通管理系统、出行信息服务系 统、商用车辆运营系统、电子收费系统、公共交通运营系统、应急管理系统、先进的 车辆控制等系统。它使交通基础设施能发挥最大的效能，提高交通的安全水平，提高道 路网的通行能力和汽车运输生产率，从而获得巨大的社会经济效益。欧美等发达国家对 i t s 系统研究都进行了相当大的投入，其中美国在这方面处于世界领先的地位，已经 建立了一些局部、小范国内的管理系统和实验系统，1 9 9 5 年美国开发出了亚特兰大奥 运会交通管理系统，另外日本和欧洲一些国家也相继推出了盯s 的相关产品，如电子 地图、车载显示器等。 i t s 系统离不开g i s 的支持，g i s 是以地理空间数据库为基础，在计算机软件的 支持下对空间相关信息数据进行采集、管理、分析、操作、模拟和显示。g i s 不同于 简单的数据管理系统，它要对其所包含的图形、属性信息具有综合、分析等功能。g i s 是i t s 中地图匹配、路径查询、路径引导等功能实现的基础。【1 4 l 智能交通系统是一个非常庞大复杂的系统，是由数字地图数据库、定位导航、地 图匹配、路径规划、路径引导、通讯等多个模块构成的，本文研究的是其中的一个子 系统，即城市公共交通系统网络，研究的重点是提出一个针对最优乘车路径快速搜索 的解决方案，包括方案的软件设计、数学建摸和算法设计，研究的对象是城市中公交 车、地铁、轮渡等具有固定线路且按时按站顺序行驶的交通工具所组成的公共交通网 络，而不包括出租车及其他私人车辆等自选线路按o d 即从起点( o t i s ) 到终 点( d e s t i n a t i o n ) 方式行驶的交通工具。它只处理与已有的公共交通路径有关的 华中科技大学硕士学位论文 信息，而不涉及车辆管理、城市建设、公交线路设计以及其他的i t s 应用，力求提出 一个简洁灵活的软件设计模型和个合理高效的数学模型，并能提供统一的函数接口 供上层i t s 系统调用。 这方面研究的着眼点在于公交网络的拓扑结构、运行特征和表示方法，重点是如 何量化公交线路的运行质量和搜索过程中的路径优化条件，如何综合决策过程中的多 目标因子。国内外学者对这些问题已经进行了大量的研究并取得了很多成果，比如日 本学者1 9 9 7 年提出的交通状况的量化模型圆，美国学者提出的动态图的最短路径搜索 和连通性搜索的优化算法f s l ，以及近年来被广泛研究的基于人工智能的网络优化算法 包括神经网络算法、遗传算法、克隆蚂蚁算法 9 1 等等。本文主要是基于经典的图论算 法，结合城市公交网络的自身特点研究如何快速搜索网络中的全局最优路径。 华中科技大学硕士学位论文 = = ；= = = = = = = = = ；= = ；= = = = = = = = = = = = = 一一 2 城市公交网络模型的建立 2 i 系统分析和面向对象的网络模型 2 1 1 系统分析 城市公交网络包含两个最基本的元素就是线路和站点，本系统内的所有交通工具 都包含这两个元素，并且具有相同的基本特征：每个站点都包含若干条线路，站点内 这些线路用名字唯一标识；每条线路由一系列站点组成，并按一定的次序经过这些站 点，一条线路上的所有站点都可以用名字唯一标识。路径搜索是建立在线路和站点的 关系上的，搜索的结果应该是站点和路径的集合，表示如何乘车和怎样经过各个站点。 在这个抽象层次上可以将不同种类的交通工具统一起来，将公交网络用线路和站点的 集合来表示。同时，不同类型的交通工具的线路和站点也有自己的特点，像地铁、城 市轻轨之类的有轨交通工具，机动性较小，速度快，准时，而且受路面条件和交通状 况的影响很小，但是车次较少；轮渡是某些城市特有的交通工具，用于渡江，线路固 定，速度慢，没有中间站点，这两种交通工具的行驶状况基本上可以看作是静态的， 相对来说公共汽车网络就复杂得多，而且也是城市公交系统的主要部分，下面详细分 析这种网络的特点和表示方法。 一般来说，在具有交通枢纽位置的地段会有很多公汽线路经过，为了不至于在同 一个站点停靠太多的汽车而阻塞交通，会在相隔不远的几个地方建几个车站分别停靠 不同的线路来分流线路密集的压力，这些站点通常具有相同的名字，这些站点之间距 离不远一般可以认为在它们之间步行是可以接受的，这一点在搜索路径的时候尤其重要。 il ! ! ii 士 厂 ( 在交通拥挤的路口有可能站点a ，b ，c 名字相同) 图：1同名但不同位置的站点 华中科技大学硕士学位论文 = = ；= = ；= = = = = = = = ；= = = = = = 公汽线路是比较复杂的，一般可以分为三类： 1 ) 完全的双向线路。这种线路有两个端点站，在这两个端点站之间双向行车，而 且两个方向上的行车路线是相同的，经过同样的站点序列和街道序列，但是线路上同 一个名字的站点都是分列街道的两旁，所以同一个名字对应两个在地理位置上不同站 点这种线路一般来说在两个方向上的交通状况是不同，因为他们分别在左行线和右 行线上行驶。 坠! ! ! ! 坚 衮1 万气r 图2 2 完全的双向线路 2 ) 环形线路。这种线路的行车路线是单向的环形的，线路内可以用名字唯一标识 一个在地理位置上唯一的站点，这种线路表示起来比较简单。 图2 3 环形线路 3 ) 部分路段是单行线的线路。有些在两个端点站之间双向行车的线路，在个别比 较窄或者比较拥挤的路段会实行单向行车，而在其他的路段跟完全的双向线路特点一 样，因此在这样的线路中两个方向的站点序列和街道序列会有部分不同，但是总体特 点跟完全的双向线路类似。 坚k ! ；蹩- 补乞莅 e 图2 4 部分路段是单行线的线路 综上所述，对于站点，并不能简单的用名字来唯一的标识，所以要引入一个难一 的正整数作为标识唯一站点的d ，对于双行线路上道路两边的同名站点是否需要区 分则由地理信息数据的分辨率和具体应用的需要来决定。同样，这些因素还决定双向 线路上每个方向的线路是否用不同的公交线路来表示，为了满足这种要求，公交线路 华中科技大学硕士学位论文 = ；= = = ；= ；= = = = = = = = ；= = = = = = = = = = = # 一： 也不能用名字在唯一标识，同样需要增加一个唯一的正整数i d 值。另外，对于同一 名字的线路上同名站点是否需要区分应该取决于同名线路是否区分方向。【1 1 城市的交通状况是非常复杂多变的，整个城市公交网络是一个规模比较大的动态 网络系统，丽公交网络的最优路径搜索本质上是一个多目标的决策问题，人们在查询 的时候往往是多种情况综合考虑，其中主要的因素是乘车时间、票价和转车的次数， 这些因素有些是网络的静态特性或者在比较长的时期内是静态特性，比如转车次数和 票价，另一些是随着交通状况的动态变化而变化的比如乘车时间。而定义查询条件的 本质就是定义一个以这些因素为自变量的函数，这样就能够将多目标决策转化成以函 数值表示的单目标决策。 网络模型的设计主要包括三个方面：软件模型设计，数学模型设计，数据库设计。 软件模型主要需要解决网络的逻辑表现方式、数据结构和提供给上层应用的程序接 口。软件模型应该与具体数据和算法无关，不至于改进数据结构或者算法后需要重新 设计软件模型：此外还应当具有相当的灵活性以适应前面分析的各种网络的静态和动 态特性，有完整的调用接口来方便使用并隔离底层的具体数据和算法。而用面向对象 的模型能很好的实现这些要求。数学模型主要解决的是路径搜索算法的问题，用数学 的方法来抽象网络模型的特征，提供快速路径搜索的解决方案，根据上面的分析，用 图论的模型来表示公交网络是非常合理的。应该说数学模型的设计和算法设计是紧密 相连的，但是这一部分侧重与讲述图论模型的建立，算法设计在下一部分详细描述。 数据库设计是模型持久化的基础，与软件模型和数学模型都相关，重点是保存需要持 久化的信息以便模型的重建，并为各种算法提供信息支持。 2 1 2 面向对象的网络模型设计 这个面向对象的网络摸型用c h 实现，三个抽象类分别表示公交网络( i t r a n s n e t ) 、 公交线路( i t r a n s l i n e ) 和公交, ：o t r a m n o d e ) ，这三个抽象类定义了模型的基本规则。 另外还有一个表示乘车费用的类( t f i p c o s t ) ，这个类表示的是某一路段的乘车花销，这 个花消并不是单纯的指票阶，而是综合了行驶路程、行驶时间、票价等多种因素的广 义概念，一个查询条件类( q u e - c o n d i t i o n ) 定义查询条件，一个路径类来表示查询结果 ( r o u 幽。上层i t s 旺甩调甩这些接口，并指定查询条件( q u e r y c o n d i t i o n 的某个实例) 华中科技大学硕士学位论文 来查询最优路径，从返回的r o u t e 实例中提取路径信息。 2 1 2 1i t r a n s n e t 类及其派生类的设计和说明 l了u t t s n e t 4 - i t r a n s n e t 0 + 一i t r a n s n e t ( 1 + c t a s s n a m e ( ) ：c q n s tc h a r * + g c t n o d e ( i n1 d ：i n t 、： t r a n s n o d e + g c t l i n o ( i ni d ：i n t l ：i t r a n s l i n o * + g e t n o d e i d s ( i nn o d e n a r n c ：c o n $ cc h a r 。i n o u ti d s ：i n t ) ：i n t + g e t l i n m d s ( i nl i n e n m n c ：c o n s tc h a r + ，i n o u ti d s ：i n t ) ：i n t - e g c t a l ! n o d e l d s ( i n o u tl o s ：i n t 、：i n t j - g e t a i l l i n e d s ( i n o u tr d s ：f n t 1 ：f n t * q u e r y o p t i m a l r o u t e ( i nf t o m n n d e ：i n t 。i nt o n o d e ：；n i nc o n d i t i o n ：q u e d c o n d i t i o n ) ：r o m e 。 + i n i t n e t ( ) ：b o o + g i c a 2 t n e * o ：v o i d 图2 5i t r a n s n e t 的类图 这个网络接口体现了上面分析到的网络特征，即站点和线路都应该用d 来区分， 同一个名字的站点或线路可能有多个，网络最主要的功能是查询在指定条件下的最优 路径，各函数的意义从函数名上可以看出来，要说明的是对于得到d 集合的函数有 一个i d s 参数是i n t * & 类型，表示在内部分配个数组来存储值，数组的长度由函 数的返回值返回。i t r a n s n e t 是上层i t s 应用主要使用的接口之一，它将具体的攫索算 法与外部应用隔离开来，算法的实现由它的派生类实现，如果需要改进算法或者是替 换数学模型都不会影响上层应用的调用代码，而只需要用新的派生类来代替原来的算 法实现。 li t r a n s n e t 【 i l i u r b a n t r a n s n e t l # r na s t o p s ：a r r a y l 蚋t 1 a l i n e s ：a r r a y 圈2 6u r b a n t r a n s n e t 的类图 u f b a n t r a n s n e t 是一个城市公交网络类，它实现了i t r m s n e t 的纯虚方法，另外还 要实现图论搜索算法，算法的实现在后文中具体说观，主要看它的两个成员变量 6 华中科技大学硕士学位论文 = = 2 = = ；= = = ；= = = = = ；自；= = = = = = = = = 一： m _ a s t o p s 和m _ a l i n e s ，它们都是a r r a y 类型的变量，a r r a y 在c + + 中等价于数组，这 样处理是用到了一种提高查询计算速度的方法，我们在给网络中的站点和线路分配i d 的时候让它们各自的i d 值都是从0 依次递增i 的非负整数，假设站点共有n 个，那 么站点的d 在【o ，的范围之类，而ma s t o p s 的长度就是n ，m 值为n 的站点存储 在m _ a s t o p s 的第n 个元素的位置，线路同理。这样可以快速的按d 值查询元素，而 且也非常有利于后面算法设计中将要遇到的判断元素是否在集合中的操作。 2 1 2 2i t r a n s l i n e 类及其派生类的设计和说明 r r a n s a n e * t r a n s l i n e 0 + - - r r r a m l i n e 0 + c l 越s n a r n e q 。c o n 啦c h a r + g c t l m c 【d n i a t + g o t l m c n 舯c 0 c o l t 对d l a p + s c t l 堋c n 锄爿i a n m cc o l o r d l a f 、v o i d 姆剁o d i nm c ：c o n s tc h 矿) * g c t t r i p c o s t ( i nf a o m n o d c c o i l s tc 时，i nt o n o m ：c c l 1 ：t d c c o s 一 + g e f f i n t n o d e 0 ：f r n m s n o d c + 眦a s t n o l - - 0 ：i t r a n s n o d e * + 萨c s 州州i n 丘o m n 吨，咕tc i 矗r ，i n t o n o d e ：c o , n 啦c h 矿，t n o 位鳅：r r r m t s n o d e 盂) i n t 图2 7i t r a n s l i n e 的类图 这个公交线路接口体现了上面分析到的线路特征，在线路内以名字定位站点，每 条线路有自己的i d 和名字，并可以查询这些属性，线路知道自己所在线路的行驶状 况，因此可以计算出任意两个站点之间的交通状况，由g e t t r i p c o s t 方法得到，一般线 路有两个端点站点，由g e t f i r g n o d e 和g e t l a s t n o d e 得到它们，另外，通过线路应该 可以取得从一个站点到另一个站点所经过的中间站点，这由函数g 吼s e r i a l n o d e s 实现。 图2 8 b i d i r l i n e l o o p l i n e ，m i x l i n e 的类图 7 华中科技大学硕士学位论文 = = ；= = = = ；= = = = ；= = = = = ；= ；= = = = = = 一= b i d i r l i n e 是完全双向线路的一种实现，用变量mn d 保存线路的i d ：ms t r n a m e 保存线路的名字：ma s t o p s 按顺序保存线路上的站点，这是一个a r r a y 类型的交量， 这是线路有次序经过站点的体现；mm a p n a m e 2 1 n d e x 是一个m a p 类型的变量，这个 m a p 以站点的名字为关键字，以站点在ma s t o p s 中的索引值为值，这样处理主要是 为了便于快速计算两个站点之间间隔多少个中间站点，同时也体现了线路中站点和站 点的名字一一对应的关系。l o o p l i n e 表示了环形线路，由b i d i r l i n e 派生，它们的结 构是完全一样的，不同的只是行车方式，l o o p l i n e 中的n la s t o p s 是首尾相连的。 m i x l i n e 表示了混和线路，它也是由b i d i r l i n e 派生的，除了继承父类的属性外还有 一个a r r a y 类型的变量ma c t s t o p s 来保存反向的站点，因为两个方向的站点序列并不 是完全相同，它的m _ m a p n a m e 2 i n d e x 的意义也有所变化，仍然是以站点的名字为关 键字，以3 2 位整数为值，不过这个3 2 位整数的高1 6 位表示这个站点在m _ a s t o p s 中 的索引，低3 2 位表示在ma c t s t o p s 中的索引。 2 1 2 3i t r a n s n o d e 类及其派生类的设计和说明 l t r 口n s n 0 d e i t r a n s n 0 d e ( 1 + 一i t r a n s n0 d e n 甲c i a 5 s n a m e ( ) ：c o n s tc h a r + g e t n o d e l d o ：i 1 1 t 一g e t n o d e n a me ( ) ：c o n s tc h a l + s e t n o d c n a m c ( i nn a t l lc ：c o n s tc h a t * ) ：v o i d 中g e l l i n e ( i 1 1l i n e n a r l le ：c o n s te h a r ) ：i t r a n s l i l l e + 一g e t a l l l i n e s ( i n o l l ts e t ：i t r a i l s l i n e + ) ：i n t 图2 9i t r a n s n o d e 的类图 这个公交站点接口表明，站点以d 来唯一标定，每个站点有自己的d 和名字， 站点里的公交线路用名字来唯一确定，通过g e t a l l l i n e s 可以得到该站点内的所有线 路。 站点接口的实现s t o p 类 华中科技大学硕士学位论文 = = = = ；= = = = = 2 = = = ；= ；= = = = = = = 一= ： 目2 1 0 s t o p 的类图 这个类由i t r a n s n o d e 派生表示一个公交站点，实现了父类的纯虚方法，这里我们 主要关心它的属性，正如上面分析的，它具有一个d 和一个名字，还有一个m a p 类 型的属性来保存站点中的线路，这个m a p 以线路的名字为关键字，以线路的指针为 值，它表示了站点中的线路和线路的名字是一一对应的。 2 1 2 4 t r i p c o s t 类的设计和说明 t r i p e o s t + t r i p c o s t o + 一t r i p c o s t o + g e t s e c t i o n s ( ) ：a t + g o t di s t a a c e o ：d o u b l o + g c t t i m c o ：d o u b l e + g e t p r i c e o ：d o u b l e 图2 1 1t r i 口c o s t 的类图 这个类表示在种乘车方案中的一些参数，反映的是人们在做路径查询时要考患的 因素，这里我们主要考虑四个参数： s e c t i o u ：“分段”数；一个“分段”是指一条线路在相邻两个站点之间的路段。“分 段”数就是指一条乘车路径从起点到目的站点的路径中经过的这种“分段”的总数。 d i s t a n c e ：路程。就是指一条乘车路径从起点到目的站点的行程。 n m e ：时间。就是指一条乘车路径从起点到目的站点要经过的时间。 p r i c e ：这个参数就是线路的票价。 以上这些参数有些是在动态变化的，比如时间。有些是相对固定的，比如票价和 “分段数”。这个类体现了决策过程中的多目标特性，同时也体现了一条线路在某个 乘车方案中的交通状况。 华中科技大学硕士学位论文 2 1 2 5 q u e r y c o n d i t i o n 类的设计和说明 q u e r y c o n d i t i o n + q u e r y c o n d i t i o n 0 + h q l 斌y 删t i o n o + g e t w e i g t a ( i ni 印l n ：t 8 p c o s t + ) ：d o u b l e 图2 1 2 q u e r y c o n d i t i o n 的类图 这个类的作用就是定义以多目标参数为自变量的函数关系，以t r i p c o s t 为输入参 数，但是这不代表多目标参数完全由t f i p c o g 表示，个明显的例子就是t d p c o g 不 表示转车次数，因为这涉及到多条线路之阃的关系。其中g e t w e i g h t 的函数值表示了 权值的概念，权值是最优化决策的量化标准，这个是一个匿论中的概念，在后面的网 络模型图结构中再详细描述。 2 1 2 6r o u t e 类的设计和说明 图2 1 3r o u 【e 的类图 r o u t e 类表示了一种乘车方案，也是查询结果的表达方式，一种乘车方案由有一 系列有序的站点和线路集合构成。而且它们之问是交错的，即第i 条线路表示从第i - 1 个站点到第i 个站点的线路，而mt r i p c o g 表示了这神乘车方案的决簟信息。 2 1 2 7 类关系图 1 0 华中科技大学硕士学位论文 ( 以上是符合u m l 规范的软件模型类关系图，类之间的关系在上面的分析已有译细说明) 图2 。1 4网络模型类关系图 2 2 网络模型的图结构和权值的设定 2 2 1 图的概念 称g = ( v ，e ) 是一个图，如果：( 1 ) 矿是一个非空的有限集合，( 2 ) e 是v 中元 素的无序对组成的有限集合。并把矿的元素叫做图的顶点，e 的元素叫做图的边。 称g = ( v ，e ) 是一个有向图，如果：( 1 ) y 是一个非空的有限集合，( 2 ) e 是矿中 元素的有序对组成的有限集合。并把矿的元素州做图的磺点，占的元素叫做图的有向 边或边。在有向图中，若e ( u ，v ) e ( g ) ，则称u 为e 的起点或尾，p 为i , t 韵出边；称v 为e 的终点或头，p 为v 的入边：又称为v 的前趋，v 为m 的后继，若两条或两条以 上的边有相同的头和尾，则这些边称为平行边。 设g 是一个图，g 的一个顶点和边的非空有限交错序列w = v o qv l e k 叱，k n ， 满足p 。z ( v 。，v 。) ，i = 1 , 2 ，k ，贝l j 称矽为一条v 。一v 。通道，v 0 为起点，v k 为终点， 华中科技大学硕士学位论文 ”l 一，v 。为内顶点，如果起点与终点不同，则称为开通道，若相同则称为镯通道，没 有重复边的通道称为迹，没有重复顶点的开通道称为路。 若图g 的每一条边e 都对应一个实数w ( p ) ，则称w ( p ) 为边口的权，并称图g 为赋 权图。若p 是v ，的路，则路p 的权w ( p ) 称为p 的长，长最小的y i v j 路称为最短路 v ，- v ，最短路的长称为顶点心到v ，的距离，记为d ( 一，v ，) 。最短路有一个重要而明显 的性质：最短路是一条路，且最短路的任段也是最短路。 2 2 2 网络模型的有向圈结构 结合上文的分析，如果用赋权图模型来表示公共交通网络将非常直观而且非常适 合于最优路径搜索的问题，如果能够将查询条件转换成图的边权值，则最优路径搜索 就可以化为赋权图的最短路问题。由于公交线路包含多种类型，而且在公共汽车网络 中，不同方向的行车路线可以会有不同的行驶情况，所以应该有有向图来表示。 公交网络的有向图有多种不同的表示方法，两种比较合理的有向图模型是： 1 ) 令图g = ( v ，e ) 表示公交网络，矿是公交站点的集合，若站点叶到v ，有边当 且仅当( i ) v 。到v ，可以步行到达，或者( 2 ) 有公交线路从v ，到v ，并且没有中间站 点。 不允许包含中俑站点 ( 第1 种情况的边) l 一 v iy ， ( 第2 种情况的边) 图2 1 5 第一种有向图模型的边定义 2 ) 令图g = ( 矿，三) 表示公交网络，矿是公交站点的集合，若站点点t 到有边当 且仅当下列三种情况之一成立( 1 ) 站点v 。到v ，有线路直达，( 2 ) 存在通路v l y ，v ，v 到l 有车直达并且也到_ 之间可以步行到达，( 3 ) 存在通路一叱，也至n 一有车直达 并- j l v ，到v ，之间可以步行到达。 i o l 华中科技大学硕士学位论文 允许包含中问站点 广弋。2 允许包含中涸站点 2 - l _ r + 。 7 八_ 叶 允许包含中闻站点 1 卜l 二- _ _ u ，7 v j v j ( 第1 种情况的边)( 第2 种情况的边)( 第3 种情况的边) 图2 1 6 第二种有向图模型的边定义 这里需要解释“可以步行到达”的概念，上面分析公汽站点的时候提到有些站点 相距很近，之所以分别设置两个站是为了分流过多的经过线路，这样的站点之间就是 “可以步行到达”的，这是为了让路径搜索的结果更合理，因为人们在实际乘车的时 候般情况下不拒绝这种步行，而且这样有可能得到比在原地等车好得多的方案，不 过到底距离多少是相距很近则由具体的i t s 应用来决定，可以动态的设置也可以根据 实际经验来静态设定。 上面两种模型各有各的优势，模型l 是网络关系的直接反应，具有比较商的灵 活性，边的数量少，因此数据量较小，而且比较直观；而模型2 ) 是在模型1 ) 的基 础上经过了前期处理后得到的，预先演算了网络中站点间的直达情况，但是数据量比 较大，而且如果公交线路某处发生改变将影响较多的边。不过模型2 ) 在概念上更符 合实际的乘车情况，在有直达线路时人们一般会将它当作一种完整的乘车计划而不是 分成几个小段来考虑，最重要的是这种模型方便于将转车这种与边序列有关的制约条 件与乘车时间等和当前边有关的制约条件统一起来，而这是能够运用图论中d i i k s u - a 算法、f l e d 算法等经典最短路径算法的基础，另外由于我们还将在内存中构造网络 的逻辑结构，按照软件模型的分析这种逻辑结构等价于模型1 ) 的关联矩阵，更加合 理更加全面的选择是用模型2 ) 来作为网络的数学模型。 2 2 3 权值的设定 上述有向图的边表示两个站点之间的连接关系。而边的权值则用来量化这种关 系，是路径优先等级的衡量标准，上文中已经分析了人们在查询过程中关心的各个因 素。其中在类t 6 p c o s t 中列出的各种因素是分摊在每条线路上的，假设由集合c 衰示， 若令、蜥= 厂( c ) ，则w ，就可以用来表示每条线路上练合了c 中各种因素权值，在上述 华中科技大学硕士学位论文 有向图模型2 ) 的情形( 1 ) 中，c , 就是3 l v 。到v ，的公交线路上的综合因素，而在情 形( 2 ) 中，由于有步行的路段，w 。还应该加上一个以步行距离d 为自变量的函数值 来表示查询人对步行的厌恶程度和步行的时间，即w 。= ，( c ) + g q ) 。情形( 3 ) 与( 2 ) 的计算方法一样a 如果图中有多条从一到v ，的平行边，则w 。取所有情形中的最小值。 一般来说在c 的诸多因素中，人们主要考虑的是时间因素，当然。对某些特殊情 况，票价也是会被重点考虑。乘车时问是和多方面的因素相联系的，通常公共汽车是 很难预计准确的到达时间的，而相比之下有轨交通工具如地铁、轻轨列车等由于行驶 环境比较稳定而具有比较严格的行驶时间表。公共汽车行驶条件的复杂性主要是原予 城市道路交通状况的复杂性，在智能公交系统( i t s ) 中一个很重要的课题就是如何 准确的计算公汽线路的行驶时间，新加坡最新的实用i t s 系统中就运用了全球定位系 统来测量城市交通质量和公汽的行驶情况。另外，除了道路的交通状况外，城市道路 的交通规则也是一个重要因素，比如单行还是双行，路口如何转弯等等。1 9 9 7 年三位 日本学者m a s aa k i ，h i k a r us h i m i z u 和y 0 hy o n e z a w a 提出了一个基于交通通畅程度和 交通信号灯变换频率的时间估算模型，在这里作以下简单介绍：1 3 1 这个模型将交通状况分为拥挤和通畅两种情况，在通畅的情况下又分为有交通信 号灯育转向控制信号和没有转向控制信号两种情况，并假设在交通信号灯变为绿色之 前车辆不能通过，在估算行驶时同时将车辆的行驶方向分为奁行、右转和左转。 在交通拥挤的情况下： 1 ) 直行时间 t l 鬯j j , m , l ，k ) j - 、- - p ：( j 嘶七f | 2 + t y + r 。+ t s + c 。1 + p y o 帅+ iy | 2 + f r + f | + 1 0 其中 + 只( f m + f ，2 + t ，+ f 口) 。= ( d y ，) y f 。= q p 2 ) 右转时间 ( f ，所。，七) ；t ( f m + r 。2 + f y + f ，+ f + f ，+ f 丌) 。 + 只( r 。+ f ，2 十f ，+ r 廿+ r ，+ f ”) + 只( f 删+ f ，2 + t 士+ f ，+ f 盯) 3 ) 左转时间 华中科技大学硕士学位论文 正( f ，t e l ，f ，k ) = 只p 舯+ t g ，2 + f y + t ，+ f 讲+ f ，+ f c f ) + 只( f 删+ f ，2 + o t r + o + f 。+ 0 ) + e ( ，删+ t ，1 2 + f 越+ t j + t a ) 在交通通畅且有转向控制 ( 1 ) 直行时间 乃( f ，m ，七) 荨匕f m + 0 ( f 抽+ y 1 2 + t ，+ f ，+ f 口) + p a t 胁+ f ，1 2 + t ，+ f 廿) ( 2 ) 右转时间 t ( j ，j ，m ，f ，七) = p , t 。+ 口，( 0 ，2 + f ，+ t ，+ f 士+ f ，+ f 矿) 4 - t f ( 1 口，) ，4 ) 七p v 0 ，。七ty 2 + t ? + f - 七t 。七1 0 七p ? 乜憾七t 。2 + t 蕾七t l 七t 0 ( 3 ) 左转时闻 l ( f ，歹，m ，七) = 0 f 胂+ 口，( f 。2 + t ，+ f ，+ f 田+ f ，+ f 一) + f f ( 1 - - ( z j ) ，4 ) 千p 。u 咖+ ty ? 2 ；t ，+ t , u 七t ：+ t 。| ) + p ，q 删+ t ，2 + f 4 + t | + t d ) 在交通通畅且没有转向控制 ( 1 ) 直行时间 t ( i ，j ，m ，f ，) = f 。 ( 2 ) 右转时间 正( i ，l ，l ，七) = ，删+ t 由+ t s + f 矿 ( 3 ) 左转时闻 正( f ，m 。，t ) = f 。+ t 女+ t ，+ t a 对于要经过多个路段和多个站点的车辆，总时间应该是 。= 正( f ，j ，脚，七) + t ，表示车辆在站点停靠的时间 l 其中各参数的意义说明如下： t 5 华中科技大学硕士学位论文 表2 1 道理通行时问模型参数说明 参数说明 l ，信号灯所在的位置 m 汽车行驶的方向 ，周中的哪一天 七时间 f m 通过这路段需要的时间 t g 绿灯持续时间 f ， 黄灯持续时间 ，红灯持续