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

年 月第 卷第 期西 北 工 业 大 学 学 报 ：收稿日期：基金项目：国家重点研发计划（）、陕西省重点研发计划（）与中国博士后基金（）资助作者简介：左磊（），长安大学副教授，主要从事多智能体协同控制、覆盖控制及车路协同控制研究。：基于覆盖控制的城市多应急救援车辆分布规划策略左磊，孟铎，闫茂德，张守旭长安大学 电子与控制工程学院，陕西 西安；西北工业大学 航海学院，陕西 西安()摘 要：为了优化应急救援车辆在城市内的分布规划，实现对城市交通事故的快速响应，研究了面向最短救援时间的多应急救援车辆分布规划策略。根据覆盖控制理论，考虑交通拥堵对车辆救援时间的影响，分析多应急救援车网络对目标区域的整体时间消耗，构建面向救援时间的优化模型；针对应急救援车辆的负责区域划分问题，以应急救援车辆达到城市路网内任意一点的行驶时间为评价指标，利用 区域分配原则，计算每辆应急救援车的负责区域；考虑应急救援车在城市路网内的行驶约束，分析城市道路中车辆的运动学特性，进一步明确优化模型中的约束条件；根据梯度下降法，计算多应急救援车辆在目标区域内的最优分布位置以及相应的负责区域。实验结果表明，多应急救援车辆能够从目标城市内的任意位置逐渐收敛到最优分布位置，使得目标区域内任意一点的交通事故都能够得到有效响应。关 键 词：车辆分布；覆盖控制；交通拥堵；区域分配；最优位置中图分类号：文献标志码：文章编号：（）近年来，随着机动车保有量快速增加与人们出行需求日益增长，城市交通安全问题愈发严峻。对于城市内频发的交通事故，交通管理部门与应急救援部门需及时处理交通事故，尽量避免通行效率降低，甚至人员伤亡的情况。城市道路应急救援车辆作为处理交通事故的主要工具，其合理的分布规划能够有效缩短交通事故的影响范围，提高救援效率，减少社会经济损失。城市应急救援车辆分布规划的核心问题是应急救援车辆的负责区域划分与分布位置优化。目前国内外在这方面已取得了一定的研究成果。国外在应急救援车辆分布规划方面的研究起步较早，针对不同的路网模型以及目标需求，提出了不同的分布模型，包括 中心模型、中位模型、集合覆盖模 型、最 大 覆 盖 模 型和 多 目 标 优 化 模型。等研究了 中心问题中整个城市大部分设施失去功能的大规模紧急情况，对路径网络上的设施位置使用动态规划方法，并进一步开发了一种有效的算法来优化位置分布。等在分配避难所空间时，考虑特殊人群需求，提出了一个容量化的 中值优化模型，最大限度地提高了现有避难所的可达性和容量。等利用地址数据来衡量需求容量以及最短路径的组合，将救护车的服务能力引入集合覆盖模型，使对目标区域的覆盖率得到了大幅度提升。等考虑了基于距离的覆盖函数和需求不确定性，提出了面向最大覆盖范围的选址模型，并通过解决定位设施的案例证明了该模型的可行性。设计了一个多目标数学模型以识别和排序候选供应商，并能够有效获取识别模型的最优解。相比之下，国内针对应急救援车辆分布问题的研究主要侧重于理论模型的改进与优化。方磊第 期左磊，等：基于覆盖控制的城市多应急救援车辆分布规划策略等在考虑应急系统时间紧迫性的基础上，提出了基于系统最小费用的数学模型，并设计了相应的求解算法。杨金顺等考虑公路自然灾害应急救援点的功能需求，建立了基于多目标的公路网应急救援点选址模型，并将选址模型应用于浙江桐庐公路网。姜涛等基于应急设施到各个事故点的最小距离，设计了考虑不确定性的应急设施选址模型，并给出了模型的求解算法。然而，上述关于应急救援车辆的分布规划大多是从管理规划的角度出发，在具体量化分析与数值理论研究方面尚显不足。因此，本文引入覆盖控制理论，综合考虑应急救援车辆的运动学模型与城市道路的拥堵状况，通过建立面向最小救援时间的应急救援车辆分布规划模型，设计不同拥堵路况下城市多应急救援车辆的分布规划策略。覆盖控制理论是面向任务需求的多智能体协同控制方法，综合考虑了智能体的运动模型和目标区域内的信息分布状态。利用覆盖控制方法，可根据目标区域内的信息分布情况，合理分布多智能体的位置，使得目标区域内的关键节点受到更多智能体的关注。近年来，随着对机器信息交互需求的加深，覆盖控制理论也应用于环境监测、智能巡逻、火灾巡检和应急救援等多个领域。根据目标区域内信息分布状态的变化特性，覆盖控制可分为静态覆盖和动态覆盖两大类。传统的覆盖控制大多是静态覆盖，在静态覆盖下信息分布状态不会随时间发生变化。等基于 分区原则，提出了面向连续和离散系统的多智能体覆盖控制算法，并验证了相应算法的可行性与收敛性。相比之下，动态覆盖更符合实际问题，由于待覆盖信息的分布规律不断变化，多智能体系统为了获得最优的覆盖效果，必须随时调整多智能体位置，持续对任务环境进行监测。等针对动态信息分布区域内的最短时间覆盖控制问题，设计了基于时间最优的 区域划分方法，并为多智能体网络提供了一种分布式覆盖控制律，使得智能体能够从目标区域内的任意位置逐渐收敛到目标区域内的最优覆盖位置。此外，从目标区域的空间维度出发，覆盖控制在三维覆盖（覆盖）、二维覆盖（平面覆盖）和一维覆盖（直线覆盖）领域内均有研究。受此启发，本文拟应用覆盖控制理论优化解决城市多应急救援车辆的分布规划问题，研究范畴及所用方法属于静态覆盖问题。在现有的覆盖控制研究成果中，智能体在目标区域内可以任意移动，其行驶轨迹不受任何约束限制，然而应急救援车辆在城市中的运动轨迹受路网的约束。两者结合会产生一个新的科学问题，即二维平面内交叉型区域的多智能体覆盖控制问题。而这一问题在覆盖控制中相关成果较少，仍需开展大量的研究工作。因此，应用覆盖控制理论解决城市多应急救援车辆的分布规划问题，具有丰富的理论意义与应用价值。有鉴于此，本文研究基于覆盖控制的城市应急救援车辆分布策略，主要创新点在于：针对城市应急救援车辆的分布规划问题，综合考虑城市交通的拥堵状态，利用覆盖控制理论，建立面向最短救援时间的多应急救援车辆分布规划模型，量化评价多应急救援车辆在目标区域内救援时间成本；综合考虑应急救援车辆在城市路网的轨迹约束与交通拥堵阻尼，利用梯度下降法计算多应急救援车辆在目标区域内的最优分布位置与救援负责区域，并通过仿真实验的方式验证所提算法的有效性与可行性。问题描述考虑 辆应急救援车随机分布在目标区域 中，每辆车的运动学模型为 ，（）式中：为第 辆应急救援车的位置信息；为它的控制输入。针对多应急救援车的最优分布规划问题，假设每辆车具有通讯、计算、采样和定位功能，且它们的最大速度相同。由于城市路网在不同路段和不同时间段上的交通流量差别较大，其交通拥堵状况也存在差异，会对车辆的救援时间产生不同的影响，因此，本文使用函数（）：来描述目标区域内交通拥堵状态，其中表示路网 内任意一点。同一路段在不同的交通拥堵状态下，应急救援车的救援时间必然有所不同。根据上述场景描述，本文主要研究城市路网在不同交通拥堵状态下，多辆应急救援车在目标区域内的最优分布问题。引入交通拥堵函数来描述目标区域内的交通拥堵状况，以车辆救援时间为评价函数，构建面向整个区域的救援时间消耗目标函数。利用覆盖控制的相关理论，调整应急救援车辆的分布位置，优化目标函数，使得目标区域内任意一点发西 北 工 业 大 学 学 报第 卷生的交通事故都能得到最快响应。注：本文考虑到交通拥堵状态是分层级的，在某一特定时间段内，可以认为不变。因此，可以利用特定时间段内的固定交通拥堵状态计算多应急车辆分布。当目标区域内的交通拥堵状态发生变化时，可以根据新的交通拥堵状态重新计算多应急救援车辆分布，调整应急车辆位置与负责区域。城市路网下的多应急救援车辆分布模型 多应急救援车辆分布建模应急救援车辆分布规划的关键点在于减少应急救援车辆到达交通事故发生点的救援时间。假设事故点附近有多辆应急救援车，在考虑交通拥堵状况下，确定每辆应急救援车的负责区域，是建立应急救援车辆分布模型的关键。有鉴于此，考虑某一交通事故的周围存在 辆应急救援车，如图 所示，其中 点处发生交通事故，车辆 和 均在事故点附近，其位置分别为 与。当前路网的交通拥堵状态函数为（）。分别计算车辆和车辆到的时间与。比较和的大小，并选择耗时最短的车辆前往事故点救援。图 交通事故应急救援场景一考虑更大的路网中存在更多的交通事故与应急救援车辆。首先需要按照时间最优的原则，确定每辆应急救援车的负责区域与最优分布位置。当目标区域中某个位置发生交通事故后，判断该点属于哪一辆车辆的负责区域，并派遣相应的车辆前往事故发生点救援。图 展示了大范围路网内多应急救援车辆分布场景，其中图）为多应急车辆初始分布场景，图中分布了 辆应急救援车辆，不同颜色的直线表示不同应急救援车辆的负责区域，假设图中任意位置发生了交通事故，则派遣事故点所属区域的应急救援车辆进行救援。图）为多应急救援车辆优化分布场景，此时每个应急救援车辆更靠近交通拥堵程度高的区域。例如车辆 此时位于交通拥堵程度高的路段，若在其负责的区域内发生了交通事故，相比于图）中初始分布的位置，车辆 可更快速地前往事故地点进行处理，进而有效减少救援响应的时间。图 多应急救援车辆分布场景从更严谨的数学角度来说，假设所构建的城市路网（目标区域）是由 条道路组成的方格形结构。在路网中，辆应急救援车辆初始时刻随机分布在路网上。根据道路上不同位置的交通拥堵状态（），规划每辆应急救援车的负责区域，并计算每辆应急救援车的最优位置，使得车辆对目标区第 期左磊，等：基于覆盖控制的城市多应急救援车辆分布规划策略域内任意一点的交通位置都能够实现快速的救援响应，进而缩小多应急救援车对整个目标区域内所有事故的救援时间。为了定量地描述车辆的救援时间，定义多应急救援车在目标区域内的救援时间目标函数为（，）（，（）（）式中：，为所有车辆的位置信息集合；，为所有车辆的负责区域；（，（）用来表示第辆车到其分配区域内任意一点 的救援时间函数。由（）式可知，应急救援车辆的救援时间由车辆的位置信息、负责区域 以及交通拥堵函数（）共同决定。由于（）已经固定，当目标函数（，）达到最小时，所有车辆的负责区域及其位置均处于最优。因此，要实现目标区域内多应急救援车辆的最优分布规划，不仅需要解决目标区域的最优分配问题，还要计算车辆在其负责区域内的最优位置。注：本文提出的应急救援车辆分布模型旨在寻找多辆应急救援车辆在目标区域内负责的子区域以及最优位置，是在交通事故发生前就进行的分配，以便真实的交通事故发生后，能够得到最快救援。注：针对应急车辆数量限制这一问题，首先应分析目标区域的范围大小，结合每辆应急救援车辆的范围能力，进一步确定应急救援车辆的数量。本文聚焦于考虑拥堵路况下应急救援车辆的分布，重点建立了城市多应急救援车覆盖网络的评价模型。对不同范围的路网，应急车辆的数量不同。同一路网中，每个应急车辆的负责区域会随应急车辆数量的增加而变小，反之亦然。多应急救援车的负责区域分配方法应急救援车的区域分配方法是基于 区域分配原理。区域分配原理是指利用特定的评价指标，根据多智能体的位置信息，将目标区域分割成多个互不重叠的子区域。在这些子区域所包含的智能体拥有优于其他智能体的特性优势。例如当以距离为评价指标时，每个智能体到其子区域内任意一点的距离都小于其他智能体到该点的距离。在此基础上，考虑 辆应急救援车随机分布在目标区域 内，其位置为。则多应急救援车辆的区域分配原则可表示为 （，）（，），（）式中：（，）为第辆车到达目标点的评价指标；为第 辆车的负责区域。多应急救援车的应急救援时间目标函数可进一步改写为（，）（，）（）式中，表示所有应急救援车的负责区域集合。以应急救援车辆到达事故点的时间为目标函数。令（）式中的评价指标（，）为车辆到达目标点 的时间，即（，）（）式中，为第 个车到点 的时间。在此基础上，多应急救援车辆的 区域分配表示为 ，（）由（）式可知，应急救援车辆到达其负责区域内任意一点的时间均小于其他车辆。即交通事故的发生地点在哪辆车的负责区域，就由相应的应急救援车进行救援。在进一步确定车辆的负责区域过程中，需具体计算车辆到点 的行驶时间。然而影响的参量不仅包括车辆的行驶轨迹，还与当前路网下的交通拥堵状态（）相关。后续将详细介绍 的计算方法。城市路网下应急救援车的救援时间针对应急救援车辆在城市路网的行驶轨迹，本文分析了应急救援车辆在城市路网中的 种典型情形：直线路段、字形交叉口和十字形交叉口。具体的行驶场景如下：情形一：当车辆位于直线路段上时，车辆在此路段内仅能朝 个方向移动。假设车辆每个单位时间内行驶距离相同，单位时间后车辆的位置会出现图 中所示的情况。图 车辆位置移动情形一情形二：当车辆位于 字形交叉口时，车辆可在此路口朝 个方向移动。假设车辆每个单位时间西 北 工 业 大 学 学 报第 卷内行驶距离相同，单位时间后车辆的位置会出现图 中所示的情况。图 车辆位置移动情形二情形三：当车辆位于十字形交叉口时，车辆可在此路口朝 个方向移动。假设车辆每个单位时间内行驶距离相同，单位时间后车辆的位置会出现图 中所示的情况。图 车辆位置移动情形三在明确应急救援车的行驶路径后，车辆到达目标区域内任意一点的行驶时间可通过如下过程计算。首先将城市路网进行栅格化处理。假设栅格化后相邻两点之间的长度均为，由于单个栅格区间的长度较短，可以认为同一栅格区间内各点的交通拥堵函数（）的大小相同，图 所示为路段栅格化后的状态。图 路段栅格化在此引入自由流车速，自由流车速是指密度为零时交通流的理论速度，定义路段的自由流车速为，假设各路段的自由流车速相同。同一栅格区间内各点的交通拥堵函数（）大小相同，以相邻 个栅格点 与 为例，与 之间的交通拥堵函数大小即为 点处的交通拥堵函数大小（）。则相应的实际车速 的数学表述为（）（）式中，为目标区域 内路网上点 的坐标。在此基础上，应急救援车辆在相邻个栅格点与 之间移动的时间 为（），（）假设应急救援车辆的当前位置 距离事故点 的行驶距离为，则该行驶距离包含上述离散化网格的数量 为（）则应急救援车辆到达事故点 的时间 可表示为 （）在此基础上，多应急救援车的救援时间目标函数（，）可进一步表述为（，）（）基于覆盖控制的车辆分布规划策略根据上述多应急救援车在城市路网的分布模型，基于覆盖控制的车辆分布规划方法重点在于：通过调整多应急救援车的位置，使得救援时间目标函数（，）的值逐渐达到最小。根据（）式中（，）的具体形式，通过梯度优化的方法，逐步求解多应急救援车辆在城市交通路网中的最优分布。图 为基于覆盖控制的多应急救援车辆分布规划控制系统框图。通过该控制系统，能够使得随机分布在城市路网中的应急救援车辆，逐渐收敛到最优分布状态。在该控制系统中，多应急救援车辆网络包括 个分布式协同控制器、车辆运动学模型和位置信息。车辆的位置信息、交通拥堵函数（）以及城市路第 期左磊，等：基于覆盖控制的城市多应急救援车辆分布规划策略网模型均为已知信息。在控制过程中，首先利用 区域分配原则对目标城市路网进行划分，得到 辆车的负责区域。其次，形成以车辆位置为变量的时间目标函数。最后，通过梯度下降法，调整每辆应急救援车的位置与负责区域，使得目标函数（，）逐渐趋向最小值。需要注意的是多应急救援车辆的负责区域与最优位置是交互影响的。由于 区域分配原则是根据 辆相邻车辆的当前位置进行划分的，当利用优化方法减少目标函数（，）时，会产生新的车辆位置，进而导致相邻车辆的区域产生变化。而新的 区域会进一步影响（，）的结构，使得（，）衍化出新的最优解。这一更新迭代过程会一直持续到（，）的优化结果与更新后的 区域结果一致为止。图 基于覆盖控制的多应急救援车分布规划控制框图 在上述控制系统的基础上，给出如图 所示的计算流程图。通过该计算流程，可使得随机分布的应急救援车辆逐步趋向于当前拥堵状态下的最优分布。图 多应急救援车分布规划算法流程图根据图 中的算法流程，基于覆盖控制的车辆分布规划算法步骤如下：考虑 辆应急车初始时刻位置（）（），（）。初始化 辆应急车位于初始位置时的 区域，得到每辆应急救援车的 区域（），（）。建立目标区域内所有路段的交通拥堵函数（）。计算第 辆应急车位于（）处时分别到达其分配区域内任意一点 的时间（）。在此基础上，求得总时间（）（）（）（）重复执行，计算其余 辆车位于其 区域内的消耗总时间（），（），得到整个应急救援车辆网络在目标区域内 的 位 于（）处 消 耗 时 间 目 标 函 数 和（）（）（）（）根据车辆位置移动的 种情形，以初始时刻位置为起点，采用梯度下降法计算每辆应急车下一步的位置，并更新每辆车的 区域。交替迭代，使得（，）逐渐趋向西 北 工 业 大 学 学 报第 卷于最小值。此时区域分配即为最优区域分配，车辆的位置即为最优位置。需要注意的是，本文提出的车辆分布规划方式属于优化问题中的一种，得到的最优分布位置可能是目标函数（，）的局部最优解。产生这一结果的原因是无法确定目标函数（，）的凹凸性。然而这一结果并不影响实际应用。因为在工程应用中，大部分结果的全局最优解是不存在的。只要能够通过该方法，有效提升应急救援车辆对目标城市区域内的救援效率，就具有一定的应用价值。仿真实验考虑 辆应急救援车随机分布在由 条交叉直线组成的 的目标区域 中。该目标区域为标准的横纵型路网模型。每辆车的运动模型由（）式描述。令路网中每条路长度为 ，栅格化后相邻两点之间的长度 ，各路段的自由流车速 ，目标区域内的交通拥堵状态分布函数（）表示为（）（）（）（）式中，为目标区域内路网上的任意一点的坐标。图 为交通拥堵状态分布函数在目标区域 内的变化规律。由该图可知，目标区域在右上角的区域拥堵系数最高。图 和图 分别为多应急救援车网络在目标区域内的初始位置和最优位置，其中星号代表车辆的初始位置，三角代表车辆的最优分布。每辆应急救援车辆的负责区域由不同颜色进行区分。图 交通拥堵状态分布函数 图 应急救援车的初始位置 图 多应急救援车最优位置及其 区域及其 区域 由图 仿真结果可知，在考虑交通拥堵情况下，每辆应急救援车的负责区域均有所不同。例如 号车所在位置的周围交通拥堵系数较高，则 号车负责的区域较小，进而有效保障该区域内的交通事故能够得到及时处理。号车的负责区域也明显大于 号车。这是因为 号车的负责区域内交通拥堵状态优于 号车的负责区域。图 为多应急救援车在目标区域内的最优分布规划，其中应急救援车辆的负责区域是根据当前车辆的优化位置（即三角标号位置）进行划分的。对比图 与图 可知，利用本文提出的分布规划算法，多应急救援车的分布位置以及负责区域都产生了不同程度变化。这一变化验证了应急救援车辆与负责区域之间的交替影响规律。更进一步地，关于该分布规划优化算法的量化分析可通过图 进行说明。图 多应急救援车网络的目标函数第 期左磊，等：基于覆盖控制的城市多应急救援车辆分布规划策略图 为多应急救援车在目标区域内的救援时间目标函数变化曲线，其中纵坐标为应急救援车到达目标区域内任意一点的整体时间，横坐标为应急救援车辆从初始位置收敛到最优分布所用的时间。由该结果可知，随着分布优化算法的实施，多应急救援车不断调整其最优分布位置，使其对目标区域的整体救援时间逐渐减少。此外，本文还在图 中将所提算法与传统的平均分布算法进行了对比，其中为平均分布规划算法，为本文所提的基于覆盖控制的分布规划算法。由该对比结果可知，本文所提算法充分考虑目标区域内的交通拥堵状态，使得应急救援车辆能够在更短的时间内对目标区域内任意一点的交通事故进行处理，整体救援时间缩短了。因此，上述仿真结果表明多应急救援车辆网络能够实现对目标区域的最优覆盖，验证了本文提出多应急救援车最优分布规划算法的有效性与可行性。结 论本文基于覆盖控制理论，考虑交通拥堵状况对城市应急救援车辆分布的影响，构建了面向最优应急救援时间的分布规划模型，并提出了多应急救援车在多事故发生情况下的分布规划策略。针对多个应急救援车在目标区域内的区域分配问题，利用 区域分配原则，以每辆车到任意一点的行驶时间为评价指标，提出了基于 区域分配原则的区域划分策略，使得目标区域内任意一点的交通事故，都能够在最短的时间内得到响应。相对于传统的车辆平均分配原则，本文所提的分配规划方法充分考虑了交通拥堵路况对分布规划策略的影响，可有效提高应急救援车辆对目标区域的覆盖效率，缩短救援时间。后续的研究将进一步在更复杂的交通路网上，进行未知路况的估计，分析未知路况下的城市多应急救援车辆分布规划方法。参考文献：方心怡，倪晓阳 城市道路交通应急救援体系研究 中国水运，（）：，（）：（），：杨兆升，高学英，孙迪 城市交通疏散救援的元胞自动机模型 交通运输工程学报，（）：，（）：（），（）：，：，（）：，方程炜，柴干，赵倩 道路交通救援点条件覆盖选址策略及评价 交通科技与经济，（）：，（）：（），（）：周愉峰，马祖军，王恪铭 应急物资储备库的可靠性 中位选址模型 管理评论，（）：，（）：（）毕娅，李文锋 基于约束的集合覆盖选址分配问题 上海交通大学学报，（）：西 北 工 业 大 学 学 报第 卷，（）：（），（）：吴艳华，王富章，李芳 铁路救援基地层级规划选址模型 交通运输工程学报，（）：，（）：（），：，：，：，：，：，（）：，（）：方磊，何建敏 应急系统优化选址的模型及其算法 系统工程学报，（）：，（）：（）杨金顺，孙洪运，李林波，等 公路网灾害应急救援点多目标选址模型及算法 同济大学学报，（）：，（）：，（）姜涛，朱金福 应急设施鲁棒优化选址模型及算法 交通运输工程学报，（）：，（）：（），（）：，（）：，（）：，（）：，：，（）：，：，：，（）：，（）：，第 期左磊，等：基于覆盖控制的城市多应急救援车辆分布规划策略，（）：，；，：，：，：；引用格式：左磊，孟铎，闫茂德，等 基于覆盖控制的城市多应急救援车辆分布规划策略 西北工业大学学报，（）：，（）：（）（：），