基于多智能体系统的应急车辆路径诱导策略研究

赵 欣，陈珊珊

（武汉理工大学 交通学院，湖北 武汉 430063）

基于多智能体系统的应急车辆路径诱导策略研究

赵 欣，陈珊珊

（武汉理工大学 交通学院，湖北 武汉 430063）

以协助应急车辆通行为目的，从交叉口信号优先控制与路径诱导两方面进行统一考虑，建立了基于多智能体系统（Multi-Agent System，MAS）的应急车辆路径诱导策略。应用相位智能体和管理智能体实现应急车辆在交叉口的信号优先权，在路段上提出了车载智能体和路段智能体，与交叉口两智能体相协同，并以改进的Dijkstra算法为决策算法，共同完成应急车辆路径诱导过程。最后通过Starlogo软件并借助Matlab完成了对应急车辆诱导过程的验证。仿真结果证明了该方法的有效性。

应急车辆；信号优先；路径诱导；多智能体系统

1 引言

近些年来由于自然灾害和人为因素而导致的突发事件频繁发生，为尽可能降低这些突发事件带来的人身财产损失，应急车辆如何更安全、高效地到达灾难现场是各国应急部门共同关注的问题。目前国内外学者就应急车辆在交叉口的信号优先权设置及路径诱导两方面都取得了一定的成果。Kwon等[1]先运用Dijkstra算法优化了应急车辆的出行路线，再对已选路线上所经过的交叉口信号进行优化设置；Yang等[2]针对某一区域发生的突发事件提出了应急车辆调度的建议，并建立了路线优化的模型；Yuan[3]针对应急物流建立了一个以时间最短为目标的路径优化模型，该模型考虑了应急车辆通行时间与灾害扩散程度之间的关系；Wang等[4]提出了在车

路协同的环境下应急车辆信号优先系统的设计和实现；钟源[5]在假设路径最短的前提条件下,结合多智能体协调技术，应用多级模糊决策算法，对应急车辆的信号优先控制问题进行了研究；刘帆[6]通过对应急物流车辆在路径优化中所需考虑的主要因素进行归纳分析后，以行驶成本和安全违背成本最小为目标，建立了路径优化模型，并运用遗传算法对该模型进行求解。从国内外的研究现状来看，应急车辆的相关研究一般都是侧重于某一方面，如应急车辆检测手段、应急车辆信号优先控制策略、路径优化等，并未在寻求合理的信号优先控制前提下对应急车辆出行路线建立完善的诱导体系。本文试图通过对解决交通问题有一定优越性的多智能体技术来对基于交叉口信号优先控制的应急车辆路径诱导策略进行研究。

2 问题描述

本文问题可描述为：假设一个有向路网N=(V，A)，其中V={1,2,…,i,i+1,…,n-1,n}是节点集合，1代表救援中心的所在地；2,…,n-1表示路网的中间节点，即交叉口；n代表灾难现场。A为弧集合，表示应急车辆可能走的路段集合。如其中(i,i+1)∈A(i=1,…,n-1)表示路网中相邻交叉口中间的路段。

此外，在计算应急车辆的路段行程时间时，由于本文考虑的是动态路径诱导，故车辆在路段的行驶速度数据将结合历史数据和实时路段信息获得，并采取时段分析法得到速度离散曲线，具体如下：将一天分成若干个相同长度的时间段在时段Tj内车辆在路段(i,i+1)的行驶速度相同，记为而在交叉口的行程时间记为假设应急车辆在时刻离开第i个交叉口，则在路段(i,i+1)的应急车辆行驶时间计算公式为[7]：

则：

本文主要考虑应急车辆行驶的时间效应，故以时效性为决策属性，目标函数式可表示为：

其中li,i+1表示相邻交叉口之间的路段长度，ti,i+1表示应急车辆通过路段(i,i+1)的时间，ti表示应急车辆通过交叉口的时间表示车辆在第j个时段内通过路段(i,i+1)的平均速度

应急车辆通过交叉口i的时间ti由于本文信号优先控制方法未投入使用，故无历史数据，可根据不同时段的交通信息仿真模拟得到。

3 基于交叉口信号优先控制的应急车辆路径诱导系统

本文结合了文献[8]对应急车辆在交叉口信号优先进行控制的研究，其以MAS为基础，建立了相位智能体（Phase Agent，PA）和管理智能体(Management Agent，MA)两种模型，依托MAS的灵活性、强适应性特征及内部可协调性的原理，并运用模糊推理完成了系统的决策过程，实现了相序可变的交叉口信号优先控制策略，在有效保证了应急车辆优先权和安全性的前提下减小了对常规车辆的影响。下面重点介绍与交叉口信号优先控制相结合的应急车辆路径诱导系统。

路径诱导的处理方法可分为集中式和分布式，本文希望借助智能体和改进的Dijstra算法来实现信息收集

分布式和计算集中式共同处理应急车辆动态路径诱导问题。

3.1 多智能体系统（MAS）

MAS是由多个单一的智能体组合而成，该系统内的智能体之间能够通过信息共享实现相互学习，并协调统一，对实现复杂系统的控制优化尤为有效。近些年来，MAS大量应用在智能交通、交通控制及电子商务等领域中，而本文中研究的应急车辆在交叉口的信号优先控制及路径诱导也尤为适合MAS的应用。因为交通网络中具有明显较强的物理关联性，而这种关系能够为多智能体间进行选择性地相互交流和协商带来便利，故而可以大大简化各智能体间的信息传递问题。因此本文将采用MAS技术解决应急车辆的信号优先控制及路径诱导问题。

3.2 应急车辆路径诱导的多智能体模型

根据需要，建立两种智能体模型，即车载智能体模型（Vehicle Agent，VA）和路段智能体模型（Road Agent，RA），VA按经过计算得到的最短路径方案运行并严格按照信号灯的指示进行停驶，RA为车辆运行智能体提供各路段实时的交通信息以供VA进行实时行驶路径决策。

VA的运作流程为：首先，结合车辆属性，VA按照其内部存储获得的最短路线方案开始运行。运行过程中，VA通过通讯器接收RA发送的路段交通信息，本文中指车辆运行平均速度信息，通过在控制器中计算来进行路线选择决策。此外，VA还可以实时地向PA发送车辆的行驶状态。一旦从通讯器获得信号指令，车辆将严格依照信号指令行驶。VA的建立很好地将应急车辆路径诱导系统与信号优先控制系统结合在一起。

RA的工作流程为：控制器通过感应器获得路段实时交通信息，并根据知识库中存有的道路基本信息计算得到车辆的平均速度信息，再运用通讯器实现各相邻RA之间以及RA与VA的信息交互，每隔5min该路段智能体将各路段反馈的信息发送给应急车辆VA，VA即可通过新的交通数据进行路线决策。

各智能体之间的关系如图1所示。

3.3 改进Dijkstra算法

为实现车辆运行智能体的动态路线生成功能及根据救援系统的短距离特征，本文引入改进Dijkstra算法，该路径诱导只针对应急车辆，故不会产生潜在的“交通聚集”和“拥挤漂移”等问题，加大了该算法的准确有效性。

（1）改进的Dijkstra算法流程图如图2所示。其中权值包括应急车辆路段行程时间和通过后续交叉口时间。

图1 多智能体关系

图2 改进的Dijkstra算法流程

（2）应急车辆动态路径行驶方案。指挥中心确定救援车辆行驶时段及灾害地点后，根据相关历史数据，按照上述方法确定出以救援中心和灾害地点为起终点的应急救援车辆路径的初始方案。但由于在实际交通路网中会有各种不确定因素存在，如交通事故或临时道路维修等，故应急车辆行驶车速不可能完全符合历史规律，因此需要根据实时交通信息即路段车速变化情况对车辆在行驶途中的路径进行调整。而交通数据的采集

及平均速度的计算可借助路段智能体来完成。如果由获得的实时数据计算得到的车辆最优路径与初始方案不同，并且新路线比原路线的节省时间达到可接受的范围，那么就接受新的路径行驶方案；否则，维持原路线方案不变。

4 仿真实验

本文将借用宋辉华[8]仿真得到的应急车辆在交叉口定时信号控制和信号优先控制下通过时间的数据，运用仿真软件Starlogo并借助Matlab对基于交叉口信号优先控制的应急车辆路径诱导过程进行仿真，目的是为了说明本文给出方法的可行性与有效性。

4.1 路径诱导仿真实验条件说明

为使实验简化，且方便编程实现，对仿真环境作如下标定：

（1）仿真道路为双向2车道。

（2）由于本实验采用人工数据，在不影响实验目的的前提下，本实验中各路段不同时段内应急车辆速度由random形式随机产生，并在30-45km/h之间产生，时段间隔设置为5min。

（3）社会车辆对应急车辆在路段上的影响已由应急车辆平均速度反映，故本实验在路段上将不产生社会车辆。

（4）本实验假设各个交叉口的应急车辆通过时间不变且相同，在定时控制和信号优先控制下分别为宋辉华[8]仿真实验得到的平均通过时间43s和36s。

Starlogo有良好的可视化仿真及编程界面，通过程序控制中心、仿真执行窗口及各种输出窗口获得所需的数据及结果。

4.2 路径诱导对比实验设计及结果分析

由于采用人工数据，故本实验采取随机生成的方式得到各路段车辆平均行驶速度，以总行程时间为评价指标，在相同仿真环境下，分别对基于信号定时控制和信号优先控制下的路径诱导、初始路径诱导模式和应急车辆动态路径诱导模式两组进行对比实验，各情况运行10次，其中前者以总行程时间为评价指标进行比较，后者分别基于不同的车速降低量和不同的车速突变路段率对两方案进行对比，以总行程时间节省量为评价标准，这里的车速突变路段率指应急车辆在诱导路径上行驶一段时间后车速降低10km/h以上的未经过路段占总未经过路段的百分比。

（1）初始路径诱导模式基于信号定时控制和信号优先控制条件下的实验对比。该实验是基于宋辉华[8]在仿真实验中得到在定时信号控制和信号优先控制下应急车辆通过交叉口的时间，分别为43s和36s，且在应急车辆行驶过程中突变车速道路百分比为0,即本文提出的初始路径诱导模式下进行的。

①各路段不同时段历史速度生成。本实验以5min为时段间隔，由Starlogo软件采用random形式随机产生的历史速度如图3所示，图中各路段上三个速度值从左至右对应时段分别为系统时间0:00-0:05、0:05-0.10、0:10-0:15。

图3 各时段对应速度（km/h）

②各路段行程时间计算。应急车辆从0时出发前，根据应急车辆通过交叉口的时间和路段行驶时间公式预测到各路段应急车辆的行驶时间。在定时信号控制和信号优先控制条件下各路段应急车辆行驶时间分别如图4、图5所示，图中Node表示交叉口，各相邻交叉口间的数值即应急车辆路段行驶时间值，由于本实验中从救援点到受灾点的总路程较短，总行程时间不超过15min，而时段间隔为5min，故图4、图5对应路段中大部分路段应急车辆到达时间都在同一时段内，根据公式得到的路段行驶时间值相同，但不影响两者之间总行程时间的对比。

由Matlab得出的最短路径结果见表1。

图4 定时信号控制下行驶时间（s）

图5 信号优先控制下行驶时间(s)

表1 最短路径输出结果表

由Matlab得出最短路径分别为1-2-5-9-12-15-16，1-2-5-9-13-15-16。其行程总时间分别为533s和489s，节省44s，该实验表明了基于信号优先控制的路径诱导系统的有效性，同时也验证了路径诱导系统的实时性。

（2）基于信号优先控制条件下的初始路径诱导和实时路径诱导模式实验对比。该实验是在基于宋辉华[8]的信号优先控制下交叉口通过时间即36s的前提下进行的，并以初始交叉口做决策点为例。

①不同车速突变量下的诱导方案对比。以基于信号优先控制下的初始路径诱导方案为初始方案，即初始路线方案为1-2-5-9-13-15-16，假设路线的交通信息发生变化，如交通事故或该时段正处于交通状况转变期，致使该路段车辆平均速度发生突变，分别以10km/h、20km/h及30km/h的下降量为例进行实验。得出结果见表2。

表2 不同车速突变量下的行程时间对比表

由表2可以看出，随着路段车速下降量的增大，运用调整的路径诱导方法节省的时间越多，当降低30km/ h时，节省量可达到33%。故本文所述方案在突发路段交通事故时或路段交通状况正处于转变期时更为有效。

②不同的车速突变路段率下的诱导方案对比。该实验以20km/h的车速下降量为突变量，当车速突变路段率分别为1/3、2/3及1的情况下进行的，各运行10次。

表3分别为车速突变路段率为1/3时初选方案与调整方案总行程时间对比表。

表3 初选方案与调整方案总行程时间对比表

不同车速突变路段率下的时间节省量整理见表4。

表4 不同车速突变路段率下的时间节省量（%）

分别以15%、20%、25%及30%的时间节省量作为

路线改变方案的基准，其路线改变需求率如图6所示，图中路线改变需求率是指在本实验不同车速突变路段率情况下各运行10次中不同时间节省量为基准时应急车辆需要改变路线的次数与总次数（即10次）的比值。

图6 路线改变需求率

从表4可以看出，随着应急车辆行驶路线上未经过路段的车速突变路段率的增高，调整路径诱导方案下的最短路径的时间节省量越大，最大时可达43%，而从图6可以看出，随着路线改变方案基准的减低，应急车辆对路线改变的需求率越高。

5 结束语

本文主要研究了应急车辆在应急响应中以交叉口的信号优先控制为前提的路径诱导问题，运用多智能体系统与改进的Dijkstra算法相结合的方式对问题进行建模与求解。目的在于在交叉口保证应急车辆享有时间优先权的同时实现常规车辆运行效率的优化，在路段上变静态路径诱导为根据实时交通变化而改变的动态路径诱导，以实现应急车辆运行最优化。

[1]Kwon E L,Kim S.Development of Dynamic Route Clearance Strategies for Emergency Vehicle Operations,Phase I[R].Minneapolis:Center for Transportation Studies and Department of Computer Science,University of Minnesota,2003.

[2]Yang S,Hamedi M,Haghani A.Online dispatching and routing model for emergency vehicles with area coverage constraints[J]. Transportation Research Record,2005,(1 923):1-9.

[3]Y Y,D W.Path Selection model and algorithm for emergency logistics management[J].Computer and Industrial Engineering, 2008,56(3):1 081-1 094.

[4]Wang Y,Wu Z,Yang X,et al.Design and Implementation of an Emergency Vehicle Signal Preemption System Based on Cooperative Vehicle-Infrastructure Technology[J].Advances in Mechanical Engineering,2013,(December).

[5]钟源.多交叉口应急车辆信号优先协调控制研究[D].哈尔滨:哈尔滨工业大学,2011.

[6]刘帆.基于遗传算法的应急物流车辆路径问题研究[D].西安:西安科技大学,2012.

[7]刘建美,马寿峰,马帅奇.基于改进的Dijkstra算法的动态最短路计算方法[J].系统工程理论与实践,2011,(6):1 153-1 157.

[8]宋辉华.基于多智能体的多应急车辆信号优先控制问题研究[D].哈尔滨:哈尔滨工业大学,2008.

Study on Emergency Vehicle Path Guidance Strategy Based on Multi-agent System

Zhao Xin,Chen Shanshan
(School of Communications,Wuhan University of Technology,Wuhan 430063,China)

In this paper,in order to ensure the smooth passage of the emergency vehicles and considering from the aspects of crosssection signal priority control and path guidance,we built the MAS-based emergency vehicle path guidance strategy.First we used the phase agent and management agent to realize the signal priority of the emergency vehicles at road cross-sections and then proposed the on-board agent and road section agent to collaborate with the foregoing two agents to finish the path guidance of the emergency vehicles.At the end, using Starlogo and Matlab,we demonstrated the emergency vehicle path guidance process which showed the validity of the method proposed in this paper.

emergency vehicle;signal priority;path guidance;multi-agent system

F253.9;U116.2

A

1005-152X(2016)10-0042-06

10.3969/j.issn.1005-152X.2016.10.012

2016-09-12

教育部留学回国人员科研启动基金“基于时间窗约束的实时交通网络流应急增载优化研究”（44130041）

赵欣（1979-），男，湖北人，副教授，研究方向：智能交通系统、交通控制优化；陈珊珊（1990-），女，安徽人，交通运输规划与管理专业硕士，主要研究方向：智能交通系统、交通控制优化。