智能交通系统中最优路径选择的设计与实现.pdf

《智能交通系统中最优路径选择的设计与实现.pdf》由会员分享，可在线阅读，更多相关《智能交通系统中最优路径选择的设计与实现.pdf（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、专业学位硕士学位论文智能交通系统中最优路径选择的设计与实现D e s i g na n dI m p l e m e n t a t i o no ft h eO p t i m a lP a t hi nI 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 s作者姓名：渣态工程领域：筮仕王猩学号：4 1 0 1 7 3 7 3指导教师：一鄞丞完成日期：呈Q!墨生墨旦史连理工大学D a l i a nU n i v e r s i t yo fT e c h n o l o g y学位论文独创性声明作者郑重声明：所呈交的学位论文

2、，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。若有不实之处，本人愿意承担相关法律责任。学位论文题目：作者签名o 大连理工大学专业学位硕士学位论文摘要智能交通系统中的核心问题是最优路径选择问题。本文分析了交通道路网络的具体特点，主要包括线性分布特点、网络分布特点、分段分布特点、动态性特点和车辆行驶的自主性特点等。将交通网络抽象成一个由边和节点组成的图，并根据图论的相关理论和知识构建

3、起交通网络模型，包括交通道路节点模型，交叉口和道路模型，并对上述道路模型信息进行存储，以构建好的交通道路模型为基础研究智能交通系统中的最优路径问题。考虑了实际道路中存在一定的交通阻抗，是算法更具有应用价值，在D i j k s t r a 算法的基础上进行了改进，缩短了道路搜索时问，提高了最优路径选择的效率。数据库的选择与设计是系统实现中不可或缺的重要组成部分，优秀的数据库选择和设计方案能够提高最优路径选择的效率、也提高了整个智能交通系统的工作效率。本文使用了G I S 数据模型与数据库的管理设计，主要包括G I S 数据的简介、选择O r a c l e 的理由、G I S 数据向O r a

4、 c l e 中的导入和存储、O r a c l e 中G I S 数据的访问和维护。对道路交通系统的建模、最优路径选择算法的研究以及数据库的开发设计目的是建立一套接近实际情况的最优路径选择系统。本文利用M a p l n f o 软件绘制交通系统的电子地图，开发工具使用G I S 控件M a p X 与V i s u a lC+。将经典的D i j k s t r a 算法和改进的O i j k s t r a 算法进行编码实现，使之在最优路径选择系统中正确运行。关键词：智能交通系统，最优路径，G I S 数据，系统设计智能交通系统中最优路径选择的设计与实现D e s i g na n dI

5、 m p l e m e n t a t i o no f t h eO p t i m a lP a t hi nI 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 sA b s t r a c tT h eo p t i m a lp a t hi sa ni m p o r t a n tp a r to ft 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 T h i sp a p e ra n a l y z e st h es p e c

6、 i f i cc h a r a c t e r i s t i c so ft h et r a f f i ca n dr o a dn e t w o r k,i n c l u d i n gl i n e a rd i s t r i b u t i o nc h a r a c t e r i s t i c so fn e t w o r kd i s t r i b u t i o nc h a r a c t e r i s t i c s，s e g m e n t e dd i s t r i b u t i o nc h a r a c t e r i s t i c

7、 s，d y n a m i cc h a r a c t e r i s t i c so fv e h i c l e sa u t o n o m o u sf e a t u r e s A b s t r a c tt r a n s p o r t a t i o nn e t w o r ka sag r a p ho fe d g e sa n dn o d e s，a n db u i l dat r a n s p o r t a t i o nn e t w o r km o d e lb a s e do ng r a p ht h e o r yt h e o r y

8、a n dk n o w l e d g e，i n c l u d i n gt r a f f i cr o a dn o d em o d e l,i n t e r s e c t i o n sa n dr o a dm o d e l,a n ds t o r a g eo f t h er o a dm o d e li n f o r m a t i o nt ob u i l dg o o dt r a f f i cr o a dm o d e lf o rb a s i cr e s e a r c hi ni n t e l l i g e n tt r a n s p

9、 o r t a t i o ns y s t e m s，t h eo p t i m a lp a t h C o n s i d e r i n gt h ea c t u a lr o a dt r a f f i ci m p e d a n c e，i st h ea l g o r i t h mm o r ea p p l i c a t i o ni m p r o v e dv a l u eo nt h eb a s i so ft h eO i j k s t r aa l g o r i t h m,s h o r t e n i n gt h ep a t hs e

10、 a r c ht i m e，a n dt oi m p r o v et h ee f f i c i e n c yo f t h es e l e c t i o no f t h eo p t i m a lp a t h T h ed a t a b a s ei sa ni m p o r t a n tp a r to fa ni n t e g r a ls y s t e md e s i g na n di m p l e m e n t a t i o n,d a t a b a s es e l e c t i o na n dd e s i g no f ad i

11、r e c ti m p a c to nt h ee f f i c i e n c yo f t h ep a t hp l a n n i n gs y s t e m T h i sa r t i c l eU s e St h ed e s i g no faG I Sd a t am o d e la n dd a t a b a s em a n a g e m e n t，m a i n l yi n c l u d i n gt h ei n t r o d u c t i o no f G I Sd a t a,s e l e c tO r a c l er e a s o

12、 ni m p o r t e da n ds t o r e di nt h eO r a c l e，G I Sd a t a,t h eO r a e l eG I Sd a t aa c c e s sa n dm a i n t e n a n c e M o d e l i n go fr o a dt r a f f i cs y s t e m,t h eo p t i m a lp a t hs e l e c t i o na l g o r i t h m 弱w e l la st h ed e v e l o p m e n to ft h ed a t a b a s

13、 ei sd e s i g n e dt oe s t a b l i s ht h eo p t i m a lr o u t es e l e c t i o ns y s t e ms e tc l o s et ot h ea c t u a ls i t u a t i o n D r a w ne l e c t r o n i cm a pi sm a d eb yM a p l n f os o t t w a r ed e v e l o p m e n tt o o l sa n dt h et o o l su s cG I Sc o m p o n e n tM a

14、p Xa n dV i s u a lC+C l a s s i c a lD i j k s t r aa l g o r i t h ma n di m p r o v e dD i j k s t r aa l g o r i t h mw e r ei m p l e m e n t e d T h eo p t i m a lp a t hs e l e c t i o ns y s t e mi sp r o v e dc o r r e c t l y K 锣W o r d 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 nS

15、y s t e m s；O p t i m a lp a t h；G I Sd a t a；S y s t e md e s i g nI I大连理工大学专业学位硕士学位论文目录摘要IA b s t r a c t I I引言ll 基础知识l O1 1 路径优化算法概述一1 01 1 1F l o y d 算法1 01 1 2D i j k s t r a 算法1l1 1 3G P S R 算法1 21 2图论简介1 21 2 1 图的概念一1 31 2 2 图的表示1 31 2 3 图的存储1 51 3 本章小结1 62 最优路径1 72 1 城市交通模型建立1 72 1 1 道路节点模型1

16、 82 1 2 交叉口和道路模型1 92 2 交通模型数据存储一2 l2 2 1 数据预处理2 12 2 2 交通路径模型建立与数据存储2 l2 3 最优路径选择2 32 3 1 最优路径的求解过程2 32 3 2 经典D i j k s t r a 算法分析2 42 3 3 交通阻抗分析2 52 3 4D i i k s 咖算法改进2 82 4 本章小结2 93Gls 数据模型和数据库设计3 03 1G I S 数据模型建立3 03 1 1 空间数据模型3 03 1 2 属性数据模型3 23 2G I S 数据的管理与组织3 2-智能交通系统中最优路径选择的设计与实现3 2 1G I S 数

17、据管理原则呻1 3 33 2 2G I S 数据的组织3 33 3O r a c l eS p a t i a l 简介。3 43 4 空间数据向O r a c l e 中的导入。3 73 5G I S 数据在0 1 T,R l e 中的存储3 73 5 1 道路数据在O r a c l e 中的存储3 83 5 2 节点数据在O r a c l e 中的存储4 03 5 3 分层道路数据在O r a c l e 中的存储4 13 5 4 多比例尺道路数据在O r a c l e 中的存储4 13 6O r e a l e 中G I S 数据的访问。4 l3 7O r c a l e 中G I

18、 S 数据的维护一4 23 7 1 数据库表的创建、删除一4 23 7 2 数据库记录的添加、删除和修改一4 23 8 本章小结一4 24 路径优化算法系统实现4 34 1电子地图制作4 34 1 1 电子地图制作的原则4 34 1 2M a p I n f o 软件概述4 34 1 3M a p l n f o 电子地图的绘制4 34 1 5 电子地图的实现4 64 2 开发工具选择一4 64 2 1M a p X 的特点4 64 2 2V i s u a lC+4 74 3 仿真结果与分析一4 74 4 本章小结4 8结论一4 9参考文献5 0致谢一5 4大连理工大学学位论文版权使用授权书

19、5 5I V大连理工大学专业学位硕士学位论文引言随着我国改革开放经济的发展，人口数量的不断增多，城市的数量和规模不断增大和增多，城市化程度和趋势十分明显，城市交通问题成为目前影响和制约我国经济发展和社会进步的主要因素。近年来，我国G D P 以8-1 0 9 6 的较高的速度增长，城市化程度逐渐提高，社会经济迅速发展，这对城市交通系统的要求提出了挑战，而我国大部分城市都集中在东部沿海地区，人口密度和区域面积与其他地区不成比例。不论是上海北京等特大城市还是其他省会城市或地级市，普遍存在交通问题，城市车辆不断增多，人口越发密集，道路环境不断恶化等原因都是导致城市交通问题的主要方面。主要体现在分时段

20、的交通拥堵、交通事故频发和环境污染严重等。交通运输是国民经济发展的重要支柱。长期以来，西方发达国家和发展中国家的大中城市都不同程度的存在交通问题，如车辆行驶缓慢、交通拥挤、交通事故频繁以及由于交通不畅引起的交通事故人员伤亡和环境污染等。这些问题的解决需依靠各种信息技术来解决口1。交通拥堵已经成为制约交通运输事业发展的瓶颈，不仅降低了物资运输或人员交流的效率，影响人们正常出行，并且很大程度上降低社会发展效率。统计了我国大约6 6 7 个城市中，在上下班或者假日的交通高峰期，约有6 7 的道路机动车行驶变得缓慢，甚至拥堵或发生交通事故。一些大中城市交通环境脆弱，由于道路设计或交通规则不合理，导致高

21、峰时段交通拥堵严重，如果城市中某一条主干道发生交通事故而交通堵塞则可常常引发大面积、长时间的交通拥堵，尤其是特大城市的主干道和次干道的交通流经常在高峰时段已达到饱和或超饱和状态(如上海或北京)，正常的经济往来，货物运输，市民出行等会受到严重影响。公路或铁路的交通系统建设是我国针对交通运输的基础设施建设，在国家的经济发展中起到不可替代的作用，是连接两个城市之间的货物、人员、信息流的大动脉，较好的公路交通环境对于各个地区的经济建设、减小城乡之间的经济差距起到了非常好的促进作用乜1。随着我国现代化建设的不断深化，城市化水平不断提高，城市规模和人口数量也在不断的扩大，这使得机动车的数量也在不断增加，在

22、不断提高人民生活水平的同时，人们的日常活动也在急剧增加，这给地区之问的交通流通带来很大压力。由于发展的需求，城市的规模和人口不断扩大，而交通道路资源是有限的，交通拥堵，意外交通事故和交通环境的污染等一系列问题由此产生，尤其是北京、上海等大城市，这些交通问题尤其突出。而造成交通拥堵、交通事故和环境污染的另一个重要原因是信息管理的缺失和不够重视。经过近几年的发展，政府部门对I T 基础设施建设已经初具规模，我国信息化产智能交通系统中最优路径选择的设计与实现业建设正处在由信息资源建设向信息资源管理转换的重要时期。交通拥堵交通事故和交通污染对一个城市造成的影响包括，增加了城市运行的成本，降低了各项服务

23、质量，对于医疗救护、消防和警务事务的影响极为致命。交通事故的数量和频率在国内大中城市每年都会不同程度的增加，事故死亡率为8-1 0 7 6 左右。交通设旅建设、管理和规划中需要的信息具有范围广、数据量大、复杂多变等特点，且绝大多数信息拥有空问意义上的特性。寻求一种对数据采集、数据挖掘和整合、数据存储和管理能够有效管理，并能将这些信息作为布局规划、交通建设、战略决策和信息管理等方面的工具成为人们不断追求的目标。在我国，几乎绝大多数社会信息资源和数据库掌握在各级政府部门手中。联合国教科文组织曾经对政府部门掌握的社会信息数据进行统计和分析，其研究的报告显示，7 0 8 5 的社会信息是有对经济发展有

24、价值的。对中国来说，政府部门及其相关单位掌握这国内社会信息的6 0 9 6 以上，而这些大量的宝贵的信息资源并没有被政府部门充分利用口1。由于近几年我国政府认识到这一点，加大交通系统管理的投入，在交通系统的管理方面虽有较大进展，但信息资源管理中仍然存在着信息量缺乏严重、质量提高速度慢、管理结构不平衡、流动不通畅和体制不健全、机制含糊、标准不统一等问题。由于国家战略和保密政务信息公开制度不完善，各部门沟通不够导致信息资源采集重复，管理机制不够先进导致开发利用的市场化、产业化程度偏低等缺点。通过最近一个世纪的发展，西方发达国家达到鼎盛，从这些国家城市化的发展历史来看，机动车数量的增长永远快于道路加

25、宽加多的速度，增加停车场数量等基础设施建设来解决当前出现的交通问题。解决这些交通问题的最有效、最根本的途径还是通过加快高新技术管理，通过信息技术来提高和完善交通信息管理的能力，提高交通运输的效率。解决交通问题出现了新的思路和办法，因此智能交通系统(I n i e l l i g e n iT r a n s p o r t a t i o ns y s t e m，I T S)H 1 的诞生为解决交通问题提供了全新的方式。随着计算机技术和电子技术的不断发展，以及电子地图测绘技术的不断进步，这使得地理信息系统也得到了长足的进步，这些技术的发展都给智能交通系统的发展奠定了良好的基础。通过中西交通道

26、路系统的比较，我国城市交通系统的主要问题包括陆1 交通管理技术落后，交通系统的发展永远跟不上社会发展的要求，交通系统供需矛盾突出。为大道交通系统的可持续发展，从根本上解决问题上述交通拥堵问题，并保持大中城市交通可持续发展带动城市的可持续反战，除了合理地进行交通道路等基础设施建设外，另一个切实可行的办法就是引进西方先进的高科技管理技术改进我们的交通系统，并使其符合我国国情，建立高性能高效率的智能城市交通系统(I T S)。智能交通系统(I T S)通过充2大连理工大学专业学位硕士学位论文分发挥现有交通资源潜力和系统内部协同作用产生的效力，能够为城市交通提供更安全、更舒适、更高效率和更高品质的新型

27、城市交通系统嘲。智能交通系统的目标是利用现金的计算机技术和先进的网络管理来减少交通拥堵、交通事故和环境污染，与此同时，交通系统能够有效的正常的运行。在交通、计算机、电子通信、信息技术和系统科学与工程应用领域中，智能交通系统是日前许多国内外学者和研究机构集中、深入的研究领域之一，具有非常好的发展前景。车辆导航系统(v N S)是城市智能交通系统的核心内容之一，主要依据实时的路况信息来提高道路的通行能力，是减少交通拥堵、以外交通事故和环境污染的有效办法。随着交通事业的不断发展，基础设施建设的不断完善，城市交通的网络建设步伐的加快，交通设旆的不断完善，以及交通管理措施的不断细化、改进和应用，驾驶员有

28、了更多的自主选择空问。但是如果缺少路况的引导方法，这些资源将会被浪费、而且交通拥堵、交通事故和环境污染也会不断增加。因此，对目前的交通系统来说，急需一套行之有效的车辆管理和导航系统来弥补这个不足，是驾驶员了解实时路况，避免交通拥堵，这样能够减少交通事故的发生，减少环境污染，安全方便的到达目的地。在西方发达国家的车辆导航系统研究中，所能够实现的也只是以同时期的历史数据为导航依据，而基于实时路况信息的动态导航系统还处在研究当中，没有达到应用水平。在我国，由于受到经济水平、技术条件和交通道路特点的限制，对只能交通系统的研究和开发应用起步晚于西方发达国家，国外的某些技术应用也不能完全使用于中国的特殊复

29、杂的交通环境，不能照搬或照抄西方国家交通系统的制度和理念。随着我国交通运输业的不断发展，交通环境日益恶化的今天，研究出一套能够适应我国国情的现代智能交通系统和车辆导航系统，使之能够为人们出行提供重要的交通信息，避免交通拥堵，减少交通事故，为驾驶者提供最佳的驾驶路径，达到交通的路网畅通已经迫在眉睫。如果能够对车辆导航系统提供行之有效的最佳路径选择算法，就能为人们出行提供有效、合理有效的出行路径，从而提高交通系统运行的效率。最佳路径选择问题是智能交通系统中的重要组成部分，也是交通地理信息系统研究中的一个热点问题之一，是出行路径设计与优化、现有有限资源重新利用和分配等问题的基础。因此最优路径选择与优

30、化问题是实时的动态交通系统中具有具有重要现实意义的研究课题。目前国内外已经有许多学者和研究机构对最佳路径选择做了深入研究，并取得了很好的效果。最佳路劲的算法研究不仅可以应用在交通网络系统中，而且对出行决策、校车路径查询、快递物流、资源分配等方面也有很好的应用价值。道路交通系统中最佳路径选择的研究能够为综合信息管理和只能决策提供先进、科学和行之有效的判决依据；为人们出行提供便利的交通运输条件；为车辆的运行提供安智能交通系统中最优路径选择的设计与实现全保障：提高了现代交通道路的利用效率；帮助车辆减少尾气排放和燃油等资源的消耗：对于建设资源节约型社会具有划时代的意义。欧美等西方发达国家在近一个世纪的

31、飞速发展中，交通拥堵问题在以前和现在都是制约其发展的主要方面，因此很早就对智能交通系统的研究投入大量的人力、物力和财力。美国智能交通系统的发展尤为突出，几个发展较快的方面分别是车辆安全系统、公路和车辆管理系统、电子收费系统、自动定位系统和商业车辆管理系统。美国先后分别颁布了对其智能交通系统发展具有重要意义的两部法律，即1 9 9 1 年颁布的综合运输效率化法案6(I S T E A，I n t e r m o d a lS u r f a c eT r a n s p o r t a ti o nE f f i e c i e n c yA c t)和1 9 9 8 年颁布的2 l 世纪的运输

32、平衡法案(TE A-2 1，t h eT r a n s p o r t a ti o nE q u k yA c tf o rt h e 2 1 s tC e n t u r y)，这两部道路交通建设法律从法律的角度和较高的高度统一规划智能交通系统(I T S)的发展，制定投资计划。继美国对智能交通系统的研究开展之后，欧洲、日本等国家对智能交通系统的相关领域的研究开发也相继展开。经过数十年的发展，美、欧、日已经成为国际智能交通系统研究的主要研究开发基地。另外一些国家和地区的智能交通系统(I T S)研究也取得长足的发展，如加拿大、澳大利亚、韩国等。欧洲在智能交通系统(I T S)方面研究的进

33、展介于美国和日本之间。由于欧盟中各个国家对交通系统需求的不一致，导致对I I 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，A V C S)、旅行信息系统(A d v a n c e dT r a v e lI n f o r m a t i o ns y s t e m s，A T I S)、电子收费系统(A d v a n c e dE l e c t r o n i cT o l lC o l

34、l e c t i o nS y s t e m)、商业车辆运行系统(A d v a n c e dC o m m e r e i a lV e h i c l e sO p e r a t i n gS y s t e m，A C V o S)等方面，前景十分可观。日本目前有五个国家部门负责智能交通系统的建设和相关活动，这五个部门分别为：建设省、警视厅、国际贸易和工业省、运输省以及邮电省阻1。这五个部门同时经由其他的组织来促进I T S 的发展，例如车辆、道路和交通智能化社团(t h eV e h i c l e，R o a da n dT r a f f i cI n t e l l i

35、g e n c eS o c i e t y，简称V E R T I S，一个致力于推动I T S 发展的行业学术组织)和I S O 厂r C2 0 4 全国委员会(I s 0 旧c2 0 4N a t i o n a lC o m m i t t e e，致力于推动I T S 国际标准的建立)等等。日本于1 9 9 8 年开始构建智能交通系统(I T S)框架，提出建设7 个终端服务系统。日本政府在智能交通系统(I T S)领域的研究与实践投入了大量人力和物力，通过很多相关政策的制定，希望能够形成智能交通系统产业化来推动国民经济的发展。在几4大连理工大学专业学位硕士学位论文年的时间里内，日本

36、本国共有4 0 0 万套车内导航系统得到了实际的应用。在智能交通系统(I T S)的应用中主要集中在交通咨询服务、电子收费系统、公共交通管理服务、以及紧急车辆优先等方面。日本目前有一亿两千万人口，每天公路上行驶的大小车辆大约有七千万。据日本建设省统计，日本每年由交通事故导致的伤亡人口达到1 0 0 万人之多。在这样一个狭窄而又拥挤的岛国上，人口密度极大，缓解交通拥堵这样的世界性难题智能依靠智能交通系统(I T S)来完成。除了欧美国家及日本等发达国家以外，一些发展中国家也开始对智能交通系统(I T S)进行全面的研究与开发，如韩国建设交通部门制订了全面I T S 框架结构和发展规划，新加坡在全

37、国推广不停车收费政策等韩国政府颁布了一项关于智能交通系统的计划用于引导智能交通系统的发展，即“2 1 世纪I T S 总计划”，对五年前制定的计划基础上进行了更新和改进，加快其发展速度，预计在2 0 3 0 年之前政府对智能交通(I T S)的投资总额达到7 5 亿美元。目前，韩国的城市的高速公路和一些普通公路以及全国的各大交通线路都采用了最先进的现代的交通管理系统。自1 9 9 5 年以来，韩国首都警察署与道路安全管理委员会通过商议一同开发了具有韩国特色的交通信号系统，该系统具有很强个性，突出地展现了首尔交通的特色之处阳1。除了解决交通问题以外，另一个重要的原因则是智能交通系统(r r S)

38、将成为高新技术应用产业最大的份额之一，这就可以解释不论发达国家还是发展中国家为什么对智能交通系统(I T S)领域投资如此巨大。目前I T S 关键技术分支主要有以下1 0 个方面呻一伽：(1)海上突发事件快速检测、预警和远程搜救资源调度技术(2)大范围高密度异构公共服务整合、优化定制和协同技术(3)军事运输资源的定位、可视化跟踪和投送能力保障技术(4)复杂交通流道路状态监测、预报和紧急事件管理技术(5)大范围高密度条件下的客户服务仿真与引导技术(6)大规模智能交通系统综合集成、采集和管理技术(7)城市道路交通仿真评估和交通网络诱导技术(8)一体化运输任务规划、推演、效能评估和资源调度技术(9

39、)高速公路联网不停车收费系统成套关键技术(1 0)重大事件条件下交通协调管理技术智能交通系统中最优路径选择的设计与实现中国政府的交通管理部门以及相关专家，充分认识到智能交通系统(I T S)对社会发展的重要作用，对交通系统领域研究的更加重视。在2 0 0 0 年国家I T S“十五”示范工程开始启动，其中包括杭州、广州、深圳、重庆、上海、中山等多个城市n“。在2 0 0 1年1 2 月又启动了“十五”国家科技攻关重大招标项目“智能交通系统关键技术开发和示范工程”，在“十一五”综合交通体系规划的发展中，我国也明确指出：“要加强交通枢纽和综合交通信息网络建设，构建现代化的智能交通系统。”我国对智能

40、交通系统的规划主要在以下四个方面进行重点研究：l，城市交通资源优化配置技术；2，智能交通系统的控制与管理技术；3，交通安全信息的预报、救援和安全保障等技术；4，城市交通信息资源无条件共享及各部门互相协同服务技术。目前，智能交通系统(I T S)在我国的实际应用可概括三大领域口2 1：l，公路交通系统的信息化建设，其中包括高速公路建设、以及国家主干道和次干道的公路建设问题；2，城市交通道路管理信息化和服务的人性化：3，城市公交系统信息化。北京、广州两大城市在城市智能交通系统的建设中走在我国前列。目前北京市对智能交通系统(I T S)的开发体现在四个方面：交通道路实时控制与管理、高速公路管理和指挥

41、、公共交通系统指挥与调度、紧急事件响应和反馈，包括大约三十个子系统，分散在各个交通管理部门和交通运营部门。北京市将在“十一五”规划期间投资两千亿元人民币构建起新型交通系统，投资主要用于交通系统的改进升级和完善，重点将包括高速公路建设与维护、轨道交通线路的建设与维护以及智能交通系统的建设与维护，占北京市每年支出费用的6 0。其中，对智能交通系统建设与维护只占有1 5，与国外发达国家对该方面的投资相比还差很远。本文研究的最优路径问题是指在交通路网的一对给定的起点和终点之间找出一条通路，使得车辆从起点到终点所走过的路程最短、耗时最少、费用最低等。在很早之前就有了求解最优路径问题的提出，但是发展速度相

42、对缓慢。有许多与最优路径求解相关的学科在侧面对这个问题做过研究，如运筹学、计算机科学、图论、数论、交通工程学理论、地理信息科学研究等n。日前网络发展十分迅速，而网络的构成类似交通道路系统，可以利用最优路径算法来解决很多网络方面的问题。经典学科中的图论、数论与计算机科学以及数据结构与算法的有效结合使得对最优路径算法的研究有了很大进展。国内外大量研究机构和相关学者对最优路径问题的解决进行过深入研究与探讨。数学家E W D i j k s t r a 在1 9 5 9 年就提出了标号设定法用于解决路径问题n“，形成了目前仍被视为经典的D i j k s t r a 算法。自从D i j k s t

43、r a 算法面世以后，又历经了很多学者对该算法的改进与发展，因此有关最优路径选择问题的研究成果不断涌现，使其求解速度和求解效一6大连理工大学专业学位硕士学位论文率不断提高 1 5 o 解决最优路径问题的其他常用的算法还包括B e l l m a n n 引，F o r d n7 1，M o o r e n 踟等人分别提出的动态规划(D y n a m i c P r o g r a m m i n g，D P)算法，又被业内称为B e l l m a n-f o u l算法，该算法解决网络最优路径问题中单源点问题；P a p e n 钔，P a l l o t t i n o 口印等人各自提出

44、的增长图(G r a P h-G r o w t h)算法；G l o v e r 瞻妇等人结合以上各算法思想的阈值提出了新的算法；H a r t E t a i 2 7 提出了A 牛启发式搜索算法解决最优路径选择问题等。最优路径选择算法在不同的应用条件下可以按照不同的方法进行分类晗2|。如按照时间顺序来分类，分为动态最优路径选择问题和静态最优路径选择问题；如果按照确定性和非确定性来划分，分为确定型和随机型最优路径选择问题；如果按照网络规模大小划分，可分为小规模网络和大规模网络最优路径选择问题：如果按照计算方式来划分，可分为串行和并行最优路径选择算法。各种不同类别的最优路径选择算法相互组合可以

45、成为解决不同问题的各种各样算法。最优路径问题按照是否是单源问题还可以分为单源最优路径选择问题及全源最优路径选择问题。其中单源最优路径选择问题更具有实际应用的意义，而且良好的单源路劲问题的算法可为全源最优路径问题提供良好的研究基础，因此本文在研究最优路径选择问题的过程巾只考虑单源最优路径选择问题。目前的研究成果中可用于求解单源最优路径选择问题的算法层出不穷1，早期就发展起米的的基于限制条件的深度优先搜索算法、基于邻接矩阵和邻接表的D i j k s t r a 算法、基于有向无环图的动态规划算法、最大相关边算法、最大相关点算法、超图数据结构的深度优化搜索算法等。针对具体实际环境可能是网络特征不同

46、、应用需求不同及具体的软硬件环境不同，各种算法在空间和时间复杂度、易实现程度等方面各有各的特点。虽然这些算法可以解决某一类的实际路劲选择问题，但是每种算法在其应用方面还存在一一定的局限性，许多学者对这些经典的基本的算法进行了改进和发展瞰1，并得到了良好的效果。在这些研究中陆1，一方面是优化实际网络特征的动态结构陆盯1，在相同的时间复杂度的基础上尽量提高算法计算的效率；第二方面是限制网络特征，如要求网络中的边的权值是整数等等陴1 等，用于采用基数堆等数据结构设计算法；第三方面是采用有损算法的特征，如限制搜索范围啪瑚1、限定搜索方向口”及限制搜索几何层次递归次数等等陋3；第四方面是采用拓扑层次编码

47、路径视图嘲，存储最短路径部分实例化编码；第五方面是采用并行计算m 3 5 1 的方法。随着人工智能领域的发展，许多学者和研究机构将人工智能的相关算法与最优路径选择算法相结合，形成了一一些新一代的最优路径选择算法啪1，其中就包括蚁群算法，蚁群算法是一种进化算法，模拟了基于种群的进化，在求解最优路径问题方面有很大优势。智能交通系统中最优路径选择的设计与实现本课题研究动态交通最优路径算法，主要研究内容如下：(1)建立城市交通模型利用图论的相关理论和知识，对图中的节点和边设法加入车道信息用于模拟就哀痛系统。以完整的交通道路网络作为模型建立对象，只需要对道路中的相关数据和参数进行显示和计算，但在实际的交

48、通道路当中，交通特征是实时变化的，这与交通道路模型密不可分。首先，在同一条道路上不同的车道在不同的行驶方向的交通特征可能不同，如交通量变化和交通规则等。例如：在早晚的上下班的高峰区段，进出同一区域的同一条道路在不同方向表现的车流量是明显不同的，交通拥堵现象大多数情况下是发生在某条车道的单向车道上。其次，不同方向的车道由于具有不同的拓扑关系，因此交通规则有可能不同。由于在节点图层和路段图层中分别存储的点、线图元是分别独立的，两个图层问不想关联。为建立点线各个元素之间的空间拓扑关系，使他们构成有机整体，需要分别在存储点线信息的两张表文件中扩展一定长度的字段，用对象的属性字段之问的相互联系来建立交通

49、网络图的拓扑关系，这样就建立了交通网络系统的有机整体即他们的拓扑关系结构图。(2)D i j k s t r a 最优路径算法改进与道路阻抗分析由于动态路径所具有的特点是信息的实时变化，需要在搜索过程中实时检测道路系统的信息变化，并将变化后的信息纳入搜索算法当中。同时，其他路段的交通限制信息也会影响最优路径选定的结果。因此，在实际情况中需要对D i j k s t r a 算法进行改良和扩展。交通阻抗是指车辆在交通道路上正常行驶时的运行距离、费用、时间、舒适度以及道路畅通情况等素的综合，即人、车、路、环境等四个方面因素对交通出行带来的综合阻力效应。针对某一个具体的交通网络，其阻抗函数所代表的意

50、义根据实际情况而不同。在城市交通系统中，道路上交通阻抗可以分为两部分，即路段的交通阻抗和节点(道路交叉口)的交通阻抗。最优路径选择问题的主要依据是计算出各个路段和交叉口的交通阻抗，交通阻抗常用的指标有出行时问、出行距离和路段或节点需要花费的费用。(3)路径选择系统仿真与实现从宏观来说，制作以路径优化为目的的专用电子地图时要遵循的原则是：以诱导为中心，以为路径优化算法服务为目的，忽略与路径选择无关的路网要素，重点描述对路径选择相关的内容，以最小的代价来表达及存储路网。8大连理工大学专业学位硕士学位论文电子地图一般是借助专业的绘制地图的软件来完成的。在本文中的电子地图相关数据信息主要是通过M a