（交通信息工程及控制专业论文）动态交通条件下车辆导航系统的最优路径规划方法研究.pdf

摘要 智能运输系统是改善城市道路交通的有效手段。车载路径导航是i t s 中重 要的部分。利用计算机和通信等技术，车载路径导航系统向驾驶员提供基于实 时交通信息的最佳行驶路线，实现车辆快速通行的目的。国内外现有路径规划 大多是基于静态、简单约束交通条件下的，利用数字地图数据库等信息为车辆 提供定位信息、地理信息等静态信息；部分研究基于实时交通信息，但没有综 合考虑道路实际状况，对于交叉口的处理也比较模糊，不能准确反映真实的交 通状况。 本文着重分析了路段行程时间的构成，把行程时间分为路段自由行驶时间 和交叉口延误时间。基于道路状况、非机动车和交叉口的影响，给出了路段自 由行驶时间的预测函数；基于集散波的排队理论给出了交叉口的延误模型。比 较了几种经典的最优路径规划算法，选取迪杰斯特算法作为本论文最优路径模 型的求解算法，并限定了动态限制区域的搜索空间。建立路网模型，提出了基 于结点的单车辆动态路径规划模型和基于周期的单车辆动态路径规划模型，分 别对两种模型的目标函数、算法和实验仿真进行了研究。 关键词：车辆导航；动态路径；路网 a b s t r a c t i n t e l li g e n tt r a n s p o r t a t i o ns y s t e mi sa l le f f e c t i v ew a y t oi m p r o v eu r b a nr o a d t r a f f i c t h en a v i g a t i o ns y s t e mf o rr o a da s s e m b l i n gi nv e h i c l e si s a l li m p o r t a n tp a r t i ni t s u t i l i z i n gt h et e c h n i q u e so fi ta n dc o r r e s p o n d e n c e t h en a v i g a t i o ns y s t e m c o u l dp r o v i d et h eb e s tr o u t eb a s e do i lr e a l t i m et r a f f i ci n f o r m a t i o nf o rt h ed r i v e r ， t h u st h ev e h i c l em o v i n gq u i c k l yc a nb et oa c h i e v e a tp r e s e n ti nd o m e s t i ca n d f o r e i g n ，m o s to ft h ep a t hp l a n n i n gp r o v i d e s t a t i ci n f o r m a t i o nf o rt h ev e h i c l e s ，s u c h a sp o s i t i o n i n gi n f o r m a t i o na n dg e o g r a p h i c a li n f o r m a t i o n ，u n d e rs t a t i c a n ds i m p l e t r a f n cc o n d i t i o n sw i t hd i g i t a lm a pd a t a b a s e ；t h eo t h e rs t u d i e sa r eb a s e do n t h e r e a l t i m et r a f f i ci n f o r m a t i o n ，b u t d o e s n t c o m p l e t e l y c o n s i d e rt h e a c t u a l c i r c u m s t a n c eo ft h er o a d s ，a n dh a v eav a g u ed e a lw i t ht h ei n t e r s c t i o n s ，a n dc a n t a c c u r a t e l yr e f l e c tt h er e a lt r a f f i c t h i sp a p e ra n a l y z e st h ec o m p o s i t i o no fl i n kt r a v e lt i m e ，t h el i n kt r a v e l t i m e i sd i v i d e di n t os e c t i o n so ft h ef r e et r a v e lt i m ea n dd e l a yt i m ei ni n t e r s e c t i o n a n di n t h i sp a p e rt h ep r e d i c a t i o nf u n c t i o nf o rt h ef r e et r a v e lt i m ei sp r o v i d e du n d e rt h e i n f l u e n c eo ft h er o a dc o n d i t i o n s ，n o n m o t o rv e h i c l ea n di n t e r s e c t i o n s ；a n dt h ed e l a y m o d e lf o ri n t e r s e c t i o ni sp r o v i d e db a s e do nt h eq u e u e i n gt h e o r yo ft h ed i s t r i b u t i n g w a v e t h ep a p e rc o m p a r e ss e v e r a lc l a s s i c a la l g o r i t h mo no p t i m a lp a t hp l a n n i n g ，a n d s e l e c td i j k s t r aa st h eo p t i m a lp a t ha l g o r i t h mo ft h em o d e li nt h i sp a p e r ，w i t ht h e l i m i t e ds e a r c hs p a c eu n d e rt h eh a b i to ft h ed r i v e r sa c t u a lr o u t ec h o i c e t h er o a d n e t w o r km o d e li ss t a b l i s h e da n dr a i s et w om o d e l s ，t h eo p t i m a lp a t hp l a n n i n go fa s i n g l ev e h i c l ed y n a m i cm o d e lb a s e do nn o d ea n d b a s e do i lc y c l e ，a n dt h ep a p e ra l s o r e s e a r c h e so nt h eo b j e c t i v ef u n c t i o n 、a l g o r i t h ma n ds i m u l a t i o na b o u tt h et w o m o d e l s k e yw o r d s ：v e h i c l e sn a v i g a t i o n ：d y n a m i cp a t h ；r o a d n e t w o r k 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：暖吩 日期：谚f 。年f 月岁。日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密呀。 ( 请在以上相应方框内打“4 ”) 、，霄 作者签名：鬏拾 日期：、扣年f 月3 d 日 、 新虢撕 吼 2 了f i ) 年岁月岁秒日 第一章绪论 路径规划历来都是智能交通系通中的一个研究重点，本论在依据国内外的 研究现状的基础上在这方面做了一些粗浅的工作，本章主要介绍车辆导航系统 研究的背景、研究的目的和意义、本论文的主要研究工作和章节的安排。 1 1 研究背景 由于汽车的增长速度超过了道路建设能力，交通拥挤、安全事故等问题在 全世界范围内变得越来越显著。根据国外的研究表明，由于城市的交通拥挤问 题，美国每年至少要造成4 7 5 亿美元的损失，并伴随着2 7 亿工作小时和1 4 3 5 亿升的燃料的浪费，并且这种损失速率每年以一定的比例持续增长。根据有关 部门的预测结果显示，到2 0 2 0 年，美国每天发生的交通事故将达到3 w 起，至 少有1 8 5 起的交通事故属于重大交通事故，将会造成1 5 0 0 亿美元的直接经济损 失。在日本，交通状况也令人堪忧，堵塞最严重的路段为东京高速公路，其拥 挤排队的时间有时长达1 7 小时，9 3 7 公里的路程，日本东京由于交通拥挤每 年造成了1 2 3 0 0 0 亿元的损失。法国、德国、英国、中国等也是如此。 目前，交通主管部门越来越倚重高新科学技术来确保交通畅通、提高行车 安全、缓解交通拥堵和废气污染对生态环境所产生的负面影响。现代交通行业 中，由于高新科学技术的广泛应用，包括计算机、通信、电子等等，使得高新 技术的交通管制得到飞速发展，交通状况得到很大的改善。大约经过了2 0 多年 的发展历程，新型的交通系统在全世界的范围内相继开始建立起来，称之为智 能交通系统儿2 1 ，实验系统和实际应用系统得到了有效的验证，在全世界范围 内被广泛的应用起来。 车辆导航系统是i t s 技术中所涉及到的一个主要的应用子系统，而路径规 划又是车辆导航系统的核心部件，因为行车成本的高低直接取决于路径规划的 效率。所以，本论文对路径规划进行了一些研究工作，主要是对通对于行程时 间的计算、动态算法的构造、路网模型的建立来对路径规划进行改进。 1 2 车辆导航系统国内外研究现状 1 2 1 国外研究现状 i t s 最早在美国、日本、欧洲等国家和地区发展研究。美国i t s 的前身是 智能车辆道路系统( i n t e l li g e n tv e h ic le h ig h w a ys y s t e miv h s ) ，最初由单 个州、单个城市研究i v h s ，1 9 9 0 年成立了工业界和学术界以及政府官员组成的 i v h sa m e r ic a 协会。1 9 9 4 年i v h s 正式更名为i t s ，面向2l 世纪的“公路交通 智能化 为其主要的战略实施方向，其主要目的是从根本上减轻和解决交通中 的各类部题。 日本的车国导航系统处于世界的先进水平。1 9 7 3 年提出了 v i c s ( c o m p r e h e n s i v ea u t o m o b i l et r a f f i cc o n t r o ls y s t e m ) 的项目，其主要内容 是进行基于射频通信的车辆路径诱导系统的综合实验，并且其结果可以减少行 程时间13 左右。1 9 9 0 年开始，世界上第一个以交通信息服务的项目在日本建 立起来。目前，先进的v i c s 车载端信息接收机主要结合了f m 调频载波接收功 能和差分g p s ，可以提供免费的信息服务和车辆导航系统的路径规划。日本东 京的a t i s 先进的交通信息服务与之类似，不是的是所提供信息服务是有偿的。 1 9 9 3 年7 月日本东京政府和私人企业组建a t i s 公司来提供优质服务的实时交 通信息。1 9 9 4 年2 月a t i s 公司利用双向通信技术正式开始投入使用a t i s 系统。 此系统主要是由a t i s 中心和终端两部分。a t i s 每隔一定时间从各种信息源获 得相应交通状态信息，经重新处理后将其传给a t i s 终端，路网的交通拥挤程度 以及所推荐最优路径以电子屏的形式进行显示。 美国典型的路径诱导系统项目主要有两个，旅行技术t r a v t e k 和先进的驾 驶员咨询与车辆导航概念a d v a n c e 。t r a v t e k 是一种路线引导系统，是由美国交 通部、商务部、旅游部、汽车制造商共同投资研发的，此路径诱导系统的开发 历时两年。于1 9 9 2 年该系统在奥多兰市首次得到推广使用。t r a v t e k 不仅能向 用户提供当前位置实时交通状况信息和丰富的交通服务信息，并且能有效的指 导驾驶员安全快速地通过拥挤路段。t r a v t e k 系统由三大部分组成： 1 ) 服务中心t i s c 和t r a v t e k 信息主要是由美国汽车委员会负责建立和管理； 2 ) 交通管理中心t m c 主要是由政府部门负责建立和管理； 3 ) 配备有计算机和通讯设施的车辆，其中包括车载系统的硬件、软件和基础通 讯设备。这些均由美国通用汽车公司所提供。 这三部分利用8 0 0 m h z 的调频广播、电话线路、自动蜂窝电话等多种方式的通讯 服备相互紧密联系 红外信标通信是欧洲对路径导航系统的研究的基础。英国和德国分别在8 0 年代末期开发出了用于示范的a u t u og u id e 系统和l i s b 系统。在此之后，世界 上第一个商用车载路径导航系统t r a f f i cm a s t e r 由英国率先提出。九十年代 德国西门子公司开发了a l i s c o u t 系统，该系统是基于l i s b 的，在国际上具有 一定的影响力。 同时国外对智能车辆导航系统的研究也逐步深化、细化、实时动态车辆导 航已经成为研究的主流。作为智能车辆导航系统重要内容之一的路径规划问题， 2 国内外学者对其最优化方法及实用性进行了大量的研究工作，其中y i h w a 等人 对城市交通动态网络阻塞模型、网络问题以及车辆的运动方向和交叉口的信号 的影响进行了深入的研究，建立模型并讨论了基于动态交通流预测的行程时间 和最小成本路径问题，对意外网络阻塞的影响做出评估。t 。n l a m 将历史的和 当前的交通模型引入到车辆导航系统中。此外最佳路径的算法也大量的涌现， 从经典的d ij k s t r a 算法等发展到启发式搜索、分层搜索等等。 1 2 2 国内研究现状 我国对于车辆导航系统的研究与国外相比要晚得多，目前主要是处于对定 位系统、通信系统电子地图等问题的研究阶段，投入使用的导航手段基本上都 是以无线广播为。可变标志牌的导航系统和基于g p s 集群通信目前正处于研究 和实验阶段，而全面的车载导航系统的研究更处于起步阶段。 1 9 9 5 年6 月，多段式接力式动态标志路线诱导系统开发完成，此诱导系统 由同济大学和上海交警总队共同研制完成，主要是通过广播电台和交通广播电 台实现交通流的诱导n 1 ，是交通诱导研究在国内的初步应用。由于可变标牌路 只能显示单一路段的交通状况信息，所以此系统只适应于结构单一的高速公路 网，在相对比较复杂的城市路网中由于诱导路径过短而产生为信息不准确的现 象。在可变标牌可以显示多条路段的交通信息，一般选择在相邻交叉口前连续 设置。通过各个连续的交叉口好像接力棒一样传递多条路段动态实时交通信息， 在广域的范围内把车辆诱导到拥挤较小的路段上，直到目的地。多段接力式动 态标志路线引导系统主要由交通信息采集系统、交通信息评价处理单元、数据 传输系统、中央计算机处理系统和可变标牌、交通信息广播及其控制单元等五 个部分组成。 哈尔滨理工大学基于gps 和蜂窝通信原理设计的实验性指挥调度系统， 方泛运用于交通、电力、消防等，作为其分组调度的系统依据。由交通部科学 研究院，北京大学，智能交通研究所共同研制了基于调频广播副载波传送差分 g p s 信号的车辆智能定位导航系统，供车载端接受并修正自身位置， 但是该系 统只能提供静态地理信息和车辆定位信息。大连理工大学杨振忠等设计开发了 大连市道路交通信息管理系统，包含相互独立的g i s 数据库模块，最短路径模 块和w e b g i s 模块并利用g i s 技术系统地管理、查询和检索道路交通数据，可视 化了多种道路交通数据的存储、查询、显示、输出和修改过程。 车辆智能定位导航系统是交通诱导系统的核心组成部分，1 9 9 8 年一款简易 定位导航系统由易可达公司提出，作为国最早的车辆导航系统，一共发行了3 0 0 套。此后，京惠达公司基于笔记本p c 机开发过一款导航仪，但未形成批量生产。 近些年，北京瑞图万方，四维图新公司，新科电子，菱科电子，南大善邻，深 圳摩森等多家导航仪公司都通过与国内外多种合作或引进或独立研制，开展了 大量的工作，取得了一定的成果，并实现了批量生产。从2 0 0 5 年开始，国内 车载导航市场进入全面启动时期。深圳易凯数码有限公司在多家科研机构会同 国家g p s 工程技术研究中心导航工程部协助开发并推出了s c a r 汽车卫星导航系 统h 1 ，可通过模糊查找电话、地址、门牌号等输入目的地，系统会自动生成最 佳路径，并配以清晰的语音提示，并能适时的查找车子附近的7 类单位：加油 站、停车场、医院、药店、修理厂、公安部门及宾馆等。 国内车辆导航系统的研究工作主要是围绕着城市交通流诱导系统展开的。 吉林大学在城市交通流诱导系统方面作了大量的工作，其中主要包括数据处理 算法的理论和模型哺1 和交通信息的处理，北京工业大学成立的智能交通研究中 心在车辆自主定位、动态监控与车辆导航系统关键技术方面开展了多项研究 1 。主要重点包括：城市交通网络拓扑关系的建立，d r 和g p s 组合定位数据融 合，最优路径算法，道路权重赋值，通过g s m 进行数据通信挖掘等方面的研究， 为后续车辆导航系统的研究提供了良好的基础。 我国的第一个动态路径诱导系统研究项目是由吉林大学负责研发的城市交 通流诱导系统u t f g s ( u r b a nt r a f f i cf 1 0 wg u i d a n c es y s t e m ) ，u t f g s 结合 我国混合交通流的现实交通状况，以城市交通面控系统资源为基础，是一种基 于实时动态交通状态的出行者信息和分布式动态路径诱导系统。目前u t f g s 己 提出了研究的分布式系统框架，但整个系统的完善和投入使用还需要长时间技 术研究和实验的较正。 1 3 研究目的和意义 智能交通系统建设的好坏直接影响到人民生活水平的高低和社会经济效益 提高，车辆导航系统中的路径规划可以提供出最优的行驶路线，为人们的出行 进行动态导航，更有利于人们的快速出行。为了进一步提高路径规划的效率， 国内外很多专家学者对于路径规划方法进行了大量的研究工作，在理论和实践 上对智能交通系统的建设做出了贡献。 不同的人在选择最佳出行路线时所依据的参照各不相同，或者是时间最少， 或者是距离最短，或者是行车条件好，或者基于某种特殊的偏好等等，路径规 划系统必需能够依据不同的选择条件规划出最优的行驶路线，这就要求在系统 内部对各种情况都做出了的对比分析，设定某个参数条件通过外部接口与用户 联系在一起，一般以触控界面的方式。 4 1 4 论文的主要研究工作 1 对交通路网中的道路阻抗进行研究，把路段与交叉口延误作为考虑对象， 使行程时间更贴近于现实。 2 对最优路径搜索算法进行研究，结合本论文的动态路网模型对算法进行 优化。 3 提出动态路网模型，并提出两种不同的单车辆动态路径规划模型，并以 实验的方法进行论证。 1 5 论文的章节安排 论文共分为六章，各章内容安排如下： 第一章介绍了论文的课题背景、研究的目的和意义、论文的主要工作和章 节安排，作为整个论文工作的大致介绍。 第二章介绍了与路径规划有关的智能交通系统、车辆导航系统，重点阐述 智能交通系统、车辆导航系统和路径规划三者的关系，强调了路径规划的重要 性；最后介绍了路径规划的效率、合理性和最优性。 第三章介绍关于行程时间的研究，通过分析选取行程时间为路网的阻抗， 把路网的行程时间分解为非拥挤部分的路段行程时间和交叉口处的排队延误时 间，并分别建立模型对于两部分时间进行计算，对于路段非拥挤部分的行程时 间把非机动车的负荷，车道数，车道宽度等客观原因考虑进去，使得规划出来 的最优路径更贴近于实际交通路网状况。 第四章介绍了最优路径的搜索算法，包括经典的最短路径搜索算法，动态 最优路径搜索算法，以及本论文所用到的d i j k s t r a 算法的优化方法。 第五章介绍了一般的动态路网模型的建立方法，并提出了两种不同的单车 辆动态路径规划模型，并针对两种模型提出了相应的算法分析与评价、实验仿 真对比。 第六章是对全文的工作总结和展望。 第二章路径规划相关理论 路径规划是路径诱导的前提，即在实施诱导前为车辆规划出一条最佳的行 驶路线，而路径规划也是车辆导航系统和广义上的智能交通系统的一个核心模 块，因此，本章有必要对于二者做一个详细的介绍，然后详细阐述有关路径规 划的内容。 2 1 智能交通系统 智能交通系统( 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 ，简称i t s ) ，是近 年来提出的新概念，其涵义是综合运用先进的信息通讯、网络、自动控制、交 通工程等技术，改善交通系统的运行情况，提高运输效率和安全性，减少交通 事故，降低环境污染，从而建立起一个智能化的、安全、便捷、高效、舒适、 环保的综合运输体系。 国内外调查表明，目前造成巨大经济损失的主要原因之一是交通拥挤和交 通事故，为了增强本国的社会生产力和减少环境污染，因此在国际上对智能交 通进行主要研究以减少交通拥挤和交通事故显得非常必要。国外发达国家投入 了大量的人力物力对智能交通进行了重点研究，目前，智能交通的研究内容主 要包括：交通控制与交通管理、车辆安全与控制、交通模型的开发、交通行政 组织及信息技术等等。车辆自主导航和定位技术是目前全世界研究成功并顺利 投入使用最多的技术之一，主要有四种：车队管理系统顾问系统便携式 系统库存系统。例如，在欧美发达国家，车主都在豪华轿车上安装了g p s ( 全 球定位系统) 车辆自动导航系统，在日本，安装自主定位和导航系统的车辆超 过5 0 万辆。美国的目标是在2 0 1 0 年为止，配备有车辆导航系统的车辆达到1 1o o 万辆”。 我国上海、北京、南京、广州等发达城市已经开始进行先进的交通管理系 统( a t m s ) 的管理和实践。吉林大学智能交通研究所的g p s 车辆导航系统和车 辆管理系统的研究成果己经应用到社会生产中，产生了良好的社会效益和经济 效益，天津博思高新技术公司也开发出了车载电视和船载电视自引导系统。北 京、上海、天津己经建立了基于无线通信电子数据广播系统( r d s ) ，g p s 的差 分信号可随r d s 信号一并播出。广京贺村立交路段设置了电子通信装置，有利 于该路段附近的车辆预先知道相关交通状况，节省出行时间，从而实现内环立 交的快速运行。我国沿海发达城市，如广州，上海，天津己经建立起交通指挥 中心、先进的交通信号控制系统和车辆监控系统阳1 。可见，我国对于智能交通 6 的研究和应用发展相当迅速。 2 2 车辆导航系统 作为智能交通系统研究领域的核心内容的车辆导航系统，是i t s 实施中的 一个重要模块，主要面向驾驶员群体的交通用户，智能交通系统主要优势在于 信息的集成服务，包括交通路况信息、道路环境信息、驾驶员出行选择信息、 动态路径规划、基础服务设施的数据资料等，上述信息的融合与数据处理是一 个复杂的工程，可以由中心服务器端完成，也可以由车载客户端直接完成或是 提供支持阳1 。一般要求车辆导航系统软硬件条件比较高，必须集成应用了g p s 定位技术、g i s 信息技术、多媒体技术、数据库技术和现代通信技术等的高科 技综合系统。 按系统的实施功能进行划分，目前的车辆导航系统主要分为两类n0 。：( 1 ) 自主式车辆导航系统：这种方式不需要与中心服务端交换数据信息，但相对而 言成本比较高，计算车辆的位置，交通信息的处理，与最优路径的计算全部在 车载设备中完成，所以必须有相当好的硬件条件。这类车辆导航系统最显著特 点是应用了最新的嵌入式计算机技术和地理信息系统技术，具有可靠性高、体 积小、功耗低的特点，可以适应不同类别车载的要求。( 2 ) 中心决定式导航系 统：这一类导航系统的主要特点是利用强大通信网络技术，把系统中心端和车 载端紧密联系在一起。由于绝大部分的数据资料都储存中心服务端，客户端能 够以请求服务的方式获取各种数据，所以不需要大量的空间来存储数据，也不 需要高效的硬件设备来保证运行速率；路径规划运算在中心服务器中进行；中 心服务器功能强大，集信息采集、信息处理和信息显示等多种功能于一体；并 且可以利用信息点指令处理机制来实现车载终端的各种特殊要求，比如配备成 为车辆防盗器，使车辆具备黑匣子硬件平台功能。 2 3 路径规划系统 路径规划是车辆导航系统的重要组成部分，也是路径诱导先决条件，车辆 导航系统就是在驾驶员在确定了行始的起终点后，预先规划出一条或多条路径 供驾驶员选择使用。路径规划可以分为单源路径规划和多源路径规划。单源路 径规划时是针对单个车辆而言的，在特定的交通网络，在确定好始末位置后规 划出一条行驶路线，属于用户最优化问题；多源路径规划是面向交通路网上的 所有车辆而言的，为所有的车辆规划出最优行驶路线，属于系统优化问题。在 计算机语言中，通常把求解两点间的路径问题称为最短路径问题。国内外学者 对这一问题进行了广泛的研究，提出了放多的算法，这此算法最终可以归纳为 7 上述两种情形。在本论文中，单源路径规划问题是本论文研究的核心。 2 4 智能交通系统、导航系统和路径规划三者的关系 智能交通系统( i t s ) 是多个子系统的复杂综合体，每个子系统都可以完成 独立交通功能，车辆导航系统作为智能交通系统主要应用子模块，而路径规划 是车辆导航系统的核心组件，所以可以用图2 1 来描述这三者的关系。 图2 。1 智能交通系统、导航系统和路径规划三者的关系图 2 5 路径规划的效率 路径规划时，对于不同的用户而言，最优行驶路线的标准是不一样的，这 主要取决于用户的意愿，因为一条最优路径取决于许多因素指标，包括行驶距 离最短、行程时间最短、拥挤程度最低、路况环境最好等等，有的驾驶员宁愿 选择路况最好的，而放弃行程时间最短或者是行驶距离最短的，这些选择标准 在系统设计时必须综合考虑，并且作为系统设计的核心成分，在路径规划时应 能满足驾驶员的需求，在车载端显示屏上有支持用户手动输入的界面。有各种 参数来作选择最优行驶路线的条件，必须加载一个有效的路网电子地图，计算 出来的最优行驶路线便显示在其终端显示屏上。 在车辆导航系统中，城市路网必须储存在微型计算机中，其储存的方式必 须把路网抽象为节点、有序对及其拓扑关系构成的有向权图。其中的节点表示 道路的平面交叉口，两相邻节点表示相邻交叉口间的道路，有序的相邻节点对 则表示车流的方向，一般的道路有两个方向的车流，边的权值在静态路径导航 时一般定义为道路的距离，而在动态路径规划时一般定义为时间费用值，抽象 为带权有向图以后便于在计算机中储存计算，所以，不论采用什么作为费用权 值，求解交通路网中特定两点的最优行驶路线问题总可以归结为求解带权有向 图中特定两点的最优路径问题。 求解带权有向图的最优路径问题，国内外学者提出了许多算法，包括 d i j s t r a 算法、f l o y d 算法、a ：l ：算法等等，而在车辆导航系统中一般不能直接采 用，原因有两个：对于动态交通而言，路径规划必须是实时的，这便要求算 法在特定时间内必须完成，如果超时，诱导产生延误，路径规划便毫无意义可 言；对于自主车辆导航系统，存储资料能力和处理能力比较弱，这主要是受 微处理器的成本制约和车载环境的限制，从成本角度考虑不具备超强的功能， 非现实生活中的路网结构是由成千上万点边组成的，要求的储存能力相当高。 在现有经济条件下制约下，不能更改其硬性条件，中能在软科学方面做文章， 本论文对路径规划的研究任务和目的是改进带权有向图的算法或者构造新的最 优路径算法，提高算法的效率，尽可能在最短时间内得到最优解。当然，如果 单从时效性方面考虑，规划出来的最优路径不一定是最优解，但可能是比较接 近最优解，通常可以被用户所接受，达到最优性与时效性的最佳平衡，这正是 车辆导航系统的目标所在。 本论文所做的工作包括对路动态路段行程时间的确定、最优路径规划算法 的研究、动态路网模型的构建、单车辆动态路径规划模型的提出。 2 6 路径规划的合理性和最优性 通过考虑规划后产生的路径的行车情况来体现路径规划的合理性和最优 性，需要满足一些路径条件包括尽可能短的行车距离，尽可能好的行车环境。 良好的行车环境指较宽的道路、质量较好的质量较好、较少的交通信号灯、较 小的路段车流量等。基于层次空间推理的交通网络行车最优路径算法是1 9 9 9 年被陆锋提出的，在该算法中，交通网络是按照道路的等级划分层次的，接着 行车最优路径规划利用交通网络的层次进行优化，优化后的路径具有合理性高 的特点，并且一般置于高层交通网络上。限制搜索区域的分层路径规划算法被 付梦印等人进一步完善，将搜索的区域限制椭圆区域、以椭圆的焦点为起点和 终点来进行最优路径的搜索，可以适当减小其搜索规模是一个方面；可以把路 网进行分层处理，首先确定大的范围，再慢慢细化，以此来提高路径规划的合 理性和最优性是另一个方面。路径规划的合理性和最优性都在这些理论和实验 的研究中体现了。 尽管对路径规划进行了大量的研究，但是仍然存在不足：路径规划算法 通常只针对一般路网，所以具有通用性，但当路网为规则的拓扑结构，一般的 路径规划算法未必能起到已有的效率，特定的路径规划算法只只适用拓扑结构 比较规则的路网，所以不具有通用性。相对于一般路径规划算法来说，较少的 涉及适用于拓扑结构比较规则的路网的算法。分层的最短路径规划，或是分 层的最优路径规划是路径规划算法最常的分析对象，路网的多比例尺算法很少 被利用，因为建立好路网的多比例尺数据库比较复杂，不过对多比例尺最优路 9 径规划算法进行研究更有实际意义。 2 7 本章小结 路径规划是i t s 研究的重要内容之一，本章主要是从宏观层面对于相关定 义做出理论解释，对路径规划的相关定义进行说明，具体所做的工作如下： ( 1 ) 智能交通系统： ( 2 ) 车辆导航系统： ( 3 ) 路径规划的概念； ( 4 ) 智能交通系统、车辆导航系统、路径规划三者的关系； ( 5 ) 路径规划的效率； ( 6 ) 路径规划的合理性和最优性； 通过本章，不难了解到道路径规划在智能交通领域占有极其重要的位置， 其规划效率的高低与智能交通建设的好坏息息相关，而路径规划本身也是一个 复杂的子系统，具有比较广泛的研究层面，具有良好的应用前景，下面章节对 其路段费用权值进行研究。 l o 第三章路段行程时间研究 路径规划就是最优路径搜索，即以行驶的距离最短、行驶的时间最少、行 驶路线的拥挤程度最低、道路质量最好等为最优目标来计算交通路网上任意两 个节点的最优行驶路线，所以在计算最优路径时应明确是在什么情况下的最优， 即选择道路使用者出发的最优目标，从道路使用者的角度出发，最实用而且最 感兴趣的般是出行时间最少的路线，而一旦确定的以行驶时间最少为目标， 下一步就是要研究如何确定路段行程时间。 3 1 动态交通网络中交通阻抗 3 1 1 状态变量的选取 目前还没有计算道路交通阻抗的统一模型，至于动态交通状态下阻抗的研 究更为少，在往常的研究中，最常用的方法是直接引用美国公路路局提出的b p r 函数n 州模型，在此基础上进行简单的修正，这种模型考虑了路网中交通流量的 影响，使用起来较为简单，被广泛运用到静态交通分配中，取得了较好的结果， 却不能被时变的动态交通网络所运用n 引，主要是交通特征不用能够通过交通 量来完整有效的描述，所以必须通过采用交通密度或交通荷载来衡量状态变量 【1 5 】f 1 6 儿17 】 交通量是指单位时间内通过某个特定地点的小汽车数量，是道路断面特定 时间观测值，其单位是辆h ，例如一般会测量干线路段的出入口交通流量，不 同地点的交通量大小差别很大。 交通荷载是指某一特定时间路段上实际存在的车辆数，而交通密度即为单 位路段上的交通荷载，其单位是辆km ，交通荷载主要是指车辆随着时间变 化，在路段上形成的空间观测量，并引发交通密度与之发生相应的变化，其 方程可以表示为： d r a - ( t ) = “口( f ) - - v a ( f ) ( 3 1 ) ，“、， 、， 一 口z 式中，x o ( t ) 是t 时刻路段上存在的车辆数，u a ( ，) 是t 时刻进入路段的车辆数， v ( t ) 是t 时刻离开此路段的车辆数。 当_ _ d x ( t ) = 0 ，即流入率等于流出率，艺( f ) 为一个常数，这是静态交通分配 口f 的一个条件，也是动态交通分配的一个特例，此时交通流量可以存一条路径的 所有路段上，而对于动态分配情况，查掣0 ，即不能只通过路面一个断点的 d f 流量对交通荷载进行有力的描述，所以静态分配的状态变量是交通量，而动态 分配的状态变量时交通密度c l e c l g 。 密度 撬置密度 图3 1 流量、密度、速度、时间相互关系图 另外，从上图可以看出，速度与行程时间并非关于交通流量的凸函数，而 是关于交通荷载或密度的凸函数，实际上，在流量超过最大值时，随着流量的 减少，速度减少的程度会变得更深，引起行程时间的变得很高，因此不能在低 流量状态下假设行程时间也是很低的，例如，当车辆行驶在路段上，走走停停， 虽然交通量很低，但行程时间反而非常高。一般情况下，在交通规划时都采用 静态分配，而动态分配却把重点放在拥挤的动力学特性上，因此都要用凸费用 函数来进行优化计算。 3 1 2 状态变量的获取 在道路某一区段范围内的交通密度每时每刻都在变化，因此，所谓密度， 总是指某一瞬间的密度值或某一时段内的平均密度值。在交通研究中关心的常 是后者。这样就需要在某一阶段内连续调查瞬时密度，然后求算平均值。从实 测经验得知调查时段越长密度变化越平缓。另外，在正常交通量条件下，车辆 在道路上分布也不均匀，即路段不同部位的交通密度也是不同的，只有实测路 段达到一定长度后，交通密度的变化才趋于平稳。 本论文对于交通密度的获取，主要采用出入量法，如下图所示：在道路a b 1 2 上，分别设黄感应检测器，在t o 时刻a b 方向上存在的车辆数为e ( t o ) ，从f 0 到f 这 一段时间内，驶入的车辆数为线，驶出的车辆为q ，那么在t 时刻a b 上的车辆 数为：e ( f ) = e ( t 。) + g g ，则不难求得t 时刻道路a b 上的交通密度为： k ( f ) ：掣堕，从上式可以看出，只需知道初始车辆数，和从到f 这一段时间内车 “ b 辆的改变数，就可以计算得到t 时刻路段现有的车辆数，从而求取交通密度。 昱i 口口口口r - 7 r - 7 7 口r - 7r - - lr - - i i 昱 r 一一一。一一+ 一一- 一一一一一一一- 一一i il ii i 图3 2 交通密度获取示意图 3 1 3 行程时间的构成 行程时间具体是指行驶的车辆通过某一路段的总的持续时间，主要包括行 驶时间和交叉口延误时间。行驶时间即表示车辆时处于运动的时间，而由于拥 挤或红绿灯等原因引起的损失时间则称交叉口延误时间。行驶时间和距离成正 比，跟行驶速度成反比，所以在在计算行驶时间时，要先考虑和计算车辆的行 驶距离，而下游交叉口的排队长度又会影响车辆的行驶距离，即路段行驶距离 为整段路段长度减去下游交叉口前的排队长度。 在做静态交通分配时，根本不会考虑下游交叉口前的排队长度来计算路段 的阻抗，这只能使用于对行程时间的精度较低的情形下。但是一般情况下动态 交通规划对行程时间要求非常精确，所以必须要考虑下游交叉口排队长度的影 响，例如在在早高峰期，路段交通量非常大，路段交叉口前的排队长度相对应 这非常长， 而且城市道路网不同于公路交通路网，城市路网交叉口非常密集，并且路段比 较短，平均在50 0 200om 之间，因此必须考虑路段下游的交叉口的车辆 排队长度来进行对路段阻抗的研究。 综上所述，在研究有信号控制的城市交通路网时，路段行程时间主要包括 行驶时间( 车辆在非拥挤路段上的并非自由的行驶时间) 和延误时间( 交 叉口延误时间和途中延误时间) ，基于主要在交叉口处发生拥挤延误现象，所以 本论文仅仅考虑交叉口年的延误时间。 abe 图3 3 路段行程时间构成图 如上图所示，可以将一条实际的道路a 分成两条子路段，a = a c ，a 。= a b ， a ，= b c ，其中b 点是排队车辆的末端，随着排队时间的变化而变化，a ，表示路段 a 的排队长度，如果没有处于排队时，b 点将于c 点重合，即b c = 0 。 用t)表示在t时刻a路段上的实际行程时间。o(t 厶= ，( f ) + 乞 f + w 口( 明，v a ( 3 2 ) v o ( t ) = 心( f ) + d a p + 比( f ) 】，v 口 ( 3 3 ) 式中：厶一表示路段a 的长度； l ，( f ) 一路段非拥挤部分的长度； w o ( t ) 一表示当车辆t 时刻进入a 后，通过路段a 。所需花费的时间； 厶p + w 口( f ) 卜一表示t 时刻车辆在a 上的排队长度； 吃 f + w 口( f ) 卜一表示车辆在f + w o ( t ) 进入路段a 的排队延误时间； 一般情况下，一条路段的距离相对比较短，相应的通过路段的第一部分其 时间也会较短，所以公式3 2 、公式3 3 可表示成如下： 厶= r ( f ) + 厶p 】，v 口 ( 3 4 ) 乃( f ) = w 口( f ) + 吃嘲，v a ( 3 5 ) 在进行路径规划时，整个路径规划期划分为许多个小时间段，假设单位时 间内驶入驶出的车辆数和每一小时段里各路段行驶的车辆数都是特定值，因此 1 4 把行程时间函数当成离散函数来处理，时间问隔采用舭= 【k ，k + l 】表示，则车辆 在路段以的行程时间如下式： t ( 宓) = w 口( 死) + 矗口嘲，v 以，k ( 3 6 ) 本文以时间作为度量函数，把道路阻抗分为两部分进行考虑：非拥挤路段 行程时间和平面交叉口排队延误时间，下面将重点阐述其计算过程。 3 2 路段自由行程时间的确定 在国内外对路段行程时间函数的研究中，产生了一些模型心n 乜引，其中具有 代表性的有：( 1 ) 美国联绑公路局所提出来的路阻函数模型( b p r ) ；( 2 ) d a y id s o n 于1 9 6 6 年提出的一个具有渐进特性的路阻函数，此函数应用了排队理论：( 3 ) 英国的t r r l 模型。国内对于智能交通的研究属于起步阶段，因此对于行程时间 的计算较为粗相，没有统一的计算模式，在静态路网中，路阻的确定一般是采 用距离除以实际的车速。该方法只考虑了道路距离对路段行程时间的影响，而 对道路的具体参数如几何形状、路幅宽度、非机动车情况没有进行公式的较正， 对于平面交叉口只是简单的作点处理。公式使用起来效果很不理想，而在动态 交通路网中，一般是采用国外的交通阻抗计算模型加以参数的重新标定，其中 b p r 函数由于其适应性强得到了广泛使用。该函数模型考虑了交通流量的影响， 对于交通流量的处理也比较方便，在国外的应用得很多，但不适用目前中国的 实际状况，对非机动车的影响也没有进行考虑，所以b p r 函数在实际的应用中 误差很大。 3 2 1 速度一函密度函数模型 国内外研究表明，现实的交通环境中的密度和速度成不规划的线性关系， 具体如下图所示，本论文将速度一密度函数模型归纳为三种情况：( 1 ) 自由车流， ( 2 ) 正常车流，( 3 ) 饱和车流。 u u - i n 利用格林伯格( g r e e n b e r g ) 的交通流理论来描述路网中的交通参数变化状 态，由于本论文采用交通密度作为状态变量，不难分析出行驶速度v 与路网中交 通流密度有关系k 的关系，其速度一密度对数车流模型表式如下： y = 帅 7 ， 其中表示交通量取最优值所对应的速度，k m h ：七，交通量过大，车流处 于阻塞时对应的密度，辆k m ；通过对现实路网中的交通数据调查，验证了这种 函数模型的正确性。但是当交通非常小的时候就不适合利用这种函数模型，为 保证对行程时i 日- j 计算结果的可靠性。格林伯格模型乜3 3 需要分成两部分才能完整 描述拥挤状态下的v - k 关系： y = h l ( 等) ，七 。3 8 ) 【归_ 式中，后，为阻塞密度，辆k m ；吒为最优密度，辆k m ；v 册为流量一密度曲 线上对应的吒的速度，k m h ；= 0 5 v i ，1 ，为自由流速度，k m h ； 本论文所采用的格林伯格模型所描述的v - k 关系，q - k 关系是研究的基础， 从公式中可以发现，利用这种模型，现实的交通状况得到了全面的反映，在交 通量小时，其对应的交通密度也非常小，车流以城市道路允许的自由流速度行 驶，这种条件下，交通密度不能限制其行车速度，只有当交通密度大到某个程 度，两者基本上呈线性相关关系，交通密度大的情况下，交通比较拥挤，出行 行车安全考虑，车速必然要下降，阻塞密度与