（道路与铁道工程专业论文）基于费用的区域道路网最短路径分析研究.pdf

摘要 随着计算机科学和地理信息科学的迅速发展，地理信息系统因其强大的空间 分析功能得到了广泛的应用。 路径分析是g i s 中最普遍也是最基本的功能之一，其核心是对最短路径求解。 本文研究的主要内容就是最短路径分析在交通运输网络中的应用。文章的结构按 照“模型建立一算法研究一系统实现”的思路来组织。在研究区域道路网模型时， 详细分析了公路交通与城市交通不同的出行特点，得到恰当的道路网络抽象模型。 由公路交通网络的特点得知，公路交通网络的路阻也就是道路的路段路阻，该路 阻即是路段的综合费用，一般包括路段行驶的油耗、路段收费和车辆折旧费，以 此为基础来构建路段综合费用模型。采用经典的d i j k s t r a 算法计算路网的最短路 径时，网络的结点数较大，会占用大量的计算机内存，且需进行大量的值为一的 无用计算。本文运用判断语句对值为一的计算进行判断，从而避免了这种无用计 算，实现了对传统d i j k s t r a 算法的改进。本文最后基于己建立的费用模型和改进 的最短路径算法提出了“基于费用的区域道路网最短路径查询系统”的总体方案， 在m a p i n f o 的平台下采用v i s u a lb a s i c6 o + m a p x 5 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 rs c i e n c ea n dg e o g r a p h i c a l i n f o m a t i o ns c i e n c e ， g e o g r a p h i c a li n f o 伽a t i o ns y s t e mh a sb e e nu s e dw i d e l yb e c a u s eo fi t ss t r o n gs p a t i a l a n a l y s i sf u n c t i o n r o u t ea n a l y s i si so n e0 ft h em o s tg e n c r a la n db a s i cf u n c t i o ni ng i s i t sk e y c o n t e n ti st h eo p t i m u mr o u t ea n a l y s i s i nt h i s p a p e r ，t h em a i n c o n t e n ti st h e a p p l i c a t i o no fo p t i m u m r o u t ea n a l y s i st om et r a n s p o r t a t i o n t h ew h o l ef h m e w o r ki s b a s e do ne s t a b l i s h i n gm o d e l ，s t u d y i n ga l g o r i t h ma n da c h i e v i n gs y s t e m t h ea u t h o r a n “y s i s e sm ed i f = f e r e n c eb e t w e e nh i g h w a ya n dc “yr o a dt r a n s p o r t a t i o ni nd e t a i l ，a n d f i n d sa ne x a c ta b s t f a c t 删3 d e l0 fr o a dn e t w o r k a c c o f d i n gt om en e t w o r km o d e lo f t r a n s p o r t a t i o n ， t h et o t a le x p e n s ec o n s i s t si n0 i lc o n s u m p t i o n ，r o a dc h 缸g e蛐d d e p r e c i a t i o n t h e 孤t h o re s t a b l i s h e sa ne x p e n s em o d e lo fo p t i m u mr o u t ea n a l y s i s t r a d i t i o n a ld i j k s t f aa l g o r i t h mi sas h o r t e s tp a t ho n e w h e nt h er o a dn e t w o r k h a sm u c h n o d e s ，t h ec l a s s i c a ld i j k s t 豫a l g o r i t h mo c c u p i e sm u c hm e m o r ya n dt h ec o m p u t e rh a s t op r o c e s sm n yi n v a l i dc o u n t s b a s e do nl i b o v es h o r t c o m i n g s ，a ni m p o v e da l g o r i t h m i sb o u g h tf o r w a r d ，w h i c hu s e sj u d g e m e n tl a n g u a g et oa v o i dm u c hi n v a l i dc o m p u t a t i o n b e f o r ec o m p u t a t i o n ，t h ec o m p u t e rw i uj u d g ei ft h ec u r r e n tn o d ei sc o n n e c t e dw i t ht h e a b o v eo p t i m u mn o d e i fm e ya r ec o n n e c t e d t h ec o m p u t e rw i l lg oo nt oc o m p u t et h e i r d i s t a n c e 0 t h e r w i s e ，i tw i un o t f i n “l y a n0 v e r a us c h e m eo f “i n q u i f ys y s t e mo f s h o n e s tp a t ho fr e g i o n a lr o a dn e t w o r kb a s e do ne x p e n s e s i sb f o u g h tf o r w a r d t h e a u t h o ru s e si n t e g r a t i o no nm 印i n f 0t o h i e v et h es y s t e m ，如db a s e do nt h er e a ld a t a s o m ef b u c t j o n sh a v eb e e na c 血i e v e d k e yw o r d s ：g i s ，o p t i m u mr o u t ea n a l y s i s ，e x p e n s em o d e i ，r e g i o n a lr o a dn e t w o r k ， s h o r t e s tp a t ha l g o r i t h m 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：f 篙掀 日期：1 年j ，月哆日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囵。 ( 请在以上相应方框内打“”) 作者签名： f 素食 日期：岬年f 月哆日 名2 呷乃矸吼哕，月衫日 1 1 地理信息系统概述 第一章绪论 1 1 1 地理信息系统的概念 地理信息系统( 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 简称g l s ) 是一门综合的新 兴信息科学技术和产业。它是测绘学、地理学、空间科学、生态环境学、信息学、 计算机科学、管理学、人工智能、专家系统与网络通讯技术等领域的边缘交叉科 学，是以这些学科为基础技术平台，用各种现代化的方法来采集、存储、管理、 分析、显示和应用与整个地球表面( 包括大气层) 空问和地理分布有关的数据信 息的信息系统。 地理信息系统是以地理空间数据库为基础，采用地理模型分析方法，适时提 供多种空间的和动态的地理信息，为地理研究和地理决策服务的计算机技术系统， 具有以下三个方面的特征： ( 1 ) 具有采集、管理、分析和输出多种地理空间信息的能力，具有空间性和 动态性： ( 2 ) 以地理研究和地理决策为目的，以地理模型方法为手段，具有区域空间 分析、多要素综合分析和动态预测能力，产生高层次的地理信息； ( 3 ) 由计算机系统支持进行空间地理数据管理，并由计算机程序模拟常规的 或专门的地理分析方法，作用于空间数据，产生有用信息，完成人类难以完成的 任务n ，。 1 1 2 地理信息系统的产生与发展 g i s 是六十年代中期开始发展起来的新技术。它最初为解决地理问题而起， 至今已成为一门涉及测绘学科、环境科学、计算机技术等多学科的交叉学科。1 9 6 3 年加拿大测量学家r ft o m l i n s o n 首先提出了地理信息系统这一术语，并建成世 界上第一个g i s ( 加拿大地理信息系统c g i s ) ，并用于自然资源的管理和规划。不 久，美国哈佛大学提出了较完整的系统软件s y m a p ，这可算是g i s 的起步。进入 7 0 年代以后，由于计算机软硬件水平的提高，促使g i s 朝着实用方向迅速发展， 一些经济发达国家先后建立了许多专业性的g i s ，在自然资源管理和规划方面发 挥了重大的作用。如从1 9 7 0 年到1 9 7 6 年的几年中，美国国家地质调查局就建成 5 0 多个信息系统。8 0 年代后兴起的计算机网络技术使地理信息的传输时效得到了 极大的提高，它的应用从基础信息管理与规划转向更复杂的实际应用，成为辅助 决策的工具，并促进了地理信息产业的形成。进入9 0 年代，地理信息系统步入用 户时代。一方面，地理信息系统己成为许多机构必备的工作系统，尤其是政府决 策部门，在一定程度上由于受地理信息系统的影响而改变了现有机构的运行方式、 设置与工作计划等。另一方面，社会对地理信息系统认识普遍提高，需求大幅度 增加，从而导致地理信息系统应用的扩大与深化。国家级乃至全球性的地理信息 系统已成为公众关注的问题，例如地理信息系统已列入美国政府制定的“信息高 速公路”计划；美国副总统戈尔提出的“数字地球”战略也包括地理信息系统。 我国地理信息系统方面的工作自上世纪8 0 年代初开始。经历了起步、发展、 产业化三个阶段。以1 9 8 0 年中国科学院遥感应用研究所成立全国第一个地理信息 系统研究室为标志，在几年的起步发展阶段中，我国地理信息系统在理论探索、 硬件配制、软件研制、规范制订和技术队伍培养等方面都取得了进步，积累了经 验，为在全国范围内展开地理信息系统的研究和应用奠定了基础。 从第七个五年计划开始我国的g i s 工作进入了发展阶段。地理信息系统研究 作为政府行为，正式列入国家科技攻关计划，开始了有计划、有组织、有目标的 科学研究、应用实验和工程建设工作。许多部门同时展开了地理信息系统研究与 开发工作。如全国性地理信息系统( 或数据库) 实体建设、区域地理信息系统研 究和建设、城市地理信息系统、地理信息系统基础软件或专题应用软件的研制和 地理信息系统教育培训。通过近五年的努力，在地理信息系统技术上的应用开创 了新的局面，并在全国性应用、区域管理、规划和决策中取得了实际的效益。 自9 0 年代起，地理信息系统步入产业化阶段。执行地理信息系统和遥感联合 科技攻关计划，强调地理信息系统的实用化、集成化和工程化，力图使地理信息 系统从初步发展时期的研究实验、局部实用走向实用化和生产化，为国民经济重 大问题提供分析和决策依据。努力实现基础环境数据库的建设，推进国产软件系 统的实用化、遥感和地理信息系统技术一体化。在地理信息系统的区域工作重心 上，出现了“东移”和“进城”的趋向，促进了地理信息系统在经济相对发达、 技术力量比较雄厚、用户需求更为急迫的地区和城市首先实用化。从应用方面看， 地理信息系统已在资源开发、环境保护、城市规划建设、土地管理、农作物调查 与交通、能源、通讯、地图测绘、林业、房地产开发、自然灾害的监测与评估、 金融、保险、石油与天然气、军事、犯罪分析、运输与导航、1 1 0 报警系统、公 共汽车调度等很多方面得到了具体应用。目前g i s 的应用领域已发展到约6 0 多个， 且用户数每年以2 6 倍左右的速度增长m 。 1 1 3 地理信息系统的功能 作为地理信息自动处理与分析系统，地理信息系统的功能遍历数据采集一分 析一决策应用的全部过程，并能回答和解决以下五类问题： ( 1 ) 位置，即在某个地方有什么。位置可表示为地方名、邮政编码、地理坐 2 标等。 ( 2 ) 条件，即符合某些条件的实体在哪里。例如在某个地区寻找面积不小于 1 0 0 0 m 2 的不被植被覆盖的，且地下条件适合于大型建筑的区域。 ( 3 ) 趋势，即某个地方发生的某个事件及其随时间的变化过程。 ( 4 ) 模式，即某个地方存在的空问实体的分布模式。模式分析揭示了地理实 体之间的空间关系。 ( 5 ) 模拟，即某个地方如果具备某种条件会发生什么。地理信息系统的模拟 是基于模型的分析。 由于地理信息系统发展的多源性，其功能具有可扩充性以及应用的广泛性。 m a u g u i r e 等按照地理信息系统中数据流程，将地理信息系统的功能分为以下5 类： 采集、检验与编辑；格式化、转换、概化； 存储与组织：分析；显示。 在分析功能中，把空间分析与模型分析功能称为地理信息系统高级功能“1 。 1 1 4 地理信息系统发展的趋势 近年来，计算机技术飞速发展，特别是软件技术的发展，促使g i s 技术发生 了很大的变化。国际g i s 技术的发展趋势，主要体现在两个方面。一是在技术上 的综合( i n t e g r a t i o n ) ；一个是软件技术上的分化( f r a c t i o n a t i o n ) 。 ( 1 ) 技术上的综合 g i s 技术上的综合，主要体现在g i s 与其它信息技术上的结合。我们常说的 “3 s ”技术，即g i s 、r s 和g p s 的一体化，就是技术综合的一个体现。现在的g i s 已经远远超出了这些，它已经与c a d 、多媒体、通信、i n t e r n e t 、办公自动化、 虚拟现实等多种技术结合，形成了综合的信息技术。综合是g i s 技术开发和应用 的重要方向。g i s 与几种信息技术的结合如表1 1 所示： 3 表1 1g i s 与几种信息技术的结合 地理信息系统( g i s ) 与全球定位系统( g p s ) 、遥感技术( r s ) 的 结合就是我们常说的3 s 技术。在3 s 技术中g p s 实现准确的实时定位， g i s + g p s + r s 遥感影像提供准确的地理信息，将g p s 数据、遥感数据和各种资料在 g i s 中进行综合处理与分析，就能得到地球空间中的地理实体全面、准 确和动态的信息。 g i s 与专家系统( e s ) 的结合称为专家g i s 或智能g i s 。目前g i s 的 应用还主要停留在建立数据库、数据库查询、空间叠加分析、缓冲区分 析和成果显示输出上。缺乏知识处理和启发式推理的能力，无法为解决 g i s + e s 空间复杂问题提供足够的决策支持。专家g i s 是解决一些空间复杂问题 的重要途径，在专家g i s 当中，由g i s 完成空间位置分析工作，由e s 来评价，二者相互补充。 虚拟g i s 就是g i s 与虚拟现实技术( v i r t u a lr e a l i t y ) 的结合。 v r 技术是一种最有效地模拟人在自然环境中视、听、动等行为的高级 人机交互技术。g i s 与虚拟环境技术相结合，将虚拟环境带入g i s 使g i s g i s + v r 更加完美。g i s 用户在计算机上就能处理真3 维的客观世界的虚拟环境， 更有效地管理、分析空间实体数据。目前虚拟g i s ( v g i s ) 的研究主要 集中在虚拟城市。 g i s 技术与i n t e r n e t 技术的融合形成一种新的技术w e b g i s ，它是 g i s 一个重要发展方向。w e b g i s 可实现网上发布、浏览、下载，实现基 g i s + i n t e r n e t 于w e b 的g i s 查询和分析。这将会使6 i s 从一门专业人员的技术变成 人人都会使用的大众技术，使g i s 从面向政府部门和科研机构扩大到公 司企业和个人，给g i s 带来一个广阔的发展前景。 无线通讯改变了人们的生活和工作方式。随着无线通讯技术的发 展，特别是w a p 技术的应用，使无线通信技术与g i s 技术以及i n t e r n e t 技术的结合成为可能。形成了一种新的技术一一无线定位技术 ( w i r e l e s sl o c a t i o nt e c h n o l o g y ) 。利用这种技术，人们可以利用手 g i s + i r e l e s s 机查询到自己所在的位置；再利用g i s 的空间查询分析功能，查到自己 c o m m u n i c a t i o n 所关心的信息。据估计，利用手机进行无线上网、无线资料传输将是下 一个热潮。到2 0 0 2 年，全球将有超过l 亿部手机有上网功能，到2 0 0 3 年其数量将达到1 0 亿部。g i s 与无线通讯的结合，使g i s 借助于无线 通讯等技术手段更加深入地融入到我们的日常生活当中，这将是一个非 常广阔的市场。 4 ( 2 ) 软件技术的分化 g i s 的软件技术的发展经历了从g i s 模块到组件式g i s 和网络式g i s 的过程 ( 如图1 1 ) 。 图1 1g i s 模块的发展过程 目前，组件式g i s ( c o m g i s ) 和w c b g i s 已经成为了许多大型g i s 公司产品 的开发方向。组件式g i s 的基本思想是把g i s 的各大功能模块划分为几个控件， 每个控件完成不同的功能。各个g i s 控件之间以及g i s 控件与其它非g i s 控件之 间可以方便地通过可视化的软件开发工具集成起来，形成最终的g i s 应用。组件 式g i s 最大的好处是能够使g i s 功能嵌入其它软件，或将其它软件功能引入到 g i s 中来。组件式g i s 代表着当今g i s 发展的潮流。国际上大多数g i s 软件公司 把开发组件式软件作为重要的发展战略。i n t e r g r a p h 公司宣称已经进入组件式g i s 时代，它制定的j u p i t e r 计划意在移植和开发多种组件式g i s ，它推出的组件式 g i s 软件一g e o m e d i a 是其庞大的j u p i t e r 计划中的一部分。e s r i 在组件式g i s 方 面了做了新的探索，在1 9 9 7 年年初推出了以m a p o b j e c t s 为代表的新一代g i s ， m a p i n f o 也于1 9 9 7 年迅速推出m a p x 。国内的朝夕科技有限公司于1 9 9 8 年年初 推出了国产组件式g i s 软件m a p e n g i n e 。 如前所述，w e b g i s 已经是当今g i s 技术发展的重要方向，成为g i s 领域的竞 争焦点。世界各大g i s 专业公司相继推出了各自的产品，如a u t o d e s k 公司的 m a p g u i d e ，e s r i 公看j 的i n t e r n e tm a ps e r v e r ，i n t e r g r a p h 公司的g e o m e d i aw e b m a p ，m a p i n f o 公司的p r o s e r v e r c 等，都希望抢占市场。然而，这些软件还不完 善，这给我国的g i s 软件事业提供了机会。 g i s 发展的下一个阶段也许是地理信息造型语言( g e o g r a p h i ci n f o r 吡t i o n m o d e l i n gl a n g u a g e ) 。超文本标记语言( h t m l ) 和虚拟现实造型语言( v r m l ) ，能 够在i n t e r n e t 上很好地描述和表达文字、多媒体和图形。这些语言的发展将对 g i s 产生巨大的影响“，。 1 2 交通地理信息系统概述 1 2 1 交通地理信息系统的概念 交通地理信息系统( 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 sf o r t r a n s p o r t a t i o n ，g i s t ) 是收集、存储、管理、综合分析和处理空间信息和交通 信息的计算机软硬件系统。它是g i s 技术在交通领域的延伸，是g i s 与多种交通信 息分析和处理技术的集成。简而言之，就是将g i s 用于交通方面的一种综合技术。 1 2 2 交通地理信息系统的意义 交通地理信息系统是g i s 在交通领域的具体应用和延伸，是在传统g i s 基础 上，充分考虑交通现象的线性特征和网络特征，并附之专门的交通建模手段而形 成的专门化系统。交通地理信息系统覆盖整个交通运输体系，包括公路、铁路、 航空、水运、管道等。 公路运输网络形成了复杂的拓扑结构体系，利用g i s 提供的完善的网络拓扑 结构和特定的数学模型对其进行分析，并以图形和表格的形式直观地表现出来， 可为决策者提供快速有效的辅助决策依据。目前g i s 已经应用在公路系统的许多 部门，如公路设计和施工部门。在保证造价最低的情况下，综合考虑道路所经过 的地形、地质、周围环境辅助设施信息等，选择最佳的路径来铺设道路。 城市交通网络在城市发展中占有至关重要的地位。它不仅是城市的一个重要 组成部分，同时也决定了城市中居民的生活方式。长期以来，交通问题己成为困 扰城市发展的重要问题。世界各国都面临着日益严重的城市交通问题，如交通拥 挤、车辆行驶缓慢、交通事故频繁及其由于交通堵塞造成的大量空气污染等，由 此而带来大量的经济损失和人员伤亡。许多发达国家逐渐认识到，欲有效地解决 这些问题，仅仅依靠道路建设、扩大路网规模是远远不够的，交通问题的解决必 须依赖现代信息技术与管理技术的有机结合。 近十几年来，随着地理信息系统技术的快速发展，地理信息系统的各种应用 在城市规划、管理方面越来越起到不可低估的作用。在众多有关城市地理信息的 应用中，城市交通地理信息系统的发展越来越受到地理学者、城市管理者的瞩目。 交通数据的种类繁多( 包括属性数据、空间数据、影像数据等) ，数据量大，操作 复杂，人工管理难度大。交通地理信息系统的出现为交通数据的自动化管理提供 了一个可行的途径。g i s t 不但可以存储、管理和更新城市交通网络的空间数据 库，辅助城市交通线路规划、交通管理，而且更重要的是，通过与g p s 技术、无 线通讯、互联网络、虚拟现实等高新技术的有机结合，在g i s 的数据操作及空间 分析技术的辅助下，可以建立广泛的实时数字交通信息用户服务体系，实现全数 字化交通信息的实时发布、存储与检索，为城市交通管理、车辆的人工及智能导 航、客货运输调度及居民出行等提供有效的技术支持。这种实时数字交通信息用 户服务体系在被交通问题困扰的大中城市具有十分迫切的市场需求。 ， 1 2 3 交通地理信息系统的具体应用 ( 1 ) 电子地图 电子地图使交通管理工作变得轻松直观。由于采用空间数据和数据库链接， 6 改变了传统的信息管理方法，地图由传统的静态纪录变为信息丰富多样的动态的 电子地图，实现了数据可视化。它使交通主管部门对公路等基础设施的管理变得 直观、简单和轻松。如通过直接对地图实体进行查询，可以获得公路线路的空间 位置和走向，技术标准，交通流量等多方位的信息。通过综合统计各种交通数据、 分析丰富多样的图表显示，可以为决策提供科学快捷的支持。 ( 2 ) 公路网规划 公路网规划和路线选择是g i s t 应用发展的重点领域之一。目前基于g i s t 的交通规划模型软件已经开发成功并进入商业化应用阶段，这些软件包括全部的 g i s 软件功能，其应用模型与g i s 集成为一体，它使交通规划的手段更加强大。 由于应用g i s t 能够更好的考虑和评估公路对环境的影响，因此在公路路线 的选择和初步设计中g i s t 将得到广泛应用。加拿大已经成功地应用g i s 完成了 在温哥华岛的一条1 2 7 公里、4 车道的公路通道选择和初步设计。在此项目中g i s 很好地解决了项目涉及的环境分析、公路选址等问题，包括野生动物、森林、水、 土壤、植被和土地利用等。 ( 3 ) 道路设计和养护 g i s t 为道路工程的计算机辅助设计c a d 提供了强大的数字化地理平台，正 是基于此，c a d 已由早期的平面二维设计跨入了三维设计，进入了可视化设计时 代，这是c a d 领域的突破性发展。 g i s t 还与路面管理系统、桥梁管理系统等公路养护管理系统相关连，借助 先进的路面和桥梁检测设备和数据搜集手段，使道路养护管理更加科学合理，经 济高效。如加拿大的a 1 b e r t a 省建立了公路维护地理信息系统，该系统使用专用 检测车辆，定期检测路面的平整度和损坏程度等；这些指标由车载全球定位仪 ( g p s ) 定位装置准确确定道路的位置，检测数据传输到公路养护地理信息系统， 养护模块自动生成路段养护报告。 ( 4 ) 运输企业运营管理 借助g i s 的运行路径选择功能，运输企业可以对公司的运营线路进行优化， 并根据专题地图的统计分析功能，分析客货流量的变化情况，制定行车计划。此 外还可以帮助运输管理部门对特种货物( 如长大件货物、危险货物或贵重货物) 运输进行线路选择和监控。 ( 5 ) 为智能运输系统( i t s ) 提供数字化平台 智能运输系统是新近发展起来的交通管理系统，它将和g i s t 、全球定位系 统g p s 一道成为未来十年交通领域快速发展的新技术。基于g i s t 、g p s 的i t s ， 将能够为道路用户提供实时动态交通信息服务，改善出行方式；也能够为道路管 理者提供控制信息，大大提高现有道路的通行能力和安全性。这三种技术如何有 效的集成还处在研究之中，但无疑这将是g i s t 的又一重大应用领域n 。 7 1 2 4 交通地理信息系统的发展现状 目前，g i s t 技术在国外发达国家发展很快。在欧美等发达国家，各地方交 通部门纷纷采用g i s t 技术建立交通管理系统、出行信息系统、商业车辆运行系 统、车辆自动定位系统及车辆自动识别系统等，并尝试通过互联网络实时发布交 通信息。在日本，以丰田公司为首的各大汽车公司，与交通部门通力合作，已制 定了完善的数字交通信息通讯协议，并在全球率先建立了全数字化交通信息台， 通过广播电台实时发布数字形式的城市交通信息，与之配套的车载交通信息系统， 可实时接收发布的数字交通信息，反映在计算机屏幕上，并可自动完成顾及实时 交通状况的车辆的自动导航。 g i s t 在我国也得到了一些应用。从2 0 世纪8 0 年代起，我国公路管理部门 采用0 r a c l e 、f o x b a s e 、d b a s e 等陆续建立了一些公路路况数据库，在“七五”、 “八五”期间，交通部组织了一系列的旨在提高公路规划和管理水平的应用系统 开发研制，包括路面管理系统c p m s 、桥梁管理系统c 酬s 等。随后，g i s t 的研 究在我国交通领域蓬勃展开。例如，国家发改委所属综合运输研究所于2 0 世纪 9 0 年代中期开发完成了全国铁路客流管理地理信息系统，为用户提供各种查询手 段和分析方法；中国和加拿大政府合作完成“广东省综合交通规划管理系统”，为 省级、国家级开展综合运输规划研究奠定基础。近年里，广州市推出“公交地理 信息系统”和公交免费查询电子触摸屏。通过公交地理信息系统，可以使公交车 重叠率、换乘系数等运行状况一目了然。该系统将各公交站点的特定位置在图像 上进行准确定位。另外“上海中心城智能交通一期工程”今年年内实施，率先启 动的将是为智能交通提供重要技术支撑的“中心城区道路交通信息采集系统”建 设。 第二章道路网最短路径的费用分析 道路网最短路径分析，是道路网g i s 拓展社会服务的重要功能之一。最短路 径的查询有多种实现方式，其中动态最短路径搜索是最理想的解决方案，它也是 车载交通诱导系统的重要功能之一。但从目前的硬件装置和技术水平( 信息采集、 处理等) 来看，其理论研究和应用多局限于城市交通网络，且尚不具备大规模工 程实用性。对于道路交通网络来说，静态或准动态最优路径搜索方式更具有工程 实用意义。它们的实现涉及到两方面内容：搜索算法和路阻确定。其中，路阻的 确定是最短路径搜索实现的基础，同时也决定了搜索的精度( 最优程度) ，本章将 对路阻的确定给予重点分析。 2 1 实验路网的选择 本文采用湖南省长株潭三地之间道路网作为实验对象。 因为是以城区之间的道路网为试验对象，所以在进行道路网络抽象时可以不 用考虑城市道路的抽象。对该道路网络进行抽象时，在城区范围的边界处，选择 适当的城区出入口。 本文最短路径分析时采用该地区的有关模型，鉴于本文主要目的是提供一种 解决问题的思路，对于实际工程应用，其地区性模型有待进一步标定。 2 2 道路网络的抽象 2 2 1 公路交通的特点 与城市交通相比，公路交通有与其不同的出行特点： ( 1 ) 公路网与城市路网在分析方面存在很大不同，公路网交通上不存在因路 口交通管制设施等所带来的一系列问题；公路网络很少存在一些应用于城市交通 的管控措施：如单向通行、限行、禁行、车型限制、转向限制等。 ( 2 ) 对于城市交通出行来说，主要考虑时间因素，即选择时间最短路径。公 路交通出行一般为长途远距出行，历时较长，且路网内道路等级、状况不等，敬 司机出行考虑因素较多。 ( 3 ) 城市交通存在较明显的“时变性”，表现为“潮汐”交通特征。公路交 通一般不存在“潮汐”特征，多数时间双向交通均衡“。 9 2 2 2 道路网络的抽象 本文所选的道路网络是由道路、交叉路口( 包括立交) 构成的。根据道路网 络的特点，在道路网g i s 中将其进行如下抽象： ( 1 ) 道路网抽象为带权无向图，道路的交叉口、断头路的终点、高速公路的 出入口和收费站点( 包括立交桥) 是图中的结点，路段是图中的边； ( 2 ) 道路网按其实际地理位置等比例构建到道路网g i s 中，保持原网络的形 状不变； ( 3 ) 路段是可以双向通行的，且平均配流，两侧路段阻抗相同； ( 4 ) 结点( 交叉路口) 处无行车控制。 2 3 基于费用的道路网最优路径分析中的关键问题 2 3 1 基于费用的道路网g i s 中的路阻 对于道路交通网络，其路阻由两部分确定：路段路阻和结点路阻。在道路网 交通分配中，路段是指两结点之间的道路，结点包括交叉路口、高速公路的出入 口和收费站等。 道路网g i s 是以地理坐标为准的，建立时对于城镇、道路网等严格按坐标等 比例构建的，所以道路网g i s 不会也不可能把一个城镇抽象为结点来考虑。其道 路网内公路路段可直接与城市内道路连接，这样在路径搜索时，只要赋予城市区 域内道路和结点及与公路不同的路阻值，就可以将他们的区别区分开来。 本文中对路网进行抽象时，我所选择的路网为城区范围之外的路网，因此本 文中交通网络的的路阻也就是道路的路段路阻。 2 3 2 标准车型的确定 对于最短路径，因为每种车型的车速一油耗模型、收费额度、对路面状况的 适应程度等都不同，司机在同一时间段对同一道路网络中所选择的最短路径应该 是不同的。因此在计算时采用标准车型，其它车型可以以此作为参考标准。 本文中标准车型的定义引用公路工程技术标准中的有关规定，它是为了 更好的量化路阻相关模型而定义的。所谓标准汽车，据现行公路工程技术标准 中的有关规定，将小客车定位各等级公路交通量换算的标准车型。 所以，本文在确定路阻时选用小客车作为标准车型，当需要确定有关模型时， 以小客车的模型为主。 本文研究的是标准车辆的最短路径，可以说是最短路径的相对表达，而非绝 对表达，即非表达对于不同车型在同一路段上的路阻差异。这个问题可以在远期 分别研究各车型的路段路阻予以解决。 1 0 2 。4 路段路阻的确定 道路阻抗值，即沿着某条道路路线完成其行驶任务的综合成本。它是道路使 用者在选择好出行目的地之后在起讫点之间选择行驶路线的主要因素。路线阻抗 值是车辆运营所发生的所有直接费用，一般包括：车辆燃油、道路收费和车辆折 旧三大类。 2 4 1 路段综合费用模型的构建 运输费用是司机选择最优路径的一项重要的参考指标。对于路线的运输费用， 我们把它拆分到每一路段进行路段运输费用的分析。 目前，对于路段综合费用来说一般包括路段行驶的油耗、路段收费和车辆折 旧费。因此，以此为基础来构建路段综合费用模型。 c 撕乞= 砌f 4 + c 氍a r g 巳+ 舰 ( 4 1 ) 式中：c 缸t 。为路段4 的综合费用( 元车) ；n 球z 。为标准车辆行驶路段口的燃 油消耗费用( 元车) ；m a r g 乞为路段4 的收费额度( 元车) ；d 节。为标准车辆在 路段n 上行驶的车辆折旧费( 元车) 。 2 4 2 路段综合费用模型分析 1 车辆燃料消耗模型 通常，衡量汽车燃油消耗的指标是完成一定行驶里程的燃油消耗( 等速百公 里消耗) 或完成一定运输量的消耗( 等速吨百公里消耗) ，这两个指标都规定是在 理想的道路和交通条件下获得的，不适合于公路运输中实际道路与交通条件下的 油耗分析。 油耗模型从建模方法上讲一般可分为三大类：( 1 ) 多元回归油耗模型；( 2 ) 理 论油耗模型；( 3 ) 台架实验油耗模型。对于第一类模型，由于它来自于大规模的野 外实验，因此具有很高的置信度。但这种方法有一个缺点，那就是异地使用性能差。 而台架实验模型的基础是比油耗一功率一转速图，由于它们是由室内实验得到的， 因此可以使用在任何地方。但它的缺点一是可信度差，二是需要有专门的设备取 得实验数据。第二类模型即理论油耗模型是根据能量守恒或功率守恒的原理，利 用牛顿法则通过力学分析和实验标定建立，用这种方法建立的模型能克服上述两 种模型的缺点，表现了高的置信度和异地使用性，因此被认为是一种较好的建模 方法。 影响燃料费用的因素主要有公路条件、车辆特性和交通条件等。在既定车型 条件下，单位行程燃料费主要受公路条件( 道路平整度和纵坡) 、交通特性( 车速) 等的影响。这里以小客车为标准车型进行计算。 ( 1 ) 车辆燃料消耗与平整度的关系模型 为了评价汽车的燃料经济性，常选取单位行程的燃料消耗量( 等速百公里消 耗) ，即l 1 0 0 k m ，或单位运输工作的燃料消耗量( 等速吨百公里消耗) ，即 l 1 0 0 t k m 、l k p k m 作为评价指标。 平整度是反映道路因素的另一指标，随着平整度的增大，汽车油耗也会增加。 但在正常的平整度范围内，油耗变化的幅度不大。单位油耗随速度变化的幅度还与 车速有关，车速越大，单位油耗对平整度越敏感。如果汽车以4 0 k m h 的时速行驶， 在平整度删为1 5 的道路上的油耗是删为3 的道路上油耗的1 1 3 倍左右。 根据有关研究成果，由文献 2 4 知采用燃料消耗模型： = 口f + 6 f 脚 ( 4 2 ) 式中：兄为燃料消耗量( 升每百车公里) ；口i 、6 ，为模型标定参数( 见表2 1 ) ； 础为国际平整度指数( m k m ) ，根据我国的道路状况，本文取j 彤平均值为 6 5 m k m ；f 为车辆等级标号，它们分别是轻、中、重。 表2 1 燃料模型参数 车墅代表车型燃料类型 口j以 l 小客车( 轻)长安之星汽 1 7 4 20 5 6 8 5 ( 2 ) 车辆燃料消耗与车速和纵坡的关系模型 汽车种类很多，不同类型车辆的技术状况、燃料消耗差别较大，需按不同车 型研究燃料消耗和建立模型。因此，其它条件下的燃料消耗与车速的关系模型， 是以基本公路条件下的模型为基础，通过不同车型的模型调整系数来确定m ，即： e = 置r ，只 ( 4 3 ) 式中：只为第f 种车型燃料消耗( 升每百车公里) ；置。为第f 种车型的模型调 整系数；只为按基本模型计算的基本燃料消耗( 升每百车公里) 。 建立不同车型的模型调整系数应考虑的因素有两个：纵坡和车速。通过对调查 数据和国内、外相关资料的分析，发现特定车型的模型调整系数变化符合以车速 和纵坡为变量的二元幂函数n “，即： 研f = 6 m l m 2 0 ( 4 4 ) 式中：置，为第i 种车型燃料消耗调整系数；玎为第f 种车型车辆行驶速度 ( k m h ) ，根据调查高速公路平均按1 2 0k m h 计算；6 、鸭、m ：为回归系数，见 表2 2 ；g 为公路纵坡( ) ，长株潭地区地形为平原微丘区，高速公路的平均纵坡 按2 计。 表2 2 回归系数表 车型 易 m 1m 2 l 小客车 0 7 2 50 9 8 51 0 2 2 这样，考虑道路平整度、纵坡和车速等因素的燃料消耗模型为 ，= 6 m l 钾j ，1 2 g ( 口f + 6 。脚) ( 4 5 ) 2 路段收费 随着国内高速公路、b o t ( b u i l d 一0 p e r a t e t r a n s f e r ，兴建一营运一转移) 模 式及民办收费公路的兴起，公路收费也随之成为不可忽视的一项支出，在路段综 合费用中成为不可缺少的一个组成部分。 不同车型在同一收费路段上收费额度的确有差异，但不同车型在所有路段上 却具有相同的变化趋势，即将不同车型在所有收费路段上的收费额度进行标准化 处理后，变化趋势相同且其值相差不大。这样，对于路段收费路阻指标来说，可 以以标准车型的路段收费路阻来代替所有车型。 3 车辆折旧费用模型 汽车的折旧是指汽车在使用的过程中，因车况下降、运行费用的增加造成的 汽车自身价值的流失。汽车的折旧一般以年为单位进行计算，它是汽车运营费用 的一个重要组成部分。车辆折旧费在运行费用中占一定的比重，故在计算运行费 用时，需将其考虑进去。 路段行驶中车辆折旧费用的影响因素很多，例如车型、驾驶水平、路况、交 通流状况、车速等等，尚没有理想的评价模型。我们可以统计标准车型的平均报 废里程和寿命期内的平均花费( 购买、维修、保养等) ，以此建立简单的线性模型。 对于运输车辆，在使用末期l = o 。按照国家汽车报废标准( 1 9 9 7 年) 规 定1 9 座以下营运客车的使用年限为8 年，即n 2 8 。 车辆折旧费用模型n ” c 。：5 吡盟n c 肼； ( 4 6 ) 。 ( 1 + f ) 4 一i 式中：c 。为车辆折旧费( 元车1 0 0 k m ) ：为新车平均价格( 元辆) ；以为 车辆使用年限；c 删，为极限行程里程数的一半( k m ) ；i 为贴现率，在工程经济 分析中，卜。般取为1 0 。以上模型的参数均列于表2 3 。 表2 3 模型参数标定值 车型代表车型燃料类型 口j轨 只1 0 4 c k m ，1 0 5 枷 i 小客车长安之星汽 1 7 4 20 5 6 8 542 5 4 路段综合费用的计算 根据以上分析，以式4 1 为基础构建路段综合费用计算模型： c 枷= n “f 4 + c a a r g 巳+ d 印 4 ， 7 、 = ( ，乞1 0 0 ) d + c a a r g 巳+ ( c 0 乞1 0 0 ) d 式中，f 为路段n 的百公里油耗( 升百公里) ；l 为路段4 里程( 公里) ；d 为标准车型消耗燃油单价( 元升) 。其中消耗燃油单价取5 元升。 1 4 第三章基于费用的道路网最短路径算法 3 1 最短路径概述 所谓最佳路径，是指网络两结点之间阻抗最小的路径。 “阻抗最小”有多种 理解，如基于单因素考虑的时间最短、费用最低、风景最好、路况最佳、过桥最 小、收费站最少、经过乡村最多等，和基于多因素综合考虑的风景最好且经过乡 村较多，或时间较短、路况较佳、且收费站最少等。最短路径问题是最优路径问 题的一个单因素特例，即认为路径最短就是最优。 最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量， 如时间、费用、线路容量等。其关键是对“短”的含义的理解，例如，如果网络 属性为时间，则为最短时间；如果网络属性为费用，则为最低费用等。本文统一 取用“最短路径”，而不再区分其具体含义。 3 2 图论的概念 图论是研究事物及其之间关系的科学，任何一个能用二元关系描述的系统， 都可以用图提供数据模型。图论中的许多基本概念，如路径、路、连通性等都是 进行网络分析的基础。下面先介绍一个关于图的几个定义。 ( 1 ) 图：图论中