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

大连理工大学专业学位硕士学位论文摘要智能交通系统中的核心问题是最优路径选择问题。本文分析了交通道路网络的具体特点，主要包括线性分布特点、网络分布特点、分段分布特点、动态性特点和车辆行驶的自主性特点等。将交通网络抽象成一个由边和节点组成的图，并根据图论的相关理论和知识构建起交通网络模型，包括交通道路节点模型，交叉口和道路模型，并对上述道路模型信息进行存储，以构建好的交通道路模型为基础研究智能交通系统中的最优路径问题。考虑了实际道路中存在一定的交通阻抗，是算法更具有应用价值，在DIJKSTRA算法的基础上进行了改进，缩短了道路搜索时问，提高了最优路径选择的效率。数据库的选择与设计是系统实现中不可或缺的重要组成部分，优秀的数据库选择和设计方案能够提高最优路径选择的效率、也提高了整个智能交通系统的工作效率。本文使用了GIS数据模型与数据库的管理设计，主要包括GIS数据的简介、选择ORACLE的理由、GIS数据向ORACLE中的导入和存储、ORACLE中GIS数据的访问和维护。对道路交通系统的建模、最优路径选择算法的研究以及数据库的开发设计目的是建立一套接近实际情况的最优路径选择系统。本文利用MAPLNFO软件绘制交通系统的电子地图，开发工具使用GIS控件MAPX与VISUALC。将经典的DIJKSTRA算法和改进的OIJKSTRA算法进行编码实现，使之在最优路径选择系统中正确运行。关键词智能交通系统，最优路径，GIS数据，系统设计智能交通系统中最优路径选择的设计与实现DESIGNANDIMPLEMENTATIONOFTHEOPTIMALPATHININTELLIGENTTRANSPORTATIONSYSTEMSABSTRACTTHEOPTIMALPATHISANIMPORTANTPARTOFTHEINTELLIGENTTRANSPORTATIONSYSTEMTHISPAPERANALYZESTHESPECIFICCHARACTERISTICSOFTHETRAFFICANDROADNETWORK,INCLUDINGLINEARDISTRIBUTIONCHARACTERISTICSOFNETWORKDISTRIBUTIONCHARACTERISTICS，SEGMENTEDDISTRIBUTIONCHARACTERISTICS，DYNAMICCHARACTERISTICSOFVEHICLESAUTONOMOUSFEATURESABSTRACTTRANSPORTATIONNETWORKASAGRAPHOFEDGESANDNODES，ANDBUILDATRANSPORTATIONNETWORKMODELBASEDONGRAPHTHEORYTHEORYANDKNOWLEDGE，INCLUDINGTRAFFICROADNODEMODEL,INTERSECTIONSANDROADMODEL,ANDSTORAGEOFTHEROADMODELINFORMATIONTOBUILDGOODTRAFFICROADMODELFORBASICRESEARCHININTELLIGENTTRANSPORTATIONSYSTEMS，THEOPTIMALPATHCONSIDERINGTHEACTUALROADTRAFFICIMPEDANCE，ISTHEALGORITHMMOREAPPLICATIONIMPROVEDVALUEONTHEBASISOFTHEOIJKSTRAALGORITHM,SHORTENINGTHEPATHSEARCHTIME，ANDTOIMPROVETHEEFFICIENCYOFTHESELECTIONOFTHEOPTIMALPATHTHEDATABASEISANIMPORTANTPARTOFANINTEGRALSYSTEMDESIGNANDIMPLEMENTATION,DATABASESELECTIONANDDESIGNOFADIRECTIMPACTONTHEEFFICIENCYOFTHEPATHPLANNINGSYSTEMTHISARTICLEUSESTHEDESIGNOFAGISDATAMODELANDDATABASEMANAGEMENT，MAINLYINCLUDINGTHEINTRODUCTIONOFGISDATA,SELECTORACLEREASONIMPORTEDANDSTOREDINTHEORACLE，GISDATA,THEORAELEGISDATAACCESSANDMAINTENANCEMODELINGOFROADTRAFFICSYSTEM,THEOPTIMALPATHSELECTIONALGORITHM弱WELLASTHEDEVELOPMENTOFTHEDATABASEISDESIGNEDTOESTABLISHTHEOPTIMALROUTESELECTIONSYSTEMSETCLOSETOTHEACTUALSITUATIONDRAWNELECTRONICMAPISMADEBYMAPLNFOSOTTWAREDEVELOPMENTTOOLSANDTHETOOLSUSCGISCOMPONENTMAPXANDVISUALCCLASSICALDIJKSTRAALGORITHMANDIMPROVEDDIJKSTRAALGORITHMWEREIMPLEMENTEDTHEOPTIMALPATHSELECTIONSYSTEMISPROVEDCORRECTLYK锣WORDSINTELLIGENTTRANSPORTATIONSYSTEMS；OPTIMALPATH；GISDATA；SYSTEMDESIGNII大连理工大学专业学位硕士学位论文目录摘要IABSTRACTII引言LL基础知识LO11路径优化算法概述一10111FLOYD算法10112DIJKSTRA算法1L113GPSR算法1212图论简介12121图的概念一13122图的表示13123图的存储1513本章小结162最优路径1721城市交通模型建立17211道路节点模型18212交叉口和道路模型1922交通模型数据存储一2L221数据预处理21222交通路径模型建立与数据存储2L23最优路径选择23231最优路径的求解过程23232经典DIJKSTRA算法分析24233交通阻抗分析25234DIIKS咖算法改进2824本章小结293GLS数据模型和数据库设计3031GIS数据模型建立30311空间数据模型30312属性数据模型3232GIS数据的管理与组织32智能交通系统中最优路径选择的设计与实现321GIS数据管理原则呻133322GIS数据的组织3333ORACLESPATIAL简介。3434空间数据向ORACLE中的导入。3735GIS数据在01T,RLE中的存储37351道路数据在ORACLE中的存储38352节点数据在ORACLE中的存储40353分层道路数据在ORACLE中的存储41354多比例尺道路数据在ORACLE中的存储4136OREALE中GIS数据的访问。4L37ORCALE中GIS数据的维护一42371数据库表的创建、删除一42372数据库记录的添加、删除和修改一4238本章小结一424路径优化算法系统实现4341电子地图制作43411电子地图制作的原则43412MAPINFO软件概述43413MAPLNFO电子地图的绘制43415电子地图的实现4642开发工具选择一46421MAPX的特点46422VISUALC4743仿真结果与分析一4744本章小结48结论一49参考文献50致谢一54大连理工大学学位论文版权使用授权书55IV大连理工大学专业学位硕士学位论文引言随着我国改革开放经济的发展，人口数量的不断增多，城市的数量和规模不断增大和增多，城市化程度和趋势十分明显，城市交通问题成为目前影响和制约我国经济发展和社会进步的主要因素。近年来，我国GDP以81096的较高的速度增长，城市化程度逐渐提高，社会经济迅速发展，这对城市交通系统的要求提出了挑战，而我国大部分城市都集中在东部沿海地区，人口密度和区域面积与其他地区不成比例。不论是上海北京等特大城市还是其他省会城市或地级市，普遍存在交通问题，城市车辆不断增多，人口越发密集，道路环境不断恶化等原因都是导致城市交通问题的主要方面。主要体现在分时段的交通拥堵、交通事故频发和环境污染严重等。交通运输是国民经济发展的重要支柱。长期以来，西方发达国家和发展中国家的大中城市都不同程度的存在交通问题，如车辆行驶缓慢、交通拥挤、交通事故频繁以及由于交通不畅引起的交通事故人员伤亡和环境污染等。这些问题的解决需依靠各种信息技术来解决口1。交通拥堵已经成为制约交通运输事业发展的瓶颈，不仅降低了物资运输或人员交流的效率，影响人们正常出行，并且很大程度上降低社会发展效率。统计了我国大约667个城市中，在上下班或者假日的交通高峰期，约有67的道路机动车行驶变得缓慢，甚至拥堵或发生交通事故。一些大中城市交通环境脆弱，由于道路设计或交通规则不合理，导致高峰时段交通拥堵严重，如果城市中某一条主干道发生交通事故而交通堵塞则可常常引发大面积、长时间的交通拥堵，尤其是特大城市的主干道和次干道的交通流经常在高峰时段已达到饱和或超饱和状态如上海或北京，正常的经济往来，货物运输，市民出行等会受到严重影响。公路或铁路的交通系统建设是我国针对交通运输的基础设施建设，在国家的经济发展中起到不可替代的作用，是连接两个城市之间的货物、人员、信息流的大动脉，较好的公路交通环境对于各个地区的经济建设、减小城乡之间的经济差距起到了非常好的促进作用乜1。随着我国现代化建设的不断深化，城市化水平不断提高，城市规模和人口数量也在不断的扩大，这使得机动车的数量也在不断增加，在不断提高人民生活水平的同时，人们的日常活动也在急剧增加，这给地区之问的交通流通带来很大压力。由于发展的需求，城市的规模和人口不断扩大，而交通道路资源是有限的，交通拥堵，意外交通事故和交通环境的污染等一系列问题由此产生，尤其是北京、上海等大城市，这些交通问题尤其突出。而造成交通拥堵、交通事故和环境污染的另一个重要原因是信息管理的缺失和不够重视。经过近几年的发展，政府部门对IT基础设施建设已经初具规模，我国信息化产智能交通系统中最优路径选择的设计与实现业建设正处在由信息资源建设向信息资源管理转换的重要时期。交通拥堵交通事故和交通污染对一个城市造成的影响包括，增加了城市运行的成本，降低了各项服务质量，对于医疗救护、消防和警务事务的影响极为致命。交通事故的数量和频率在国内大中城市每年都会不同程度的增加，事故死亡率为81076左右。交通设旅建设、管理和规划中需要的信息具有范围广、数据量大、复杂多变等特点，且绝大多数信息拥有空问意义上的特性。寻求一种对数据采集、数据挖掘和整合、数据存储和管理能够有效管理，并能将这些信息作为布局规划、交通建设、战略决策和信息管理等方面的工具成为人们不断追求的目标。在我国，几乎绝大多数社会信息资源和数据库掌握在各级政府部门手中。联合国教科文组织曾经对政府部门掌握的社会信息数据进行统计和分析，其研究的报告显示，7085的社会信息是有对经济发展有价值的。对中国来说，政府部门及其相关单位掌握这国内社会信息的6096以上，而这些大量的宝贵的信息资源并没有被政府部门充分利用口1。由于近几年我国政府认识到这一点，加大交通系统管理的投入，在交通系统的管理方面虽有较大进展，但信息资源管理中仍然存在着信息量缺乏严重、质量提高速度慢、管理结构不平衡、流动不通畅和体制不健全、机制含糊、标准不统一等问题。由于国家战略和保密政务信息公开制度不完善，各部门沟通不够导致信息资源采集重复，管理机制不够先进导致开发利用的市场化、产业化程度偏低等缺点。通过最近一个世纪的发展，西方发达国家达到鼎盛，从这些国家城市化的发展历史来看，机动车数量的增长永远快于道路加宽加多的速度，增加停车场数量等基础设施建设来解决当前出现的交通问题。解决这些交通问题的最有效、最根本的途径还是通过加快高新技术管理，通过信息技术来提高和完善交通信息管理的能力，提高交通运输的效率。解决交通问题出现了新的思路和办法，因此智能交通系统INIELLIGENITRANSPORTATIONSYSTEM，ITSH1的诞生为解决交通问题提供了全新的方式。随着计算机技术和电子技术的不断发展，以及电子地图测绘技术的不断进步，这使得地理信息系统也得到了长足的进步，这些技术的发展都给智能交通系统的发展奠定了良好的基础。通过中西交通道路系统的比较，我国城市交通系统的主要问题包括陆1交通管理技术落后，交通系统的发展永远跟不上社会发展的要求，交通系统供需矛盾突出。为大道交通系统的可持续发展，从根本上解决问题上述交通拥堵问题，并保持大中城市交通可持续发展带动城市的可持续反战，除了合理地进行交通道路等基础设施建设外，另一个切实可行的办法就是引进西方先进的高科技管理技术改进我们的交通系统，并使其符合我国国情，建立高性能高效率的智能城市交通系统ITS。智能交通系统ITS通过充2大连理工大学专业学位硕士学位论文分发挥现有交通资源潜力和系统内部协同作用产生的效力，能够为城市交通提供更安全、更舒适、更高效率和更高品质的新型城市交通系统嘲。智能交通系统的目标是利用现金的计算机技术和先进的网络管理来减少交通拥堵、交通事故和环境污染，与此同时，交通系统能够有效的正常的运行。在交通、计算机、电子通信、信息技术和系统科学与工程应用领域中，智能交通系统是日前许多国内外学者和研究机构集中、深入的研究领域之一，具有非常好的发展前景。车辆导航系统VNS是城市智能交通系统的核心内容之一，主要依据实时的路况信息来提高道路的通行能力，是减少交通拥堵、以外交通事故和环境污染的有效办法。随着交通事业的不断发展，基础设施建设的不断完善，城市交通的网络建设步伐的加快，交通设旆的不断完善，以及交通管理措施的不断细化、改进和应用，驾驶员有了更多的自主选择空问。但是如果缺少路况的引导方法，这些资源将会被浪费、而且交通拥堵、交通事故和环境污染也会不断增加。因此，对目前的交通系统来说，急需一套行之有效的车辆管理和导航系统来弥补这个不足，是驾驶员了解实时路况，避免交通拥堵，这样能够减少交通事故的发生，减少环境污染，安全方便的到达目的地。在西方发达国家的车辆导航系统研究中，所能够实现的也只是以同时期的历史数据为导航依据，而基于实时路况信息的动态导航系统还处在研究当中，没有达到应用水平。在我国，由于受到经济水平、技术条件和交通道路特点的限制，对只能交通系统的研究和开发应用起步晚于西方发达国家，国外的某些技术应用也不能完全使用于中国的特殊复杂的交通环境，不能照搬或照抄西方国家交通系统的制度和理念。随着我国交通运输业的不断发展，交通环境日益恶化的今天，研究出一套能够适应我国国情的现代智能交通系统和车辆导航系统，使之能够为人们出行提供重要的交通信息，避免交通拥堵，减少交通事故，为驾驶者提供最佳的驾驶路径，达到交通的路网畅通已经迫在眉睫。如果能够对车辆导航系统提供行之有效的最佳路径选择算法，就能为人们出行提供有效、合理有效的出行路径，从而提高交通系统运行的效率。最佳路径选择问题是智能交通系统中的重要组成部分，也是交通地理信息系统研究中的一个热点问题之一，是出行路径设计与优化、现有有限资源重新利用和分配等问题的基础。因此最优路径选择与优化问题是实时的动态交通系统中具有具有重要现实意义的研究课题。目前国内外已经有许多学者和研究机构对最佳路径选择做了深入研究，并取得了很好的效果。最佳路劲的算法研究不仅可以应用在交通网络系统中，而且对出行决策、校车路径查询、快递物流、资源分配等方面也有很好的应用价值。道路交通系统中最佳路径选择的研究能够为综合信息管理和只能决策提供先进、科学和行之有效的判决依据；为人们出行提供便利的交通运输条件；为车辆的运行提供安智能交通系统中最优路径选择的设计与实现全保障提高了现代交通道路的利用效率；帮助车辆减少尾气排放和燃油等资源的消耗对于建设资源节约型社会具有划时代的意义。欧美等西方发达国家在近一个世纪的飞速发展中，交通拥堵问题在以前和现在都是制约其发展的主要方面，因此很早就对智能交通系统的研究投入大量的人力、物力和财力。美国智能交通系统的发展尤为突出，几个发展较快的方面分别是车辆安全系统、公路和车辆管理系统、电子收费系统、自动定位系统和商业车辆管理系统。美国先后分别颁布了对其智能交通系统发展具有重要意义的两部法律，即1991年颁布的综合运输效率化法案6ISTEA，INTERMODALSURFACETRANSPORTATIONEFFIECIENCYACT和1998年颁布的2L世纪的运输平衡法案TEA21，THETRANSPORTATIONEQUKYACTFORTHE21STCENTURY，这两部道路交通建设法律从法律的角度和较高的高度统一规划智能交通系统ITS的发展，制定投资计划。继美国对智能交通系统的研究开展之后，欧洲、日本等国家对智能交通系统的相关领域的研究开发也相继展开。经过数十年的发展，美、欧、日已经成为国际智能交通系统研究的主要研究开发基地。另外一些国家和地区的智能交通系统ITS研究也取得长足的发展，如加拿大、澳大利亚、韩国等。欧洲在智能交通系统ITS方面研究的进展介于美国和日本之间。由于欧盟中各个国家对交通系统需求的不一致，导致对IIS的投资比较分散，不能集中所有国家的资源共同研究和开发同一套系统，整个欧洲建立同一的交通信息附体体系较难。然后在研究开发车辆控制系统ADVANCEDVEHICLECONTROLSYSTEM，AVCS、旅行信息系统ADVANCEDTRAVELINFORMATIONSYSTEMS，ATIS、电子收费系统ADVANCEDELECTRONICTOLLCOLLECTIONSYSTEM、商业车辆运行系统ADVANCEDCOMMEREIALVEHICLESOPERATINGSYSTEM，ACVOS等方面，前景十分可观。日本目前有五个国家部门负责智能交通系统的建设和相关活动，这五个部门分别为建设省、警视厅、国际贸易和工业省、运输省以及邮电省阻1。这五个部门同时经由其他的组织来促进ITS的发展，例如车辆、道路和交通智能化社团THEVEHICLE，ROADANDTRAFFICINTELLIGENCESOCIETY，简称VERTIS，一个致力于推动ITS发展的行业学术组织和ISO厂RC204全国委员会IS0旧C204NATIONALCOMMITTEE，致力于推动ITS国际标准的建立等等。日本于1998年开始构建智能交通系统ITS框架，提出建设7个终端服务系统。日本政府在智能交通系统ITS领域的研究与实践投入了大量人力和物力，通过很多相关政策的制定，希望能够形成智能交通系统产业化来推动国民经济的发展。在几4大连理工大学专业学位硕士学位论文年的时间里内，日本本国共有400万套车内导航系统得到了实际的应用。在智能交通系统ITS的应用中主要集中在交通咨询服务、电子收费系统、公共交通管理服务、以及紧急车辆优先等方面。日本目前有一亿两千万人口，每天公路上行驶的大小车辆大约有七千万。据日本建设省统计，日本每年由交通事故导致的伤亡人口达到100万人之多。在这样一个狭窄而又拥挤的岛国上，人口密度极大，缓解交通拥堵这样的世界性难题智能依靠智能交通系统ITS来完成。除了欧美国家及日本等发达国家以外，一些发展中国家也开始对智能交通系统ITS进行全面的研究与开发，如韩国建设交通部门制订了全面ITS框架结构和发展规划，新加坡在全国推广不停车收费政策等韩国政府颁布了一项关于智能交通系统的计划用于引导智能交通系统的发展，即“21世纪ITS总计划”，对五年前制定的计划基础上进行了更新和改进，加快其发展速度，预计在2030年之前政府对智能交通ITS的投资总额达到75亿美元。目前，韩国的城市的高速公路和一些普通公路以及全国的各大交通线路都采用了最先进的现代的交通管理系统。自1995年以来，韩国首都警察署与道路安全管理委员会通过商议一同开发了具有韩国特色的交通信号系统，该系统具有很强个性，突出地展现了首尔交通的特色之处阳1。除了解决交通问题以外，另一个重要的原因则是智能交通系统RRS将成为高新技术应用产业最大的份额之一，这就可以解释不论发达国家还是发展中国家为什么对智能交通系统ITS领域投资如此巨大。目前ITS关键技术分支主要有以下10个方面呻一伽1海上突发事件快速检测、预警和远程搜救资源调度技术2大范围高密度异构公共服务整合、优化定制和协同技术3军事运输资源的定位、可视化跟踪和投送能力保障技术4复杂交通流道路状态监测、预报和紧急事件管理技术5大范围高密度条件下的客户服务仿真与引导技术6大规模智能交通系统综合集成、采集和管理技术7城市道路交通仿真评估和交通网络诱导技术8一体化运输任务规划、推演、效能评估和资源调度技术9高速公路联网不停车收费系统成套关键技术10重大事件条件下交通协调管理技术智能交通系统中最优路径选择的设计与实现中国政府的交通管理部门以及相关专家，充分认识到智能交通系统ITS对社会发展的重要作用，对交通系统领域研究的更加重视。在2000年国家ITS“十五”示范工程开始启动，其中包括杭州、广州、深圳、重庆、上海、中山等多个城市N“。在2001年12月又启动了“十五”国家科技攻关重大招标项目“智能交通系统关键技术开发和示范工程”，在“十一五”综合交通体系规划的发展中，我国也明确指出“要加强交通枢纽和综合交通信息网络建设，构建现代化的智能交通系统。”我国对智能交通系统的规划主要在以下四个方面进行重点研究L，城市交通资源优化配置技术；2，智能交通系统的控制与管理技术；3，交通安全信息的预报、救援和安全保障等技术；4，城市交通信息资源无条件共享及各部门互相协同服务技术。目前，智能交通系统ITS在我国的实际应用可概括三大领域口21L，公路交通系统的信息化建设，其中包括高速公路建设、以及国家主干道和次干道的公路建设问题；2，城市交通道路管理信息化和服务的人性化3，城市公交系统信息化。北京、广州两大城市在城市智能交通系统的建设中走在我国前列。目前北京市对智能交通系统ITS的开发体现在四个方面交通道路实时控制与管理、高速公路管理和指挥、公共交通系统指挥与调度、紧急事件响应和反馈，包括大约三十个子系统，分散在各个交通管理部门和交通运营部门。北京市将在“十一五”规划期间投资两千亿元人民币构建起新型交通系统，投资主要用于交通系统的改进升级和完善，重点将包括高速公路建设与维护、轨道交通线路的建设与维护以及智能交通系统的建设与维护，占北京市每年支出费用的60。其中，对智能交通系统建设与维护只占有15，与国外发达国家对该方面的投资相比还差很远。本文研究的最优路径问题是指在交通路网的一对给定的起点和终点之间找出一条通路，使得车辆从起点到终点所走过的路程最短、耗时最少、费用最低等。在很早之前就有了求解最优路径问题的提出，但是发展速度相对缓慢。有许多与最优路径求解相关的学科在侧面对这个问题做过研究，如运筹学、计算机科学、图论、数论、交通工程学理论、地理信息科学研究等N。日前网络发展十分迅速，而网络的构成类似交通道路系统，可以利用最优路径算法来解决很多网络方面的问题。经典学科中的图论、数论与计算机科学以及数据结构与算法的有效结合使得对最优路径算法的研究有了很大进展。国内外大量研究机构和相关学者对最优路径问题的解决进行过深入研究与探讨。数学家EWDIJKSTRA在1959年就提出了标号设定法用于解决路径问题N“，形成了目前仍被视为经典的DIJKSTRA算法。自从DIJKSTRA算法面世以后，又历经了很多学者对该算法的改进与发展，因此有关最优路径选择问题的研究成果不断涌现，使其求解速度和求解效一6大连理工大学专业学位硕士学位论文率不断提高15O解决最优路径问题的其他常用的算法还包括BELLMANN引，FORDN71，MOOREN踟等人分别提出的动态规划DYNAMICPROGRAMMING，DP算法，又被业内称为BELLMANFOUL算法，该算法解决网络最优路径问题中单源点问题；PAPEN钔，PALLOTTINO口印等人各自提出的增长图GRAPHGROWTH算法；GLOVER瞻妇等人结合以上各算法思想的阈值提出了新的算法；HARTETAI27提出了A牛启发式搜索算法解决最优路径选择问题等。最优路径选择算法在不同的应用条件下可以按照不同的方法进行分类晗2|。如按照时间顺序来分类，分为动态最优路径选择问题和静态最优路径选择问题；如果按照确定性和非确定性来划分，分为确定型和随机型最优路径选择问题；如果按照网络规模大小划分，可分为小规模网络和大规模网络最优路径选择问题如果按照计算方式来划分，可分为串行和并行最优路径选择算法。各种不同类别的最优路径选择算法相互组合可以成为解决不同问题的各种各样算法。最优路径问题按照是否是单源问题还可以分为单源最优路径选择问题及全源最优路径选择问题。其中单源最优路径选择问题更具有实际应用的意义，而且良好的单源路劲问题的算法可为全源最优路径问题提供良好的研究基础，因此本文在研究最优路径选择问题的过程巾只考虑单源最优路径选择问题。目前的研究成果中可用于求解单源最优路径选择问题的算法层出不穷1，早期就发展起米的的基于限制条件的深度优先搜索算法、基于邻接矩阵和邻接表的DIJKSTRA算法、基于有向无环图的动态规划算法、最大相关边算法、最大相关点算法、超图数据结构的深度优化搜索算法等。针对具体实际环境可能是网络特征不同、应用需求不同及具体的软硬件环境不同，各种算法在空间和时间复杂度、易实现程度等方面各有各的特点。虽然这些算法可以解决某一类的实际路劲选择问题，但是每种算法在其应用方面还存在一一定的局限性，许多学者对这些经典的基本的算法进行了改进和发展瞰1，并得到了良好的效果。在这些研究中陆1，一方面是优化实际网络特征的动态结构陆盯1，在相同的时间复杂度的基础上尽量提高算法计算的效率；第二方面是限制网络特征，如要求网络中的边的权值是整数等等陴1等，用于采用基数堆等数据结构设计算法；第三方面是采用有损算法的特征，如限制搜索范围啪瑚1、限定搜索方向口”及限制搜索几何层次递归次数等等陋3；第四方面是采用拓扑层次编码路径视图嘲，存储最短路径部分实例化编码；第五方面是采用并行计算M351的方法。随着人工智能领域的发展，许多学者和研究机构将人工智能的相关算法与最优路径选择算法相结合，形成了一一些新一代的最优路径选择算法啪1，其中就包括蚁群算法，蚁群算法是一种进化算法，模拟了基于种群的进化，在求解最优路径问题方面有很大优势。智能交通系统中最优路径选择的设计与实现本课题研究动态交通最优路径算法，主要研究内容如下1建立城市交通模型利用图论的相关理论和知识，对图中的节点和边设法加入车道信息用于模拟就哀痛系统。以完整的交通道路网络作为模型建立对象，只需要对道路中的相关数据和参数进行显示和计算，但在实际的交通道路当中，交通特征是实时变化的，这与交通道路模型密不可分。首先，在同一条道路上不同的车道在不同的行驶方向的交通特征可能不同，如交通量变化和交通规则等。例如在早晚的上下班的高峰区段，进出同一区域的同一条道路在不同方向表现的车流量是明显不同的，交通拥堵现象大多数情况下是发生在某条车道的单向车道上。其次，不同方向的车道由于具有不同的拓扑关系，因此交通规则有可能不同。由于在节点图层和路段图层中分别存储的点、线图元是分别独立的，两个图层问不想关联。为建立点线各个元素之间的空间拓扑关系，使他们构成有机整体，需要分别在存储点线信息的两张表文件中扩展一定长度的字段，用对象的属性字段之问的相互联系来建立交通网络图的拓扑关系，这样就建立了交通网络系统的有机整体即他们的拓扑关系结构图。2DIJKSTRA最优路径算法改进与道路阻抗分析由于动态路径所具有的特点是信息的实时变化，需要在搜索过程中实时检测道路系统的信息变化，并将变化后的信息纳入搜索算法当中。同时，其他路段的交通限制信息也会影响最优路径选定的结果。因此，在实际情况中需要对DIJKSTRA算法进行改良和扩展。交通阻抗是指车辆在交通道路上正常行驶时的运行距离、费用、时间、舒适度以及道路畅通情况等素的综合，即人、车、路、环境等四个方面因素对交通出行带来的综合阻力效应。针对某一个具体的交通网络，其阻抗函数所代表的意义根据实际情况而不同。在城市交通系统中，道路上交通阻抗可以分为两部分，即路段的交通阻抗和节点道路交叉口的交通阻抗。最优路径选择问题的主要依据是计算出各个路段和交叉口的交通阻抗，交通阻抗常用的指标有出行时问、出行距离和路段或节点需要花费的费用。3路径选择系统仿真与实现从宏观来说，制作以路径优化为目的的专用电子地图时要遵循的原则是以诱导为中心，以为路径优化算法服务为目的，忽略与路径选择无关的路网要素，重点描述对路径选择相关的内容，以最小的代价来表达及存储路网。8大连理工大学专业学位硕士学位论文电子地图一般是借助专业的绘制地图的软件来完成的。在本文中的电子地图相关数据信息主要是通过MAPINFO软件，该软件将地图的图元对象属性以“表”和“记录”的方式保存下来，系统使用其信息是利用数据库进行学习和调用，从而可以将地图信息进行动态地绘制并可以放大、缩小或旋转等操作。论文共分为五章第一章引言。介绍了本文的研究背景及意义，阐述了国内外对智能交通系统研究的基本现状、最优路径算法研究的的基本概况和存在的问题，并对论文的内容组织和章节安排进行了说明。第二章基础知识概述。详细描述了经典路径优化算法内容，包括FLOYD、DIJKSTRA、GPSR算法等。对图论做了一定的介绍，包括图的概念、图的表示和图的存储。第三章最优路径算法。本文在经典的DIJKSTRA算法基础上进行了改进，并对实际的交通系统中进行了阻抗分析，将交通阻抗融入最优路径选择中，增加实用性。第四章GIS数据模型和数据库设计。包括GIS数据模的建立、管理与组织。对ORACLESPATIAL进行了介绍，包括空间数据向ORACLE的导入和存储，ORACLE中GIS数据的访问和维护。第五章系统仿真与实现。使用MAPINFOPROFESSIONAL软件进行地图制作，然后利用DELPHI、VISUALC、VISUALBASIC等开发平台进行二者的集成开发。第六章结束语。智能交通系统中最优路径选择的设计与实现1基础知识11路径优化算法概述国内外的研究机构和学者对不同的路径优化算法进行了研究、分析、比较和论证，比较经典的路径优化算法有FLOYD算法、DIJKSTM算法、GPSR算法、遗传算法、蚁群算法等。实际的交通网络是一个复杂的动态网络系统结构，它包括各种道路的限制信息以及交通流量的实时信息，然而现有的所有路径优化算法均是对某种抽象的具体网络结构进行优化计算各种，这就需要对实际的交通网络建立模型。路径优化的效率和速度室友所建立模型的准确程度来决定的口81。日前，国内外学者己经有许多传统的经典算法用来解决路径优化问题，但这些算法具有共同的点就是并没考虑实际出行的具体特点特点，如路况信息、道路质量、道路上的车流量等。最短路径算法求出的仅仅是在空间距离最短的路径，但在实际应用中人们需要的是最优路径，最优路径不一定是距离最短，还要考虑交通阻抗的问题，比如想要求得从A地到B地的最优路径，这个问题是指在所有从A地到B地的所有路线当中选择最优的一条，包括最节省时问，最节省资源，是驾驶者最舒适，对交通工具的各项消耗最小等。最优路径问题并不是普通意义上的距离最短路径选择问题。实际情况下最优路径选择问题包括两层含义首先最优路径是一条可以从A地到达B地的畅通的路径；其次这条路径在所有路径当中是最佳的。从A地到B地想要找一条最优路径，应是一条的所用时间最短、驾驶者最舒适、道路上的车辆数量较少啪1，或对交通车辆的损耗最硝、。111FLOYD算法FLOYD算法“”是由FLOYD在1962年提出的。将图的节点和边的信息计算利用矩阵计算来完成，通过一个图的权值矩阵中求出交通网络中任意两点之问的最短路径。基本思想比如求图中两节点VI到VJ的之问的最短路径问题。如果VI，VJ之间有边存在，即在VI与VJ之间随意选取一条长度为A的路径，该路径只是路径选择的初始值，一般不是最短路径，需要利用最短路径算法进行迭代计算和比较。首先若VI到VJ之间存在点V0存在路径VI，V0，叼，则比较VI，VJ与VI，V0，VJ的路径的长度，取得从VI到VJ的结点数小于或等于0的最短路径。如果在路径上再增添一结点VL，则路径变为VI，VL，VJ，如果其中子路径VI，V1与VL，VJ分别是当前找到的结点数不大于0的最短路径。那么VI，VL，VJ这条路径就是从VI到VJ的中间结点数大连理工大学专业学位硕士学位论文目小于或等于1的一条最短路径。将它和最初选取的从VI到VJ中间那条路径进行比较，从中选出中间结点个数小于或等于L的最短路径，利用此方法，再次增加一个结点进行迭代计算，继续试探。依次类推，经过多次迭代计算后，最后求得的从VI到VJ的路径一定是在距离上的最短路径。F10YD算法相当于穷举型算法，其时问复杂度为O112。在计算最短路径过程中，用邻接矩阵G来表示图，如果从VI到VJ有路径可以到达，则GI，J】D，路径长度用D表示；否则GI，J】_0。用矩阵D用来表示图中所有插入点的信息，DI，J】表示从点I到点J需要插入的节点，初始化DI，J一。把D中各个插入点信息存储在图中，比较插入点后的路径距离的变化情况，GI，J】MIN6I，J】，6I，K】G【I【，J1，如果GI，J】的值变小，则DI，J1K。比如，要寻找从V5到V1的路径。根据D，假如D5，13则说明从V5到V1经过V3，路径为V5，V3，V1L，如果D5，3_3，说明V5与V3直接相连，如果D3，1L，说明V3与V1直接相连。FLOYD算法是一种动态规划算法，由于是穷举法进行计算，因此对于稠密图效果较好。此算法思路简单，该算法对于稠密图来说，效率要高于经典的D独STRA算法。但缺点是时间复杂度较高，不适合大规模数据的计算，耗时较长。112D西KSTM算法DIJKSTRA算法H厶例由荷兰数学家EDSGERWYBCDJKST豫在1959年提出来的，是一种单源最短路算法适用于非负权值网络的计算，是目前在求解最短路径问题较为完备且应用广泛的算法之一，可以计算出图中从指定结点到图中其他任意节点之问的最短路径。在一个图G中，D嵇KGCM算法不但可以给出两指定结点之间的一条具有权值最下送的路径，且还可找出从指定点到图G中所有结点的最短路径。D蝎S咖算法的缺点就是当网络中结点数量较大时，就会增加算法的复杂度，降低了效率。该算法通过图中的每个节点V建立额外的信息数组，存储从其他任意节点S到V的最短路径。在初始状态下，原始节点S的路径长度值被赋为0即DIS的值为0，同时假设其他所有节点到该节点的路径长度为无穷大，用无穷大长度的路径表示任何其他节点到该结点的路径是未知的。如果存在从S到V的路径，那么当苏算法结束时DH中储存的信息是S到V的距离最短路径；如果从S到V的路径不存在，则D【V】中储存信息是无穷大。DJSTM算法的操作对边进行了拓展如果从U到V的路径是存在的，将边U，V添加到S，V尾部，则这条新的路径的长度为DMWU，V。如果这条路径的长度比已知的路径长度D【V】的值小，我们可以用新的路径来代替原有路径。这种拓展边的迭代运算一直进行，一直运行到所有的DM都代表从S到V最短路径为止。算法需要维护两个结点集Q和P，集合P保留了我们通过迭代运算所得的所有DN的最短路径的智能交通系统中最优路径选择的设计与实现值结点，而集合Q则保留其他剩下的所有结点。集合P初始状态为空，而后每一步都有一个结点从集合Q中转移到集合P中，并相应的在Q中删除该节点信息。113GPSR算法GPSR路由算法的思路是利用地理位置信息进行最优路径选择，该算法需要通过贪婪转发算法来建立与其他信息之间的关联和路由。当节点S向D转发数据分组时，他首先找到与相邻节点中距离最小的那个节点，然后将数据分组转发给那个节点，将距离最小的那个节点称为跳点，然后将S的数据传送给这个跳点，该过程需要一直迭代计算，直到分组数据全部到达节点D。利用欧氏距离计算距离方法计算距离该节点最近的相邻节点，但如果数据传输的某一节点是发现没有找到下一个距离最小的节点使得数据传送的目标节点时，导致了数据传输的失败。在发生生无法传送数据时，节点能够探测到周围的空洞，并利用右手法则沿着空洞周围的节点传输数据来解决这类问题。该方法的优点在于米面了在节点信息中存储建立和维护路由表信息，只需要利用相邻节点进行路径选取即可进行，几乎是不需要任何协议辅助；并且利用欧氏距离最小的方法进行路由，数据传输的延时最小；并能够保证只要网络路径不被破坏，数据一定能到传送到目标节点中去。但该算法存在这一定的缺点，当网络中的某节点与源点集中在两个区域时，由于通信的不平衡能够导致部分节点无效，从而是网络的连通性遭到破坏；另一方面是该方法需要GPS定位系统的辅助来计算几点的位置信息。GPSR中贪婪转发算法能够正常转发数据的前提是目的结点的位置都包含于每个数据分组中，每个结点都有邻居结点列表信息以及邻居结点和本结点的位置信息。在实际的路线选取过程中，我们将路口与上述的结点对用。在电子地图中，每个路口都有坐标位置和列表信息，那么在算法程序中我们首先要做的是让每个结点都包含一条邻居结点链表，并将结点号与位置信息关联起来。12图论简介图论GRAPHTHEORY是组合数学的一个分支，它源于瑞士数学家欧拉EULCR1736年对于著名的哥尼斯堡七桥问题的解决，从而使欧拉成为了图论的创始人。图论是数学学科当中比较年轻的一个分支。在图论被提出后的两百年中，图论的发展相对缓慢，但自从图论与大量的实际问题相结合，在物理学、化学、信息论、运筹学、计算机科学、控制论、社会科学，经济管理等各种学科中找到了更广泛的应用，使图论在近几十年来得到了快速的的发展。目前在图论领域中形成了两个不同的方向抽象图论和最优化图大连理工大学专业学位硕士学位论文论。前者主要研究图的性质，后者主要讨论与图有关的优化问题。最优化图论既可以算作图论中的一个研究方向，也可以看作运筹学中最优化理论的组成部分【“”。图论中的图是由若干节点以及两节点之间的连线所构成的图形，图论的研究对象是图，这种图形不考虑点的大小、形状和边的形状、长度、大小以及边与边的角度等几何问题，而主要表达的是点点之间通过线的连通关系，通常可以用来描述某些事物之间的相互关系，即用点来代表事件发生，用连接两点的边表示两个事件之间的关系。因此图论中的图能够代表多种含义，因此图论在诸多领域都有着非常广泛的应用。121图的概念无向图是指有序三元组Y，E，沙中边没有方向，其中集合Y被称为结点集，Y中的元素称为结点集合E被称为边集，E中的元素被称为边；而函数是边集E到无序结点对儿所构成的集合的一个映射关系，称之为关联函数。如果P是一条边，“，两个结点，且满足助ZN，那么就可称为E连接并且称，Y为E的端点。每条边与边两端的节点是相互关联的因此称为相互关联，与同一条边相关联的节点或者与同一个节点相互关联的边称为相邻的节点或者相邻的边，具有相同两个节点的边称为重合边或者是平行边，两个节点相同的边组成环，简单图就是没有环和重边的图。每个结点度数相同的简单图称为正则图，最大度与最小度恰好相差1的简单图被称为几乎正则图。图的结点的个数称为图的阶。122图的表示由点集合矿和点与点之间的连线的集合E所组成的集合对矿，E可以构成图，用GV，目来表示。图GV，毋由其结点与边之间的关系确定，且是唯一的。也由它的结点对儿之间的邻接关系唯一确定。Y中的元素为结点，E中的元素为边。节点集合Y与边集合E均为有限的图称为有限图。图21图的结构FIG21THESTRUCTUREOFGRAPH智能交通系统中最优路径选择的设计与实现在图21中，节点集合V彳，B，C，D，包括四个结点，边集合为EQ，E2，E3，E4，岛，E6，E7，ES，包括8条边。连接两个节点间的边可能不唯一，如Q，屹同时连接A和B。连接同一节点的边称为自圈，如。G的结点和边交替组成的有限序列为WVOELVLE2V2E3唯21如果叶L，K恰好是Q的端点1FK，我们称矿是一条从V0至UVK的途径。VO和唯称为形的起点和终点，矿中包含的边的数日K被称为形的长度，而起点和终点之间的结点称为路径形的内部结点。对于简单图来说，两点之问的边最多只有一条，因此可以把形简单写成图G的结点的序列WVOVIV2唯22这里只要求E小M是相邻的。序列信息中结点不能重复出现的路径被称为路。显然，如果在G中存在以V0为起点，心为终点的途径，则一定存在分别以V0和唯为起点和终点的路。当唯且长度为正值的途径称为闭途径。如果只有相同的起点和终点，而其他结点都不相同，这样的闭途径被称为圈，或者回路。对于圈来说，任何一点都可以看作是圈的起点或终点，圈通过每个结点都只有一次机会。考虑G中的某一对结点“，V，如果G中存在一条连接W的路，我们就说结点“，V是连通的。结点的连通性质在图G的结点集合Y上定义了一个等价的关系。它具有对称性和传递性，因此可以把结点集合Y划分为W个等价类，即VKUKUU圪23图的这种节点和边相互关联关系均可以用数学中的矩阵来进行描述，包括图G的关联矩阵，邻接矩阵和回路矩阵等等。一个图的矩阵表示不仅仅是对图的一种表示方法，更重要的是可以通过对这些矩阵的分析与讨论得到有关图的若干个性质，而且对图的些运算和操作也可以转化为对矩阵的计算。设G是一个阶数为P，边数为G的图，其中结点集合VG“，V2，V，边集合EGPL，E2，岛。图G的邻接矩阵定义为IX的矩阵A【A】，其中AO10瓷器嚣泣4，21萁他情况旺一图G的关联矩阵定义为大小NXR的矩阵BTO】，其中大连理工大学专业学位硕士学位论文器慧组5，对于邻接矩阵和关联矩阵来说，有些很重要的性质。矩阵首先要依赖于结点和边而存在。在任何情况下，邻接矩阵都是一个主对角线为全0的、大小为RX的对称矩阵。邻接矩阵第I行或者是第I列中数值1的个数是结点U的度。图用矩阵表示后，对图论的分析和讨论就可以通过对矩阵的图谱的分析讨论来发现图的主要性质和结构。通常在图像分割中，对连接两结点的边赋予一定的权值来表示结点之间的相似程度，用与邻接矩阵或关联矩阵相似的矩阵形式来表示加权矩阵，称为相似度矩阵W【】心鬣篙泣6，其中J。代表结点之间的相似程度的数值。如果用相似度矩阵形的行列式DETWE表示图G，记为DETG。图的特征多项式记为PG；APG；A卜1DETWGIC,2P一27形的特征值也被称为图G的特征值，图G的所有特征值称为G的谱，记为SPECG。因此，使用图G的谱解决聚类问题的方法又被称为谱方法。近年来，谱方法在应用图论的图像分割方法中为学者所研究和应用，也得到的广泛的发展与应用。123图的存储1邻接表表结点头结点匝丑三圈E圈图22邻接表结构FIG22T