基于覆盖控制的城市多应急救援车辆分布规划策略

左磊, 孟铎, 闫茂德, 张守旭

1.长安大学 电子与控制工程学院,陕西 西安 710064; 2.西北工业大学 航海学院, 陕西 西安 710072

近年来,随着机动车保有量快速增加与人们出行需求日益增长,城市交通安全问题愈发严峻。对于城市内频发的交通事故,交通管理部门与应急救援部门需及时处理交通事故,尽量避免通行效率降低,甚至人员伤亡的情况[1]。城市道路应急救援车辆作为处理交通事故的主要工具,其合理的分布规划能够有效缩短交通事故的影响范围,提高救援效率,减少社会经济损失[2]。

城市应急救援车辆分布规划的核心问题是应急救援车辆的负责区域划分与分布位置优化。目前国内外在这方面已取得了一定的研究成果[3-7]。国外在应急救援车辆分布规划方面的研究起步较早,针对不同的路网模型以及目标需求,提出了不同的分布模型,包括P-中心模型[8]、P-中位模型[9]、集合覆盖模型[10]、最大覆盖模型[11]和多目标优化模型[12]。Huang等[13]研究了P-中心问题中整个城市大部分设施失去功能的大规模紧急情况,对路径网络上的设施位置使用动态规划方法,并进一步开发了一种有效的算法来优化位置分布。Kocatepe等[14]在分配避难所空间时,考虑特殊人群需求,提出了一个容量化的P中值优化模型,最大限度地提高了现有避难所的可达性和容量。Shiah等[15]利用地址数据来衡量需求容量以及最短路径的组合,将救护车的服务能力引入集合覆盖模型,使对目标区域的覆盖率得到了大幅度提升。Murali等[16]考虑了基于距离的覆盖函数和需求不确定性,提出了面向最大覆盖范围的选址模型,并通过解决定位设施的案例证明了该模型的可行性。Moghaddam[17]设计了一个多目标数学模型以识别和排序候选供应商,并能够有效获取识别模型的最优解。

相比之下,国内针对应急救援车辆分布问题的研究主要侧重于理论模型的改进与优化。方磊等[18]在考虑应急系统时间紧迫性的基础上,提出了基于系统最小费用的数学模型,并设计了相应的求解算法。杨金顺等[19]考虑公路自然灾害应急救援点的功能需求,建立了基于多目标的公路网应急救援点选址模型,并将选址模型应用于浙江桐庐公路网。姜涛等[20]基于应急设施到各个事故点的最小距离,设计了考虑不确定性的应急设施选址模型,并给出了模型的求解算法。

然而,上述关于应急救援车辆的分布规划大多是从管理规划的角度出发,在具体量化分析与数值理论研究方面尚显不足。因此,本文引入覆盖控制理论,综合考虑应急救援车辆的运动学模型与城市道路的拥堵状况,通过建立面向最小救援时间的应急救援车辆分布规划模型,设计不同拥堵路况下城市多应急救援车辆的分布规划策略。

覆盖控制理论是面向任务需求的多智能体协同控制方法,综合考虑了智能体的运动模型和目标区域内的信息分布状态。利用覆盖控制方法,可根据目标区域内的信息分布情况,合理分布多智能体的位置,使得目标区域内的关键节点受到更多智能体的关注。近年来,随着对机器-信息交互需求的加深,覆盖控制理论也应用于环境监测、智能巡逻、火灾巡检和应急救援等多个领域[21-23]。

根据目标区域内信息分布状态的变化特性,覆盖控制可分为静态覆盖和动态覆盖两大类[24]。传统的覆盖控制大多是静态覆盖,在静态覆盖下信息分布状态不会随时间发生变化。Cortes等[25]基于Voronoi分区原则,提出了面向连续和离散系统的多智能体覆盖控制算法,并验证了相应算法的可行性与收敛性。相比之下,动态覆盖更符合实际问题,由于待覆盖信息的分布规律不断变化,多智能体系统为了获得最优的覆盖效果,必须随时调整多智能体位置,持续对任务环境进行监测。Zuo等[26]针对动态信息分布区域内的最短时间覆盖控制问题,设计了基于时间最优的Voronoi区域划分方法,并为多智能体网络提供了一种分布式覆盖控制律,使得智能体能够从目标区域内的任意位置逐渐收敛到目标区域内的最优覆盖位置。此外,从目标区域的空间维度出发,覆盖控制在三维覆盖(3D覆盖)、二维覆盖(平面覆盖)和一维覆盖(直线覆盖)领域内均有研究[27-29]。

受此启发,本文拟应用覆盖控制理论优化解决城市多应急救援车辆的分布规划问题,研究范畴及所用方法属于静态覆盖问题。在现有的覆盖控制研究成果中,智能体在目标区域内可以任意移动,其行驶轨迹不受任何约束限制,然而应急救援车辆在城市中的运动轨迹受路网的约束。两者结合会产生一个新的科学问题,即二维平面内交叉型区域的多智能体覆盖控制问题。而这一问题在覆盖控制中相关成果较少,仍需开展大量的研究工作。因此,应用覆盖控制理论解决城市多应急救援车辆的分布规划问题,具有丰富的理论意义与应用价值。

有鉴于此,本文研究基于覆盖控制的城市应急救援车辆分布策略,主要创新点在于:①针对城市应急救援车辆的分布规划问题,综合考虑城市交通的拥堵状态,利用覆盖控制理论,建立面向最短救援时间的多应急救援车辆分布规划模型,量化评价多应急救援车辆在目标区域内救援时间成本;②综合考虑应急救援车辆在城市路网的轨迹约束与交通拥堵阻尼,利用梯度下降法计算多应急救援车辆在目标区域内的最优分布位置与救援负责区域,并通过仿真实验的方式验证所提算法的有效性与可行性。

1 问题描述

考虑n辆应急救援车随机分布在目标区域Q中,每辆车的运动学模型为

(1)

式中:pi为第i辆应急救援车的位置信息;ui为它的控制输入。

针对多应急救援车的最优分布规划问题,假设每辆车具有通讯、计算、采样和定位功能,且它们的最大速度相同。由于城市路网在不同路段和不同时间段上的交通流量差别较大,其交通拥堵状况也存在差异,会对车辆的救援时间产生不同的影响,因此,本文使用函数φ(q):Q→R+来描述目标区域内交通拥堵状态,其中q∈Q表示路网Q内任意一点。同一路段在不同的交通拥堵状态下,应急救援车的救援时间必然有所不同。

根据上述场景描述,本文主要研究城市路网在不同交通拥堵状态下,多辆应急救援车在目标区域内的最优分布问题。引入交通拥堵函数来描述目标区域内的交通拥堵状况,以车辆救援时间为评价函数,构建面向整个区域的救援时间消耗目标函数。利用覆盖控制的相关理论,调整应急救援车辆的分布位置,优化目标函数,使得目标区域内任意一点发生的交通事故都能得到最快响应。

注1:本文考虑到交通拥堵状态是分层级的,在某一特定时间段内,可以认为不变。因此,可以利用特定时间段内的固定交通拥堵状态计算多应急车辆分布。当目标区域内的交通拥堵状态发生变化时,可以根据新的交通拥堵状态重新计算多应急救援车辆分布,调整应急车辆位置与负责区域。

2 城市路网下的多应急救援车辆分布模型

2.1 多应急救援车辆分布建模

应急救援车辆分布规划的关键点在于减少应急救援车辆到达交通事故发生点的救援时间。假设事故点附近有多辆应急救援车,在考虑交通拥堵状况下,确定每辆应急救援车的负责区域,是建立应急救援车辆分布模型的关键。

有鉴于此,考虑某一交通事故的周围存在2辆应急救援车,如图1所示,其中q点处发生交通事故,车辆i和j均在事故点附近,其位置分别为pi与pj。当前路网的交通拥堵状态函数为φ(q)。分别计算车辆i和车辆j到q的时间tiq与tjq。比较tiq和tjq的大小,并选择耗时最短的车辆前往事故点救援。

考虑更大的路网中存在更多的交通事故与应急救援车辆。首先需要按照时间最优的原则,确定每辆应急救援车的负责区域与最优分布位置。当目标区域中某个位置发生交通事故后,判断该点属于哪一辆车辆的负责区域,并派遣相应的车辆前往事故发生点救援。

图2展示了大范围路网内多应急救援车辆分布场景,其中图2a)为多应急车辆初始分布场景,图中分布了4辆应急救援车辆,不同颜色的直线表示不同应急救援车辆的负责区域,假设图中任意位置发生了交通事故,则派遣事故点所属区域的应急救援车辆进行救援。图2b)为多应急救援车辆优化分布场景,此时每个应急救援车辆更靠近交通拥堵程度高的区域。例如车辆4此时位于交通拥堵程度高的路段,若在其负责的区域内发生了交通事故,相比于图2a)中初始分布的位置,车辆4可更快速地前往事故地点进行处理,进而有效减少救援响应的时间。

从更严谨的数学角度来说,假设所构建的城市路网(目标区域)是由n×n条道路组成的方格形结构。在路网中,n辆应急救援车辆初始时刻随机分布在路网上。根据道路上不同位置的交通拥堵状态φ(q),规划每辆应急救援车的负责区域Wi,并计算每辆应急救援车的最优位置pi,使得车辆对目标区域内任意一点的交通位置都能够实现快速的救援响应,进而缩小多应急救援车对整个目标区域内所有事故的救援时间。

为了定量地描述车辆的救援时间,定义多应急救援车在目标区域内的救援时间目标函数为

(2)

式中:P={p1,…,pn}为所有车辆的位置信息集合;W={W1,…,Wn}为所有车辆的负责区域;f(pi,q,φ(q))用来表示第i辆车到其分配区域Wi内任意一点q的救援时间函数。

由(2)式可知,应急救援车辆的救援时间由车辆的位置信息P、负责区域Wi以及交通拥堵函数φ(q)共同决定。由于φ(q)已经固定,当目标函数H(P,W)达到最小时,所有车辆的负责区域及其位置均处于最优。

因此,要实现目标区域内多应急救援车辆的最优分布规划,不仅需要解决目标区域的最优分配问题,还要计算车辆在其负责区域内的最优位置。

注2:本文提出的应急救援车辆分布模型旨在寻找多辆应急救援车辆在目标区域内负责的子区域以及最优位置,是在交通事故发生前就进行的分配,以便真实的交通事故发生后,能够得到最快救援。

注3:针对应急车辆数量限制这一问题,首先应分析目标区域的范围大小,结合每辆应急救援车辆的范围能力,进一步确定应急救援车辆的数量。本文聚焦于考虑拥堵路况下应急救援车辆的分布,重点建立了城市多应急救援车覆盖网络的评价模型。对不同范围的路网,应急车辆的数量不同。同一路网中,每个应急车辆的负责区域会随应急车辆数量的增加而变小,反之亦然。

2.2 多应急救援车的负责区域分配方法

应急救援车的区域分配方法是基于Voronoi区域分配原理。Voronoi区域分配原理是指利用特定的评价指标,根据多智能体的位置信息,将目标区域分割成多个互不重叠的子区域。在这些子区域所包含的智能体拥有优于其他智能体的特性优势[30]。例如当以距离为评价指标时,每个智能体到其子区域内任意一点的距离都小于其他智能体到该点的距离。

在此基础上,考虑n辆应急救援车随机分布在目标区域Q内,其位置为P。则多应急救援车辆的区域分配原则可表示为

Vi={q∈Q|f(pi,q)≤f(pj,q),∀i≠j,∀i,j∈n}

(3)

式中:f(pi,q)为第i辆车到达目标点q的评价指标;Vi为第i辆车的负责区域。

多应急救援车的应急救援时间目标函数可进一步改写为

(4)

式中,V={V1,…,Vn}表示所有应急救援车的负责区域集合。

以应急救援车辆到达事故点的时间为目标函数。令(4)式中的评价指标f(pi,q)为车辆到达目标点q的时间,即

f(pi,q)=tiq

(5)

式中,tiq为第i个车到点q的时间。

在此基础上,多应急救援车辆的Voronoi区域分配表示为

Vi={q∈Q|tiq≤tjq,∀i≠j,∀i,j∈n}

(6)

由(6)式可知,应急救援车辆到达其负责区域内任意一点的时间均小于其他车辆。即交通事故的发生地点在哪辆车的负责区域,就由相应的应急救援车进行救援。

在进一步确定车辆的负责区域过程中,需具体计算车辆到点q的行驶时间tiq。然而影响tiq的参量不仅包括车辆的行驶轨迹,还与当前路网下的交通拥堵状态φ(q)相关。后续将详细介绍tiq的计算方法。

2.3 城市路网下应急救援车的救援时间

针对应急救援车辆在城市路网的行驶轨迹,本文分析了应急救援车辆在城市路网中的3种典型情形:直线路段、T字形交叉口和十字形交叉口。具体的行驶场景如下:

情形一:当车辆位于直线路段上时,车辆在此路段内仅能朝2个方向移动。假设车辆每个单位时间内行驶距离相同,单位时间后车辆的位置会出现图3中所示的情况。

图3 车辆位置移动情形一

情形二:当车辆位于T字形交叉口时,车辆可在此路口朝3个方向移动。假设车辆每个单位时间内行驶距离相同,单位时间后车辆的位置会出现图4中所示的情况。

图4 车辆位置移动情形二

情形三:当车辆位于十字形交叉口时,车辆可在此路口朝4个方向移动。假设车辆每个单位时间内行驶距离相同,单位时间后车辆的位置会出现图5中所示的情况。

图5 车辆位置移动情形三

在明确应急救援车的行驶路径后,车辆到达目标区域内任意一点的行驶时间可通过如下过程计算。

首先将城市路网进行栅格化处理。假设栅格化后相邻两点之间的长度均为l,由于单个栅格区间的长度较短,可以认为同一栅格区间内各点的交通拥堵函数φ(q)的大小相同,图6所示为路段栅格化后的状态。

图6 路段栅格化

在此引入自由流车速,自由流车速是指密度为零时交通流的理论速度,定义路段的自由流车速为vf,假设各路段的自由流车速相同。同一栅格区间内各点的交通拥堵函数φ(q)大小相同,以相邻2个栅格点a与b为例,a与b之间的交通拥堵函数大小即为a点处的交通拥堵函数大小φ(qa)。则相应的实际车速vr的数学表述为

(7)

式中,qa=[xa,ya]为目标区域Q内路网上点a的坐标。

(8)

假设应急救援车辆的当前位置pi距离事故点q的行驶距离为Liq,则该行驶距离包含上述离散化网格的数量Niq为

(9)

则应急救援车辆到达事故点q的时间tiq可表示为

(10)

在此基础上,多应急救援车的救援时间目标函数H(P,V)可进一步表述为

(11)

3 基于覆盖控制的车辆分布规划策略

根据上述多应急救援车在城市路网的分布模型,基于覆盖控制的车辆分布规划方法重点在于:通过调整多应急救援车的位置,使得救援时间目标函数H(P,V)的值逐渐达到最小。根据(11)式中H(P,V)的具体形式,通过梯度优化的方法,逐步求解多应急救援车辆在城市交通路网中的最优分布。

图7为基于覆盖控制的多应急救援车辆分布规划控制系统框图。通过该控制系统,能够使得随机分布在城市路网中的应急救援车辆,逐渐收敛到最优分布状态。

图7 基于覆盖控制的多应急救援车分布规划控制框图

在该控制系统中,多应急救援车辆网络包括n个分布式协同控制器、车辆运动学模型和位置信息。车辆的位置信息P、交通拥堵函数φ(q)以及城市路网模型均为已知信息。在控制过程中,首先利用Voronoi区域分配原则对目标城市路网进行划分,得到n辆车的负责区域。其次,形成以车辆位置为变量的时间目标函数。最后,通过梯度下降法,调整每辆应急救援车的位置与负责区域,使得目标函数H(P,V)逐渐趋向最小值。

需要注意的是多应急救援车辆的负责区域与最优位置是交互影响的。由于Voronoi区域分配原则是根据2辆相邻车辆的当前位置进行划分的,当利用优化方法减少目标函数H(P,V)时,会产生新的车辆位置,进而导致相邻车辆的Voronoi区域产生变化。而新的Voronoi区域会进一步影响H(P,V)的结构,使得H(P,V)衍化出新的最优解。这一更新迭代过程会一直持续到H(P,V)的优化结果与更新后的Voronoi区域结果一致为止。

在上述控制系统的基础上,给出如图8所示的计算流程图。通过该计算流程,可使得随机分布的应急救援车辆逐步趋向于当前拥堵状态下的最优分布。

图8 多应急救援车分布规划算法流程图

根据图8中的算法流程,基于覆盖控制的车辆分布规划算法步骤如下:

step1 考虑n辆应急车初始时刻位置P(t0)={p1(t0),…,pn(t0)}。

step2 初始化n辆应急车位于初始位置时的Voronoi区域,得到每辆应急救援车的Voronoi区域{V(p1(t0)),…,V(pn(t0))}。

step3 建立目标区域内所有路段的交通拥堵函数φ(q)。

step4 计算第i辆应急车位于P(t0)处时分别到达其分配区域内任意一点q的时间tiq(pi(t0))。在此基础上,求得总时间T(pi(t0))

(12)

step5 重复执行step4,计算其余n-1辆车位于其Voronoi区域内的消耗总时间{T(p1(t0)),…,T(pn(t0))},得到整个应急救援车辆网络在目标区域内的位于P(t0)处消耗时间目标函数和H(P(t0))

(13)

step6 根据车辆位置移动的3种情形,以初始时刻位置为起点,采用梯度下降法计算每辆应急车下一步的位置,并更新每辆车的Voronoi区域。

step7 交替迭代step6,使得H(P,V)逐渐趋向于最小值。此时区域分配即为最优区域分配,车辆的位置即为最优位置。

需要注意的是,本文提出的车辆分布规划方式属于优化问题中的一种,得到的最优分布位置可能是目标函数H(P,V)的局部最优解。产生这一结果的原因是无法确定目标函数H(P,V)的凹凸性。然而这一结果并不影响实际应用。因为在工程应用中,大部分结果的全局最优解是不存在的。只要能够通过该方法,有效提升应急救援车辆对目标城市区域内的救援效率,就具有一定的应用价值。

4 仿真实验

考虑6辆应急救援车随机分布在由12条交叉直线组成的5 km×5 km的目标区域Q中。该目标区域Q为标准的横纵型路网模型。每辆车的运动模型由(1)式描述。令路网中每条路长度为L=5 km,栅格化后相邻两点之间的长度l=0.1 km,各路段的自由流车速vf=40 km/h,目标区域内的交通拥堵状态分布函数φ(q)表示为

φ(q)=1+9exp(-0.1(x-5)2-0.1(y-5)2)

(14)

式中,q=[x,y]为目标区域Q内路网上的任意一点的坐标。

图9为交通拥堵状态分布函数在目标区域Q内的变化规律。由该图可知,目标区域在右上角的区域拥堵系数最高。

图9 交通拥堵状态分布函数 图10 应急救援车的初始位置及其Voronoi区域 图11 多应急救援车最优位置及其Voronoi区域

图10和图11分别为多应急救援车网络在目标区域内的初始位置和最优位置,其中星号代表车辆的初始位置,三角代表车辆的最优分布。每辆应急救援车辆的负责区域由不同颜色进行区分。

由图10仿真结果可知,在考虑交通拥堵情况下,每辆应急救援车的负责区域均有所不同。例如6号车所在位置的周围交通拥堵系数较高,则6号车负责的区域较小,进而有效保障该区域内的交通事故能够得到及时处理。4号车的负责区域也明显大于6号车。这是因为4号车的负责区域内交通拥堵状态优于6号车的负责区域。

图11为多应急救援车在目标区域内的最优分布规划,其中应急救援车辆的负责区域是根据当前车辆的优化位置(即三角标号位置)进行划分的。对比图10与图11可知,利用本文提出的分布规划算法,多应急救援车的分布位置以及负责区域都产生了不同程度变化。这一变化验证了应急救援车辆与负责区域之间的交替影响规律。更进一步地,关于该分布规划优化算法的量化分析可通过图12进行说明。

图12 多应急救援车网络的目标函数

图12为多应急救援车在目标区域内的救援时间目标函数变化曲线,其中纵坐标为应急救援车到达目标区域内任意一点的整体时间,横坐标为应急救援车辆从初始位置收敛到最优分布所用的时间。由该结果可知,随着分布优化算法的实施,多应急救援车不断调整其最优分布位置,使其对目标区域的整体救援时间逐渐减少。此外,本文还在图12中将所提算法与传统的平均分布算法进行了对比,其中H1为平均分布规划算法,H2为本文所提的基于覆盖控制的分布规划算法。由该对比结果可知,本文所提算法充分考虑目标区域内的交通拥堵状态,使得应急救援车辆能够在更短的时间内对目标区域内任意一点的交通事故进行处理,整体救援时间缩短了15%。

因此,上述仿真结果表明多应急救援车辆网络能够实现对目标区域的最优覆盖,验证了本文提出多应急救援车最优分布规划算法的有效性与可行性。

5 结 论

本文基于覆盖控制理论,考虑交通拥堵状况对城市应急救援车辆分布的影响,构建了面向最优应急救援时间的分布规划模型,并提出了多应急救援车在多事故发生情况下的分布规划策略。

针对多个应急救援车在目标区域内的区域分配问题,利用Voronoi区域分配原则,以每辆车到任意一点的行驶时间为评价指标,提出了基于Voronoi区域分配原则的区域划分策略,使得目标区域内任意一点的交通事故,都能够在最短的时间内得到响应。

相对于传统的车辆平均分配原则,本文所提的分配规划方法充分考虑了交通拥堵路况对分布规划策略的影响,可有效提高应急救援车辆对目标区域的覆盖效率,缩短救援时间。

后续的研究将进一步在更复杂的交通路网上,进行未知路况的估计,分析未知路况下的城市多应急救援车辆分布规划方法。