（交通信息工程及控制专业论文）停车诱导系统最优路径算法研究及其仿真平台构建.pdf

长安大学硕士学位论文 摘要 目前国内各大中城市停车供需矛盾日益突出，而停车诱导系统是解决停车问 题的一种有效途径。停车诱导系统是智能交通系统( i t s ) 的重要组成部分，是应 用车辆自主定位技术、地理信息系统与数据库技术、计算机技术、多媒体技术和 现代通信技术的综合系统。 本文首先分析了大城市建设停车诱导系统的必要性与可行性，介绍了国内外 当前所使用的停车诱导系统的特点。本文主要研究内容是为停车诱导系统设计最 优路径算法及其仿真，在对基于经典d i j k s t r a 算法的最优路径算法分析的基础 上，着重对最优路径算法搜索区域确定，路段权值确定方法进行了探讨，在此基 础上，提出了停车诱导最优路径算法，并论述了该算法的实现过程。 本文设计了一个实验用途的停车诱导仿真系统，采用地理信息系统的集成二 次开发方式，利用m a p i n f o 公司的m a p x 控件，以可视化开发工具v c + + 为平台， 开发了停车路径诱导仿真系统，并在该系统中部分实现最优路径算法。仿真结果 表明，本文设计的算法在停车诱导系统中是可行和实用的，为解决停车供需矛盾 的问题做出了积极有益探索。 关键词：停车诱导系统，d i j k s t r a 算法，数字地图，组件g i s ，m a p x 长安大学硕士学位论文 a b s t r a c t t h ec o n t r a v e n t i o no fv e h i c l ep a r k i n gb e t w e e ns u p p l ya n dd e m a n db e c o m e sm o r e a n dm o r ec o n s p i c u o u sa n ds e r i o u si ns o m em a j o rc i t i e so fc h i n ad u r i n gt h e s ey e a r s ， w h i l ep a r k i n gg u i d a n c es y s t e m ( p g s ) o f f e r sa l le f f e c t i v es o l u t i o nt os o l v et h i si s s u e t h es y s t e mi sa ni m p o r t a n tc o m p o n e n to fi 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 ) t h es y s t e mi st h e i n t e g r a t e ds y s t e m o fa p p l y i n gv e h i c l ea u t o m a t i cl o c a t i o n t e c h n o l o g y , g i s ( g e o g r a p h i ci n f o r m a t i o ns y s t e m ) ，d a t a b a s et e c h n o l o g y , c o m p u t e r t e c h n o l o g y , m u l t i m e d i at e c h n o l o g ya n dc o n t e m p o r a r yc o m m u n i c a t i o n st e c h n o l o g y i nt h i sp a p e r ，t h en e c e s s i t ya n df e a s i b i l i t yt ob u i l dt h ep a r k i n gg u i d a n c es y s t e m a r ep o i n t e do u tf i r s t t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ep r e s e n tp a r k i n g g u i d a n c es y s t e ma th o m ea n da b r o a da l ea l s oi n t r o d u c e d t h em a i ns u b j e c ti nt h i s a r t i c l ei st od e s i g na n dr e a l i z ea no p t i m a lp a t ha l g o r i t h mi nap a r k i n gg u i d a n c e s y s t e m ( p g s ) o nt h eb a s i co fs t u d y i n gc l a s s i c a ld i j k s t r aa l g o r i t h m ，t h e a l g o r i t h mi si m p r o v e di nd e t e r m i n i n gr o a dw e i g h ta n ds e a r c h i n ga r e a ，t h e n t h eo p t i m a lp a t ha l g o r i t h ma d o p t e db yap g si so b t a i n e d t h ea r t i c l ea l s ot e l l sh o wt od e s i g na n dm a k eas i m u l a t e ds y s t e m i ti n t r o d u c e s t h ed e v e l o p m e n to ft h ew h o l es y s t e mu s i n gv c + + o b j e c t - o r i e n t e dp r o g r a ma s d e s i g n i n gp l a t f o r m ，m a p i n f o m a p xa sd e v e l o p m e n tt 0 0 1 i na d d i t i o n ，i te x p l a i n sh o w t od e s i g nas i m u l a t e dp g sa n dr e a l i z ep a r t l yt h ea l g o r i t h mi nt h ep g s s i m u l a t i o n r e s u l t ss h o wt h a tt h ea l g o r i t h mi sn o to n l yf e a s i b l eb u ta l s op r a c t i c a l a n da9 0 0 dd e v e l o p m e n t f o rs o l v i n gt h ep a r k i n gc o n t r a v e n t i o nb e t w e e ns u p p l ya n dd e m a n di sd o n e k e yw o r d s ：p a r k i n gg u i d a n c es y s t e m ( p g s ) ，d i j k s t r aa l g o r i t h m ，d i g i t a lm 印， c o m p o n e n tg i s ，m a p x 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行 研究工作所取得的成果。除论文中已经注明引用的内容外，对论文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论 文中不包含任何未加明确注明的其他个人或集体已经公开发表的成 果。 本声明的法律责任由本人承担。 论文作者签名： 论文知识产权权属声明 年月 日 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请 专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的 学术论文或成果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名： 导师签名： 年月 日 年月 日 长安大学硕士学位论文 1 1 课题提出背景 第一章绪论 随着我国汽车工业的发展和城市化进程的加快，城市机动车的保有量持续增 长。自上世纪9 0 年代中期，随着国家汽车产业政策的颁布，与小汽车生产、流 通相关的重大举措亦相继出台，“小汽车进入家庭 被确定为国家扶持汽车工业 发展的战略安排，国产汽车的生产开始转向小汽车，小汽车的销售价格大幅度下 降。小汽车拥有量逐年增加，且增长速度越来越快，平均增长率达到1 6 8 。小 汽车产业的迅速发展，使我国大中城市机动化呈现不可遏制的势头。近年来我国 经济发达城市小汽车保有量年增长速度达到3 0 ，尤其是私家车增长速度最快。 城市私人汽车大量出现使城市道路交通量日益增加，全国各大城市特别是特大城 市的停车问题也成为加重道路通行能力的负担和造成交通拥堵的主要原因之一。 交通拥堵现象日益加剧，严重影响了城市的运转效率，在客观上阻碍了社会、经 济的发展。据调查，路面交通量中有1 5 是因为寻找停车场或停车位而形成的无 效交通流瞳1 ，如果合理地理顺这部分交通流，城市交通状况可得到有效改观。但 与此同时，城市的停车设施建设却相对滞后，车辆发展和与之相配套的基础设施 发展不协调的矛盾不断加剧，所以，停车问题在我国大城市已成为难题。因此， 在不可能大规模建设停车设施的情况下，提高停车场( 库) 的管理水平，充分发挥 停车场( 库) 的作用，提高其使用率和周转率，对于我国大城市的长远发展具有积 极深远的意义。 目前，以信息为主导的智能交通系统( i n t e l l i g e n tt r a n s p o r t a t i o n s y s t e m s ，i t s ) 通常被认为是解决城市交通问题的有效途径口1 。作为智能交通系 统核心组成部分的城市交通诱导系统( u r b a nt r a f f i cf l o wg u i d a n c es y s t e m u t f g s ) 与实时交通信息相匹配，能有效地解决城市交通拥挤、减少交通事故、降 低空气污染、提高运输效率口1 。车载信息装置是城市交通流诱导系统中为驾驶员 提供动态交通诱导的使用终端，它应用了现代通信技术、计算机技术、控制技术、 定位技术和g i s 技术等高新技术，能够实现车辆的实时跟踪、定位、路径诱导， 获取丰富的交通信息。因此，该装置是从车辆智能化的角度解决城市交通问题的 第一章绪论 一项重要措施。最优路径搜索理论是车载信息装置的核心理论基础，决定了车载 信息装置在进行动态行车诱导时产生的实际效果。对于最优路径搜索理论的研究 就是要为城市交通流诱导系统的实施建立理论基础，而对最优路径搜索理论实施 技术的研究对城市交通流系统及车载信息装置的应用更具有直接的实际意义口1 。 停车诱导系统( p a r k i n gg u i d a n c es y s t e m ，简称p g s ) 是城市交通诱导系统 的重要组成部分，伴随着城市交通诱导系统的发展而发展，是提高城市停车管理 水平、解决城市停车难问题的有效方法与途径h 1 。它是诸多高新技术( 如计算机 网络技术、信息系统、定位技术、现代无线通信技术等) 的集成，具有多种功能。 利用它可帮助驾驶员迅速找到目的地的最佳停车位置，如果有实时交通信息的支 撑，停车诱导系统就能够更有效地引导寻泊车辆在路网中运行，减少寻泊车辆在 道路上的行驶时间，提高城市全体停车场的利用率、提高停车管理水平、减少寻 找停车场的车辆占路面的比例、减少交通负荷和道路交通事故，并为驾驶员选择 合适的停车场提供决策依据，进而为促进智能运输系统( i t s ) 的进一步发展作 出更大贡献。 停车诱导系统现在欧洲己广泛地使用，在北美地区的应用范围也正不断扩 大。在国内，引进停车诱导的时间不长，但许多城市己经开始着手停车诱导系统 f 的建设。目前，国内纳入计划建设智能交通与停车诱导系统的城市较多，共有十 几个，但大都还处在规划之中，同时，因我国现在尚未制定统一的停车诱导系统 的国家标准，而国内对停车诱导系统方面的研究也起步较晚，因此，对停车诱导 系统的研究愈显迫切和必要，进行智能化的停车诱导系统关键理论与实施方法研 究，具有重大的理论意义和现实意义。 1 2 国外研究发展现状 发达国家的大城市同样也存在停车难的问题，几十年来他们一直采用当时的 先进技术来对停车问题进行管理，取得了明显的经济效益和社会效益。 第一个停车诱导系统于1 9 7 1 年出现在德国的亚深( a a c h e n ) 市强1 ，7 0 年代末 英国也开始采用，其后逐渐在欧洲其他国家( 如法国) 和日本得到应用，到1 9 9 5 年，日本己有4 0 个城市引进了停车诱导系统，美国1 9 9 6 年在圣保罗市商业区建 立了第一个停车诱导系统1 。瑞典的首都s t o c k h o l m 市现有停车诱导系统4 0 0 2 长安大学硕士学位论文 多套，阿联酋迪拜市也引进安装了5 2 个停车诱导显示牌晦1 。 德国科隆市的停车诱导系统是比较成功的一个例子，科隆市自从1 9 8 6 年起 停车诱导系统开始操作实施，一直在进行完善和改进。1 9 9 8 年作为停车诱导系 统的延伸，装置了新型的、具有艺术性的、展示技术的标志牌，而且在贸易展览 中心附近建了一座多功能控制中心，整个系统的运作由市政府交通管理中心管 理。科隆市停车诱导系统覆盖了整个内城中心区，总的区域面积约4 5 平方公里。 在这个系统内包括3 6 个大型停车场和2 个p + r 设施，即停车换乘设施 ( p a r k i n g + r i d e ) ，约1 7 0 0 0 个停车位口1 。科隆市的停车诱导系统是在整个城市 智能交通系统支持下的系统，在每个停车场( 库) 设有电脑计数器，随时感应小汽 车驶进、离开停车场状况，并将停车场剩余的车位数据传输给市政府的交通监控 中心，所有的停车场送来的信息经过交通中心综合处理后，再将这些数据及综合 信息输送到城市街道上每个动态指示牌，所以每个区域以及区域外的停车场使用 情况的信息是实时动态的。在科隆的系统中有1 1 0 个显示动态停车容量的指示牌 和1 7 0 个方向指示牌，在这个信息共享平台上，建立了基础数据库，通过政府的 交通监控管理中心统一管理。 科隆市的交通信息是公开、共享的，通过图文电视、广播、电话、电台都 能获得交通信息，甚至通过互联网访问，得到系统内每个停车场的使用情况。 停车诱导系统在国外也被称为先进的停车信息系统( a d v a n c e dp a r k i n g i n f o r m a t i o ns y s t e m ，简称a p i s ) ，a p i s 在欧洲已广泛地使用，在北美地区的应 用范围也正不断扩大阳1 。 国外停车诱导系统主要由数据采集系统、中央处理系统、信息发布系统、通 信系统以及与之相关联的外部系统构成。目前国外的大多数停车诱导系统，均采 用动态的电子显示引导牌来发布停车诱导信息，通过显示停车场位置、停车场行 车方向和是否有空位等信息，引导驾驶员尽快到达停车场。在停车诱导的理论方 面发达国家已经有了很深入的研究并且已经建立了多种实用的停车诱导系统，停 车诱导系统的评价结果显示：停车诱导系统提高了停车管理水平、削减了路上非 法停车车辆、减少停车场入口处排队等待车辆数并能合理的分散使用停车场口1 。 第一章绪论 1 3 国内研究发展现状 中国引进停车诱导系统的时间不长，但许多城市己经开始着手停车诱导系统 的建设。国内纳入计划建设智能交通与停车诱导系统的城市较多，但大都还处在 规划建设之中，已有十个i t s 示范城市提出了建设智能化的停车诱导系统的规 划。 目前，北京已经开通的停车诱导系统有三个n 引，分别是王府井商业区停车诱 导系统、西单商业区停车诱导系统和新世界商业区停车诱导系统。上海停车诱导 系统示范工程分两期进行n ，一期于2 0 0 2 年1 月2 4 日正式开通，2 0 0 3 年底完 成了二期工程。整个工程共有3 6 处、6 4 块停车诱导发布牌，覆盖了整个黄浦区 中心区域，包括3 9 个对外开放停车库的5 9 0 0 余个车位。广州停车场诱导系统目 前完成了系统一期工程的建设n 羽。该系统由停车信息采集、信息传输、信息处理 以及信息发布等4 部分组成，在功能主体上分为3 部分：即停车场、管理中心和 电子显示屏。通过在停车场安装控制设备、监控设备、检测设备显示设备、计算 机网络和通信设备，配置相应的系统软件和应用软件，实现停车场出入口管理、 收费管理、车位管理、车辆管理、泊位诱导和事务管理自动化。利用g p r s 无线 通信技术把停车信息、车辆信息和统计数据等发送到管理中心。管理中心对信息 进行分类和处理后，将信息通过传输网络发送到l e d 电子显示屏，显示内容包括 街道分布图、街道名称、停车场名称等静态信息和各停车场空闲车位数量等动态 信息。电子显示牌采用反光材料进行印制，解决夜间视觉问题。 目前，停车诱导系统发展和研究方向是停车诱导系统的智能化，智能停车诱 导系统由主控中心、分控中心、智能停车场的计数装置、车载g p s 定位和接收装 置、路边可变信息显示版( v a r i a b l em e s s a g es y s t e m ，v m s ) 和通信网络组成u 羽。 二者之间的主要区别在于智能停车诱导系统实现了系统和驾驶员之间的信息互 动，从而使驾驶员由被动引导变为主动选择。而智能停车场也逐步引进了不停车 收费系统、手机交停车费系统等主动收费系统，智能停车诱导系统的发展必将对 智能交通系统起到巨大的促进作用。 目前，国内许多大城市急于改善停车管理的水平，对停车诱导系统有着广泛 的需求，但是，在停车诱导系统的基本理论和基本技术方法方面还没有做深入的 研究。 4 长安大学硕士学位论文 1 4 研究内容及论文结构 本文主要研究内容是结合实时交通信息和地理信息，为停车诱导系统设计一 个合适的、高效的、实时性较强的最优路径算法，并设计一个实验用途的停车诱 导仿真系统框架，以电子地图为平台，在停车诱导仿真系统内部分实现最优路径 算法。 全文的结构如下： 第一章：绪论。概述了停车诱导最优路径算法的应用背景，然后概述了国内 外停车诱导系统研究发展现状，最后概括了本论文的主要研究内容及论文结构。 第二章：停车诱导最优路径算法研究。在对基于经典d ij k s t r a 算法的最优 路径算法分析的基础上，着重对最优路径算法搜索区域确定，路段权值确定方法 进行了探讨，在此基础上，提出了停车诱导最优路径算法，并对该算法的实现过 程进行了阐述。 第三章：首先介绍了智能交通中的电子地图的特点，包括电子地图的组成要 素、比例尺种类和电子地图的显示，在此基础上介绍了本文开发电子地图的硬件 平台和软件平台，本文采用的主要是m a p i n f o 及其相应组件m a p x ，以可视化开 发工具v c + + 为平台，进行电子地图开发设计。故着重对m a p x 控件技术进行了介 绍，包括其空间数据结构，模型结构和基本对象。在此基础上阐述了本文电子地 图基本功能的实现。 第四章：本文要在停车诱导仿真系统中部分实现停车诱导最优路径选择算 法。故在这一章设计了一个简单的停车诱导系统框架，为后一章仿真系统的设计 奠定基础，着重探讨了停车诱导系统的分类、结构框架、技术构成和路线优化软 件模块构成等内容。 第五章：在上一章内容的基础上，设计了一个简化的停车路径诱导仿真系统， 以电子地图为平台，在仿真系统内部分实现停车最优路径选择算法。内容包括仿 真系统结构设计、系统界面设计、最优路径计算模块的软件实现、通信仿真模块 的软件实现，最后介绍了仿真测试功能效果。 第六章：总结与展望。概括了本文所做的主要工作，提出了有待进一步改进 的问题。 第二章停车诱导最优路径算法研究 2 1 引言 第二章停车诱导最优路径算法研究 最优路径问题，简单的讲也就是基于道路网拓扑结构的最短路径算法问题。 因为具有实际的应用背景，最优路径算法考虑的因素和限制的条件比经典最短路 径算法复杂得多。不管怎样，其核心思想还是源于经典最短路径算法。 最短路径算法问题，实质上就是数学上的最短路问题。最短路问题是个相对 古老的数学问题，国内外很多学者长期以来都对此做出过深入的研究，并有很多 成熟的算法可以利用。但在路网规模大且结构复杂的城市路网中实现最优路径搜 索采用一般通用的最短路算法往往得不到理想的效果，因为一般通用的算法常常 会由于计算时间过长而无法在实时动态交通流诱导方面获得应用。因此，为了满 足动态交通停车诱导的需要，就必须对通用的最短路算法进行必要的改进。本论 文对此进行了比较深入的研究，并提出了一种基于实时动态交通流的停车诱导最 优路径搜索算法。 2 1 1 最优路径搜索问题的一般数学描述 1 ) 路网的抽象 最优路径搜索技术通常采用图论中的“图 来表示路网，两者的概念对应如 下n 钔： 结点( n o d e ，记做n ) ：道路的交叉口或断头路的终点。 边( e d g e ，记做e ) 弧( a r c ，记做a ) ：两结点之间的路段称为边，若规 定了路段的方向，则称为弧。 边( 弧) 的权( w e i g h t ，记做w ) ：是路段某个或某些特征属性的量化表示。 根据不同的最优目标，可以选择不同的路段属性，如路段长度、路段平均行程时 间等作为该路段对应的边( 弧) 的权，或称为道路权重。 在规定了结点、边( 弧) 及其权值之后，便将路网抽象为一个赋权无向图或 赋权有向图。从而确定路网中某两地间的最优路线便转化为图论中的最短路问 6 长安人学硕士学位论文 题。 其中有向图和无向图的区别在于前者虽然增大了路网的存储量，但适用于弧 的两个方向权值大小不同的情况，由于一般来说路段两个方向的交通流情况并不 一致，当采用与交通流有关的路阻函数时，应采用有向图表示路网。另外，有向 图便于处理单行线、路口禁止转向等特殊情况。 一个运输网络可以用一个有向图g = ( v ，e ，w ) 来表示。其中v 为结点集， v = v 。li = l ，2 ，n ) ；e 为边集e = o ( v 。，v j ) l v 。，v j v 。) ，w 为权集，w = w ( v 。， v j ) i v i ，v j e e v j ) 。 就动态路径诱导系统中的最优路径搜索技术而言，抽象路网不仅要明确交叉 口和路段的邻接关系，路段的非空间属性，还应该能够反映交叉口的延误。评价 指标主要表现为广义路阻的确定，评价指标的约束条件包括道路和交叉口的通行 能力等，系统的特殊要求包括驾驶员出行特点、交通控制策略和驾驶员的反应等。 2 ) 道路权重的标定 道路权重的标定决定了最短路径搜索的依据，也就是搜索指标。常用的路权 指标有出行距离、出行时间和出行费用。本文道路权重以出行时间为指标。 根据权重的时变特性，可以把系统分为静态和动态两种，由于交通网络通常 都比较庞大，不可能有足够的采集装置，因此，完全实时的权重数据是不可能得 到的，因此，所谓动态路径诱导系统通常都是准实时的n 钔。 2 1 2 最优路径搜索问题的一般求解过程 由前两节可以看出，最优路径搜索问题总的解决思路是：把问题转化成最优 化问题。应用最优化的解决思路下手。其求解过程大致有以下几步n 5 1 ： 1 ) 路网抽象 2 ) 道路权重的标定 3 ) 应用最短路算法求解图中的最短路径 4 ) 把图中的最短路径还原成现实路网中的路段集 7 第二章停车诱导最优路径算法研究 2 2 基于d i j k s t r a 算法的最优路径算法分析 2 2 1 经典d i j k s t r a 算法 d i j k s t r a 算法是由荷兰数学家e w d i j k s t r a 于1 9 5 9 年提出的一个适 用于所有弧的权均为非负的最短路算法，也是目前公认的求解最短路问题高效的 经典算法之一n 7 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 算法。 值得注意的是d i j k s t r a 算法描述的是算法的实现方法：与网络的存储结构 无关，不同的实现方法决定了不同的时间复杂度。现实世界的空间地物各式各样， 在千变万化的空间数据中不乏有这样一类空间数据类型，他们由点一线构成空间 网络，而且可以用一个坐标系统来标识空间网络中的各点，网络中的线具有长度 的属性。例如生活中的道路网，管线网，河流网等，这类空间网络可以表示为矢 量化的网络模型g ，g 可以用一个有序三元组( v ，e ，f ) 表示，其中v 是网络模型 g 的顶点集合，e 是边集，而f 是函数，f ( e ) 表示边e ( e e ) 的长度，也就 是g 中边e 对应的顶点对( u ，v ) 之间的距离，因此f 也可以表示为f ( u ，v ) n 引。 下面介绍一下d ij k s t r a 算法的基本原理n 引： 首先，引进一个辅助量d ( u ，v ) ，它的每个分量d ( u ，v ) 表示当前所找到的从起 始点u 到终点v 的最短路径的长度。在算法过程中d ( u ，v ) 的值是在不断逼近 最终结果，但在过程中不一定就等于最短路径的长度。它的初始状态为：若从u 到有弧，则d 0 ，v ，) 为弧上的权值；否则置d ( u ，1 ，) 为。显然，长度为 d 0 ，y ，) = m i n d ( u ，u ) h v 的路径就是从v 出发的长度最短的一条最短路径。 此路径为k ，) 。 那么，下一条长度次短的路径是那一条呢? 假设该次短路径的终点是，。，则 长安大学硕士学位论文 可想而知，这条路径或者是o ，1 ，。) 或者是【v ，y j ：v k ) 。它的长度或者是从v 至；j v k 的 弧上的权值，或者是d 0 ，) 和从匕到叱的弧上的权值之和。 一般情况下，假设s 为已求得最短路径的终点的集合，则可证明：下一条最 短路径( 设其终点为x ) 或者是弧p ，x ) ，或者是中间只经过s 集合中的顶点而最 后到达顶点x 的路径。因此，下一条长度次短的最短路径的长度必是研尼】( 1 ，。s ) 和弧“，v ，) 上的权值之和。 d ij k s t r a 算法过程的具体描述如下： ( 1 ) 如果0 ，v ，) 之间没有直接存在连线，则置九“，u 】为0 0 。s 为已找到从u 出发的最短路径的终点的集合，初始状态为空集。那么，从起点u 到图上其余各 项点屹可能达到的最短路径长度的初值为d ( u ，1 ，) = f l u ，】，u 是与起点邻接的 点。 ( 2 ) 选择1 ，使得饥“，v j 】= m i n d u ，h 】iu v - s ) 。 ( 3 ) 修改从顶点u s 出发到集合v s 上任一顶点屹可达的最短路径长度。 如果讲“， ，】+ 厂【_ ，七】 丁时，表示车辆需要一个以上时段( 设为n ) 才能通过该路段，则 根据运动学原理，下式成立： ( 寺a t ) l 繁忙状态 对于繁忙状态的公路，各种车辆在该类型路段上的行程时间跟时段有着很紧 密关联( 如很多城市一到上下班时间就容易堵车) ，所以对这种状态下的路段可 以考虑2 3 2 节提过的算法计算权值。 空闲状态 处于这种状态的路段行程时间主要考虑公路的自身的状况如路宽、路面质量 等，同时也要考虑车的性能，不同的车辆在公路上的行程时间是不同的。 针对这三种不同状态，权值的确定也采用不同的方法。对于堵塞的路段可以 简单的设置为0 0 ；对于处于繁忙状态的路段，可以直接使用第2 2 2 节的算法来 设定权值。 对于处于空闲状态的路段权值的计算方法，由于该状态的路段不随时间动态 变化，其行程时问主要依赖交通工具的性能和道路的状况。要计算通过每个路段 的时间权值，必须知道用户行驶速度，或者至少要能够预估到行驶速度。根据地 理信息系统中的交通信息数据库提供的各种道路属性和车辆的类型可以粗略的 估算出车辆行驶速度，本文对此不作深入研究。 2 3 2 交叉口延误带来的节点权值 通常的路线优化算法将节点看作抽象的点，节点是没有权值的。然而，在实 际的路网中，车辆在通过作为节点的交叉口时不可避免地要产生时间延误。停车 诱导最优路径算法主要应用于城市道路网，而城市路网交叉口比较多，因此在计 算路段权值时必须考虑车辆通过节点的时间延误。用数学的手段描述，就是路网 中的节点和弧段都具有权值。同时，交叉口的延误还和车辆的行驶方向有关，即 车辆的直行、左转和右转在交叉口处产生的延误往往是不同的，这就给停车诱导 最优路径算法的实施带来了定的难题。 本文对于交叉口时间延误的分析，主要用于停车诱导系统中的节点权值的计 1 5 第二二章停车诱导最优路径算法研究 算，为路线优化系统提供依据。因为每一个城市的交叉口情况千差万别，很难用 一个固定的模型完全描述。因此，本文提供的模型只能为实际采用时选择参考。 2 3 2 1 函数形式的讨论 在交叉口延误函数的统计分析中，发现在国内的混合交通模式下，很难找到 交通延误和道路条件以及交通条件的具有物理意义的相关模型，目前只能应用数 学的手段提供描述交叉口延误变化规律的数学模型。指数形式的模型、修正的延 误函数模型都符合这一要求，因此，本文根据不同的考量，对多种可能的函数形 式进行了分析，并分别标定了参数。以供将来的使用者根据该地区的实际情况进 行检验并取舍。 2 3 2 2 函数形式及参数的标定2 1 3 函数形式1 ： f 垒兰1 z ：竺：三墨：鱼二墨! ：三二生! 墨! ：! 竺! ， 6 0 式中：l ：机动车交叉口延误( m i n ) 矿：机动车流量( 辆h ) c ：进口道的通行能力( 用前述进口道通行能力计算公式计算) 疋：调整系数，采用绿信比名 五：进口道的绿信比 丁：进口道的信号灯周期 标定系数k ，、k ：如表2 2 所示： 表2 2 函数1 参数表 系数平面十字交叉口平面错位交叉口 k 10 51o 51 k 23 8 2 3 2 85 6 54 8 5 函数形式2 ： 驴掣 式中：乃：机动车交叉口延误( m i n ) 1 6 长安人学硕上学位论文 y ：机动车流量( 辆h ) c ：进口道的通行能力( 用前述进口道通行能力计算公式计算) k ，：调整系数，采用绿信比力 兄：进口道的绿信比 r ：进口道的信号灯周期 标定系数k 。、k ：如表2 3 所示： 表2 3 函数2 参数表 系数平面十字交叉口平面错位交叉口 k 1o 510 51 k 2 3 9 53 45 8 95 0 9 、耻堕墨：幽玉! 堕 7 6 0 式中：乃：机动车交叉口延误( m i n ) 矿：机动车流量( 辆h ) c ：进口道的通行能力( 用前述进口道通行能力计算公式计算) k ，：标定系数，平面十字交叉口采用1 4 6 ，平面错位交叉口采用1 8 9 k ，：调整系数，采用绿信比力 a ：进口道的绿信比 r ：进口道的信号灯周期 标定无信号灯控制平面交叉口延误函数如下： d ( f ，) ( 无控) = k d ( i ，) ( 信号) 式中：d ( i ，) ( 无控) ：无信号灯控制平面交叉口延误 d ( f ，) ( 信号) ：和该无信号灯控制平面交叉口的物理条件及交通条件对应的 信号灯控制平面交叉口的延误( 用前述信号灯控制平面交叉口延误函数公式计 算) k ：换算系数，采用1 9 6 1 7 第二章停车诱导最优路径算法研究 2 3 2 3 关于左转、右转和直行延误 在停车诱导系统中，节点的权重，即交叉口的延误时间还和车辆到达该节点 的转向操作有关。即左转、右转和直行延误各不相同。然而，转向延误之间的关 系是非常复杂的。它和交叉口的相位数以及信号灯的配时、和转向车辆的比例有 关、和有无右转专用车道有关、还和转向操作所处的时间段以及非机动干扰的影 响大小有关。因此，很难用统一的模型描述为数众多的交叉口的转向延误。 在停车诱导系统中，我们关心的并不是精确的车辆运行状态，事实上，对于 并没有明确物理意义的转向延误，我们也不可能精确地用模型来描述，车辆的节 点延误只要符合在路径比选中找出最优路径的需要即可。因此，本文主张，通过 对所研究城市的典型交叉口，或者主要交叉口转向延误的调查，统计分析出各种 转向延误在交叉口的平均延误中所占的比例，并以此作为该交叉口转向延误系 数，最终提供给路线优化系统作为计算节点延误的依据。如以下所示乜： 。， 左转延误均值 人左一菱页币两蓊夏 矿一右转延误均值 a 右一菱页币两藤 矿一直行延误均值 人直一菱页i 两瓣 通过对一些典型路口转向延误的分析，得出上述参数的推荐值为： k 左= 1 0 1 8 ，k 右= o 9 0 6 ，k 直- - 0 9 3 5 。该参数尚需在特定的城市路网中的交叉 口进行检测和标定。 综上两节内容，得到每个路段的行程时间计算的整个流程如图2 3 所示。 1 8 长安大学硕士学位论文 图2 3 权值计算流程图 2 4 停车诱导最优路径算法设计 值 不 为 n u l l 通过对上述几个算法的仔细分析，并结合停车路径诱导系统的特点，本论文 把停车诱导最优路径算法分为三个部分：计算各个路段及节点的权值；确定路径 搜索的范围；使用d i j k s t r a 改进算法完成最优路径的搜索。 确定路径搜索范围是为了使最优路径算法能够适应各种类型道路网，路段数 量巨大的时候，保证最优路径算法的效率，提高算法的实时性和可靠性。 不难发现，设计一个功能强大的停车诱导最优路径算法，如何确定各路段及 节点的权值是整个算法的重点。其实算法的动态性就是通过权值的动态性来显示 的，所以如何设计一个可靠、正确的确定权值是非常重要也是相当困难的，本文 在前一节已经对停车诱导系统最优路径算法路段权值的确定作了比较详细的分 析，这里不再赘述。而搜索区域范围的确定对于提高d ij k s t r a 算法的效率起着十 1 9 第二章停车诱导最优路径算法研究 分关键的作用。 2 4 1 搜索范围的确定 矩形框区域搜索算法在很多情况下是一个效率比较高的算法，矩形框区域搜 索算法是建立在一般道路网的基础上，对动态路径诱导进行研究，当算法应用于 停车路径诱导时需作些特殊说明。 比例因子f 的确定，直接影响着搜索区域的大小。文献 1 6 中对北京市区域 市道路网采样并经过统计计算得到的f = 1 3 7 9 。不过根据作者实际观察地理信息 系统数字地图的道路网的拓扑结构发现搜索区域比较小的时候，f 的不确定度比 较大，f 甚至有时候大于2 才能够找到最优路线，当搜索区域比较大时，虽然实 际的f 值可能大于1 1 ，但是，把f 设为1 1 ，算法依然在绝大多数情况下找到最 优路径。分析原因，主要是城市道路一般都是直线，或近似于直线，而一些山区 城市道路路弯曲的程度比较大( 尤其是像重庆等山区比较多的城市) 。根据这一 性质，如果仍旧使用固定的f ，显然是不准确的。这里根据d 的大小分为几个区 间，在每个区间的f 的大小都不同，不过，f 的大小随着搜索区域的增加而递减。 当然随着f 的确定，一般情况下，都能搜索到一条路径，但是，也不能排除 在极个别道路的结构比较特别的时候，也有可能在所定的区域里不能找到一条连 通停车场的路线，这时候就需要自动拓宽搜索区域。 基于矩形限制搜索区域的类c 代码如下： s h o r t e s t p a t h o p t j x x z q y ( m g r a p hg ， i n tv o ，i n tu o ， j n t 木d ， i n t 宰a ) d v o = o ；f i n a l v o = t r u e ： m a k e h e a p ( a ) ： f o r ( i = o ；i v 。；a d j n u m ；i + + ) 将v o 邻接节点对应权值插入堆中 h e a p i n s e r t ( a ，d v o a d j i ) ；： e l l i p s e p a r a m e t e r ( ) ；由u o 。，u o , ，v o i v 竹，计算a ，b ，a ，b ，0 ，构造椭圆 方程 r e c t a n g l e p a r a m e t e r0 ：计算x m i n ， ( m a x ，y m i n ，y m a x ，构造限制矩形 f o r ( i = l ；i x m i n v x y m i n v y y m a x ) ) c o n t i n u e ：g , j 断节点是否落在限制矩形内 i f ( v = = u o ) b r e a k ；n 达终点后退出 f i n a l v = t r u e ； f o r ( f o ：w v a d j n u m ；w + + ) e d g e = ( n o d e i n f o v f i r s t w ) i n d e x w a y ：寻找v ，w 对应路段 i f ( v = w a y i n f o e d g e f n o d e ) 决定路段方向阻抗 c v v a d j w = w a y i n f o e d g e f t i n p ： e l s e c v v a d j w = w a y i n f o e d g e t f i n p ： t u r n i n p = o ： f o r ( j = 0 ：j n o d e t u r n v n u m t u r n ：j +