资源描述：
《机场应急救援系统中资源动态调配研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
南京航空航天大学硕士学位论文机场应急救援系统中资源动态调配研究姓名：崔国山申请学位级别：硕士专业：交通运输规划与管理指导教师：韩松臣;汤新民20090101 南京航空航天大学硕士学位论文摘要民航应急救援的主体是机场，在突发事件的处理过程中，涉及的救援资源、救援单位比较多，合理快速的调配所需资源，尽快施救成为救援的重中之重。本文首先从资源动态源调配的整体角度上出发，运用Agent思想建立了资源动态调配组织结构模型，详细分析了指挥中心Agent、资源Agent、交通网络Agent、救援现场Agent的主要功能和结构，并且详细阐述了资源动态调配的协同运作模型和协同过程；在分析现应急资源筹集研究现状的基础上，根据实际处置应急事件中应急资源的需求及消耗情况，将问题描述为离散化消耗多资源多目标的资源筹集形式，分析了“多资源、多目标、离散化”三要素，建立其数学理论模型并利用蚁群算法求解，最后通过一个医疗救援组需求量的案例来验证模型及算法的正确性；资源动态调配的重要依据是路径的实时通行时间，先是对交通波理论进行分析，然后运用交通波理论对路段分四种状态进行研究，建立“空间—时间映射”模型，将路段距离大小映射为时间大小，最后采用示例求解的方式验证模型；根据交通路网实时变化快的特点，将应急救援车辆的工作时间划分为若干时间段，并且应急车辆行驶过程中运用动态规划路径的思想，实现时间最短路径的实时模拟显示。从整体上看，该研究为机场应急救援系统中资源动态调配研究进行了全面的、具体的论述，其方法及理论具有一定的现实意义。关键词:机场应急救援，动态调配，资源筹集，空间—时间映射，时间最短路径I 机场应急救援系统中资源动态调配研究AbstractThemainunitofCivilAviationEmergencyRescueisairport.Itinvolvesmanyresoursesandunitsindealingwithemergencies,rescuingassoonaspossiblebecomesthemostimportantthing.Firstly,thepaperbuildstheorganizationalstructuremodelbasedontheideaofAgentfromtheoverallperspectiveofresourcesdynamicallocation,ThestructureandfunctionofcommandcenterAgent,resourceAgent,transportnetworkAgentandrescursceneAgentareanalysiseddetailly.ThecollaborativemodelandcooperatingstepswerediscussedonthebasisoffunctionanalysisofthemembersofeachAgentgroup,also.Secondly,fortheproblemofemergencyresourcesdemandandconsumptionindealingwiththeemergencycase,thispaperdescribstheproblemintotheissuesoftheemergencysuppliesschedulingwithmulti-sitesandmulti-objectiveandmulti-resources.Andthethethreefactor:“non-lineandmulti-objectiveandmulti-resources”isresearchedthenestablishedanewmathematicalmodelfortheproblemofemergencyresourcesallocationofnonconstantmaterialcontinuousconsumptionwithmulti-sitesandmulti-objectiveandmulti-resources,andfinallythearticlegaveoutagoodsolutionthatbasedonACObygivingacaseofmedicalrecuedemandresourcessuccorpower.Andproveitcorrect.Thirdly,thereal-timepathisthebasisofresourcesallocation.Thearticleanalysiesthetheoryoftrafficwave.Thenthefourstatesofroadisresearchedbyusingtrafficwavetheory,andthe“distancetotime”modelisrealizedandproveditisexactitudebygivingademonstration.Lastly,forthecharacteristicsofchangingsoonintrafficnetworkstate,theworkingtimebeingcutmanysmalltimesandtheideaofdynamicvehicleroutingmodeisexerted,lastly,thetechnologyofGISandthetoolofVBisusedtorealizeshowingofdynamicshortesttime-path.Aboveall,thestudyisall-aroundandembodyfortheresourcesallocationinairportemergencyrescuesystem,itsmethodandtheoryisrealismmeaning.KeyWords:airportemergencyrescue,dynamicallocation,rescourcescollection,distancetotimemapping,shortest-timepathII 南京航空航天大学硕士学位论文图表清单图2.1单个AGENT的基本结构.................................................................................................................7图2.2机场应急救援资源动态调配MAS组织结构图...........................................................................7图2.3协调推理模型...............................................................................................................................10图2.4AGENT的协调推理过程图...........................................................................................................11图2.5基于MAS机场应急资源动态调配协同工作过程.....................................................................13图3.1应急资源的筹集流程组织..........................................................................................................15图3.2资源j需求函数图.......................................................................................................................17图4.1路段上两种密度情况下的车流运行情况.................................................................................30图4.2路段无排队时的区段示意图......................................................................................................31图4.3瓶颈处流量与密度的变化图......................................................................................................31图4.4路段有排队队列时的区段示意图..............................................................................................32图4.5路段车流波状态判别流程图......................................................................................................36图4.6路段示意图...................................................................................................................................37图4.7路段的初试状态图.......................................................................................................................37图4.8障碍车离开路段时的路段低速车队图......................................................................................38图4.9障碍车离开路段后的路况波形图..............................................................................................38图5.1桶状存储图...................................................................................................................................43图5.2动态最优路径算法流程图...........................................................................................................46图5.3应急车辆行驶路线动态规划图..................................................................................................47图5.4距离最短路径显示图...................................................................................................................49图5.5初始时间最短路径显示图..........................................................................................................49图5.6实时时间最短路径显示图...........................................................................................................50图5.7实时时间最短路径显示图..........................................................................................................50表3.1资源出救点到事故地点的资源可用量/费用表1....................................................................24表3.2资源出救点到事故地点的到达时间表1..................................................................................24表3.3资源出救点到事故地点的资源筹集方案表.............................................................................27V 机场应急救援系统中资源动态调配研究表3.4资源出救点到事故地点的资源可用量/费用表2....................................................................27表3.5资源出救点到事故地点的到达时间表2...................................................................................28表5.1几种图的存储结构比较...............................................................................................................43表5.2路段的时刻通行时间表...............................................................................................................44VI 南京航空航天大学硕士学位论文注释表MAS多Agent系统（Multi-AgentSystem）GIS地理信息系统（GeographicInformationSystem）GPS全球定位系统（GlobalPositioningSystem）GSM全球移动通信系统（GlobalSystemforMobileCommunications）BDI信念、愿望、意图（Belief、Desire、Intention）ACO蚁群算法（AntColonyAlgorithm）FIFO先进先出（FirstInFirstOut）EMAS城市快速路监控信息系统（ExpresswayMonitoringandAdvisorySystem）FAST-TRAC更快捷安全的出行交通路线和高级控制（FasterandSaferTravelthroughTrafficRoutingandAdvancedControl）FVD浮动车数据系统（FloatingVehicleDataSystem）ADVANCE先进的驾驶员咨询与车辆导航概念（AdvancedDriverandVehicleAdvisoryNavigationConcept）VICS车辆信息与通讯系统（VehicleInformationandCommunicationSystem）ITS智能交通系统（IntellectualTransportationSystem）TQQ用两队列实现的图形增长算法（Pallottino’sgraphgrowthalgorithmimplementedwithtwoQueues）DKA用桶实现的迪杰斯特拉算法（Dijkstra'salgorithmimplementedwithApproximatebuckets）DKD用两桶实现的迪杰斯特拉算法（theDijkstra'salgorithmimplementedwithDoublebuckets）DVR动态路径规划（DynamicVehicleRouting）VII 承诺书本人声明：所呈交的硕士学位论文是本人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得南京航空航天大学或其他教育机构的学位或证书而使用过的材料。本人授权南京航空航天大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本承诺书）作者签名：日期： 南京航空航天大学硕士学位论文第一章绪论1.1研究背景突发事件一直是社会生产中难以预测的问题，如何快速有效地应对突发事件，最大程度的降低财产损失和人员伤亡对相关部门来说仍然是一个很大的挑战。当前，很多相关部门都建立[1]了相关的应急救援反应机制来尽最大可能的降低突发事件带来的损失。民航运输业是我国快速发展的行业，推动了国家经济、政治、文化发展。然而民航运输业受天气影响严重，加上事故极低的生还率和较大的社会影响，民航安全问题显得尤为引人注目。近两年来在世界各地发生各类重大空难事故，如2007年9月16日，泰国“一二走”航空公司一架麦道82型客机在普吉国际机场降落时滑出跑道，折为两段并起火爆炸。机上123名乘客和7名机组人员中有89人丧生，41人受伤；2008年8月21日西班牙一架客机在首都马德里机场起飞时冲出跑道起火，飞机失事造成153人死亡。特别是“911”事件后，可以说民航安全问题已经引起了整个国际社会的高度关注，成为整个社会的关注焦点。在整个民航事故中，机场是处置民航突发事件、实施应急救援工作的主体。民航总局于2004[2]年4月3日颁布《民用运输机场应急救援规则》，要求个运输机场根据本地和本场实际制定完备的、可具操作性的应急救援计划，以便在紧急的情况下，能够及时地对各类意外事故作出快速反应，避免或者减少人员伤亡和财产损失。民用航空涉及到的紧急事件又是所有交通运输门类中最多、最复杂的。民航机场应急救援关键技术研究综合多个学科和领域的先进理论和技术，目的是大大提高应急救援工作的效率、减少突发事件造成的损失，也是避免因延误施救时机而导致二次事故发生而造成更为严重损失的有效手段。该研究与开发对所有交通运输门类相应的应急救援系统具有重要的指导和借鉴作用。特别是近年来中央将各级政府应对社会重大突发事件的能力作为“三个文明”中“政治文明”的高度进行建设，反观民航机场应急救援的现状，民航机场应急救援的关键技术研究与建设需求显得十分迫切。1.2研究意义本课题来源于国家自然科学基金委员会与中国民用航空总局联合资助项目（60776813）《机场应急救援辅助决策系统关键技术研究》，对其中的子问题（机场应急救援系统中资源动态调配研究）进行探索研究。在机场应急救援辅助决策系统中，所涉及的救援资源种类和救援单位比较多，各个救援单位相互独立，相同救援单位的资源数量有限，救援单位到事故地点的距离各不相同，在发生应急事件的情况下，筹集哪些救援单位的哪些资源参与救援更加合理；到达事故地点的道路状况错综复杂，同一道路的车速也会由于车流量和车流密度不同存在较大的差异，同一天的不同时1 机场应急救援系统中资源动态调配研究间段道路交通状况也不同，车辆到达事故地点的时间不容易确定，这些问题主要体现在以下几点：（1）救援资源单位筹集决策问题由于各个救援单位的资源数量有限，很可能存在的情况便是所需同一类救援资源的救援单位不仅仅是一个，此时决策最优单位组合能够使救援工作的更合理更有效的展开。（2）路段的“空间—时间映射”问题普通的以路段平均行驶时间作为路阻函数不能充分体现动态性。分析路段，将道路距离大小动态的转换为时间大小，建立距离与时间的映射模型，将空间道路网络映射为时间道路网络，这显得更加符合常理。（3）救援单位以最短的时间到达事故地点的问题确定好救援单位以后，各个救援单位协调一致，根据动态路网结构决策出救点的出救路线，以最短的时间到达事故地点，对整个救援工作的起了指导作用，使救援工作更加顺利的进行，提高救援的效率。鉴于存在的上述问题以及当前民航业的高速发展，各机场迫切需要尽快建立一套完善的民航运输机场应急资源动态调配救援体系，从复杂的动态变化的道路网络中找到到离事故地点“时间最短”救援资源，并且将救援资源以最短的时间、最小的费用调配到救援地点，实时地决策出出救路线，指导救援车辆以最短的时间到达事故地点，使救援在更早的时间展开，在整个机场应急救援工作中起了关键作用。因此，对机场应急救援中资源动态调配研究是十分必要的，其直接影响着救援效果。1.3研究现状机场应急救援由于其具有突发性、紧迫性等特点，利用先进技术解决此问题一直以来都是研究的热点，吸引了国内外许多专家和学者的关注。该问题的解决对机场应急救援来说具有重要的意义。从目前掌握的文献来看，研究情况如下：在应急救援过程中资源调配方面，国外许多学者对资源动态调配问题进行了很多研究，主要集中在医疗，火灾等方面，所研究目标多是侧重路径最短优化、路径显示、车辆的实时调配、资源的筹集等目标，而在机场事故方面上着重分析及组织优化、模拟紧急救援、对人员培训和[3]配置救援设备等方面。1998年，GeorgeF.List在放射性危险品运输优化模型中引入了应急问题，在他的模型中，总是离应急点最近的出救点参与应急救援，没有考虑单个出救点不能满足[4]需求时的情况。AliHaghani将应急物流描述为有时间限制的多物品、多模式网络流问题，并[15]给出了求解方法。AliHaghan并于2003年利用数学规划方法建立了应急医疗系统的急救车辆[5]调度优化模型并进行了仿真验证。Alle等人介绍了紧急救援的训练程序，模拟飞机碰撞后的救援，它的重点放在机场救援人员和社会救援资源的协调上,通过该方式的训练，提高了救援的2 南京航空航天大学硕士学位论文[6]效率。Tsai-YunLiao以医疗紧急救援为背景，基于分布式GIS网络，用无线电通信来安排和[7]调度应急资源，并用网络路径成功的解释了系统的动态模型。Fiedrich等在时间、资源数量和质量有限的情况下，以死亡人数最小作为目标，研究了地震后向多个受灾地点分配和运输资[8]源的优化模型。AliHaghani将应急物流描述为有时间限制的多物品、多模式网络流问题，并[9]给出了求解方法。AliHaghani并于2003年利用数学规划方法建立了应急医疗系统的急救车[10]辆调度优化模型并进行了仿真验证。G.Derekenaris等人介绍了希腊的救护车管理和紧急事故处理系统。在系统中，将GIS、GPS、GSM技术相结合，由指挥中心统一管理调度救护车，并对[11]救护车辆的路径进行优化，缩短了救援时间，提高了效率。GeorgeF以应急时间最短为目标，从一次性资源消耗的角度对应急救援中的路径选择进行优化处理，分析研究了其数学模型。[12]Cohn等人针对不同种类的机场，对机场进行紧急救援的最小需求进行了研究。这项研究分析了以往的事故报告，从不同的来源对数据进行推断，讨论了属于不同部门的服务设施，提出了不同资源数量和使用效率的最小需求，救援车辆的数量，救援的响应时间以及救援人员和其它[13]有关要素的最小需求。QUENTINK.WAN考虑了路网中多重路线的设计并提出了一种混合整数[14]仿真方法，以便挖掘路径结构和价值最小的运输路径。HaiboHu1分析了Dijkstra算法和NN算法，用一种叫做SPIE的模型来代替几何上的网络拓扑结构，该模型避免了不必要网络的价值浪费，最后通过数学分析和试验证明该方法可行，能够在动态变化的网络拓扑结构中效率更高[15]的分配资源。HESheng-xue给出了动态有效路径的明确定义，并将深度优先搜索的树搜索算*法、寻路定向性、层次空间推理策略以及A算法中的定向估价函数相结合，提出了动态有效路径的一种有效算法。在新算法中通过对交叉口延误的特殊处理，使得城市交通路网中的分向交叉口延误得以充分体现，并有利于将交通导行系统与交通控制系统相融合。同时对动态有效路径搜索在动态车辆路径导行和动态交通分配中的应用作了初步分析。在应急救援过程中资源动态调配方面，国内许多学者对该问题进行了研究，主要是资源筹集问题的联动处置，模糊数学方法优化道路，集中在路网中最短路径的优化设计、道路动态变化因素等，而在机场方面上的资源调配优化研究的较少，也没有形成一个完整的概括体系。刘[16-18]春林、何建敏等研究了物资需求约束条件下多出救点的组合出救的资源调配问题，提出了基于“时间最短”、“出救点数目最少”的多目标数学模型，并构造模糊目标集进行求解。高淑阳[19]建立了基于最短和出救点数目最少为目标的的两层优化数学模型，并给出求解算法。数值算[20]例验证了所建立模型的合理性与算法的有效性。2005年，迟文学等人基于GIS（地理信息系统）建立了一套机场应急救援与辅助决策支持系统，并利用NetEngine网络工具包实现最短路径[21]分析。魏新宇以优化道路交通网中路段的权值为出发点，结合消防工作实际情况的特点，运[22]用模糊数学中的层次分析法评定道路的权值，建立了消防灭火救援最优调度模型。苏永云对车辆导航系统中线路引导信息的供给与需求进行了综合分析,提出了一种新的具有真实最短路3 机场应急救援系统中资源动态调配研究*径意义的实时动态最优路径,并设计了搜索该路径的改进Dijkstra算法与改进A算法,前者[23]适用于多车导航,后者适用于单车导航。李元臣通过对Dijkstra算法运行速度分析,在该算法的基础上采用二叉树结构来改进Dijkstra算法,在一定程度上优化了最短路径的计算过[24]程,并提高了算法的分析效率,实际数据测试也表明了该算法的可行性。李德龙从道路网络拓扑结构的自动构建以Dijkstra算法中快速搜索技术的实现入手，综合考虑核心算法和数据存储结构两个方面,提出了直线优化Dijkstra算法，该算法能够有效降低时间复杂性,提高系统的[25]效率。刘海燕通过对经典Dijkstra算法的改进，使用完全二叉树结构来实现优先级队列的操作,在一定程度上优化了最短路径的计算过程,并降低了算法的时间复杂度,使时间复杂度达N[26]OE(lg),并用实际数据测试也表明了该算法的可行性。唐铁桥介绍了交通流动力学理论[27]的发展、研究，并结合当前国内发展现状提出它将来的发展趋势。顾国民等利用微观交通模型的仿真现实交通,在模型中进行短期的交通预测，预测交通道路在未来某一个时刻的行车状[28]况，在这个基础上运用改进栅格法的Dijstra算法演化方法进行动态的路径规划。孙海鹏等研究动态路网模型及其算法的基础上,结合实时交通信息,提出并实现了一种适合国内车载导[29]航应用的动态路径规划的改进方案，并用仿真结果验证了其有效性。李志鹏依据现有交通流微观模型的基础上，提出了改进的模型，并进行相应的理论分析和数值模拟。此外，还探讨了宏观交通流模型在路网交通状态分析中的应用。纵观上述文献，在资源的筹集方面主要有多点组合的确定型应急资源筹集、应急时间最小为目标的一次性消耗资源筹集、在时间最早的前提下，出救点数目最少多的目标应急资源筹集、连续消耗应急资源筹集；在路阻函数方面有众多的模型，主要是从交通分配及控制的角度上进行考虑研究。这些研究为机场应急救援管理系统中资源动态调配问题提供了可以借鉴的思路和数学模型。但文献中有的侧重于机场应急救援工作的某一方面，如资源的优化筹集、救援机制的建立等，有的研究的是工业、农业、医疗等单方面的救援路径优化，有的是对交通流路径优化问题的研究。没有将机场应急救援系统中资源动态调配的整个过程充分整合起来，没有去考虑应急筹集所形成的资源出动成本(费用)问题，充分形成一个完整的多资源多目标的应急资源调配体系的研究讨论；没有从道路的空间与时间的关系上寻找最优映射模型、实现路段的空间距离向时间大小的实时转化进行深入分析。1.4本文主要研究内容1.4.1研究目标近些年来，随着计算机科学、人工智能技术、运筹学、交通工程学、地理信息科学、管理学技术等学科的发展，为本课题的研究与实施提供了强有力的理论支撑。本课题的研究目标是：（1）在救援系统中所涉及的救援资源和救援单位比较多的情况下，借助计算机技术、人工4 南京航空航天大学硕士学位论文智能理论将各种救援资源的快速联动处理，快速建立资源筹集方案，并随时间的递进动态改变救援动态调配方案。（2）资源动态筹集的依据是时间，车辆行驶路径的选择依据也是时间。在车速和道路交通状况动态变化且具有不确定性的条件下，采用“空间—时间映射”的思想建立数学模型，将空间距离转化为时间大小，获得时间最短的救援资源派遣优先权。（3）从理论上论证路段权值的确定方法及车辆路径的动态规划过程，实现动态的时间最短路径的搜索确定，形成救援资源的动态行走路线，进一步实现资源动态调配的优化，借助GIS技术、VB工具，实现路径动态变化的模拟显示。1.4.2研究内容本课题的研究内容是，在救援等级和资源规模决策出以后，指挥哪些救援单位来筹集相应的资源以及怎样确定救援资源调配优先权。具体内容安排如下：第二章对资源动态调配进行整体分析。依据机场应急资源动态调配的特点，运用Agent理论构建了MAS动态调配组织机构；详细分析了指挥中心Agent、资源Agent、交通网络Agent、救援现场Agent的主要功能和结构；并在分析资源调配过程的基础上阐述了协同推理机制模型及过程。第三章对资源动态筹集进行研究。将机场应急救援系统中的资源筹集问题描述为离散化消耗多资源多目标调配形式，通过建立其数学模型来阐述“多资源、多目标、离散化”三要素，并采用蚁群算法求解，验证其结果的正确性。第四章对路段的“空间—时间映射”模型进行构造。在路网的“空间—时间映射”问题上采用了交通波理论对各种情况下的路段进行分析研究，并确立了其对应的数学模型，最后通过举例来计算求解，验证所建“空间—时间映射”模型的可行性、正确性，体现出路段通行时间的动态变化特性。第五章是实现时间最短路径的动态规划实时显示。在时间最短路径的动态模拟显示上采用了将工作时间划分为若干时间段的方法，以及在应急车辆行驶过程中动态规划的思想进行分析研究，最后通过软件编程将车辆的运行过程的实时路径变化在地图上模拟显示。最后，对所做论文进行总结，以及对机场应急救援系统中资源动态调配研究的进一步展望。5 机场应急救援系统中资源动态调配研究第二章资源动态调配的整体组织结构分析机场应急救援中涉及的单位众多，包括驻场救援单位和协作救援单位。当救援规模较小时，调动小部分救援单位就可以完成救援任务，反之，则需要调动多个救援单位来参与救援工作。救援工作中，救援指挥中心需要与救援单位、救援现场、交通部门及时协调沟通，获得实时相关信息来动态的指挥救援。救援过程中，各相关部分之间的决策过程实质上属于分布式决策的范畴，因此，在本章中，基于多Agent理论在协同决策中的优势，从全局观出发，对资源动态调配的进行整体上分析，利用多Agent理论对应急资源的各主体进行组织结构分析，以协调指导救援资源的实施方案。2.1AGENT理论及结构Agent是一个具有控制问题求解机理的计算单元，它可以指一个机器人、一个专家系统、[30～33]一个过程、一个模式或求解单元。Agent既能完成各自的局部问题求解，又能通过协作求解全局问题，Agent相互协作产生不同的行为，适应不断变化的环境。每个Agent根据当前的状态决定自己的行为，协作解决当前[30][30-31]的全局任务。Agent有许多特性，本文主要研究Agent下面三个特性：(1)自主性。它是指Agent具有自己的目标模式，并由目标引导自己的行为，这种行为不是简单的反应行为，而是具有主动性，能实现单个Agent最优。应急单位中心Agent的基本目标是调配合理，它基于自己的知识库和复杂的决策判断能力，给出合理的调配结果。(2)适应性。它是指适应环境，具有从经验中学习的能力，以实现在变化的环境中改善自己。Agent在接受任务、完成任务的过程中不断地更新自己的知识库，使自己的行为计划与实际目标的偏差不断减小。(3)合作性和协调性。它是Agent的重要特性，特别是在此多Agent系统中。各单位Agent和主控中心Agent之间进行协调达到个体用户和系统较优，同时达到它们各自的目标。在Agent系统中，Agent总处于一定的环境中并能通过某种感知方式探测环境，单个Agent是具有行为能力的实体，基于预先制定的目标主动地采取行动，并在执行过程中不断地与环境[30]进行交互、充分地了解和适应环境的变化。在应急资源筹集中，各个应急单位在实现系统目标的同时，充分实现个体的目标。Agent对不断变化的环境的适应性和求解问题的自主性，以及Agent间的相互合作和协调的特性很适合于解决资源的调配。基本的单个Agent主要由环境、感知器、建模、规划、决策生成、通信、执行器等模块组成。图2.1给出了单个Agent的基本功能结构。6 南京航空航天大学硕士学位论文Agent规划预测协作与通信建模决策生成通信请求/答应信息一般情况紧急和简单情况动作感知器反射执行器环境其他Agent图2.1单个AGENT的基本结构2.2资源动态调配组织结构的建立2.2.1基于MAS的资源动态调配组织结构模型MAS（多Agent系统）是一种典型的分布式系统，基本结构为集中式、分布式、混合式。其中混合式结构是由集中式和分布式两类结构组成，它包含一个或多个管理服务机构，该机构只对部分成员Agent以某种方式进行统一管理，参与解决Agent之间的任务划分和分配、共享资源的分配和管理、冲突的协调等。其它成员之间是平等的，它们的所有行为由自身做出决策。此种结构平衡了集中式和分布式两种结构的优缺点，适应分布式MAS复杂、开放的特性，因此针对机场应急资源动态调配特点，从整体与部分的角度考虑整个系统的相互协调与协作，并需要对于数据资源实现最佳协调共享。因此，提出了构造混合式多Agent的机场应急救援资源动态调配系统模型。系统组织结构模型如图2.2所示。机场资源调配指挥中心Agent事故现场Agent救援资源Agent交通网络Agent外部环境组织关系交互作用范围Agent图2.2机场应急救援资源动态调配MAS组织结构图7 机场应急救援系统中资源动态调配研究2.2.2各AGENT主体的主要功能及结构机场资源调配指挥中心Agent：它是最高级领导，包括信息收集Agent，协调Agent、管理Agent、监控Agent等智能体。它负责对下面所辖四个Agent组进行协调管理工作，根据资源消息、救援现场信息、路网实时信息进行全局规划，领导整个Agent系统实现全局目标，即最大限度减少事故损失，防止二次事故发生。管理协调Agent采用混合型，它能够在收到事故信息报告以后，通过建模和规划，产生救援方案，并且根据消息反馈，动态修改救援方案，以达到最佳效果。救援资源Agent：根据单位所拥有资源种类进行分类，生成单位Agent。主要功能是接收机场资源调配指挥中心Agent传来的资源调配信息并根据调配信息形成资源调配方案，派遣资源点Agent；资源点Agent为一个移动Agent，移动Agent具有自治性、移动性、智能性、协作性和安[31]全性，它能够根据外界环境变化与交通网络Agent进行协商计算出资源点Agent到事故地点的最短时间和最佳行车路线；将最短时间和资源量等信息传给机场指挥中心Agent和原来资源所在单位Agent。以便各救援点Agent主要目标是尽快赶赴事故现场，实施救援。救援资源Agent采用分布式结构，资源Agent独立运行，资源Agent采用集中式结构，根据外在环境迅速决策出由那些单位参与救援，生成资源调配方案。交通网络Agent：主要包括区域路网Agent，区域路网Agent又包括路段Agent、交叉路口Agent等。主要功能是获得道路的实时交通信息，并根据这些实时交通信息建立“空间—时间映射”模型将路段的空间距离大小转化成时间大小，从而计算资源点到事故点的最短行程时间及时间最短路径告诉资源Agent，以便资源点能够尽快的时间内筹集资源赶赴事故地点。各区域路网Agent是分布式的，相临路网Agent相互通信协作；区域路网Agent内部是集中式结构，这样能够提高与移动Agent实时交互效率。救援现场Agent：该智能体在事故发生时生成，事故救援结束后消失。主要功能是接受资源点Agent的救援措施；协调救援步骤，使救援工作顺利展开；监视救援现场的进展情况，并将救援进展情况反馈给机场资源调配指挥中心Agent。图2.2中的最底层是外部环境，各个Agent在系统运行过程中都会作用于一定范围的外部环境，并从外部环境中获得信息用于本Agent学习、管理、协调内部结构等。2.3基于AGENT的协同推理过程构建协同推理过程是整个资源动态调配过程的关键问题，它能在实现各主体的充分自治和效用的同时保证各主体在信息充分共享的基础上进行协调、协作，实现复杂系统的整体优化。协调是指一组智能Agent完成一些集体活动时相互作用的性质，是对环境的适应，在这个环境中存在多个Agent并且都在执行某个动作。协调一般是改变Agent的意图，协调的原因是由于其它8 南京航空航天大学硕士学位论文[32]Agent意图的存在。协作是非对抗的Agent之间保持行为协调的一个特例。2.3.1AGENT间的协同推理模型及结构对于协调的需求，是由于实体、信息、资源的分布特性以及它们之间的相互依赖而产生的[32]。各Agent分布在不同的空间位置，如网络节点上，不可能也没有必要进行集中的全局最优化计算。一方面，由于所研究的协调的应用环境一般是复杂系统，系统中信息量巨大，任何集中的计算都是非常耗时的，无疑可能超过计算时限，使得需要实现的“事先”协调推理失效；另一方面，由于资源限制和隐私问题，Agent只能感知局部环境，且不能完全感知其它Agent的信息，任何Agent不可能也不需要感知到整个系统的情况。这就决定了Agent的信息是主观的、局部的，甚至可能是不正确的。Agent只具有各自的局部视图，因此需要不断修正自己的局部解，才能得到全局满意解。Agent内部的协调推理结构在整个Agent的生命周期内都处于活动状态，控制行为过程的理性选择。它根据Agent自己感知到的外部环境信息，通过交互、通信获知或预测其它Agent的状态及行为规划，对自己的局部行为进行推理，评价活动规划的可行方案，从中选择一个最优活动执行方案。Agent通过交互、通信，为自身的活动规划对其它相关Agent做出承诺，以保证在一定范围内Agent社会的活动一致性。显然，Agent在这个过程中需要根据感知和通信得到的新信息修正、补充自身的主观信息中不正确、不完全的部分。在一个开放的系统中，每个Agent可能具有各自不同的的内部结构，也就是说，这些Agent可以是异构的。但是，协调推理作为内部结构的一部分，无论如何实现都必需遵照个体理性的原则，也就是自我利益驱动的原则。其作用是使Agent的活动与其它Agent、环境协调一致，以达成个体目标或团队的联合目标。在多Agent系统中，Agent通过感知器感知环境的变化和其它主体的行为，规划器根据这些数据和变化产生Agent状态转换之间的动作序列和时间安排，并将这一规划交给协调推理机。状态之间的转换可以有多条路径，也就是多个可选择的计划，协调推理机根据协调模型和信念、愿望、意图知识库对这些计划路径进行过滤、筛选，找到最佳方案，然后交给Agent执行机构来完成。如果把推理结构看作一个黑匣子，可以通过输入输出模型描述协调推理模型，如图2.3所示：输入：感知到的外部环境和其它Agent的信息；输出：做出承诺的行为序列。下面主要探讨协调的推理过程next函数，推理过程next函数是通过描述Agent心智状态的BDI来建模。9 机场应急救援系统中资源动态调配研究协调模型核心推理结构推理模型SeeAction合作模型BDI图2.3协调推理模型2.3.1.1AGENT的BDI模型协同和推理是协调推理机的两个关键问题。在MAS中，虽然处理协调的方法有很多种，包括反应式Agent的仿生学方法、纯数学计算方法，但是，Agent之间的协调和推理行为如果不涉及到Agent的思维状态模型，就难以理解和设计复杂的社会行为。Agent的思维状态模型用来描述Agent的思维属性和它们之间的关联，以及与感知、规划、[34][35][36]协调、合作等活动的关系。在Bratman的哲学分析基础上，Cohen和Levesque提出Agent[37,38]的意图模型，Rao和Georgeff进而将其发展为BDI框架。BDI理论模型把Agent看作是理性主体，通过信念（Belief）、愿望（Desire）、意图（Intention）的关系来表达Agent的理性。信念是Agent的状态信息；愿望是Agent的动机状态；意图是Agent的慎思状态，表示Agent对未来行为的当前选择。这对人类社会行为和生物的群体行为提供了很好的解释工具，更进一步的为构造类似的行为提供了设计方法。2.3.1.2BDI的协调推理结构在讨论协调的个体理性之前，先给出几个定义：S：环境状态集；Ag：所有Agent的集合；Per：感知信息集；BEL：信念集；DES：愿望集；INT：意图集；Act：原子行为集；T：时间集,τ∈T；*Π：计划集，其中π=×()ActT,π∈Π；*(X）：表示由集合X中的元素构成的序列；f()g：α是偏好函数，α∈Ag。α对于aA∈g，可以这样描述：ia≡(,,,,PBDIACTseebrfoptionfilterexcute,,,,,)i10 南京航空航天大学硕士学位论文其中：PP⊂er表示a可以感知到的信息，B⊂BEL，DD⊂ES，I⊂INT分别表示iprepostpreAgent三种心智状态。其中，Ixxs=={|(,,)πs}，sS⊂为实现意图的前提，π∈Πxxxxxpost为实现意图的行为规划，sS⊂为意图最终实现的目标。xsee：SP→er，表示Agent的感知过程。brf：B×→PerB，表示Agent的信念修正过程。option：B×→ID，表示愿望的确定过程，包括两方面：一是递归的发现更具体的愿望，即子目标的形成；二是保证愿望与信念、意图的一致。filter：B××→IDI，表示意图的选择、确定过程。这里有三种可能：放弃不可达或不相容的意图；保持未证明不可达或不相容的意图；加入新的意图。execute：I→Act，表示Agent的执行过程。文中讨论的是Agent协调的推理结构，对于感知过程see和信念修正过程brf不做详述。对于aA∈g来说，推理过程如下（示意图如图2.4）：①给定s，sD⊂，它可由通信、感知、内部推理等得到。iipost②如果∃X,stxX..∈，ss⊇，则X为可能意图集。xipre③如果∃Y，YX⊆，styY..∈，sB⊂，则Y为现实可能意图集。y④如果yY∈，∀∈yY，f()()yf≥y，则选取y为承诺意图，其中，π为承诺计mααmmmpost划，s为承诺目标。m⑤若执行y中失败，则从Y中去除y从(4)重新选取承诺意图。mm通信模块内部推理，模块感知模块获得siYX为可能集∃XN继续执行N∃Y结束YY为现实可能意图集Nf()()yf≥y结束ααmY执行ymN执行成功结束Yym为承诺意图图2.4AGENT的协调推理过程图11 机场应急救援系统中资源动态调配研究2.3.2资源动态调配的协同工作过程在上面提出的BDI理性模型之后，下面分析机场应急救援资源动态调配的协同工作过程。机场应急救援系统中，确定救援等级、救援资源调用规模后需要协调完成以下调配工作：（1）需要决策出派遣哪些单位参与救援。在机场资源调配指挥中心根据调配规模及救援等级，分析出需要哪些救援资源（resource）、资源数量（quantity）、资源所在单位（unit）、单位需要做的动作（action），形成任务表（table），并将该任务表信息传送给相应单位组（unit）。（2）救援相关单位组（unit）将资源情况告知机场资源调配指挥中心，包括相关资源可用数量（quantity）、资源所在地点（area）、资源完好程度（degree）。（3）机场资源调配指挥中心得到相关单位组（unit）的反馈信息后，对救援资源进行初步决策筛选，决策是否需要向更高层次救援单位派遣救援任务。同时救援相关单位组（unit）在得到机场资源调配指挥中心的回答之后，与交通管理部门进行协商，根据当时的交通网络状况分析资源点（A）到事故点（D）的耗时并告诉机场资源调配指挥中心。（4）在机场资源调配指挥中心得到上述信息后下，下达调配命令，将此时参与此次救援的资源（resource）、资源种类（sort）、资源数量（quantity）等任务信息告诉相关单位组（unit）。（5）相关救援单位组将资源派遣下去，资源点变成一个独立的子救援单位（su_unit），与交通路网管理部门实时通信协商，根据实时交通情况将路网的空间距离映射成为时间大小来确定最合理的行驶路线(line)。并将实际情况告诉所在救援单位组和机场资源调配指挥中心，以便能够及时更正调配信息。（6）救援资源点（A）到达事故地点（D）后实施救援，此时，救援现场指挥中心与机场资源调配指挥中心保持实时通信，将实际救援进展情况告知指挥中心，传送的信息主要有救援进行程度（extent）、伤亡程度（injure_extent）等。指挥中心根据救援的实时状况再进行资源决策筹集。图2.5给出了基于多Agent机场应急资源动态调配协同工作过程。该协同过程的实现基于理性Agent的BDI模型，使用的三个基本模态算符为：信念(belief)、愿望(desire)和意图(intention)。Agent间的协调是一种动态行为，是Agent对环境及其它Agent的适用，它往往通过改变Agent的心智状态来实现。协作则是保持对非对抗Agent间行为协调的特例，它通过适当的协调、合作完成共同目标。多Agent虽然代表着不同领域,有着自身的局部利益和局部目标，但在协同求解时，应在共同规划的约束下，协调有序地进行求解。即局部求解过程必须根据外部环境的变化做出及时调整，以达到协同求解过程的交互性、动态性和及时性。12 南京航空航天大学硕士学位论文获得事故相关信息协调救援规模、等级信息识别与分析救援资源协调拟派出资源点Agent交通路网状况分析形成调度计划否各单位组Agent指挥中心Agent重新协调调度方案是否合理是任务分配到资源点Agent协调资源调度计划执行资源调度任务交通路网状况实时分析资源行进否资源调度是否合理重新协调是参与救援工作救援进展状况实时协调救援现场监控图2.5基于MAS机场应急资源动态调配协同工作过程2.4本章小结本章根据机场应急救援资源动态调配的特点，从整体角度分析构建了基于多Agent的资源动态调配的组织结构模型，接着分析了指挥中心Agent、资源Agent、交通网络Agent、救援现场Agent的主要结构及功能，论述了资源动态调配的协同推理过程。本章通过利用多Agent理论来建立应急资源的动态调配模型，为救援资源的出动方案的部署提供一个很好的依据。13 机场应急救援系统中资源动态调配研究第三章应急资源筹集问题的研究3.1引言当民航突发应急事件发生后，通常必须调用多个应急资源单位进行救援，但各相关救援单位分布在不同位置，距离事故地点的位置不等，而且不同的救援单位所拥有的救援资源有限，不同的单位拥有不同的救援资源，甚至相同的单位拥有不同的资源。根据救援等级和规模进行组合优化，及时地、合理地、准确地筹集相关救援资源，一方面使得救援时间尽早展开，另一方面使得救援出动费用最低，因此基于时间约束下的运输规划问题和组合优化更能够体现应急[39]资源筹集问题的本质特点。另外，突发事件本身的随机变化与动态性等特点决定了应急管理的资源筹集是一个动态的多阶段过程。突发事件的发生发展不可完全预见，很多因素综合作用于事件的发展情况，所以资源筹集又是一个动态的过程。因为一次筹集救援资源很可能不能完全结束救援工作，这就需要第二次、第三次⋯⋯直至完全消除灾情。这里所说的多阶段资源筹集可能是由于突发事件不断发展变化，需要继续调用相关救援资源，也可能是由于某些资源只[40]能与其它种类的资源匹配使用而连续调运。为此，如何科学合理地进行救援资源的筹集，使得在满足处置突发应急事件需求的同时，所筹集的资源到事故地点的时间最短，并且从总体上最大限度地降低处置突发应急事件资源运输的出动费用，这对于日常的生活生产具有很重要的意义，也正是机场应急资源调配问题所要解决的重点之一。从上面的资源筹集过程分析可以看出，应急资源的消耗更多的情况下并不是匀速消耗的，而是随着时间的变化呈现出一种离散函数式的变化。一般地，处置突发应急事件的过程可以划分为应急准备期、应急展开期、应急持续期和应急恢复期等阶段，在各个阶段实际的应急资源[40,41]消耗是各不相同的。随着应急阶段的转换，应急资源的消耗也随时间做动态变化。本文将以离散消耗这个特点为背景探讨多资源点应急资源筹集的组合优化方案问题。在资源需求约束和应急时间约束下，考虑应急救援活动的出动费用最小的优化模型。从应急系统成本费用角度考虑，将救援活动的出救出动费用极小化作为另外一个应急优化目标是合理的，且更具实际意义。3.2应急资源筹集的流程组织在问题需求中，文中提到突发事件的多动态性，需要多阶段筹集资源，直到事故救援结束。筹集过程有一下几个方面（图3.1）：（1）民航突发事件发生时，机场救援指挥调配中心获得事故等级及救援力量等信息，分析决策相关资源。（2）将相关救援资源进行分类，并将之分配到二级指挥调配中心，如医疗、公安、消防等，14 南京航空航天大学硕士学位论文由二级指挥调度中心实施资源的筹集。（3）二级指挥调配中心根据救援现场在该时刻所需要的各类资源量，制定资源筹集方案，筹集资源，决策出由哪些单位的那些种类的资源参与救援。（4）检查资源筹集是否合理，若合理，奔赴救援现场；若不合理，重新筹集。（5）救援资源到达现场参与救援，救援过程中的，若发现派遣资源在某时刻短缺、不足，则将该动态的实时需求量反馈到机场救援指挥调配中心。回到第（3）步，重新筹集资源，若没有出现上述情况，则继续实施救援。（6）继续救援，直到救援结束。应急事件开始事故等级、救援力量信息救援资源分类资源需求量决策资源筹集方案否评价方案是否合理是奔赴事故现场实施救援否资源是否充足是继续救援救援结束图3.1应急资源的筹集流程组织3.3资源动态筹集的数学描述模型机场应急资源的筹集与其它类救援的筹集有相似性，也有自己的特点，此处从机场应急救援资源的筹集方面上分析了其特点：机场应急资源筹集问题，其资源消耗是离散化的；机场应急资源筹集问题，是一个多目标的组合优化问题；机场应急资源筹集问题，涉及到的应急资源[16,19,42,43，44]是多种类的。基于上述应急资源筹集问题的特点，在参考现有研究成果的基础上，描述了一种新的资源筹集问题——离散化消耗多目标多应急资源筹集问题。（1）当突发事件发生，所需要的应急资源一般是多种多样的。较大的突发应急事件，如民15 机场应急救援系统中资源动态调配研究航事故的应急处置，需要涉及的应急资源包括了医疗方面的救护车、医生、护士，消防方面的消防车、消防员等等。只需一种应急资源的突发事件在现实中还是较少的。因此，大部分的基于应急的资源筹集问题，应该作为多资源筹集问题来求解。设A12,,AA⋯,n为n个可供选择的资源出救点，Ai点第jj(1=,2,⋯，m)中资源的可出救量为bb(0>=),1i,2,⋯,n，这些数据来源于平时已知的资源潜力调查数据。D为事故现场，ijijnD上的资源j需求量为dj，且∑bdij≥i，需求数据dj为救援规模等级决定。要求制定出一个i=1最优的资源筹集方案，既从n个可供选择的资源点中确定出相应资源j的p()pn≤个资源点jj参与救援，并且确定相应的筹集资源量xx(0≥)，资源筹集的结果需要满足资源需求的条件。ijij经过抽象后的资源点选择理论模型如下：设资源筹集方案的形式为ϕ，则任一方案ϕ可表示为(3-1)：xxxK11121mxxLxϕ=21222mMOMxLxnn1m(3-1)0≤≤xbijijnst.∑xij=dji=1n∑bdij≥ii=1由上式看一看出，第i行表示资源点A参与应急救援的资源向量，若该向量为0，则表示i资源点A不参与应急；第j列表示各资源出救点参与应急救援的第j种资源数量。i（2）当应急事件指挥中心对应急资源进行筹集时，一般都会对资源筹集提出要求，一般有如下几个：一是对资源的筹集应该能够使得应急时间最早，从而使得对应急事件的处置能够尽早开始。二是对应急资源的筹集，应该使得各种应急资源的出动费用最少。针对具体的应急需求，还会提出相应的具体特殊要求。由此可见，应急资源筹集问题实质上是一个多目标的组合优化问题，既不同于一般的单目标组合优化问题，也不同于两阶段目标。对该问题的求解，应充分估计人的主观能动性，考虑各个目标的合理折算。资源筹集中满足的目标条件之一：追求应急救援开始时间最早，即到达事故地点的最大时间为救援开始的最短时间。设从A到D需要的时间为tt(0>)，设tt<<，密度增加，产生的w为集结波；21当kk<，密度降低，产生的w为消散波。214.2.2“空间—时间映射”模型建立城市的道路交通状况比较复杂，应急救援车辆有其独有的特点，在交叉口处不受红灯限制，因此，本章结合实际，利用交通工程学中的交通波理论对基本的路段进行分析建模。在通常情况下，路段的交通状态可以分四种情况:（1）路段正常，其通行时间就是正常情况下的行驶时间；（2）由于障碍物等不确定因素的影响，行驶道路的通行能力降低，但不产生排队；（3）由于障碍物等不确定因素的影响，行驶道路的通行能力严重降低，而且产生了排队队列；（4）由于障碍物等不确定因素的影响，道路被完全阻塞。（1）路段正常时的通行时间确定30 南京航空航天大学硕士学位论文设路段()ab,总长度为L，t时刻通过路段(ab,)的速度为vt()，应急车辆的最大可行()ab,ab速度为v。因为应急车辆追求最快时间，所以，此时vt()为应急救援车辆的最大可行速度v，车ab车则此时路段的通行时间Tt()表示为：abL()ab,Tt()=(4-4)abv车（2）路段不产生排队时的通行时间设上游交通需求为q，瓶颈处的通行能力为:s，当qs≤时，不产生排队。当路abnab1abnab1段上游的交通需求没有超过不确定因素导致的瓶颈处通行能力时，上游驶来的车辆在瓶颈处低速通过，不形成排队。这种情况的通行时间分配如图4.2所示，设路段拥挤处为图示“e”，不确定因素的存在引起的瓶颈长度为L。abpLabpvvt=ab()L()ab,图4.2路段无排队时的区段示意图流量非瓶颈路段Q︵辆/h)瓶颈路段密度K（辆/km)图4.3瓶颈处流量与密度的变化图图4.3是瓶颈处的流量—密度曲线变化图，从图中可以看出，由于瓶颈点的通行能力降低，当上游的流量到达瓶颈处流量时，密度达到增大，车速开始降低，通行时间相应增加，所以此时路段的通行时间Tt()表示为：abLLL−ababpabpTt()=+(4-5)abvv()t车abp式中：vt()是t时刻路段()ab,瓶颈路段的车辆平均行驶速度。abp31 机场应急救援系统中资源动态调配研究（3）路段有排队队列时的通行时间在（2）中分析了qs≤情况下的无排队时路段通行时间，然而，当上游的交通需求大abnab1于瓶颈处的通行能力时（qs>)，在瓶颈处上游产生排队队列。此时，在瓶颈段上游就会abnab1有排队队列，即形成一个排队等待路段，队列上游则是驶入流所处的路段，在瓶颈段下游则是驶出流所处的路段(如图4.4中所示)。因此，应急资源车辆在此路段上的通行时间主要由四部分构成：第一部分是车辆在驶入流的通行时间Tt()；第二部分是车辆在排队流中的排队等待ab1时间Tt()；第三部分是在瓶颈段的通行时间Tt()；第四部分是车辆在瓶颈段下游的通行时ab2ab3间Tt()。ab4Lab1()tLab2()tLab3()tLab4()tL()tab5图4.4路段有排队队列时的区段示意图假设Lt()为车辆在瓶颈段上游正常行驶的长度，Lt()为某时刻队列的排队长度，ab1ab2Lt()为不确定因素造成的瓶颈段长度，Lt()为车辆在瓶颈段下游行驶的长度，Lt()为ab3ab4ab5瓶颈段与道路入口间的距离，其中Lt()和Lt()固定不变，Lt()随集结波上移而增长，ab3ab4ab2Lt()随集结波上移而减小。ab1定义：TT()为时间t时刻进入路段(ab,)的应急车辆在(ab,)上的通行时间，则有：abTtTtTtTtTtab()=+++ab1234()ab()ab()ab()(4-6)LtLtLtab512()=+ab()ab()(4-7)其中，Lt()是确定路段不确定因素位置后就已知的量。ab5A）应急车辆驶入时间Tt()ab1由上游驶入流的流率q与密度k，根据交通流的“流量一密度一速度”关系式可以求abnabn出驶入流的车辆平均行驶速度为v，则驶入时间Tt()为：abnab1LLk⋅ab11ababnTtab1()==(4-8)vqabnabn因为Lt()的大小受到集结波位置的影响，所以要计算Tt()必须先求得队列末端位置ab1ab1到不确定因素发生的距离(即集结波向上游蔓延的长度)。设不确定因素发生在t时刻，则t时0刻，集结波会移动到离不确定因素发生地距离Lt()的地方，即：Ltvtt()=w⋅−(00)()tt≤(4-9)式中：v为集结波移动速度。w32 南京航空航天大学硕士学位论文因此，可得Lt()的值：ab1LtLtLtLtvtab15()=ab()−=−()ab5()w⋅(4-10)Lkab1⋅n(Ltvttkab50()−⋅−w())nTtab1()==(4-11)qqnn由上式可见，应急车辆通过该类型路段所需要的时间与驶入流的流率q、密度k、事件nn发生的位置Lt()、集结波速v，以及时刻t相关。ab5wB）应急车辆排队等待时间Tt()ab2由排队队列的流率q与密度k，可得一辆车通过队列的时间Tt()为：abq1abq1ab2LLk⋅ab2ab21qTt()==（4-12）ab2vqqq11由于不确定因素造成的排队队列长度为Ltvtt()=⋅−()，因此，排队等待时间Tt()ab20wab2为：vttkwa⋅−⋅(01)bqTtab2()=(4-13)qabq1C）应急车辆瓶颈段处的通行时间Tt()ab3瓶颈段是指不确定因素发生后，对道路造成破坏的具体路段，短时间内很难恢复，所以瓶颈段的路段长度Lt()不发生变化。假设瓶颈路段车辆的行驶速度为v，则瓶颈路段行驶时ab3ab3间Tt()为：ab3Lab3Ttab3()=(4-14)vab3D）驶出时间Tt()ab4驶出时间是车辆驶过瓶颈段后，是以自由流状态行驶的一段时间，因为瓶颈段限制了车辆的驶出数目，因而这个地段的交通流为高速低密度的自由流。因而瓶颈地段不变，所以驶出路段的长度Lt()也是不变的。应急车辆的以最大可行速度驶出，则驶出时间Tt()为：ab4ab4Lab4Ttab4()=(4-15)v车可见，Tt()和Tt()都只与不确定因素发生的位置有关。ab3ab4（4）道路被完全堵塞情况下的通行时间由于障碍物等不确定因素的影响，道路被完全阻塞，这种情况可设其通行时间无限大。即：Ttab()=∞（4-16）以上是根据路段的4种情况分别进行分析，从路段的动态变化角度上，将路段距离长度映射为时间大小。33 机场应急救援系统中资源动态调配研究4.3模型求解方法路网错综复杂，路段中交通状态即实时路况的判别是实现“空间—时间映射”的根本解决方法。空间的距离信息容易获得，可以从精确的电子地图上获得，而路段交通状态判别需要解决如下几方面的问题：动态交通信息采集与处理：采用何种信息采集手段、在何处布置检测设备、如何以最低的成本全面有效的采集路段的动态交通信息，动态交通信息是多信息源、多种类，并且是海量的信息，如何运用先进的信息处理技术对这些海量的交通信息进行进行分析和处理，从中挖掘出交通流运行的特征信息，以便准确的进行交通状态辨别。路段状态判别：根据实时的动态交通信息，准确、快速地判断出路段中交通流的运行状态，及时地判别路段中集结波状态，以便应急车辆能够更好的分析路段。1．实时交通数据的采集与处理办法实时交通流信息自动采集技术可根据交通检测器的工作地点不同划分为固定型采集技术和移动型采集技术两大类。其中固定型采集技术可提供地点交通流参数数据，而移动型采集技术可提供路段交通流参数数据。实时交通信息的采集方式通常有固定检测器采集和探测车系统采集，其中固定检测器提供的数据为地点交通流参数数据，探测车系统提供的数据为路段交通流参数数据，下面分别进行阐述。（1）固定检测器固定型采集技术是指利用安装在固定地点的交通检测器设备对移动的车辆进行监视，从而实现采集交通流参数的方法总称，目前主要包括磁频、波频和视频三种类型。发达国家的大城市一般都建有较完善的交通信息采集系统，其中绝大部分的动态交通流信息是由固定检测器采集的，这是一种相对成熟的采集技术。例如新加坡的EMAS，美国的FAST-TRAC、TRAVTEK和欧洲的Traffic-Master等。北京市交通信息采集系统已建成，四环内基本实现网状覆盖，检测路段包括二、三、四环快速路和城市主干道。所采用的交通流信息采集设备主要有：环型线圈、视频检测器微波检测器、超声波检测器和牌照识别系统等。固定检测器采集数据为实时地点交通流参数数据，通常包括地点交通量、地点车速等，可直接求得实时的路段通行时间。对固定检测器数据的处理步骤为：①剔除不合理的上传数据；②在电子地图上匹配固定检测器所在路段的ArcID；③处理上传数据，获得地点交通量和地点车速；④读取路段的长度；⑤用路段长度除以地点车速，得到路段的通行时间；通过处理固定检测器数据得到的地点车速和路段通行时间可用于应急车辆的道路权重实时34 南京航空航天大学硕士学位论文更新。（2）探测车系统探测车（也称浮动车）交通信息采集是伴随着车辆定位、导航以及车辆调度等智能交通系统技术而发展起来的，现在逐渐成为一种独具特色，能够对传统交通信息采集方法进行有益补充的新型信息采集技术。探测车就是指安装有定位和无线通信装置的普通车辆（如出租车、公交车、警车等），这种车辆能够与交通信息中心进行信息交换。而探测车系统是指通过交通流中一定比例的探测车辆与交通信息中心实时交换数据的一种新型的交通信息采集系统。目前欧洲（主要是英国、德国）、美国、日本都在积极研发和推广应用探测车系统，典型的应用系统包括英国的FVD，美国的ADVANCE，以及日本的新一代VICS试验系统等。北京交通发展研究中心承担的北京市ITS系列研究项目之一“北京市路网功能层次划分及功能整合研究”使用GPS数据记录器记录移动车辆的运行轨迹，估计路段的旅行时间、旅行速度、基于各路段的信息得到整个城市交通网络的现状评价。利用探测车进行交通信息采集，处理和分析，获取实时路网交通流数据，并将其应用到应急车辆是未来发展的重要趋势之一。当探测车在道路上行驶时，可以采集路网纵剖面的交通流数据，直接和方便地采集到车辆行驶速度、通行时间等参数。探测车系统采集的路段平均车速、通行时间对于了解道路运行状况、分析拥堵原因、提供交通诱导服务都是非常关键的参数，这些参数不但能很好地满足应急车辆以行程时间为道路权重的需求，而且计算涉及的算法相对于传统检测方法要简单，结果更精确、可靠。对探测车上传数据的处理步骤为：①剔除不合理的上传数据；②在电子地图上匹配探测车所在路段的ArcID；③计算得到路段通行时间（已包含交叉口延误）；④读取路段的长度；⑤利用路段长度和路段通行时间，得到路段的行程速度；通过处理探测车上传数据得到的道路行程速度和通行时间可用于应急车辆动态的道路权重实时更新。2．路段状态判别及时准确的根据处理过的交通信息对准确的判断出道路系统中的异常状态，估计车流波的长度及速度，利用“空间—时间映射”模型进行求解，计算出路段的实时通行时间，即能够为应急车辆提供准确的路段行驶时间信息。路段中交通波的判别对于将空间的距离映射为时间大小是关键，具体实现流程如图4.535 机场应急救援系统中资源动态调配研究实时交通数据的获得固定型交通移动性交通检测数据检测数据对数据处理路段交通状态判别否存在结束集结波是单对路段的个车流波估计路段车对上游交叉流集结波蔓延到口相连的路波上游交叉口上段进行分析波属性估计车流波估输出单个路段的车流的长度及扩计波长度及扩散速度散速度图4.5路段车流波状态判别流程图4.4“空间—时间映射”模型的验证4.4.1示例的假设假定（如图4.6）：某段道路()ab,上的车流量为720辆/h，正常车速为60km/h，长度L=5km。在时刻8：10分的时候，有一辆障碍车以30km/h的速度从左交叉口a进入交通流()ab,并行驶5km后从有交叉口b离去，且规定无法超车，因此会在该障碍车后形成一低速车队，设定密度为40辆/km，该障碍车离去后，受到拥挤低速车队以车速50km/h，密度为25辆/km的车流疏散。（注：图中红色车为障碍车，黑色车为正常车辆。）计算：（1）拥挤消散时间t；(2)拥挤持续时间t；(3)最大排队长度l；（3）求8：14，sj大8：18，8：22，8：26；8：30这5个时刻时通过路段(ab,)的时间ttttt,,,,。1234536 南京航空航天大学硕士学位论文L=5km()ab.ab图4.6路段示意图4.4.2示例的求解过程从题意中可以分析出，障碍车进入路段(ab,)后，由于障碍车的行驶速度较低，而且不能超车，所以导致了该路段比正常的时候的交通量降低，障碍车面形成了低速车队。等障碍车离开路段后，路段的交通状态逐渐回复正常。具体的求解过程如下：三种状态的Q、K、V分别如图4.7所示：5kmⅠw1Ⅱw2Ⅲq1=720q2=1200q3=1250v1=60v2=30v3=50k1=12k=40k3=252图4.7路段的初试状态图（1）基本量（拥挤消散时间t；拥挤持续时间t；最大排队长度l）的求取sj大障碍车从交叉口进入后，路段上的交通流由状态变Ⅰ为状态Ⅱ,此时将产生一个集结波，集结波的方向为车辆的行驶方向，集结波移速度可以由式（4-3）求得：qq−3040720×−21w===17.14(km/h)1kk−−40720/6021所以，障碍车插入后，由于障碍车的速度为30km/h，集结波由障碍车进入点以w=17.14km/h1的速度沿车流方向运动。如果这种状况持续1h，1h后跟在障碍车后的低速车队长度为：30-17.14=12.86km。但障碍车行驶5km后离去，故障碍车在路段(ab,)上的行驶时间t为：aL()ab,5kmtha===0.167()vk30m/h2即集结波持续时间为：t。a'时刻t时障碍车驶离从交叉口b离开，如图4.8，此时障碍车后的低速车队长度最大，为：lLw低=−=−×=()ab,1tka5m17.140.1672.14(km)37 机场应急救援系统中资源动态调配研究't为：8：205kmww2wtLab(,)-wt1a=2.14km1a图4.8障碍车离开路段时的路段低速车队图障碍车在时刻8：20：02时离去后，车流由状态Ⅱ变为状态Ⅲ，因此在障碍车驶离点b产生一个消散波，根据公式（4-3）求解如下：qq−50253040×−×32w===−3.33(km/h)2kk−−254032所以，障碍车离去后，低速车队前端以-3.33km/h的速度消散，后端还在以17.14km/h的速度集结，如图4.9所示。5kmww2Lab(,)-wt=2.14km1a图4.9障碍车离开路段后的路况波形图由此可见，在障碍车离去的时刻低速车队最长。所以：最大排队长度：l=2.14km。大障碍车离去的时刻，由于低速车队前端以-3.33km/h的速度消散，后端还在以17.14km/h的速度集结，则要消散长度为2.14km的低速车队需要的时间ts由图4.9可见，消散长度为2.14km的低速车队需要的排队消散时间t应采用下式计算：swtwt12ss+=2.14(km)2.14kmts==0.105()h()17.143.33+kmh/则车辆排队持续时间t为集结时间t与排队消散时间t之和，即如下式：jastttjas=+=0.167+0.105=0.272(h)（2）5个时刻时通过路段()ab,时间ttttt,,,,的求取12345由上面的求解中，获得了三个基本量：拥挤消散时间t=0.105h=6.3分钟；拥挤持续时间st=0.272h=16.3分钟；最大排队长度l=2.14km。由此得知：障碍车在8：20时刻离开路段，j大38 南京航空航天大学硕士学位论文在时刻8：26：32时路段交通状况恢复正常。①因此，路段在时刻8：30的时候映射的时间大小为：L()ab,5kmt5==×=60min5()minvk60m/h1即：5分钟。'②在时刻8：14时，障碍车仅仅行驶了t=4分钟，波移距离为：1'4minlw11==t117.14kmh/×=1.143()km60min障碍车行驶距离s为：1'4minsvt12==130kmh/×=2()km60min因此，路段在8：14时刻映射的时间大小为：sl11−−Ls()ab,−−()11l2km1.143km5km−−(2km1.143km)th1=+=+=0.153()vv60km/h30km/h12即：0.153×60=9.18分钟。③同理：在时刻8：18时，障碍车行驶了8分钟，还没有驶离路段，因此计算方法同上。sl11−Ls()ab,−−()11lt=+2vv128min8min8min8min30kmh/×−17.14kmh/×5km−×−×30kmh/17.14kmh/60min60min60min60min=+60kmh/30kmh/=0.138()h即t=0.138×60=8.27分钟。2④在时刻8：22时，障碍车行驶了12分钟，此刻，障碍车已经驶离路段，然而障碍车所造成的路段拥挤现象还没有消除。障碍车在8：20的时候驶离路段，因此有∆t=2分钟的拥挤消散时间，前面应急求到障碍车驶离路段是的最短排队长度l，∆t=2分钟的减小排队长度为：大lwtwt=∆+∆减122min=+()17.140.33kmh/×60min=0.582()km因此，在此刻的顺畅路段长度为：Lllk−+=−5mk2.14m+0.582km=3.446(km)()ab,大减即拥挤路段的长度为：5-3.446=1.554（km）所以，此刻路段在8：14时刻映射的时间大小为：39 机场应急救援系统中资源动态调配研究3.446km1.554kmth3=+=0.1092()60kmh/30kmh/即：6.55分钟。⑤在时刻8：26时，障碍车已经驶离路段，而且时刻8：26：32时路段交通状况恢复正常，因此只有32秒的拥挤时间。而车辆在此时通过该路段的前3km时花费的时间为：3km×=>60min3min32s60kmh/因此，次拥挤时间可以忽略不计，即路段在8：14时刻映射的时间大小为：t=5分钟。4综上：（1）拥挤消散时间t=0.105h=6.3分钟；s（2）拥挤持续时间t=0.272h=16.3分钟；j（3）最大排队长度l=2.14km；大（4）求8：14，8：18，8：22，8：26；8：30这5个时刻时通过路段()ab,的时间：t=9.18分钟；t=8.27分钟；t=6.55分钟；t=5分钟；t=5分钟。12345其中（1）（2）（3）的求解是为（4）的求解做准备，该案例的求解充分体现出路段随时间的推进，其“空间—时间映射”的时间大小也在发生变化。充分体现出路段通行时间的实时变化特性。4.5本章小结本章主要对现实的交通拥挤状况进行分析，运用交通工程学上的交通波理论对路段的各种情况进行分析并建立路段的“空间—时间映射”模型，实现空间的距离大小转化为时间大小；介绍了模型的求解方法及交通状态的判断流程；最后运用一个假定示例来验证模型的可行性、正确性，体现了路段通行时间的实时动态变化特性。40 南京航空航天大学硕士学位论文第五章应急车辆动态路径的实时显示实现5.1引言应急车辆需要在尽快到达事故地点，所以应急车辆必须实时地选择合适的行驶路径以便快速到达救援现场。应急车辆的时间最短路径动态规划思想可以这样理解：如果应急车辆按照一条预先规划好并且这条路径固定不变不被重新优化的路线行驶，那么这个路径是静态的。反之，如果一个应急车辆不是按照一条预先规划好的路线行驶，而是在应急车辆行驶过程中根据交通状况实时调整路线，这个路径就是动态的。应急车辆行驶过程中，路段通行时间是随时间变化的，但是受交通参数检测技术和预测分析技术的限制，难以找出准确、可用的路段通行时间随时间连续变化的关系式。为此，将系统工作时间划分为若干时间段，把单个时段内交通状态稳定、通行时间看做是固定，但不同时段的通行时间可能不相等。然而，当时段划分得很长时，应急车辆可能在一个时段内就能完成任务，这实际上未考虑路径行程时间的变化，行驶过程中路径没有发生变化，这种路径实际为静态路径。将时段划分适当时，应急车辆一次出行会跨越若干时段，实际交通状态与行程时间都是变化的，以应急车辆通过各路段所需的实际时间为依据计算所需最短路，这种最短路径为动态最短路。在应急救援资源车辆行走路线选择这个问题上，本章构造出网络图GVAH=(,,)，其中Vk={1,2,3,L,}为节点集，表示应急救援车辆所要经过的节点集合；Aa==≠{(,)|,bab0,1,2,,,Lkab}为弧集，表示车辆所有可能走过的路段集合，其中a和b为道路网络中节点的标号；Ha==≠{λ(,)|,bab0,1,2,,;Lkab}为权集，表示路段(,)ab的ab路权集合，并定义λab()ab,,=ft()()()ab,,Xab(ab,0=,1,2,,;Lkab≠)，t()ab,表示路段(,)ab的通行时间，X表示其它不确定因素（如交通堵塞、障碍物、交通意外等）。其决策属性分()ab,量可以按照线性分配法的求解步骤来求解。kk目标函数：min∑∑xabλab(5-1)ab==11Na=0,1,2,L,,kN为足够大整数λ==0ab(5-2)ab∞ab与不相邻，或者、之间路段阻塞ab1车辆通过路段(a,b)时x=(5-3)ab0车辆不通过路段(a,b)时k约束条件：∑xab==11bk,2,L,（5-4)a=041 机场应急救援系统中资源动态调配研究k∑xab==11ak,2,L,(5-5)b=0X=∈()xS（5-6)ab其中，S表示消去支路约束的集合，以保证解的连通性。5.2时间最短路径的算法改进传统Dijkstra算法是求解最短路径问题的经典算法，Dijkstra算法是建立在抽象网络模型上，把路线抽象为网络中的边，以边的权值来表示道路的相关的参数，算法确定了赋权网络中从某点到所有其它节点的具有最小权值的路，Dijkstra算法是求解最小权值问题的通用算法[48]，当前的许多流行的最短路径算法中用很多还是基于Dijkstra算法的，不同的是都是根据实际的网络拓扑环境的限制条件、自身特征的因素等进行修改。最短路径算法按照不同的分类原则可以分成许多种不同的类型，将最短路径算法应用到实际中的时候，所求解的最短路径往往不是单一约束下的最短路径而是几种不同约束的优化组合。这样传统的用于求解单一约束的最短路径算法就很难满足要求。对于城市道路网的最短路径算法也是一个最短路径算法的组合优化问题，所以不能直接应用经典的最短路径算法来求解。以下是针对Dijkstra算法对数据结构进行改进。原始的Dijkstra算法将网络节点分为3部分：未标记节点、临时标记节点和永久标记节点。网络中所有节点初始化为未标记节点，在搜索过程中和最短路径相连通的节点为临时节点，每次循环都是从临时节点中搜索距源点路径长度最短的节点作为永久标记节点，直到找到目标节[49]点或者所有的节点都成为永久标记节点来结束算法。在原始的Dijkstra算法中，临时标记节点无序的存储在无序表中，这无疑成为Dijkstra算法的瓶颈。因此每次从临时标记点中搜索路径最短的节点时都要遍历所有的临时标记节点。解决这个问题的办法就是：按照起点和终点将所有路段的权值分别排序，每个搜索过程只需较少地遍历临时标记节点。这也是目前各种基于Dijkstra算法的优化算法的重要出发点之一。另外一个优化途径是尽量减少最短路径分析过程中搜索的临时节点数量，从而尽快到达目标节点。目前，对于算法中快速搜索技术的实现，主要有桶结构法、队列法以及堆栈实现法。TQQ、[50]DKA以及DKD在这方面是比较典型的代表。TQQ虽然是基于图增长理论的，但是快速搜索技术同样是其算法实现的关键，它用两个FIFO的队列实现了一个双端队列结构来支持搜索过程。DKA和DKD是采用如图5.1所示的桶状结构来支持这个运算的，其算法的命名也是源于此。**在DKA算法中，第i个桶装有权值落在[,()]bii+b范围内的可供扫描的点，其中b是根据网络*^中权值分布情况而定的一个常数。最坏情况下，DKA的时间复杂度将会是ombnbCb(()++)，其中，C为图中边的最大权值。DKD将点按权值的范围大小分别装在两个级别的桶内，高级别的桶保存权值较大的点，相应的权值较小的点都放在低级别的桶内，每次扫描都只针对低级别42 南京航空航天大学硕士学位论文桶内的点，当然随着点的插入和删除。两个桶内的点是需要动态的调整的。在DKA算法中，给以每个桶一定的范围以及DKD中使用双桶在一定程度上都是空间换时间的做法需要改进。01C2C-1⋯⋯⋯⋯⋯⋯⋯⋯K+1K-1K图5.1桶状存储图文中提出的Dijkstra算法的高效实现的流程基本符合前面介绍的算法思想，网络在数学和计算机领域中被抽象为图，所以其基础是图的存储结构。一般而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图可以用邻接表和十字链表表示，如表5.1所示。表5.1几种图的存储结构比较实现名称优点缺点时间复杂度方法二维易判断两点间的关系，2邻接矩阵占用空间大Onmn()+g数组容易求得顶点的度节省空间，不易判断两点间的关系，Omn()+或邻接表链表易得到顶点的出度不易得到顶点的入度On()m空间要求较小，易求得十字链表链表结构较复杂同邻接表顶点的出度和入度节省空间，邻接多重表链表结构较复杂同邻接表易判断两点间的关系根据最短路径算法的特性可以知道，顶点的出度是个重要指标，其入度在算法里则一般不予考虑。但是城市道路网有很多的路段是单向行驶的也就是说由城市道路网抽象出来的网络图一般都是有向图。从A点到B点的最短路径往往不是从B点到A点的最短路径。所以，仅仅考虑节点的入度会大大增加算法的时间复杂度。在本章的算法里，对每一个节点既考虑入度，也要考虑出度。综合以上4种存储结构的优缺点，文中采用了四个数组来存储网络图的按出度和入度分别排序的节点。无论何种算法，基本思想都是将点按权值的大小顺序排列，以节省操作时间。前面提到现在的一些优化算法都是以空间换时间的算法，所以在这里有必要讨论存储空间问题（这部分空间的大小依赖于点的个数及其出度）。根据图中顶点和边的个数可以求出顶点的平均出度emn=/（m为边数，n为顶点数），这个数值代表了图的连通程度，一般在GIS的网络图中e∈[2,5]，这样，如果当前永久标记的点为t个，那么下一步需要扫描的点的个数约为t−4个。如果采用数组结构，上万个节点规模的网络，所需的存储空间一般不会超过100K。43 机场应急救援系统中资源动态调配研究以现在计算机的存储量来说，完全没有必要采用以时间换空间的做法，相反以空间换时间的做法就变成完全可行的了。实现这部分，文中采用了一个FIFO对列，相应的操作主要是插入、排序、删除，插入和删除的时间复杂度都是o(1)，所以关键问题在于选择一个合适的排序算法。一般可供选择的排序有快速排序、堆排序以及归并排序，其实现的平均时间都为onn(lg)。经过反复比较，文章选择了快速排序法。5.3路段权值的确定方法在应急车辆出动的时刻为t，将车辆到达救援现场所用工作时间划分为若干时段，以∆t表0[50]示一个时段的长度。系统开始工作时刻属于第一个时段，对各时段进行编号（i、ii、iii、iv、v、vi、vii、viii、⋯⋯），称此编号序列为系统工作时段序列；对涉及的路段进行编号。以T表示路段i第j个时段的通行时间，将各路段各时段的通行时间表示为表5.2。ij应急车辆可能在某时刻呼叫服务，某车辆从起点到目的地可能需经过若干条路段，对其所'经过的路段按序编号(1,2,3,⋯k−1,k,k+1,⋯)，以[,]tt表示车辆经过第k路段的时kk'间范围，车辆通过路段k的通行时间记为T，则ttT=+。路段k为路段k−1的后续路段，kkkk'可知tt=。kk−1表5.2路段的时刻通行时间表时路段1234⋯⋯j⋯⋯段1T11T12T13T14⋯⋯T1j⋯⋯2T21T12T13T24⋯⋯T2j⋯⋯3T31T32T33T34⋯⋯T3j⋯⋯4T41T42T43T44⋯⋯T4j⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯iTi1Ti2Ti3Ti4⋯⋯Tij⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯''''车辆通过路段k可能跨越若干时段，各时段对应的通行时间表示为T、T、T、T⋯，k1k2k3k4以x表示车辆通过路段k起点时刻所属时段在系统工作时段序列中的次序，则：k()tt−k0x=+int1（5-7）k∆t'int：取整函数。且TT=。K1(1kxik++)'当时间段∆T、路段长度(L)与行驶速度有不同取值或不同组合时，可能出现T比∆Tk1''大、T比∆T小、T与∆T相等三种情况。k1K1''当TT≤∆时，表示车辆在一个时段内就能通过路段k，则TT=。K1kk1'当TT≥∆时，表示车辆需要一个以上时段(设为f)才能通过该路段，则根据运动学原K1理，下式成立：44 南京航空航天大学硕士学位论文ff+1LL∑∑()(''gg∆TL≤<∆T)（5-8）ii==11TTkiki化简为：ff+111∑∑''≤≤L（5-9）ii==11TTkiki可采用试算法确定f值。由f值，根据运动学原理可计算应急车辆通过路段k的通行时间（T）：kff−−11LL''∆TTfTLkk=−∆+−(1)[∑∑()'']/()(1ggTfTf=−∆+−)(1')Tkf（5-10）ii==11TTKikfTKi由此，得到路段k通行时间计算公式为：'TT()≤∆Tkk11T=f−1∆T(5-11)k'(1f−∆+−)(TT1∑')(gkfTk1>∆T)i=1TK2式中：ff+111∆T'f∑∑''≤<的TTki=kx(1k+i−)(5-12)ii==11TTTki∆ki5.4时间最短路径的动态规划实现根据路段长短、道路状况这些静态的参数选择最优的路径。最终路径规划的结果不能反映实际的交通状况，很难作为应急车辆行驶线路的参考。实际的情况下交通状况随时间不断的改变，动态的路径规划是在静态的路径规划中，在短时交通流等数据采集的基础上，考虑时间的因素，在原先的二维平面的路径规划上添加一个时间维，形成动态路径规划(Dynamicvehiclerouting，DVR)。简单的来说，DVR就是综合考虑时间和道路状况，包括交通拥挤和交通流量等一些变化的最优路径的查找问题。文中的DVR系统从应急资源动态筹集上考虑车辆运行的时间最短，并以此为目标选择最优的行车路径。5.4.1搜索过程的实现过程由于应急车辆路径动态规划过程中的路网拓扑环境复杂多变，所以基于改进的Dijkstra算法的动态路径算法完成最后的搜索工作，要比经典的Dijkstra算法的过程还要复杂。首先，经典Dijkstra算法的权值都是预先设定的固定不变的，也无需确定搜索范围，而动态实时最短路径算法，既要经过计算步骤比较复杂的权值确定过程，还要为搜索过程确定一个范围。最后才采用Dijkstra算法原理来完成搜索。另外，在动态路径诱导系统中还有一些实时交通信息的影响，很有可能搜索到的最短路径在某一时刻是最短的，但是，当发生一些实时交通状况以后，就不再是最短路径，需要根据实际情况重新计算。整个动态实时最短路径算法各个模块大致可45 机场应急救援系统中资源动态调配研究如图5.2所示。输入起点和根据Dijkstra算计算动态权值终点信息法完成搜索实时交通信息图5.2动态最优路径算法流程图很明显，整个计算的实际过程要比上图显示的信息复杂的多，不过基本步骤还是按照上图执行的。基本步骤如下：（1）输入起点FNode和终点TNode的信息；（2）计算动态权值，V集合初始化，保存在限定区域内的所有点；集合完成初始化，并把起点FNode加入该集合，result集合是来保存每次搜索得到的最短路径定点vV∈，把起k点加入该集合；S1集合(保存动态时间权值)初始化为空集。另外需要说明的是S1集合采用数组的方式保存数据，如Sk1[]表示定点v到起点的最短距离。所以开始的时候所有的定点的值k初始化为∞；（3）选择顶点v，使得dFNodev[,]{=Minduv[,]|v∈−Vresult}，并且将v加入jjjijresult集合；（4）然后根据动态权值确定方法修改从顶点vr∈esult出发到集合Vr−esult上任一点jv可达的最短时间权值。如果dFNodev[,]+fjk[,]20->19->45->430->44->43->42->41->40->153->154，时间最短路径：10->18->21->24->25->26->43->42->41->40->153->154。由初始状态的两种情况，可以看出，距离最短并不一定是时间最短路，从该意义上讲，以时间最短来研究是非常有必要的。实时最短路径模拟应急车辆从节点10出发，沿着时间最短路径行驶，系统每隔∆t对路网的交通信息有一个统计，将路网的实时信息反映到数据库表中，当应急车辆即将到达节点18，在过去几个时刻的基础上对时间最短路径实现一次求解，发现节点18至24之间的交通比较拥挤，耗时突然增大，也就是说明该路段不能再作为应急车辆的选择路径（系统设计中求解时，通过调用不同的数据表来体现这种变化），此时所求得的时间路径如图5.6，车辆从节点18转向19节点，选择了另外一条路径，变为：时间最短路径：10->18->19->45->430->44->43->42->41->40->153->154。48 南京航空航天大学硕士学位论文图5.4距离最短路径显示图图5.5初始时间最短路径显示图49 机场应急救援系统中资源动态调配研究图5.6实时时间最短路径显示图图5.7实时时间最短路径显示图50 南京航空航天大学硕士学位论文应急车辆在节点18和19之间，通过数据检测，所求得的路径与前一时刻所求相同，此处没有再例图。同样，应急车辆继续行驶，当车辆在节点19和45之间的路段上行驶的过程中，通过上述相同的计算方式获得节点44处，有大量车辆排队，造成在该路口的延误比较的大，即耗费时间增大。因此车辆在45节点的时候改变原来的方向，向26节点方向行驶。如图5.7，可以很直观的看到路径的改变图示。在以后的各个时刻，根据实时的交通信息所获得的时间路径，没有再发生变化，此处不再继续叙述。5.6本章小结本章主要介绍了应急车辆的动态路径的实时显示。文中先是对最短路径的算法进行改性，并论述了时间最短路径的动态规划实现过程及路段权值的确定方法，在时间最短路径的动态显示上采用了将工作时间划分为成若干时间段的方法，并且在应急车辆行驶过程中运用动态规划的思想进行分析研究。最后运用GIS技术，VB开发工具实现应急车辆的时间最短路径的模拟显示，体现出应急车辆的时间最短路径是动态规划实现的。51 机场应急救援系统中资源动态调配研究第六章总结与展望6.1本文总结机场应急救援系统中资源动态调配是应急救援系统研究的关键技术之一，本文在此问题上所做的主要工作是：对资源动态调配的整体组织结构分析、应急救援资源的动态筹集研究、路段的“空间—时间映射”模型研究建立、应急车辆的时间最短路径模拟显示研究。（1）在分析资源动态调配的整体组织结构时，依据机场应急资源动态调配的特点，基于多Agent理论在协同决策中的优势，从全局观出发，对资源动态调配涉及的主要问题进行整体上分析；建立了基于Agent的应急资源动态调配的组织结构模型，并分析了指挥中心Agent、资源Agent、交通路网Agent、救援现场Agent等主要单元的功能及结构；在分析资源调配过程的基础上研究了协同推理机制模型及过程。（2）在应急救援资源的动态筹集研究中，考虑到救援过程中会出现再筹集现象，分析了资源筹集的流程组织，提出了离散化资源消耗多资源多目标资源筹集形式，确立了应急时间最早和资源出动费用最低两个目标；通过建立数学模型来分析“多资源、多目标、离散化”等要素；最后通过假定一个医疗救援组的资源需求量，运用蚁群算法给以求解。（3）在路段的“空间—时间映射”模型研究中，文中采用了交通工程学中的交通波理论进行建模研究。文中先是对交通流中流量、速度、密度的关系及交通波理论进行分析；然后利用交通波理论对路段分四种状态进行研究，构造出相应的“空间—时间映射”模型；最后通过假定示例，运用所建立的模型求解，从而得出路段的通行时间是实时动态变化的结论。（4）在应急车辆的时间最短路径动态显示研究中，将车辆到达救援现场所用工作时间划分为若干时间段，并且将时间段内的交通状态看作是静态不变的，故采用优化的Dijkstra算法进行时间最短路径求取；车辆在行驶过程中动态规划时间最短路径；最后运用GIS技术，结合VB语言实现应急车辆在地图上的实时动态显示。本文的内容包括了机场应急救援系统中资源动态调配的各个方面，其中的原理和方法也可以运用到其它方面的救援系统中。6.2工作展望以上这些工作的完成，为机场应急救援系统中资源动态筹集研究提供了新的分析方法和思路，由于研究条件和时间的限制，实现的功能还需要进一步完善，例如：（1）资源动态筹集的高效性。引入决策优化算法、采用智能化自动筹集，建立一个自动化的智能型决策优化系统，能够提高资源筹集的合理性、正确性、快速性，并且能够节省大量的人力、物力。52 南京航空航天大学硕士学位论文（2）“空间—时间映射”模型的更加深入研究，从应急车辆的特殊特点及路段的更多实时变化的影响因素上进行考虑，建立更加完善的映射模型，进一步提高映射模型的高效性，这能够使得资源动态调配的依据更加准确。（3）实时最短路径的算法优化。路网实时数据庞大，而且路网动态信息不停的存入数据库，动态数据库的不停调用耗费大量时间，因此，采用优化的数据库技术提高数据库的搜索效率，以及构建高效的算法缩短最短路径求取时间，这对应急车辆来说显得尤为重要。以上这些方面的进一步实现可以提高机场应急救援资源动态调配效率，同时也为其它类型的突发事件的救援提供了非常高效的工具，这将给社会带来的效益和价值将是不可估量的。53 机场应急救援系统中资源动态调配研究参考文献[1]薛澜.危机管理—转型期中国面临的挑战[M].北京：清华大学出版社,2003：55-13.[2]国际民航组织.ICAO第2版,1991.[3]GeorgeF.List.RoutingandEmergency-Response-TeamSitingforhigh-levelreadioactivewasteshipments[J].IEEETRANSACTIONSONENGINEERINGMANAGEMENT,1998,45(2):141-152.[4]ALIHSEFCHANGO.Formulationandsolutionofamulti-commoditymulti-modalnetworkflowmodelfordisasterreliefoperation[J].RansportationResearch,PartA,1996,30(2):231-250.[5]AllenRobert,C.Wen.ObservationsandRecommendationsofasimulatedairportemergencyresponsemanagementexercise.In:Proceedingsofthe199842ndAnnualMeetingHumanFactorsandErgonomicsSociety,Chicago,IL,1998,2.[6]Tsai-Yun,LiaoTa-YinHu.ACORBA-BasedGIS-TforAmbulanceAssignmentDeptofInformationManagementChaoyangUniversityofTechnology,Taichung,Taiwan,R.O.C.[7]FIEDRICHF,GEHBAUERF,RICKERSU.Optimizedresourceallocationforemergencyresponseafterearthquakedisasters[J].SafetyScience，2000.35(1):41-57.[8]ALIH,SEFCHANGO.Formulationandsolutionofamulti-commoditymulti-modalnetworkflowmodelfordisasterreliefoperation[J].TransportationResearch,PartA,1996,30(2):231-250.[9]HaghaniAli,TianQiang,HuHuijun.Asimulationmodelforrealtimeemergencyvehicledispatchingandrouting[C].82stAnnualMeetingoftheTransportationResearchBoard,2003.[10]G.DerekenarisJ,Garofalakis,C.Makrisetc.IntegratingGIS、GPSandGSMtechnologiesfortheeffectivemanagementofambulances,Computers.EnviromentandUrbanSystems，2001，25:267-278.[11]GeorgeF．Routingandemergencyresponseteamsittingforhighlevelradioactivewasteshipments[J].IEEETransactionsonEngineeringManagement,1998,45(2):141-152．[12]Cohn,Campbell.MinimumNeedsforAirportFireFightingandRescueServices.54 南京航空航天大学硕士学位论文Report:7113,FAAAS-71-1,1971.97.[13]QUENTINK,WANHONGK.LOAMixedIntegerFormulationforMultiple-RouteTransitNetworkDesign.JournalofMathematicalModellingandAlgorithms,pp.299-308,2003.[14]HaiboHu,DikLunLee,JianliangXu.FastNearestNeighborSearchonRoadNetworks.Vo1.4,No.1,pp.163-169,2005.[15]HESheng-xue,FANBing-quan.SearchingtheEffectivePathsinDynamicTransportationNetwork.JournalofTransportationEngineeringandInformation,No.1,Vo1.4,Mar,2006.[16]何建敏,刘春林等编著.应急管理与应急系统——选址、调度与算法[M].北京:科学出版社,2005.7.[17]刘春林，何建敏．一类应急资源调度的优化模型研究[J]．中国管理科学，2001,3(9)：29-36．[18]刘春林，施建军，李春雨．模糊应急系统组合优化方案选择问题的研究[J]．管理工程学报,2002,2(16):25-28．[19]高淑萍，刘三阳．应急系统调度问题的最优决策[J]．系统工程与电子技术，2003，10(25)：1222-1224．[20]迟文学,孙刚,武峥.基于GIS民航应急救援与辅助决策支持系统研究[J].交通与计算机工程,2005,23(6):46-48.[21]魏新宇.消防灭火救援最优路径研究.硕士学位论文,西安科技大学,2005.[22]苏永云,晏克非.车辆导航系统的动态最优路径搜索方法研究.系统工程,2004.8,18(4)[23]李元臣,刘维群.基于Dijkstra算法的网络最短路径分析.微计算机应用，No.3.[24]李德龙,张冰.智能车辆最短路径算法的研究与实现.现代电子技术,2006,NO.19.[25]刘海燕.智能交通系统的车辆行驶最佳路径算法.北京工商大学学报(自然科学版),24(1).[26]唐铁桥,熊雄.对交通流动力学理论的认识.山东理工大学学报,2005.1,19(1).[27]顾国民,王卫红,李琰琰.基于微观交通模型的动态路径规划,系统工程,2003.[28]孙海鹏,翟传润,战兴群,张炎华.基于实时交通信息的动态路径规划技术,微计算机信息,2007.23(8),177-178.[29]李志鹏.交通流建模及城市路网交通状态分析.上海交通大学博士学位论文,2007.3.[30]何炎祥,陈莘萌.Agent和多Agent系统的设计和应用[M].武汉:武汉大学出版社,2001.[31]Ashri,Ronald,Luck.FromSMARTtoAgentSystemsDevelopment[J].EngineeringApplocationsofArtificialIntelligence,18(2),2005.[32]董红斌.多Agent系统的现状与进展[J].计算机应用研究,2001,1:54-56.[33]V.R.Lesser,Reflectionsonthenatureofmulti-agentcoordinationandits55 机场应急救援系统中资源动态调配研究implicationsforanagentarchitecture,AutonomousAgentsandMulti-AgentSystems,1998,Vol.1(1),pp:89-111.[34]M.E.Bratman,Intension、PlansandPracticalReason.1sted,Cambridge.MA：HarvardUniv.Press,1987.[35]胡山立,石纯一.Agent的意图模型.软件学报,2000,Vol.7:965-970.[36]P.Cohen、H.Levesque,IntentionisChoicewithCommitmentArtificialIntelligence,1990,Vol.42:213-261.[37]A.Rao,M.Georgeff.BDIAgentsfromTheorytoPractice.TechnicalNote56,AAII,1995.[38]A.S.Rao,M.Georgeff.ModelingrationalagentswithinaBDI-architecture.ProceedingsoftheSecondInternationalConferenceonPrinciplesofKnowledge，RepresentationandReasoning,1992:473-484.[39]WyboJL.FIMS:adecisionsupportsystemforforestfirepreventionandfighting[A].IEEETransactionsonEngineeringManagement[C].1998.127-131.[40]计雷,池宏,陈安等.突发事件应急管理[M].北京:高等教育出版社,2006.3.[41]BalM0LFL.Areliabilitymodelappliedtoemergencyservicevehiclelocation[J].OperationResearch,1993,4:18-23.[42]戴更新、达庆利.多资源组合应急调度问题的研究[J].系统工程理论与实践,2000,(9)[43]李连宏，王永军，李俊峰，陈靖.多资源非恒定消耗应急调度优化模型研究[J].北京理工大学学报,2006,26:157-160.[44]黄金虎.应急物流系统若干关键技术的研究与实现.上海交通大学.2007.1[45]王炜,过秀成.交通工程学.东南大学出版社.2004.10.81,118.[46]陈智宏.基于动态车辆导航系统的道路权重赋值方法研究.北京工业大学硕士学位论文.2006.4.[47]王培宏.城市交通事件应急管理系统及其理论问题的研究[D].2005.1.[48]朱文兴,贾磊,丁绪东,胡咏梅.城市交通网络中的路径优化研究.山东大学学报，2005,35(l):74-77.[49]王凌,段江涛,王保保.GIS中最短路径的算法研究与仿真.计算机仿真,2005,Vol.22,No.1:117-118.[50]晏克非,覃煜,朱培康.车辆导航系统基于GIS的动态K最短路递推解法.西安公路交通大学学报,2001.1,21(2):64-67.56 南京航空航天大学硕士学位论文致谢本论文是在我的导师韩松臣教授的精心指导下完成的。在我的研究生学业期间，韩老师在学习和生活方面给予了我全力的支持和帮助。进入课题研究阶段后，他独到的见解常常让我豁然开朗。他渊博的学识、严谨的治学态度和诲人不倦的作风，使我不仅顺利的完成了课题、增长了知识，也懂得了许多做人的道理，这些都将使我终身受益。在此谨向韩老师致以最衷心的感谢。同时感谢在论文准备和撰写过程中给予我帮助的汤新民老师等，他们在专业知识方面也给我提出了许多宝贵、中肯的意见和建议。实验室的朱新平、丁毅萍、尤杰、梁世华等同学也给予我很大的帮助，在此一并致以诚挚的谢意。最后，我要感谢我的家人在我漫长的求学生涯中对我的长期的支持和帮助。57 机场应急救援系统中资源动态调配研究在学期间的研究成果及发表的学术论文攻读硕士学位期间发表(录用)论文情况1、崔国山.基于Agent的机场应急救援资源动态调配研究.2008年全国工业控制计算机年会.2008.11,p:53-57.攻读硕士学位期间参加科研项目情况1、参与研发“南京禄口国际机场应急救援辅助决策系统”。2、参与研究“机场应急救援关键技术研究”。58
