（运筹学与控制论专业论文）动态最短路径的拟物方法的研究.pdf

山东科技大学硕士学位论文摘要 摘要 随着经济的讯猛发展，交通运输的需求变得愈加迫切。而大城市中新建和扩建道路 的可能性却越来越小，并且，仅仅依靠基础设施的建设，不可能满足交通需求，城市交 通拥挤状况越来越严重。 随着科技的飞速发展，计算机技术、网络技术和通讯技术已逐步渗入到交通领域。 随着计算机的迅猛普及以及信息技术的发展，地理信息系统得到f 二| 益广泛和深入的应 用。随着信息的发展，利用现代化科学技术管理城市交通，合理并科学地引导和控制交 通流，有效地提高现有交通网络的运行效率，这是城市交通管理发展的必然。智能运输 系统i t s ，正是在这种情况下提出来的。城市交通流诱导系统，简称u t f g s ，是i t s 的 重要组成部分，是解决城市交通问题的关键。最短路径算法是交通网络分析的核心，网 络分析是空间分析的一个重要方面，网络分析中最基本最关键的问题是最短路径问题。 最短路径问题是许多领域中选择最优问题的基础，在交通网络分析中占有重要地位。 本文正是基于交通信息的路网的动态最短路径的拟物方法研究。在本文中，首先从 图论的角度描述了最短路径含义及其分类，讨论了静态最优路径的算法及高度信息化的 条件下的动态最短路径算法；然后阐述了拟物方法的含义、应用并给出用拟物方法解决 问题的路线；最后，分析了已有的求静态和动态最短路径的算法的不足，提出了用拟物 方法求解最短路径的思路。 本文提出了拟物方法求最短路径的思路，这无疑对解决城市交通问题提供了一定的 理论基础，因此此文具有一定的学术价值和现实意义。 关键词：智能交通系统，最短路径，交通信息，动态最短路径，静态最短路径，拟 物方法，拟人方法 山东科技大学硕士学位论文摘要 摘要 随着经济的讯猛发展，交通运输的需求变得愈加迫切。而大城市中新建和扩建道路 的可能性却越来越小，并且，仅仅依靠基础设施的建设，不可能满足交通需求，城市交 通拥挤状况越来越严重。 随着科技的飞速发展，计算机技术、网络技术和通讯技术已逐步渗入到交通领域。 随着计算机的迅猛普及以及信息技术的发展，地理信息系统得到f 二| 益广泛和深入的应 用。随着信息的发展，利用现代化科学技术管理城市交通，合理并科学地引导和控制交 通流，有效地提高现有交通网络的运行效率，这是城市交通管理发展的必然。智能运输 系统i t s ，正是在这种情况下提出来的。城市交通流诱导系统，简称u t f g s ，是i t s 的 重要组成部分，是解决城市交通问题的关键。最短路径算法是交通网络分析的核心，网 络分析是空间分析的一个重要方面，网络分析中最基本最关键的问题是最短路径问题。 最短路径问题是许多领域中选择最优问题的基础，在交通网络分析中占有重要地位。 本文正是基于交通信息的路网的动态最短路径的拟物方法研究。在本文中，首先从 图论的角度描述了最短路径含义及其分类，讨论了静态最优路径的算法及高度信息化的 条件下的动态最短路径算法；然后阐述了拟物方法的含义、应用并给出用拟物方法解决 问题的路线；最后，分析了已有的求静态和动态最短路径的算法的不足，提出了用拟物 方法求解最短路径的思路。 本文提出了拟物方法求最短路径的思路，这无疑对解决城市交通问题提供了一定的 理论基础，因此此文具有一定的学术价值和现实意义。 关键词：智能交通系统，最短路径，交通信息，动态最短路径，静态最短路径，拟 物方法，拟人方法 山东科技大学硕t 学位论文 摘要 a b s t r a c t w i t ht h ed e v e l o p m e n to fg l o b a le c o n o m y t h en e e do ft r a f f i ca n d t r a n s p o r t a t i o ni sm o r ea n dm o r eu r g e n t a n dt h ep o s s i b i l i t yo t 。b u i i d i n gn e wr o a d s o re x t e n d i n go l dr o a d si ss m a l l e r i tc a n n o tm e e tt h et r a f f i cd e m a n do n l yr e l y i n g o nc o n s t r u c t i o no ft h ei n f r a s t r u c t u r e t h eu r b a nt r a f f icj a mb e c o m e sm o r ea n d m o r es e r i o u s w i t ht h er a p i dd e v e l o p m e n to fs e i e n c ea n dt e e h n o l o g y e s p e c i a l l yt h o s eo f t h ec o m p u t e r ，t h en e t w o r ka n dc o m m u n i c a t i o nh a sa l r e a d yp e r m e a t e di nt r a f f i c f i e h lp r o g r e s s i v e l y w i t ht h er a p i dd e v e l o p m e n to ft h ec o m p u t e ra n di n f o r m a t i o n t e c h n o l o g y ，g e o g r a p h i cl n f o r m a t i o ns y s t e m si su s e dw i d e l y d e e p l yd a yb yd a y i t i su r g e n tf o rc i t yt r a f f i ca d m i n i s t r a t i o nd e v e l o p m e n tt ou s em o d e r n i z e d t e c h n o l o g i e st om a n a g eu r b a nt r a f f i c ，l e a da n dc o n t r o lt h et r a f f i ct o f l o w e f f i c i e n t l ya n de f f e c t i v e l y ，s p e e du pt h eo p e r a t i o n a le f f i c i e n e yo ft h ee x is t i n g t r a f f i cn e t w o r k t h u st h ei 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 ) i sp r o p o s e d u r b a nt r a f f i cf l o w g u i d a n c es y s t e m ( u t f g s ) i sa ni m p o r t a n tp a r to ft h e i n t e 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 ti sa s ot h ek e yt os o l v i n gc i t yt r a f f i c p r o b e m t h es h o r t e s tp a t ha i g o r i t h mi st h ec o r eo ft h et r a f f i cn e t w o r ka n a l y s i s ， a n dn e t w o r ka n a l y s i si so n ei m p o r t a n tp a r tjns p a t i a la n a l y s i s i na d d i t i o nt h e s h o r le s tp a t hp r o b l e mi st h eb a s i ci nn e t w o r ka n a l y s i s i ti st h ef o u n d a t i o n i nm a n yf i e l d sb yc h o o s i n gt h eo p t i m u mr o u t ea n ditp l a y sa ni m p o r t a n tr o l ei n n e t w o r ka n a l y s i s r h i sp a p e ri sas t u d yo fq u a s i p h y s i c a lm e t h o di nt h ed y n a m i ca n ds h o r t e s t r o u tjn go fr o a dn e t w o r kb a s e do nt r a f f i ci n f o r m a t i o n f i r s t l y ，t h i sp a p e r d e s c l i b e st h es h o r t e s tr o u t ef r o mt h ev i e wo fg r a p ht h e o r yd i s c u s s i n gt h et y p i c a l a l g mi t h mo ft h es t a t i cs h o r t e s tr o u t ea n d t h ed y n a m i cs h o r t e s tr o u t ew i t he n o u g h i n f o r m a t i o n s e c o n d l y ，i td e s c r i b e st h eq u a s i p h y s i c a l m e t h o da n di t s a p p l i c a t i o n ，g i v i n gt h ep r o c e s s t os e t t l et h ep r o b l e mu s i n gq u a s i p h y s i c a l m e t h o d a tl a s t ，i ta n a l y z e st h ed i s a d v a n t a g e so ft h ee x i s t i n ga l g o r i t h mo ft h e s t a t i cs h o r t e s tr o u t ea n dt h ed y n a m i cs h o r t e s tr o u t e o nt h i sb a s i s ，i tg i v e s 型垫尘堂塑：! 兰堡丝苎 塑墨 m e t h o do fs h o r t e s tp a t hu s i n gq u a s i p h y s i c a l t h i sp a p e rg i v e sm e t h o do fs h o r t e s tp a t hu s i n gq u a s i p h y s i c a l i t h a s f a r re a c h i n ga c a d e m i cv a l u ea n dr e a l i s t i cm e a n i n ga n dp r o v i d e sat h e o r e t i c a l b a s et os o l v eu r b a nt r a f f i cp r o b l e m k e y w o r d s ：i n t e l l i g e n tt r a f f i cs y s t e m ，s h o r t e s tp a t h ，t r a f f i ci n f o r m a t i o n d y n a m i c s h o r t e s t p a t h ， s t a t i cs h o r t e s t p a t h ，q u a s i p h y s i c a lm e t h o d q u a s i s o c i o l o g i c a lm e t h o d 山东科技大学硕t ：学位论文 引言 1引言 1 1选题背景 随着科技的飞速发展，计算机技术、网络技术和通讯技术已逐步渗入到交通领域。 随着计算机的迅猛普及以及信息技术的发展，地理信息系统( g e o g r a p h i ci n f o r m a t i o n s y s t e m s ，简称g i s ) 得到日益广泛和深入的应用得到日益广泛和深入的应用。网络分 析作为g i s 最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各 种管网、管线的布局设计中发挥了重要的作用。交通网络在城市发展中占有至关重要的 地位“。，最短路径算法是交通网络分析的核心，现已成为g i s t 中的一个研究热点。 最短路径问题是资源分配、路线设计及分析等优化问题的基础。交通网络分析中的其它 问题，如最可靠路径问题、最大容量路径问题、各种各样的路径导航问题都可以归并到 最短路径问题类型中“1 。网络分析是空间分析的一个重要方面，网络分析中最基本最 关键的问题是最短路径问题。它是许多领域中选择最优问题的基础，在交通网络分析中 占有重要地位。最短路径分析在汽车导航系统以及各种城市应急系统( 如11 0 报警、1 1 9 火警和1 2 0 医疗急救系统) 中的应用非常广泛。而最短路径不仅仅指一般地理意义上的 距离最短，还可以引申到其他方面的度量，如时间、费用等。从而，最短路径问题就成 为最快路径问题、最低费用问题等。其实，无论是距离最短、时间最快还是费用最低， 它们的核心算法都是最短路径算法。经典的最短路径算法一d i j k s t r a 算法是目前多数 系统解决最短路径问题采用的理论基础。 目前提出的解决此类最短路径的算法有多种。但是总体来说这些算法采用的数据结 构及其实现方法由于受到当时计算机硬件发展水平的限制，将空间存储问题放到了一个 很重要的位置，以牺牲适当的时间效率来换取空间节省。算法思想都比较难于理解，实 现起来也比较复杂。鉴于此，本人所承担的课题便是在这样的背景下产生了，用拟物法 对求最短路径进行研究。所谓拟物，就是寻找到与原始问题等价的物理世界并观察这个 世界中物质运动的生动形象，然后从中得出启发并逐步形式化为算法，以求解原来的问 题“。 本文的正是基于交通信息化下的交通道路网络最短路经路径的拟物方法研究也即 坐变型垫查兰堡主兰垡堡兰 ! ! 童 动态嘏短路径的拟物方法研究。求交通道路网络的最短路径是城市交通流诱导系统 u t f g s ( 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 是智能运输系统 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 ns y s t e m ) 的重要组成部分，是解决城市交通问题的 关键。因此，本文拟研究用拟物方法求解动态最短路经，这无疑对解决城市交通问题提 供了一一定的理论基础，因此此文具有一定的学术价值和现实意义。 1 2 研究领域概况 1 2 1 国外的l t s 概述 随着科技的发展，通信、导航、控制、计算机和数据库等技术在交通领域中越来 越广泛的综合利用，正在逐步形成一个跨学科的新兴领域一一智能交通系统i t s ( i n t e l l i g e n tt r a f f i cs y s t e m s ) 或叫智能车辆高速公路系统。其基本含义是利用现代 高新技术对己有的交通设施进行改进，辅之以车辆自动识别系统、电子收费系统、车辆 管理系统、交通控制系统等，以提高道路的利用率，减少车辆行驶时间，增加车辆和行 人和安全性，节省能源、改善环保。在交通管理系统中，无论是处理突发事件还是合理 车辆调度，知道车队中每辆车的位置信息都是车队管理中心的最主要要求之。智能运 输系统作为未来交通发展趋势之一，为解决交通拥挤和公路阻塞造成的汽车延时、汽油 的浪费、汽车废气的排放量都成倍增长造成空气污染等问题提供了有效途径”。 日本i t s 的发展：i t s 在日本的发展始于7 0 年代，从1 9 7 3 年到1 9 7 8 年日本成功 地组织了一个叫动态路径诱导系统的实验。从8 0 年代中期到9 0 年代中期的1 0 年时间， 相继完成了路车间通信系统( r a c s ) 、交通信息通信系统( t i c s ) 、宽区域旅行信息系统、 超智能车辆系统、安全车辆系统及新交通管理系统等方面的研究，1 9 9 4 年1 月成立了 v e r t i s ( 路车交通智能协会) ，1 9 9 5 年7 月成立v i c s ( 道路交通通信系统) 中心，1 9 9 6 年 4 月正式启动v i c s ，先在首都圈内而后推向大阪、名古屋等地，1 9 9 8 年向全国推进。 r 本的v i c s 是i t s 实用化的第1 步，居于世界领先水平。 美国i t s 的发展：美国i t s 的雏形是始于6 0 年代束期的电子路径导向系统( e r g s ) ， 中间停顿了l o 多年，8 0 年代中期加里福尼亚交通部门研究的p a t h f i n d e r 系统获得成 功，此后开展了一系列的这方面的研究，1 9 9 0 年美国运输部成立智能化车辆道路系统 ( i v h s ) 组织，1 9 9 1 年国会制定了i s t e a ( 综合地面运输效率方案) ，1 9 9 4 年i v h s 更名 为i t s ，其实施战略是通过实现面向2 1 世纪的“公路交通智能化”，以便从根本上解 2 坐查至! 垫查兰堡主堂些垒墨 ! 堕 决和减轻事故、混杂、非效率、能源浪费等交通中的各种问题。 欧洲i t s 的发展：t 9 8 8 年由欧洲1 0 多个国家投资5 0 多亿美元，联合执行一项旨 在完善道路设施，提高服务质量的d r i v e 计划，其含义是欧洲用于车辆安全的专用道路 基础设施，现在已经进入第2 阶段的研究开发工作，目前欧洲各国正在进行t e l e m a t i c s 的全面应用开发工作，计划在全欧洲范围内建立专门的交通无线数据通信网。智能交通 系统的交通管理、车辆行驶和电子收费等都围绕t e l e m a t i c s 和全欧无线数据通信网来 开展。欧洲民间业联合搞了一个叫p r o m e t h e u s 的计划，即欧洲高效安全交通系统计划。 除此以外，新兴的工业国家和发展中匡】家也已经，r 始智能交通系统的全面研究和开发。 1 2 2 国内l t s 的发展 i t s 在国内的研究刚刚起步，但中国在交通运输和管理中应用电子信息技术的工作 早在7 0 年代末就已经开始，当时称为交通工程，根据国际上对智能运输系统发展的研 究，可以认为交通工程的研究与应用是智能运输系统初级阶段的工作，根据国际上的这 种观点，中国的i t s 前身或基础工作早在7 0 年代末已经开始，当时交通部公路科学研 究所与北京市公安局合作首次在中国进行计算机控制交通信号的工程试验，8 0 年代初 国家科技攻关项目“津塘疏港公路交通工程研究”，首次在高等级公路上把计算机技 术、通信技术和电子技术用于监视和管理系统。在1 9 8 6 年1 9 9 5 年期间国家在交通 管理系统方面开展了一系列科学研究和工程实施，在城市交通管理、高速公路监控系统、 收费系统、安全保障系统等方面取得多项科研成果，并开发生产了车辆检测器、可交情 报板：可变限速标志、紧急电话、分车型检测仪、通信控制器，监控地图板等多种专用 设备，制定了一系列的标准和规范，无疑这些工作是我们今天进行i t s 研究和开发的基 础。作为其基础的城市交通控制系统的开发研究从7 0 年代就己经开始，如北京、上海 等城市建立的交通信号控制和电视监控系统、警车定位系统、交通地理信息系统，以及 交通事故、车辆和驾驶员档案等静态信息系统等：在某些省市还建立了不停车自动收费 系统和i c 卡驾驶员管理系统。 9 0 年代中期以来，在交通部的组织下，我国交通运输界的科学家和工程技术人员 开始跟踪国际上智能运输系统的发展，交通部将智能运输系统的研究纳入了“公路、水 运科技发展九五计划和2 0 1 0 发展纲要”，1 9 9 5 年交通部科技信息研究所出版了介 绍美国智能运输系统发展和美国“综合地面运输效率法案”的专集，交通部组织部公路 所、部科技信息所、部重庆公路所参加了1 9 9 5 年在日本举行的第二界世界智能运输系 统大会，详细了解了国际i t s 发展动向，与国外有关研究机构和组织建立了联系。1 9 9 5 3 幽垫盔堂堡圭兰竺堡塞 ! li 年交通部又被国家技术监督局确定为道路交通工程标准化委员会依托部门，委员会秘书 处依托在部公路所，同时国家技术监督局确定国际标准化组织智能运输系统技术委员会 ( i s o t c2 0 4 ) 在中国的归口部门为交通部，技术依托单位为交通部公路科学研究所， 目前正在筹备成立i s 0 t c 2 0 4 中国委员会。为了更好的开发和应用智能运输系统，根据 交通郏“九五”科技方针计划，交通部确定在交通部公路科学研究所成立国家智能运 输系统工程研究中心”，该中心目前正在向国家有关部门进行申报。1 9 9 6 年1 月，智 能运输系统t 程研究中心于交通部公路科学研究所正式成立，可以认为中国耐i t s 的重 视并开始对i t s 的研究。在此基础上1 9 9 8 年1 月变通部批准成立了交通智能运输系 统工程研究中心依托单位为交通部公路科学研究所。在交通部的组织下，该中心承担 了部重点科研项目“智能运输系统发展战略研究”。通过该项目的研究，提出我国智能 运输系统发展的整体框架，为交通运输界提供指导性意见。目前该研究已完成并通过交 通部的评审，研究报告的中英文版己正式出版发行。 1 2 3 i t s 主要研究系统 从目前各国开发的i t s 项目的功能上分，i t s 主要研究系统基本上n ，分为以下几类： 先进的交通管理系统a t m s ( a d v a n c e dt r a f f i cm a n a g e m e n ts y s t e m ) 先进的驾驶员信息系统a d i s ( a d v a n c e dd r i v e ri n f o r m a t i c ns y s t e m ) 先进的车辆控制系统a v c s ( a d v a n c e dv e h i c l ec o n t r o ls y s t e m ) 运营车辆调度管理系统c v o m ( c o m m e r c i a lv e h i c l eo p e r a t i o nf l e e t m a n a g e m e n t ) 先进的公共交通系统a p t s ( a d v a n c e dp u b i i ct r a n s p o r t a t i o ns y s t e m ) 先进的乡村交通系统a r t s ( a d v a n c e dr u r a lt r a n s p o r ts y s t e m ) 自动高速公路系统a h s ( a u t o m a t e dh i g h w a ys y s t e m ) i 。3 论文的现实意义 先进的交通管理系统与先进的驾驶员信息系统，二者都提出了对行驶车辆的实时诱 导。因此可以得出：城市交通流诱导系统u t f g s 是i t s 的重要组成部分也是i t s 能 够实施的关键技术。u t f g s 利用全球定位系统( g i o b a lp o s i t i f ) n l n gs y s t e m ，g p s ) 、 电子交通图( d i g i t a lm a p ) 、计算机和先进的通信技术，在车载计算机上自动显示当 前车辆所处的位置、道路网络图和道路交通状况，实时为驾驶员的出行指明最优路线， 并引导驾驶员行驶。近年来随着经济的发展，交通事业也正以前所未有的速度迅猛发展 着。新建道路和其它各种交通设施越来越多，单行线、禁行线、路口禁止转向等交通管 理措施也被越柬越广泛地采用。这对于出行者来说，一方面为他们提供了更大的出行路 理措施也被越柬越广泛地采用。这对于出行者来说，一方面为他们提供了更大的出行路 d 坐查型垫查堂堡主兰垡笙塞! ! 直 线的选择余地，保证了道路交通网的畅通，但同时也增大了其出行的复杂性。据美国联 邦公路局进行的一项研究表明非商用车辆全部出行距离的约7 以及全部行驶时间的 1 2 以上由于缺乏良好的导航和路线引导而被浪费掉了，这无疑加剧了拥堵和交通事 故。正因如此，出行者在出行时迫切需要个能够使其避免拥堵，避免违规驾驶，安全、 便利、快捷地到达目的地的出行服务。而对于交通管理者来说，也希望交通流能够尽量 合理地分配在整个路网上。因此，一套行之有效的行车路线优化及其实施技术无疑成为 动态路径诱导系统的关键。 在现有的技术经济条件下，研究设计适用于中的行车路线优化模型、算法和实施技 术就是行车路线优化及其实施技术。行车路线优化技术根据路网的车流合理地引导车辆 行驶，减少行车延误，并且优化交通流在整个路网上的分配。通过实时行驶诱导，可以 使驾驶员避免迷路和错误驾驶，一方面减少单个车辆在路网中的滞留时间，从而改善整 个路网的交通拥挤状况；另一方面，顺利地驾驶可以稳定驾驶员的心理，在一定程度上 降低事故发生率，提高交通安全。具备了良好的行车路线优化技术，动态路径诱导系统 就可以成为减少交通拥挤的一个高效而可行的方式，不仅可带来巨大的经济效益，还可 减少环境污染，基于实时行车路线优化技术的动态路径诱导系统将成为一种崭新的交通 模式：。 而最短路经问题尤其是动态路径问题动态路径诱导系统的部分。最短路径问题一 直是计算机科学、运筹学、交通工程学、地理信息学等学科的一个研究热点。动态最短 路径的最优解的求得是关键，动态最短路经的求解方法有许多但是有许多的不足。而拟 物方法与最短路径的结合使得求解最短路径的问题变得简单化，本人的课题“动态最短 路径的拟物方法的研究“正是在这样的前提下提出的。因此本文的完成将对于研究交通 诱导系统的实际应用提供更完整的理论指导和并具有一定的实用价值。 1 4 本文主要内容 本文分析了最短路径的有关问题、拟物拟人方法等问题，最后探讨了拟物法求静态 最短路径及拟物法求动态最短路径的有关问题，在此基础上根据交通信息对城市交通的 影响，对高度信息化下的用拟物法求动态最短路径做了探讨。主要研究的内容如下： 最短路径 静态最短路径 动态最短路径 5 山东科技大学硕士学位论文 引言 拟物方法 静态最短路径的拟物方法研究 动态最短路径的拟物方法研究 6 山东科技人学硕士学位论文 网络的最短路经 2 网络的最短路径 2 1 图的概念 图论是一个新的数学分支，也是一门很有实用价值的学科，它在自然科学、社会科 学等各领域均有很多应用。近年来它受计算机科学蓬勃发展的刺激，发展极其迅速，应 用范围不断扩大，己渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科 学以及数学的其它分枝中。特别在计算机科学中，如形式语言、数据结构、操作系统、 分布式系统、计算机网络等方面均扮演着重要的角色。 世界上许多事物以及它们之间的联系都可以用图形直观地表示。这时人们往往用结 点表示事物，用边表示它们之间的联系。这种由结点和边构成的图形就是图论所研究的 对象。与几何图形不同，我们不关心图形结点的位置，也不关心边的长短、形状，只关 心结点与结点的联结关系。这就是说，我们要研究的图是不同于几何图形的另一种数学 结构，它由如下定义给出： 定义l ：二元组( v ( g ) ，e ( g ) ) 称为图( g r a p h ) 。其中v ( g ) 是一个非空的结点( 或叫 顶点) 集合，其成员称为结点或顶点( ( n o d e so rv e r t i c e s ) e ( g ) 是边( 或叫弧) 的集合， 其成员称为边或弧( e d g e so ra r c s ) 。常用g = ( v ， e ) 表示图。 图可以分为有限图与无限图两类。本论文只讨论有限图，即v 和e 都是有限集。给 定某个图g = ( v ，e ) ，如果不加特殊说明，就认为v = v t ，v z ，v 。，v 。 ，e = e ， e z ， e 。，e 。 ，即结点数i p l = n ，l e = m 。“ 2 2 最短路径及其分类 2 2 1 最短路径 在实际生活中常见的最短路径问题描述：如司机用汽车运输货物从a 地到b 地，司 机会考虑走路程最短或时间最少的道路，这是考虑路程或时间的最短路径问题；又如要 在a 地到b 地之间铺设煤气管道，在a ，b 两地间的长方形地区划分格子点，根据地形、 土壤、江河、农田、村庄、郊区、公路等各种情况，估计一格子点至另一格子点的铺设 费用。求由a 地到b 地铺设煤气管道经过哪些格子点使总的造价最小，这是考虑费用的 最短路径问题；最短路问题可以用来解决许多生产和生活问题，如：线路安排、设备更 7 些堡型垫i ! ! 鎏主兰些堡兰 型丝堕墨堑堕丝 新、厂区布局、城市规划、电子导航、公交转车等，相应地，最短路径问题就成了最快 路径问题、最低费用问题等“。 最短路径问题一直是计算机科学、运筹学、交通工程学、地理信息学等学科的个 研究热点。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最 短路径算法不断涌现，各具特色“。网络分析作为地理信息系统中最主要的功能之一， 在电子导航、交通旅游及管网管理等领域中发挥着越来越重要的作用。在网络分析中， 最基本、最关键的问题是最短路径问题。最短路径般指地理意义上的距离最短，也可 以引伸到其它的度量，如时间最短、费用最低等，但其核心算法都是最短路径算法“。 我们知道，点、线、及其拓扑关系组成了网络。在交通网络分析中，每一个交叉路 口可抽象为一个结点对象，两结点之间的连线为弧段，弧段的长度为该边的权重。采用 这种“结点一弧段”的数据组织方式，按照弧段的起始结点与终止结点所形成的路径， 分析网络中的无向边，抽象出网络结构模型( 网络描述矩阵) ，即可运用特定的算法求得 道路网络图中任意两结点间的最短路径。交通路网可以画成带权的图，详细描述如下： 结点：道路的交叉口或断头路的终点。 边弧：两结点之间的路段称为边，若规定了路段的方向，则称为弧。 边( 弧) 的权：是路段某个或某些特征属性的量化表示。根据不同的最优目标，可 以选择不同的路段属性，如路段长度、路段平均行程时问等作为该路段对应的边( 弧) 的权，或称为道路权重。 规定了结点、边( 弧) 及其权值之后，路网就可以抽象为一个赋权无向图或赋权有 向图。从而确定路网中某两地间的最优路线便转化为图论中的最短路问题。其中有向图 和无向图的区别在于前者虽然增大了路网的存储量，但适用于弧的两个方向权值大小不 同的情况，由于一般来说路段两个方向的交通流情况并不一致，当采用与交通流有关的 路阻函数时，应采用有向图表示路网。另外，有向图便于处理单行线、路口禁止转向等 特殊情况。 赋权图的最短路径：设图g 中的每一条边( v 。，v ，) ，对应有一个数w m 。，称为该 边的权或长。图g 连同其各边的权被称为赋权图。一条道路c = v ，v ”，v 。的长是l 上所有长的和。即w 。，+ w 。v ? ) + + w 。m 。在赋权图中给定两点v 。和v ，所谓最 短路径问题就是在( v 。，v ) 的道路集合 p 。) 中，寻求权最小的路径，该路径称为v ，到 v 。的最短路径。该路径长度，即最短距离记作d m 。赋权图中的权可以是两个顶点间 的距离，或者途中所用的时间或者交通费用等。 8 当至型塾查兰堡主兰垡丝兰 塑些塑里塑堕丝 有向图的最短路径： 一个图g ( v ， e ) 是由有穷而非空的顶点集v 和边集e 所组成，如果边是顶点的有 序对( v ， v ，) ， ( v ， v j ) e ：v ， v 。e v ，则说这个图是有向的。一个城市交 通网可以用一个有向加权图g = ( v ，e ，w ) 来表示。其中v 为顶点集，v = v i i i = l ，2 ， n ；e 为边集e 2 e ( v i ，v j ) i v i ，v j v ) ，w 为权集，w = w ( v i ，v j ) iv i ，v j e v 。图g 的一个边序列e 。，e - ，e 。，e 。称为图g 从u 到v 。结点的一条路经：从v 0 到v 。的所有 路径中，权w ( v 0 ，v - ) 最小的路径称为从v 。到v 。的最短路径，记为p 。其长度为： d ( ，o ，k ) = m i n w m o v k ) lv o ，v k v ：i = l ，2 ，】n 7 1 。 2 2 2 最短路径分类 上面提到了一个城市交通网可以用一个有向加权图来表示。道路权重的标定决定了 最短路路径搜索的依据，也就是所谓的搜索指标。常用的路权指标有两地问的距离，或 者途中所用的时间，或者交通费用等等。 根据权重是否随着时间发生改变，可以把交通网中的最短路径分为静态最短路径和 动态最短路径两种。 静态的最短路径问题可分为五种类型“，一是网络中给定两个顶点的最短路径；二 是某一顶点到其它所有顶点之间的最短路径。又称为单源点最短路径问题( t h es i n g l e s o u r c es h o r t e s tp a t hp r o b l e m ，简称s s s p ) ；三是网络中各对顶点之间的最短距离： 四是第k 短最短路径：五是规定顶点之间通过某些规定顶点的最短路径。其中又可衍生 出其它一些特殊的最短路径问题，如限制弧段数目最短路径、含环路径等。其分类见图 2 1 。 其中，尤以单源点最短路径问题( s s s p ) 为基础，解决了单源点最短路径问题，第一 种问题就自然解决了，而其它几种问题可由s s s p 算法参考懈决。 9 旦堕堡堕型苎堑坠兰兰生堂皇二一一 堕垒塑墨堑堕丝 图2 1 最短路径的分类 f i g 2 1t h es o r to f t h es h o r t e s tp a r t h 2 3 静态最短路径 2 3 1 静态最短路径 从上面分析可知：一个城市交通网可以用一个有向加权图g ：( v ，e ，w ) 来表示。 权重不随时间发生改变的最短路径问题就是静态最短路径。 2 3 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 算法，a $ 算 法等。 2 3 2 1 传统的d i j k s t r a 最短路径算法 据统计，目前提出的最短路径的算法大约有1 7 种。f b e n j a m i n z h a n 等人对其中的 1 5 种进行了测试，结果显示有3 种效果比较好，它们分别是：t q q ( g r a p hg r o w t hw i t h t w oq u e u e s ) 、d k a ( t h ed i j k s t r a sa l g o r i t h mi m p l e m e n t e dw i t ha p p r o x i m a t eb u c k e t s ) 1 0 些查型垫查鲎塑主兰垡堕壅 塑堡堕墨望堕丝 以及d k o ( t h ed i j k s t r a sa l g o r i t h mi m p l e m e n t e dw i t hd o u b l eb u c k e t s ) ，这些算法 的具体内容可以参见文献汹1 。其中t q q 算法的基础是图增长理论，较适合于计算单源点 到其他所有点间的最短距离；后两种算法则是基于d i j k s t r a 的算法，更适合于计算两 点问的最短路径问题1 。总体来说，这些算法采用的数据结构及其实现方法由于受到 当时汁算机硬件发展水平的限制，将空间存储问题放到了一个很重要的位置，以牺牲适 当的时间效率来换取空间节省。目前，空间存储问题已不是要考虑的主要问题，因此有 必要对已有的算法重新进行考虑并进行改进，可以用空间换时间来提高最短路径算法的 效率”。 传统的最短路径算法中，d i j k s t r a 算法用于计算一个源节点到其它节点的最短路 径，有较高的应用价值。1 9 9 6 年z h a n 和n o o n 使用实际交通网络测试了1 7 种算法中的 1 5 种，测试结果表明：计算一点到所有其它点的最短路径最快的算法是d i j k s t r a 算法。 在论文中主要阐述d i j k s t r a 算法。 d i j k s t r a 算法的基本思想是：设从顶点v 1 出发，找出从v l 到图中其它各顶点的 最短路径。把图中的所有顶点分为两组，第一组是已经确定最短路径的顶点，第二组是 尚未确定最短路径的顶点，按最短路径长度递增的顺序逐个把第二组的顶点加到第一组 中去，直到从v 1 出发可以到达的所有顶点都包括在第一组中。在这个过程中，总保持 从v 到第一组的各顶点的最短路径长度，都不大于从v 1 到第二组的任何顶点的最短路 径长度，另外，每个顶点对应一个距离值，第一组的顶点对应的距离值就是从v l 到此 顶点的最短路径长度，第二组的顶点对应的距离值是从v l 到此顶点的只包括第一组的 顶点为中间顶点的最短路径长度。 d i j k s t r a 算法实现：一开始第一组只包括顶点v 1 ，第二组包括其它所有顶点。v 1 对应的距离值为0 ，第二组的顶点对应的距离值是这样确定的：若图中有弧 ， 则v j 的距离值为此弧的权值，否则v j 的距离为一个很大的数( 大于所有顶点的路径长 度即可) ，然后每次从第二组的顶点中选一个距离值为最小的v m 加入到第一组中。每 往第一组中加入一个顶点v m ，就要对第二组的各个顶点的距离值进行一次修正。若加 进v m 做中间结点，使从v 1 到v j 的最短路径比不加v m 的路径短，则要修正v j 的距离 值。修改后再选距离最小的顶点加到第一组中。如此进行下去，直到图中所有顶点都包 括在第一组中，或再也没有加入到第一组的顶点存在为止。 2 3 2 2 改进的d i j k s t r a 算法 d i j k s t r a 算法的标号方法 1 1 山东科技大学硕士学位论文 网络的最短路经 d i j k s t r a 算法的标号输出是一个_ 最短代价树，每个节点的标号有3 种：d ( i ) ，p ( i ) 和s ( i ) 。其中d ( i ) 表示第i 个节点与源节点之间的最短代价；p ( i ) 表示按照当前的最 短代价路径，第i 个节点在最短代价树中的父节点号；s ( i ) 表示该节点的状态，分为未 标号节点、临时标号节点和永久标号节点3 种状态。 改进算法的相关定义： 定义1 图g 的节点用v 表示；弧用e 表示；曲( v ) 表示在图g 中顶点v 的度；v ( g ) 表 示图g 的节点数目；e ( g ) 表示图g 的边的数目。 定义2 一个平面图g 把平面划分成若干个连通区域；这些区域的闭包称为图g 的面， 表示为f 。图g 的所有面的个数表示为审( g ) ；图g 所有面的集合表示为f ( g ) ；d g ( f ) 表示图g 的面f 的度，即在图g 中与面f 相关联的边的数目。 定义3 给出平面图g ，可以定义另一个图g 如下：对于g 的每个面f ，都有g 的 顶点f 与之对应，对于g 的每条边e ，都有g 的边e 与之对应：g 中顶点f 和g 由边e 连接，当且仅当g 中与顶点f 和g 对应的面f 和g 被边e 分隔图g 称为g 的 对偶图。 定理1由上面的定义可以得到等式v ( g ) = m ( g ) ，e ( g ) = e ( g ) ，d g ( f ) = d g ( f ) 对所有f f ( g ) 成立。 定理2图g 中所有节点的度数和为图g 中弧数的2 倍。 定理3 若g 是平面图，则有 d ( ，) = 2 ref 定理4 若g 是连通平面图，则v ( g ) 一e ( g ) + 中( g ) = 2 ( 欧拉公式) 。 下面证明连通简单平面图的节点的平均度小于一个常数。 证明：若v ( g ) 1 3 成立，并且有 d ( 厂) 荔 f e f 根据定理3 有2e ( g ) 3 中( g ) ，于是由定理4 可得v ( g ) 一( g ) 十2e ( a ) 3 2 即( g ) 3 v ( g ) 一6 ，根据定理2 有 d ( v ) 6 v ( g ) 1 2 v e g 即图g 的每个得到的平均度小于6 。 坐壅型垫查堂堡主堂些堡奎 型竺塑墨堑堕丝 根据以上证明结果，本算法采用了与传统的d i j k s t r a 算法使用的表示方法基本一 致的拓扑网络表示方法。即使用两个数组表示拓扑结构：一个数组用于存储所有与节点 相关的数据，包括节点的标识、节点的邻接弧数目以及用一个长度为7 的数组保存与节 点相关联的弧的序号，对于个别长度大于7 的节点增加一个单链表指针指向保存其它节 点的链表。这样设计的目的是为了加快存取与节点相关联的弧的速度；另个数组用于 存储与弧相关联的数据”“。 节点选择方法及数据结构： 从上面的讨论中可以看到，d i j k s t r a 算法运行速度的关键在于如何选取下一个要 扩展的节点，文中使用了b f s 搜索策略。 在标号过