[硕士论文精品]交通网络分析中的最优路径算法研究

中国科学技术大学硕士论文摘要I摘要最优路径算法是交通网络分析中路径分析的核心。当前对交通网络动态最优路径问题的研究有两大方向，一是传统静态最优路径算法在交通网络中的应用。二是通过对道路交通流的建模，运用动态规划、变分理论、随机过程理论等知识建立影响交通流的各要素间的依赖关系，再求解最优路径。前者基于一种静态的路段权值假设，即该路段的权值在最优路径算法求解过程中保持不变。而这种假设在交通网络中是不成立的。交通网络的一大特征正是时变性和不可预知性。若以道路的通行时间来表示该路的权值，则同样一条道路的权值可能因为一天中的不同时刻而有很大的差别，从而最优路径可能也不止一条。静态最优路径算法无法解决这个问题。后者往往由于模型一般比较复杂（模型越是接近实际的交通流状况就越复杂）而难于求解。本文针对最优路径算法在实际应用（如导航应用）中的特点，提出了分时分段计算动态最优路径的思想，即在对应时段对应路段应用得到的交通信息指导路径寻优；并依据该思想提出了动态最优路径算法和自适应的动态最优路径算法。前者依据各路段的权值在一天中对应时段的统计分布状况，根据车辆到达路口的时间，通过查表的方式计算出一个全局的最优路径，该算法用以解决成批派车的点到点之间最优路径问题。后者依据车辆到达路口的时间，实时接收该时刻各路段的权值分布情况，选出一条最优路径到达下一个路口；在下一个路口继续应用该策略直到到达目的地，该算法可以解决具有随机出行特征的单车实时选择最优路径问题。关键词A算法动态最优路径算法自适应动态最优路径算法矢量地图全球卫星定位系统地理信息系统智能交通系统中国科学技术大学硕士论文ABSTRACTIIABSTRACTTHESHORTESTPATHALGORITHMSARETHECOREOFPATHANALYSISOFTRANSPORTNETWORKANALYSISTHECURRENTRESEARCHOFTHEDYNAMICSHORTESTPATHALGORITHMSHASTWOORIENTATIONSONETHEAPPLICATIONOFTRADITIONALSTATICSHORTESTPATHALGORITHMSANDTHEOTHERISCOMPUTINGTHESHORTESTPATHWITHTHEAPPLICATIONOFKINDSOFKNOWLEDGETHROUGHMODELINGTHETRANSPORTATIONENVIRONMENTSTHEFIRSTMETHODBASESONTHEFIXEDWEIGHHYPOTHESISOFTHEPATHWHICHDOESNTCOINCIDETHEFACTTHATTHETRANSPORTNETWORKISADYNAMICNETWORKWITHAVARIEDANDUNPREDICTABLEWEIGHOFEACHPATHINALLTIMETHEDYNAMICSHORTESTPATHSMAYVARYWITHDIFFERENTTIMEINADAY,SOSTATICSHORTESTPATHCANNOTSOLVETHISNEWPROBLEMTHESECONDMETHODOFTENCANNOTGETTHEACCURATESOLUTIONFORITSCOMPLICATEDMODELTHISTHESISRAISESANEWSTRATEGYTOCOMPUTETHEDYNAMICSHORTESTPATHINTRANSPORTNETWORKACCORDINGTOTHECHARACTERSOFAREALTIMEENVIRONMENTTHATISSEARCHINGTHESHORTESTPATHINTHELIGHTOFTHEPOSITIONANDTHEARRIVALTIMETHROUGHTHEACQUIREMENTOFREALTIMEINFORMATIONOFTRANSPORTATIONTHETHESISALSOGIVESTWOALGORITHMSWHICHADAPTTODIFFERENTCIRCUMSTANCESTHEDYNAMICSHORTESTPATHALGORITHMCOMPUTESTHEGLOBALSHORTESTPATHTHROUGHCHECKINGTHETABLEWHICHMAINTAINSALLPATHSWEIGHINTHECORRESPONDINGTIMESEGMENT,ANDTHISALGORITHMCANAFFORDASOLUTIONFORABATCHOFCARRIERSTRAVELTHEADAPTIVEDYNAMICSHORTESTPATHALGORITHMACHIEVESANEWSHORTESTPATHINEVERYCROSSINGTOGUIDETHECARRIERTOGOTOTHENEXTONETHROUGHACQUIRINGTHEREALTIMEINFORMATIONOFTRANSPORTATION,WHICHCANSOLVETHEREALTIMENAVIGATIONOFINDIVIDUALTRAVELKEYWORDAALGORITHM,DYNAMICSHORTESTPATHALGORITHM,ADAPTIVEDYNAMICSHORTESTPATHALGORITHM,VECTORMAPS,GLOBALPOSITIONINGSYSTEMGPS,GEOGRAPHICINFORMATIONSYSTEMFORTRANSPORTATIONGIST,INTELLIGENTTRANSPORTSYSTEMITS中国科学技术大学硕士论文目录III目录摘要IABSTRACTII目录III第一章绪论111ITS简介1111ITS的由来1112ITS的组成212GPS、GIS简介3121GPS简介3122GIS简介4123GIST简介613交通网络分析中动态最优路径算法研究意义714最优路径算法的研究现状8141静态最优路径算法的研究现状8142动态最优路径算法的研究现状11第二章矢量地图综述1221矢量地图的基本概念12211电子地图及其分类12212矢量地图在GIS中的应用1322GPS实验室开发的矢量地图与GIS系统13221系统组成14222地图矢量库15223地图数据库1523交通矢量地图的生成1624地图矢量库的存储组织18第三章A算法1931最优路径的数学模型1932A算法概述21321A算法的基本思想21322A算法原理2233A算法性质23331评估函数的选取23332A算法的可接纳性23323A的最优性2434A算法的变种27中国科学技术大学硕士论文目录IV第四章静态最优路径2841松弛运算2841标号算法29411DIJKSTRA算法30412FLOYD算法31413各类标号算法复杂度之比较3142A算法应用于矢量地图的分析33421A算法的应用分析33422应用于矢量地图的算法可接纳性的简要证明3343静态最优路径的程序实现34431算法步骤34432矢量地图的数据结构35433A算法涉及的数据结构36434A算法的函数说明36435实验结果42第五章动态最优路径4451动态最优路径问题类型4452动态最优路径的求解思想4553动态交通网络的表示及性质47531动态交通网络的表示47532动态交通网络的性质4854动态最优路径求解方案49541时段的划分49542路段行程时间的确定50543车载型最优路径计算的系统配置示意图51544时间最优路径的计算方法52545模拟的实验效果图5455自适应动态最优路径算法57551自适应动态最优路径算法的必要性57552自适应解决方案57553自适应动态最优路径算法的模拟效果图59第六章总结与展望61参考文献62致谢65附录66中国科学技术大学硕士论文绪论1第一章绪论本章首先简要介绍了智能交通系统（INTELLIGENTTRANSPORTSYSTEM,ITS）、全球定位系统（GLOBALPOSITIONINGSYSTEM,GPS）、地理信息系统（GEOGRAPHICINFORMATIONSYSTEM,GIS）和交通地理信息系统（GEOGRAPHICINFORMATIONSYSTEMFORTRANSPORTATION,GIST）的相关内容。然后分别就静态最优路径和动态最优路径的研究现状做出简要概括，最后给出了本文的研究方向。11ITS简介ITS是数字城市的一个重要组成部分，本节就ITS的发展历史和组成作一简介。111ITS的由来交通是国民经济发展的两大支柱之一，交通运输是国家的经济命脉，是生产力的重要体现。交通问题具有明显的地域特征，是地理信息科学的一个主要研究发展。此外，交通技术的发展与电子技术、通讯技术、计算机技术等高新技术的发展息息相关；这些高新技术也是实施“数字地球”战略必须着重发展的技术。可以毫不夸张地说，数字交通将是“数字地球”战略发展的最大受益者之一，同时也是实施“数字地球”战略的一个重要组成部分。城市交通网络在城市发展中占有至关重要的地位。它不仅是城市的一个重要组成部分，同时也决定了城市中居民的生活方式。长期以来，交通问题已成为困扰城市发展的重要问题。世界各国都面临这日益严重的城市交通问题，如交通拥挤、车辆行驶缓慢、交通事故频繁及其由于交通堵塞造成的大量空气污染等问题。很多发达国家逐渐认识到，欲有效解决这些问题，仅仅依靠道路建设，扩大路网规模是远远不够的，交通问题的解决必须依赖现代信息技术与管理技术的有机结合。他们纷纷呼吁对现代交通问题给予新的认识，建立卓有成效的、对环境危害低的交通系统，更方便地进行客货运输，促进经济发展，减少交通事故。为了解决我国城市的交通问题，改善城市交通系统的性能，一方面需要通过改造路网系统、拓宽路面、增添交通设施以及道路建设等城市交通所必需的“硬件”建设来实现；另一方面需要通过采用科学的管理手段，把现代高新技术引入到交通管理中来提高现有路网的交通性能。这样就可以改善整个道路交通的管理效率，提高道路设施的利用率，实现城市交通管理的科学性和有效性。20世纪90年代初，美国、日本和西欧等竞相投入大量资金和人力，中国科学技术大学硕士论文绪论2开始大规模地进行道路交通运输智能化的研究和实验，称之为“智能车辆道路系统”（INTELLIGENTVEHICLEANDHIGHWAYSYSTEMS,IVHS）。随着研究的不断深入，系统功能扩展到道路交通运输全过程及其有关服务部门，发展成为带动整个公路交通运输现代化的“智能交通系统”（INTELLIGENTTRANSPORTATIONSYSTEMS，ITS）。112ITS的组成ITS是将先进的信息技术、数据通讯传输技术、电子传感技术、电子控制技术以及计算机处理技术等有效地集成运用于整个地面运输管理体系，而建立起的一种在大范围内、全方位发挥作用的，实时、准确、高效的综合运输和管理系统1。ITS将汽车、司机、道路及其相关的服务部门相互连接起来，使得汽车在道路上的运行智能化。它的概念模型如图11所示具体地说，该系统将采集到的各种道路交通及服务信息经交通管理中心集中处理后，传输到公路运输系统的各个用户（司机、居民、公安局、停车场、运输公司、医院、救护排障等部门），出行者可实时选择交通方式和交通路线；交通管理部门可自动进行合理的交通疏导、控制和事故处理；运输部门可随时掌握车辆的运行情况，进行合理调度。ITS主要由6个高级交通系统构成，分别为高级交通管理系统、高级出行信息系统、高级车辆控制系统、商业车辆运行系统、车辆自动定位系统及车辆自动识别系统1。这6个高级系统有可细分为29个公共服务系统。ITS通过这些公共服务系统完成公路与街道的交通监控，为出行者提供交通信息，对可能出现的险情及延误预先提出警告，帮助交通管理部INFORMATIONANDTELECOMMUNICATIONSTECHNOLOGIESVEHICLESUSERSROADS图11智能交通系统（ITS）的概念模中国科学技术大学硕士论文绪论3门对车辆进行有效的实施疏导、控制和事故处理，减少交通阻塞和延误，辅助车辆的自动导航、进行公共交通的实时调度和行驶路线的调整，帮助运输部门增加客运率，降低运营成本，提高商业运输效率等。12GPS、GIS简介121GPS简介世界上第一个实用的卫星导航系统是美国研制的“子午仪”（TRANSIT），它于1964年正式投入使用。子午仪系统能在全球范围内，全天候实现二维（经度、纬度）定位，其定位的精度为0103海里，因而获得了广泛的应用。然而其定位不连续、不实时、不能给出高度的缺点对航空、航天、测绘等一些用户的应用受到影响2。为了满足军事应用和民用提出的更高要求，美国于1973年开始研制一种新的卫星导航系统导航星全球定位系统（NAVSTARGLOBALPOSITIONINGSYSTEM），该系统简称为全球定位系统（GPS）或导航星（NAVSTAR）系统。NAVSTAR是NAVIGATIONSATELLITETIMINGANDRANGING的缩写，其含义为用导航卫星类进行计时和测距。目前，国际上已经公认将这一全球定位系统简称为GPS。GPS经过漫长的研究、试验、研制和组网阶段，经受来自经费和技术方面的挫折，于1994年3月10日第24颗工作卫星进入预定轨道，系统全面投入使用。它不仅能在世界上任何一个地方任何时候同时接收4颗卫星信号进行高精度的三维位置（经度、纬度和高度）测定，还能实时地对运载体进行三维速度的测定和高精度的授时。它从根本上解决了定位和导航的问题，可以满足各类不同用户的需要。GPS已经成功地应用于舰船和飞机的导航、导弹卫星测控、精密绘制、精密授时、作战训练、石油资源开发、车辆的跟踪和导航等方面。近几年来，农业、公安和旅游等行业也纳入了GPS的应用范围。虽然美国原计划研制GPS主要是为了军事目的，但是，考虑到民用卫星定位的大量需求；美国政府在进行GPS系统设计时，计划提供两种服务2标准定位服务（SPSSTANDARDPOSITIONINGSERVICE）和精密定位服务（PPSPRECISEPOSITIONINGSERVICE）。标准定位服务利用粗测捕获码（C/A码COARSE/ACQUISITIONCODE）定位，预计精度约为400M，以供民间用户使用。精密定位服务利用精测码（P码PRECISECODE）定位预计精度约为100M，供军方和某些特许用户使用。在GPS实验卫星应用阶段，多次测试表明实际定位精度远远高于预计的精度，利用C/A码定位精度可以达到15M，利用P码定位精度可以达到3M。对于使用中国科学技术大学硕士论文绪论4C/A码的民用用户来说，这样的定位精度太高，影响到美国的自身利益。于是，美国政府对GPS应用采取选择可用性SA（SELECTIVEAVAILABILITY）政策。实施SA政策就是在卫星上采用一种技术，人为地将误差引入卫星钟和导航数据以降低GPS的定位精度，使得非特许用户不能利用C/A码获得高精度定位3。在卫星上采用SA技术后，使C/A码的水平定位精度限制到100M，垂直测量精度为156M。美国国防部常年对SA政策进行测量，并根据形势和要求对部分和全部卫星取消SA政策。SA政策的引入，在一定程度上限制了GPS的应用。为了提高定位精度，人们研究出差分GPS技术DGPS（DIFFERENTIALGPS）。但是，DGPS系统需要建立相应的差分基准站和监测站，造价昂贵。随着GPS应用的不断发展，GPS广大用户要求取消SA政策的呼声越来越高，考虑到庞大的GPS应用市场，美国政府最终于2000年5月1日取消了SA政策，这大大促进GPS定位和导航的应用的进一步发展。2000年以后，以波音公司为首，休斯空间和通信公司、计算机科学公司CSC、洛克西德马丁管理与数据系统MINTYTYPEDEFSTRUCTNETPOINT/节点和内点结构，用于生成地图的拓扑INTID/点的ID号STRUCTPOINTPT/点的几何坐标，包括X，YINTARCNUM/包含该点的弧的条数INTPARCHEAD/包含了该点的弧的序号组成的链表的头指针NETPOINT弧TYPEDEFSTRUCTLINKINTID/弧的ID号DOUBLELEN/弧长INTNPOINTNUM/弧包含的节点和内点的数目INTPNPOINTHEAD/组成该弧的序号组成的链表的头指针中国科学技术大学硕士论文静态最优路径算法36LINK433A算法涉及的数据结构从前面的A算法应用分析，可知对于弧段上的内点不需要计算它的F值，为此另外定义了一种节点结构，该结构存储了搜索过程中节点的启发信息以及最优路径上的父节点。定义两种点的数据结构的好处在于1将矢量图的显示与最优路径算法分离，矢量地图本身的数据结构不需变化，原有在该结构上的其他应用也不需作变化。从而便于A算法的移植，可以花较小代价应用到其他具有类似数据结构的矢量地图中。2分散了计算任务，减小计算量，提高了算法的执行效率。TYPEDEFSTRUCTNODE/补充的节点结构，用于实现算法INTID/节点的ID号CRECTPT/为使节点清楚显示，并捕捉用户的输入，并非必需INTPARENTID/存储最优路径上父节点的ID，初始化为0表示不存在父子关系DOUBLEG_VALUE/节点的G值，初始化为0DOUBLEH_VALUE/节点的H值，初始化为0DOUBLEF_VALUE/节点的F值，初始化为0NODEOPEN表和CLOSED表的实现OPEN表采用排序链表实现，从而节省了存储空间。TYPEDEFSTRUCTNODEID/用于表示OPEN表INTIDSTRUCTNODEIDPNEXTNODEIDCLOSED表采用动态数组实现，最大程度地节省了存储空间434A算法的函数说明A算法代码实现主要由3个函数组成主函数FINDPATHINTORGID,INTDESID，类型BOOL，中国科学技术大学硕士论文静态最优路径算法37两个参数分别是起始节点和目标节点的ID号，若找到起始节点和目标节点的一条最优路径，则返回TRUE。OPEN表中节点插入和排序函数INSERTNODEIDSRC,NODEIDDES，类型是NODEID，表示将链表DES插入到SRC中并排序。节点扩展函数EXTENDNODEINTN,INTPCLS,INTK，类型NODEID，表示扩展ID序号为N的节点，生成其后继节点集。此外，还有返回OPEN表中第一个节点ID的函数RETURNFIRSTNODEIDP。A算法所需的3个主要函数说明如下BOOLFINDPATHINTORGID,INTDESID/主函数，用于寻找源节点到目标节点间的最优路径INTM0INTMAX42INTCLOSEDINTMALLOCMAX4SIZEOFINTINTVNULLNODEIDOPENNULLNODEIDSUCCESSORNULLINTNNODEIDN0NODEIDMALLOCSIZEOFNODEIDN0IDORGIDN0PNEXTNULLOPENN0INTKIDTOINDEXS,J,ORGIDSKPARENTID0SKG_VALUE0SKH_VALUESQRTAORGID1PTXADESID1PTXAORGID1PTXADESID1PTXAORGID1PTYADESID1PTYAORGID1PTYADESID1PTYSKF_VALUESKG_VALUESKH_VALUEWHILEOPENNULL中国科学技术大学硕士论文静态最优路径算法38NRETURNFIRSTIFNDESIDRETURNTRUECLOSEDMNMIFMMAX4MAX42MAX4VINTREALLOCCLOSED,MAX4SIZEOFINTIFVNULEXIT1CLOSEDVSUCCESSOREXTENDNODEN,CLOSED,MOPENINSERTOPEN,SUCCESSORRETURNFALSEINTRETURNFIRSTNODEIDPINTKPIDNODEIDTEMPPPPPNEXTFREETEMP中国科学技术大学硕士论文静态最优路径算法39RETURNKNODEIDINSERTNODEIDSRC,NODEIDDES/OPEN表中插入和排序函数NODEIDP1SRCNODEIDQ1DESIFSRCNULL|DESNULLIFSRCNULLRETURNSRCELSEIFDESNULLRETURNDESELSERETURNNULLNODEIDHEADNULL,R1NULLIFSIDTOINDEXS,J,P1IDF_VALUEIDF_VALUER1INSERTP1PNEXT,Q1P1PNEXTR1HEADP1ELSER1INSERTP1,Q1PNEXTQ1PNEXTR1HEADQ1NODEIDS1HEADWHILES1PNEXTNULL中国科学技术大学硕士论文静态最优路径算法40IFS1IDS1PNEXTIDS1S1PNEXTPNEXTS1S1PNEXTRETURNHEADNODEIDEXTENDNODEINTN,INTPCLS,INTK/扩展ID号为N的节点，生成后继节点集NODEIDH1NULLNODEIDH2NULLINTU0INTU1INTTEMP10/保存扩展的临时IDINTINDEXIDTOINDEXS,J,N/S数组类型为NODE，存储A算法需遍历的节点INTNUM1AN1ARCNUM/A数组存储了显示地图拓扑所需的所有点，包括节点和内点INTNUM2WHILENUM10BOOLFLAGTRUEINTARCINDEXAN1PARCHEADNUM11INTRPARCINDEXPNPOINTHEADNUM2PARCINDEXNPOINTNUMIFNR0TEMPURNUM21ELSETEMPUR0中国科学技术大学硕士论文静态最优路径算法41FORU10U1KU1/检测扩展的节点是否在CLOSED表中IFTEMPUPCLSU1FLAGFALSEBREAKIFFLAGINTNODEINDEXIDTOINDEXS,J,TEMPUDOUBLETEMP_G,TEMP_H,TEMP_FTEMP_GSINDEXG_VALUEPARCINDEXLENTEMP_HSQRTADESID1PTXATEMPU1PTXADESID1PTXATEMPU1PTXADESID1PTYATEMPU1PTYADESID1PTYATEMPU1PTYTEMP_FTEMP_GTEMP_HIFSNODEINDEXF_VALUE0|TEMP_F0U1/冒泡法排序FORINTU20U2SIDTOINDEXS,J,TEMPU21F_VALUE中国科学技术大学硕士论文静态最优路径算法42INTTEMPIDTEMPU21TEMPU21TEMPU2TEMPU2TEMPIDWHILEU0/尾部插入法形成排序链表H1NODEIDMALLOCSIZEOFNODEIDH1IDTEMPUIFH2NULLH1PNEXTNULLELSEH1PNEXTH2H2H1RETURNH1435实验结果将A算法分别应用于合肥市、成都市智能交通导航系统，得到如下图所示的效果图。其中图54中粗黑线所示的是合肥工业大学到三孝口的最优路径，途经屯溪路、桐城路、庐江路、金寨路，全长334公里。图55中粗黑线所示的是成都市电子科大到华西医科大学最优路径，途经建设北二路，红星路，成都气象学院东门到达华西医科大学，全长554公里。中国科学技术大学硕士论文静态最优路径算法43图54合肥城区应用A算法求解最优路径效果图图55成都城区应用A算法求解最优路径效果图中国科学技术大学硕士论文动态最优路径算法44第五章动态最优路径本章首先介绍了交通网络中动态最优路径算法的类型和求解的思想，接下来重点探讨了一类具有FIFO性质的交通网络所具有的性质。在54节和55节分别提出了两种具备FIFO性质的交通动态最优路径的求解方案DSPT和ADSPT，前者得到一条最优路径，后者得到一条次最优路径，二者有不同的适用范围。本章同时也给出动态交通网络中时间最优路径中权值的确定方法，并通过对A算法的改进，将其应用到动态的最优路径求解中。51动态最优路径问题类型交通网络本质上是一个动态网络，若以路段的行程时间来表示路段的权值（本章以下皆是基于这样一个前提），该路段的权值会因出发时刻的不同而有所不同，即此时的交通网络是一个时间依赖网络（TIMEDEPENDENTNETWORK，TDN）。目前对于动态最优路径的研究主要集中在两类TDN网络第一类是在源节点的一个给定时刻出发的单源点多汇点的最优路径。这类问题有一类特殊情形，即当先进先出（FIRSTINFIRSTOUT）性质满足时，任何静态的最优路径算法都可用来解决动态的最优路径问题，且具有与静态最优路径算法相同的时间复杂度，学者DREYFUS50首先提出这个结论。而后，AHN、SHIN51和KAUFMAN证明了这个结论的正确性。第二类是在多个源节点的多个可能时刻出发的多源点单汇点的最优路径。对于这类问题，有学者提出了BELLMANFORD算法在TDN中的变种39，该算法中节点的标签用一个状态向量而不是静态网络中的一个标量来表示。另外还有一种标号改正算法在TDN应用中的变种算法被提出，其基本思想与前者一致，即节点标签采用了一个状态向量。CHABINI52等人经过研究发现这两种算法的时间复杂度都是MNMNMO，并提出了一种依据时间的递减次序建立最优路径耗费的DOT算法，其时间复杂度为M,NSSPMMNM。其中M表示离散的时间段，M、N分别表示图的边数和节点数，M,NSSP表示一个多源点到单汇点地最优路径算法的时间复杂度。以上这两类算法之所以得到广发研究的一个重要的原因是因为这两类是智能交通系统路径诱导的主要目标。随着经济的发展，交通网络的单车导航需求日益增长，这就衍生出一类新的最优路径问题，即对一个给定时刻或所有可能时刻，从起始点到目标点的最优路径。在这种情况下，最优路径一般有两种计算方式，第一种中心型计算方式，由出行者向交管中心发送所在的位置、中国科学技术大学硕士论文动态最优路径算法45目标位置及时刻，由交管中心根据道路交通网络状况的模型通过计算然后再经由通讯网络传给出行者；第二种是车载型计算方式，由出行者向交管中心发送所在位置、目标位置，并要求与该起止位置相关的路段的预计行程时间数据，交管中心接受请求向出行者发送目前交通网络状态的信息，最后由车载设备根据接收到的信息计算最优路径。此外，单对顶点间的最优路径还广泛应用于各类应急系统（110报警、119火警、120急救等等），因而是一个有着重要研究意义的课题。本文以下也正是基于这样的一个研究内容，即单个OD（ORIGINDESTINATION）对之间满足FIFO性质的时间最优路径。为叙述方便，这里考虑最优路径算法在车载导航中的应用，且鉴于我国目前ITS的发展水平，本论文以介绍最优路径车载型计算方式为主。52动态最优路径的求解思想本文提出的动态路径寻优的思想是在起始节点的一次计算法。在起始节点根据目前及今后一段时间的路段行程时间（权值）的变化情况，预测到达各路口时刻和各路段的行程时间，根据预测的数据计算出全局动态最优路径。为在实际的交通环境中实现动态寻优，关键的是要确定起始点与目标点间各路段的权值，即各路段的行程时间。路段上交通状态是动态变化的，因而路段行程时间也是动态变化的。如交通比较拥挤时，路段的行程时间就会比较长；反之，路段的行程时间就会比较短。即路段行程时间的一个影响因素是车流的平均密度，平均密度越大，车流的平均速度越小，行程时间越长。与此有紧密关联的另一个因素是路段的通行时刻，即选择在什么时间通过该路段。对于那些时间依赖路段，一般说来，早上8点钟左右和晚上10点钟通过同样的路段所花费的时间是不同的。此外，诸如道路的等级、设计时速道路限制（禁左转、单行道等）、车辆类型等等因素都会对路段的行程时间有所影响。尽管影响路段行程时间的因素有很多，我们却可以将以上各类因素近似地归结为两个直接因素1）路口出发的时刻。2）待进入路段在进入时的平均行程时间。其他的各类因素，大多可以直接或间接地归结为这两类的根源。然而，在车辆的行驶过程中任意时刻，根据该时刻的交通网络的状态，由此来实现完全的动态路径寻优，却并非是必要的。主要的原因有三个1）车载设备存储和处理以及通讯网络的传输能力有限。一般在这种情况下，大量的交通网络的状态数据主要是对各个路段的车流平均行程时间的估算需要被传输和存储在车载设备中。若在交通网络中各车都有这种导航需求，除非以数据流压缩的方式来传输这些数据，中国科学技术大学硕士论文动态最优路径算法46一般的通讯网络是处理不了这种需求的。此外，对于一个从起始节点到目标节点间的通行过程中，若计算比较频繁，一来车载设备的处理能力有限，可能不能满足这种需求。二来路段的权值没有太大的变化，计算出来的最优路径仍然是前一时刻计算选定的最优路径，这实际上是造成了有限计算资源的浪费。2）据统计数据表明，一个实际的交通网络并非是完全动态的，即并非所有路段的行程时间都是时间依赖的。这其实是一个明显的事实，比如在一个次干道上的行程时间，由于该路段可能一天之中都不会有拥塞的情形发生，故而在任意时刻通过该路段的时间都可看成是基本保持不变的。3）由交通流变化特性可知，路段行程时间的变化并非是完全随机的，在一天之中、一周之中，一月之中是有一定统计特性的。这主要是因为道路的交通流组成在一天不会较大波动。如城市交通中，公交车、私家车、出租车等等一天都是在固定的路线上通行。那么引起交通流变化的只是外来车辆的加入，而这种因素对整个的交通状态的影响是不大的。总结上述三点，为计算动态最优路径所需的路段权值（路段的行程时间）可以通过一种查表结合计算的方式来获得。一般说来，在交管中心维护有这样的两类表来提供给车载设备在当前时刻各路段的通行时间的估计值。第一类表记录了那些非时间依赖路段的行程时间，这类路段的行程时间在一天中的任何时刻可看成是使一个定值。一个例子如表51所示。第二类表记录了那些时间依赖路段的行程时间，这些路段行程时间在一天中的不同时段会有较大变化的情况。为此需对时间作离散化处理，将系统工作时间划分为若干时段，认为每个时段内每条路段上的交通状态稳定。一个例子如表52所示。该表主要记录了不同路段在不同时段的行程时间。路段ID路段的行程时间（S）1T12T23T3ITI表51静态的路段行程时间中国科学技术大学硕士论文动态最优路径算法47时段路段ID12JM非工作时段I1TI11TI12TI1JTI1MTI10I2TI21TI22TI2JTI2MTI20KTK1TK2TKJTKMTK0NTN1TN2TNJTNMTN0表52动态的路段行程时间53动态交通网络的表示及性质本节主要介绍了动态交通网络的表示，并在此基础上探讨了具备FIFO性质的交通网络的一些重要性质，这些性质是后续最优路径算法的理论基础。531动态交通网络的表示在31节曾经介绍了最优路径的图论模型。这里为叙述简便起见，首先介绍几个的术语路口，指道路的端点或交叉点。路段，指相邻路口之间直接相通的道路。路径，任意两个路口之间有路相通的路段的集合。结合动态交通网络的特征，可将动态交通网络表示如下设DE,VG表示一个交通网络。为简化问题表示，对交通网中的所有路口编号，则N,1,2,I|IVNULL表示该网络中的所有路口的集合，N|V|表示路口总数。对交通网络中的所有路段也给以编号，则VJI,|JI,KE表示该网络中的路段集合，若路口J,I之间没有路段，则J,I没有定义。M|E|表示路段总数。EK|TDDK表示路段的行程时间权值的集合，行程时间函数TDK表示路段K在时刻T的行程时间。依据上节分时分段的思想，1M,2,0,1T，表示将出行者离开路段端点的时刻离散化为M个出发时刻。则对于求在0T时刻出发的从起始节点到目标节点间的最优路径R，即是求在第一条路中国科学技术大学硕士论文动态最优路径算法48段处0TT的满足RKKTDT取得最小值的各路段组成。532动态交通网络的性质交通网络虽然是一个动态网络，但它却不是一个完全的随机时间网络。交通网络在一定的时期内，是有一定的统计特性的。本文研究的动态交通网络满足FIFO特性，以下首先介绍FIFO的定义。定义51FIFO特性。在一个交通网络中，以一个统计的水平，路段的行程时间通常具有以下特性出行者到达路段终止点的时间与出行者离开路段起始点地时间同序。一般地，说一个行程时间函数TDK满足FIFO特性是指到达时间TDTK是非递减的。在一个离散的时间网络，一个路段EJ,I是一个FIFO特性的路段当且仅当1M,0T,1TD1TTDTKK类似地，如果一条路径满足FIFO特性，我们就说这是一条FIFO路径。如果一个交通网络中所有的路段都是FIFO路段，就说这个网络是一个FIFO网络。具有FIFO特性的网络还具有以下的性质定理51如果一条路径上的所有路段都是FIFO路段，这条路径就是FIFO路径。证数学归纳法。设该路径具有K条路段，在开始节点的出发时间是T。不失一般性，给K条路段依次编号为1,2,K。假设到达第L条路径的终点的时间ALAL1AL2A1T是T的一个非递减函数。现在要证明到达第L1条路径的终点的时间AL1ALAL1AL2A1T也是T的非递减函数。首先，考虑路径的第1条路段，这是一条FIFO路段，从而假设成立。由归纳假设，可知GTALAL1AL2A1T是T的非递减函数。该路径的每一条路段都是FIFO路段。故从第L条路段终点出发到达第L1条路段终点的时间FTAL1T也是T的一个非递减函数。由GT及FT都是T的非递减函数，有TGTGTT及YFYFYY。令YGT及YGT，则可得TGFTGF。这就证明了到达第L1条路段终点的时间也是T的一个非递减函数。中国科学技术大学硕士论文动态最优路径算法49从而由归纳法原理以及FIFO特性定义可知，满足该性质的路径是一条FIFO路径。推论52在一个FIFO网络，任意一条路径都是FIFO路径。证在一个FIFO网络，所有的路段都满足FIFO特性，从而任意路径上的所有路段也都满足FIFO特性。由定理51，任意一条路径都是FIFO路径。定理53若在起始节点到目标节点的每一条路径都满足FIFO特性，则起始节点到目标节点间的最优路径的行程时间函数也满足FIFO特性。证设PT表示从起始节点到目标节点的在时刻T出发的一条最优路径，则可将在该路径上的行程时间表示成为LPT,T，且满足TLPT,T的情况，可将路径的权值（行程时间）看成固定不变，且可以事先计算出来，如表52的第M1列所示。此时的路径寻优实质上已是静态最优路径问题。如可取007T0，0022TM。考虑到晚上2200到次日早晨700之间，一般城市路段行程时间的非时间依赖特性，将其划分为一个时段，在这种情况下可直接应用静态最优路径算法。542路段行程时间的确定如表51、表52中数据一般由交管部门通过统计的方式得到。对于非时间依赖路段I上的行程时间IT可以通过事先计算的方式，即III/VLT，其中IL表示路段I的长度，IV表示车辆通过路段I的自由行驶速度。对于时间依赖路段K，在时段J的JTK计算可以通过一段时期（如一周或一月）内的测得的在对应时段的车流平均速度来求得。表51和表52的数据当及时更新，以反映最新的交通状况。在实际车载导航中，车辆通过路段K的行程时间与车辆到达该路段路口的时刻有关，在不同的时刻通过路段的时间也是不一样的。设在车辆导航过程中，车辆通过路段K的时间段为T,TAL，已知到达该路段的起点时刻为LT，路段K的长度为KL，求路段K的行程时间KT或到达该路段终点时刻TTTTLAKA。首先，确定在该路段的导航在整个时间段的序列数J为1TTTJ0L；（51）其中表示取整运算。车辆通过路段K可能经历多个时段，各时段对应的行程时间表示为NULL,1JT,JTKK，从而可将路段K的行程时间KT确定如下1若LJKKKKLJTTJT,LJTLTT，则车辆在J时段就通过了路段K，JTJTTKKK中国科学技术大学硕士论文动态最优路径算法512若LJKKKKLJTTJT,LJTLTTLJKK2N1IKKLJLJLJKKKTTJT,1NJTIJTTJTTT1T2NTTTTJT,JTT53式中N可由N1IKKLJ1N1IKIJTTJTTT1IJTT确定。543车载型最优路径计算的系统配置示意图如图51所示是一般的车载型最优路径计算的系统配置示意图中国科学技术大学硕士论文动态最优路径算法52其工作模式如下当车辆到达第一个路口时，车载导航系统开始工作。第一步，定位。由GPS接收器通过接收GPS卫星信号，将车辆的位置在车载矢量地图上显示出来。第二步，接收交通信息。通过通信网络的上行线路向交管中心发送请求，要求的得到各路段的动态行程时间（路段的权值）。交管中心接受请求后，向该车辆发送如表51、表52所示的交通信息。第三步，最优路径计算。车载系统的最优路径计算模块通过查询表51、表52，计算出在当前交通环境下到达目标节点的时间最优路径。第四步，路径决策。选择计算出来的最优路径，到达目的地。544时间最优路径的计算方法从第3章及第4章可知A算法是一类求解点到点之间最优路径的高效算法。该算法引入启发式评估函数，用于评价每个生成节点的优先级。为求以S为源节点，Q为目标节点间以动态行程时间为路段代价的时间最优路径，构造节点N的评估量为数值对NT,TNL，其中NLT既是到达节点N的时刻，又是从节点N出发前往下一个节点的出发时刻；NT为节点N的评估函数，定义如下GPS卫星车载导航系统下行线路上行线路收集GPS定位数据计算TKT内部数据库交管中心矢量地图最优路径计算模块路径决策图51车载型最优路径计算的系统配置示意图中国科学技术大学硕士论文动态最优路径算法53VQN,DTNHNTNTNPS,KK，54NT表示S到Q之间经过节点N的最优路径行程时间的估计值。NT表示源节点S到节点N所经过的所有路段的动态行程时间总和，KT是路段K的动态行程时间，N,SP表示源节点S到节点N的最优路径。估计项NH表示当前节点N和目标节点之间Q欧氏距离Q,ND除以估计的最高车速V。根据动态路径的特点，将车辆到达某路段起点时刻对应时段在系统工作时段序列中的次序和通过路段的行程时间纳入最优路径搜索过程，对静态A算法进行改进，提出一种动态的最优路径算法（DYNAMICSHORTESTPATHFORTRANSPORTATION，DSPT），应用于动态交通环境，其基本思想是导航系统开始工作时，通过获取如表51、表52所示的交通信息，得到整个交通网络的各路段在当前及今后各时段的行程时间的分布情况。当车辆到达第一个路口，由到达该路口的时间LT、与该路口相关联的各路段的长度KL以及表51、表52所示的各路段的各时段行程时间信息，根据54式计算出该路口相关联的各路段终点N的预计到达时刻NLT及评估函数值NT，即可置与节点N相关的评估量为数值对NT,TNL。而后选择具有最小NT值的节点，置该节点的父节点为当前路口编号，并依据从该节点的出发时刻NLT及其他各量继续扩展，直到选择的具有最小NT值的节点是目标节点终止。从目标节点到起始节点依次索引父节点，找到最优路径，车辆沿着找到的这条最优路径行驶，到达目的地。具体的计算步骤为1根据公式54计算源节点S的T值，再由源节点S的出发时刻LST，得到S的评估量ST,TLS。生成一个只包含S的搜索图S，并将S置于一个称为OPEN的列表上。置所有其他节点的T值及到达时刻为或一个极大值。生成一个空的列表CLOSED。2若OPEN为空，则失败退出。3选择OPEN表的第一个节点，把它从OPEN上移入CLOSED中，称该节点为N。若N是目标节点Q，顺着搜索图S中，从Q到S依次索引当前节点的父节点找到一条最优路径，成功退出置节点的父节点操作在第4步完成。中国科学技术大学硕士论文动态最优路径算法544扩展节点N，生成其后继节点集M。检查CLOSED表，去除M中的同时在CLOSED表中的节点。根据节点N的评估量NT,TLN可得NLT，查表51和表52计算出在M中剩下的节点的T值及预计到达时刻LT。对M的每一个已在OPEN表中的节点M，若到目前为止找到的到达M的最优路径通过N，更新OPEN表中节点M的评估量MT,TLM，置M的父节点为N，并在M中去除该节点，把M中剩下的节点加到OPEN表中。5按递增T值，重排OPEN表。返回第2步。说明任意扩展的节点M的评估量MT,TLM计算如下，在计算MT之前，M的父节点N的评估量NT,TLN必为已知初始节点S没有父节点，ST可直接计算为VQ,SD。若从N到M的路段为非时间依赖路段，查表51直接可得从N到M的路段的行程时间。否则，根据式公式51计算到达节点N的时刻在整个时间段的序列数。根据公式53可计算从N到M的路段的行程时间。于是NTMTN到M的路段的行程时间，再由公式54可计算MT；NMLLTTN到M的路段的行程时间,从而可得M的评估量MT,TLM。总结以上，可将交通网络的动态最优路径的算法归纳为如下两条1若车辆行驶在导航系统工作时段以外，即车辆到达路口的时间0LTT或MLTT，查表51和52的第M1列得到网络中各路段的行程时间，直接应用静态A算法可求得从起始节点S到目标节点Q的时间最优路径。2否则，根据上述算法求得从起始节点S到目标节点Q的时间最优路径。545模拟的实验效果图以下的结果对比了根据上述思想计算出的合肥市两组不同地点不同时刻的最优路径。图52和图54是在静态的路段权值下的相应起止点之间的时间最优路径。图53和图54是在动态路段权值下的相应起止点之间的时间最优路径。其中，图53和图54中的三角形表示在对应的时段道路权值较大的情形，即路况比较拥挤的情形。中国科学技术大学硕士论文动态最优路径算法55图52工大南区到北区在静态路段权值下的时间最优路径图53工大南区到北区在动态路段权值下的时间最优路径中国科学技术大学硕士论文动态最优路径算法56图54科大西区到长江路与马鞍山路交口在静态路段权值下的时间最优路径图55科大西区到长江路与马鞍山路交口在动态路段权值下的时间最优路径中国科学技术大学硕士论文动态最优路径算法5755自适应动态最优路径算法考虑到实际交通网络的权值时变性，针对车辆导航的特点，本节提出了动态交通网络中的自适应动态最优路径算法ADSPT，以满足实时导航的需求。该算法的思想是将起始点和目标点之间的整体动态路径寻优看成是按路口到达时刻的各个静态路径寻优的组合。551自适应动态最优路径算法的必要性DSPT算法虽然可以解决动态交通网络的最优路径求解问题，但在实际的导航系统中却有可能受限于以下两个因素，而不能得到较好的效果1交通信息的非实时性。在DSPT算法中，路经的权值是通过查询表51和表52来获得的，表51和表52是根据在对应时段的历史的交通流平均车速计算得来的，即各路段的权值事实上是一个在对应路段、对应时段的所有车辆的平均行程时间。在一个实际的交通网络中，导航系统不能得到当天的各路段权值在各时段的分布情况，因为路段的权值是时间的一个连续函数，依据交通环境的不同总是在不断变化的。不同车辆通过在同一时段通过