【www.zhangdahai.com--其他范文】
温惠英，蒋 晗，吴嘉彬，林译峰*
(华南理工大学土木与交通学院，广东 广州 510641)
新冠疫情的爆发使得感染患者骤增，救援隔离需求日渐增长，应急救援服务能力亟待加强。在救护车辆数量有限的情况下，如何提高患者的救援效率成为当今重要的研究热点。然而，随着机动车保有量不断攀升，道路交通负荷庞大，使救护车辆的出行时间延长[1]。相关研究表明，路径规划是影响车辆出行时间的关键要素[2，3]。合理规划应急救援路线，可有效控制疫情传播范围，保障社会稳定运行。近几十年，国内外学者对车辆路径规划问题开展了大量研究，并取得了丰富的实践成果。现有常用的路径规划算法主要包括Dijkstra[4]、蚁群算法[5，6]、遗传算法[7]等。另外，Haiyang Shi等人[8]利用基于模型的计算方法和基于知识的搜索方法优势，提出了一种在线智能调度方法。陈则辉等人[9]和段满珍[10]等人针对不确定性环境下的应急救援策略，提出了车辆路径选择模型。毛新华等人[11]考虑交通流时空演变的不确定性，建立了带有区间参数的机会约束规划模型。
虽然诸多学者在求解路径规划问题上取得了一定的成果，但仍存在以下不足：①多数文献着重研究地震、交通事故背景下的VRP问题，较少针对新冠患者的隔离运输开展研究；
②部分文献将路径规划简单视为静态路网下的路径决策，忽视信号控制、交通流时空演变等因素对路径选择的影响；
③现有主流方法将时变网络下的动态路径规划简单视为若干静态路径规划的叠加，鲜有考虑交通环境演变对路径规划的影响。
为弥补现有研究缺陷，本文提出一种与交通环境协同演变的救护车辆路径规划方法，为新冠患者的隔离运输提供路径决策支持。
2.1 问题分析
由于新冠疫情具有易传染、难预防且缺少专属特效药等特点，是公共卫生事件中较难处理的问题[12]。由此可见，新冠患者运输是典型的单源最短路径问题，而非VRP问题。然而，现有应急救援系统难以满足日益膨胀的新冠患者隔离需求，亟需进一步提升患者运输效率。此外，交通拥堵的频发使车辆行程时间较长，导致患者医疗时间滞后，易错过黄金治疗时间。如何在复杂多变的交通环境中缩短救援路径的行程时间，提高救护车辆出行效率，是当前疫情背景下的研究热点之一。
现有基于在线优化的动态路径规划方法本质是根据当前路网交通环境实时更新最短路径，所得路径是由多次静态优化的路径拼接而成[13]。尽管在线优化方法每次优化的路径在当前时刻可能是全局最优的，但其实际行驶轨迹远非最佳路径，其优化原理如图1所示。
图1(a)表示车辆基于拥堵区A的当前位置与范围规划行驶路径。图1(b)表示车辆沿优化路径绕行至原拥堵区A附近时，拥堵区A已移动演变为拥堵区B。此时，车辆根据拥堵区B的当前状态更新调整剩余优化路径。图1(c)表示原拥堵区B演变至拥堵区C，车辆根据拥堵区状态演变不断调整当前优化路径，导致多余的绕行。图1(d)表示车辆实际行驶轨迹与最佳路径之间的差异。因此，路径的实时最优并不等于全局最优。
图1 在线优化方法优化路径原理
2.2 协同优化方法基本思想
路径协同优化是考虑未来时段内交通环境演变对子路径优化的影响，使路径规划过程与交通环境同步演变，从而避免冗余的绕行路径或滞后的绕行决策。事实上，如何准确获取未来交通环境数据直接决定了路径协同规划方法可行性的核心问题。随着人工智能技术在交通流预测领域的应用，未来交通数据逐渐变得可预测。因此，路径协同优化的数据基础是交通流的预测数据，与实际交通数据存在一定的误差。
2.3 假设条件
根据城市路网交通运行特性与现实患者隔离运输状况，做出以下假设：
1) 救护车辆可实时获取路网交通流数据；
2) 救护车辆在某一路段的行驶速度具有随机性，受到路段交通流的扰动与约束，其正常行驶速度与该路段平均行驶速度大体一致，存在一定偏差；
3) 若路段设有应急车道，则救护车辆行驶速度最高可达所在路段设计速度；
4) 救护车辆通过信号控制交叉口时将产生行程延误，取值范围受交叉口交通流运行状态的影响，具有随机性；
5) 新冠患者位置短时间内保持不变。
2.4 优化目标
新冠患者的救护车辆出行时间由三部分组成，即救护车辆的去程时间、抵达目的地后的等待时间以及其返程时间。考虑到新冠患者治疗与隔离具有一定时效性，救援时间越短，越早控制患者病情，传染风险越小，应急救援服务效率越高，即在同等时间内可治疗或隔离的新冠患者越多。因此，本文以救护车辆出行时间最小为优化目标，计算公式为
(1)
式中，m为患者数。TR(i)为第i辆救护车辆的出行时间。T1(i)为救护车辆从医院前往患者i所在地的行程时间。T2为救护车辆抵达目的地后的等待时间。T3(i)为救护车辆从目的地返回医院或隔离点的行程时间。
T1(i)主要受车辆在路段的行程时间Tl(i)、交叉口通行延误Td(i)和快速路(或高速公路)应急车道的自由行驶速度增益所节省的行程时间Te(i)影响。故T1(i)可表示为
T1(i)=T1(i)+Td(i)-Te(i)
(2)
由于城市交通环境的时变特性，等待时间直接影响了车辆返程时所处的路网交通状态，进而影响救护车辆的路径选择。本文忽略新冠患者搭乘救护车辆所需时间的异质性，设等待时间T2为常数。
返程时间T3(i)的计算过程与T1(i)相似，即
(3)
式中，Tl′(i)为救护车辆在返程时的路段行程时间；
Td′(i)为救护车辆在返程时的交叉口行程延误；
Te′(i)为救护车辆在返程时通过快速路(或高速公路)应急车道所节省的行程时间。
3.1 IRSA基本原理
改进波纹扩散算法(IRSA，Improved Ripple Spreading Algorithm)是一种以时间单元为导向的全局遍历算法[14]，其核心技术是波纹接力赛。波纹接力赛的运行原理为：从起点开始向四周扩散波纹，被波纹激活的节点将进入等待状态(反映车辆在节点的排队等候状态)。当节点变为可通行时，将向四周继续扩散波纹进行接力。波纹接力过程不断迭代运行，直到波纹首次抵达扩散边界或目的点，并进入等待状态。当终点被波纹激活时，将回溯首个抵达终点的波纹遍历各节点的顺序，从而形成完整链路，确定起点到各目标节点的最优路径，如图2所示。
波纹接力赛的开始、运行过程与结束均由节点的状态变换过程主导。每个节点有4种状态，即未激活、激活、等待、死亡。如图2(a)所示，波纹由起点向四周扩散。当波纹到达邻近节点后激活邻近节点，并向四周传播新的波纹，如图2(b)和图2(c)。若某一节点的所有邻近节点均已被激活，则该节点进入死亡状态，不再被任何波纹激活。此外，当波纹到达最大扩散边界或终点时停止扩散，并通过回溯波纹遍历节点的顺序推导最优路径，如图2(d)所示。
图2 波纹接力赛扩散示意图
IRSA的运行特性如下：①具有多个终点且设有最大扩散范围；
②波纹抵达终点后不会立即结束波纹接力赛，而是进入等待状态，等待期间路网交通环境将持续演变；
③波纹抵达终点等待一段时间后将置换起终点位置，即由终点扩散波纹至起点，形成闭环回路并结束波纹接力赛；
④波纹在通过节点时进入等待状态，产生一定的行程延误，而通过应急车道时其扩散速度与该车道自由流行驶速度一致。
3.2 算法步骤
假设N个节点随机分布城市路网中，令SR(i)表示节点i的波纹状态。起始节点编号为1，终点节点编号为Mi。l(i，j)为路段(i，j)的长度。tc为路网变化时间间隔。SR(i)=0，1，2，3分别代表节点i的波纹处于未激活、等待、激活、死亡状态。It+k(i，j)表示在预测时间t+k时节点i与节点j之间的连通状态，1表示连通，0表示不连通。当It+k(i，j)=1时，波纹方可从节点i向节点j传播。Vt+k(i，j)表示在预测时间单元t+k内波纹i由节点i传播节点j的扩散速度，与路段平均行驶速度一致。IRSA的算法流程如图3所示。
IRSA算法详细步骤为：
图3 IRSA算法流程图
Step 1：激活起点，波纹由起点向相邻节点i扩散，令k=1，SR(1)=2；
Step 2：当波纹抵达节点i时，若SR(i)=0且It+k(i，j)=1，则令SR(i)=1，并转入Step 3；
Step 3：判断节点i是否可通行，若是则激活节点i的波纹，令SR(i)=2。更新波纹半径Rt+k(i，j)，令Rt+k(i，j)=Rt+k-1(i，j)+Vt+k(i，j)×tc；
Step 4：当波纹i到达节点j时，节点j激发的波纹j会继承波纹i的溢出波纹半径和行程时间属性TR(i)，SR(j)=2。设节点j的邻近节点为p，则令Rt+k(j，p)=Rt+k(i，j)-l(i，j)。TR(i)用于记录传递波纹i所需的累积用时；
Step 5：判断节点i的所有邻近节点是否均已被激活。若是，则令SR(i)=3；
Step 6：判断波纹是否抵达终点，若是，则转至Step 7，否则跳转Step 2，令k=k+1。
Step 7：波纹在终点等待返程，将等待时间T2计入波纹行程时间属性TR(i)，当终点被激活时开始反向扩散波纹，反向传播过程与Step1至Step 6同理，令SR(Mi)=2；
Step 8：当波纹i返回起点时，根据波纹携带的行程时间属性，得到总行程时间的估计值。
4.1 仿真设计
为验证算法性能，仿真提取南京市中心城区路网拓扑结构，包括建邺区、鼓楼区、秦淮区、雨花台区部分区域，并以区域内的江苏省人民医院为起点，随机生成5个患者位置作为终点Mi，i≤m，m=5。
根据路网道路等级设置城市快速路，车辆在快速路的平均行驶速度大于普通路段。路网中各路段平均行驶速度服从正态分布，普通路段速度vij取值为[0，60]，快速路段取值为[30，80]，单位为km/h。由于救护车辆到达交叉口时的交通环境具有随机性，在此假设救护车辆通过交叉口时的延误为随机取值，取值范围为[1，3]，单位为min。设救护车辆在患者处的等待时长T2=15 min。
信号控制、交通流动态演变、交通事故等不确定因素对路网交通环境的影响通常表现为交通拥堵区域的动态演变。由于现有速度预测算法难以达到100%精确，且预测误差随着时间跨度不断累积增大。则路段平均行驶预测速度为
(4)
4.2 结果分析
Dijkstra算法是最为经典的最短路算法，在路径规划问题求解中得到了广泛应用。本文将Dijkstra算法作为在线优化方法的基准算法，并通过Python编程进行20次随机测试。设σ=0.1、γ=0.1，路径优化结果如图4所示。两种方法在路径选择上存在明显的差异，且协同优化方法优化路径的长度与行程时间均比在线优化方法短。在行驶距离相近的情况下，协同优化方法更倾向于选择平均行驶速度较高的快速路，使救援路径的总出行时间更小。
图5为两种路径优化方法在σ=0.1、γ=0.1条件下的出行时间折线图。在路网行驶速度预测误差较大的情况下，协同优化方法的路径行程时间始终小于在线优化方法，具有较强的行程时间稳定性，可适应复杂多变的现实道路交通环境。
图4 两种方法路径优化结果(σ=0.1、γ=0.1)
为验证两种方法在不同预测误差条件下的优化性能，选取不同误差组合进行仿真，得到平均出行时间如表1所示。协同优化方法优化路径的出行时间比在线优化方法小23.92%～30.51%。
图5 两种方法的出行时间折线图
表1 不同预测误差下的平均出行时间(min)
协同优化方法和在线优化方法在不同预测误差下的出行时间85分位数如图6所示。协同优化方法在不同预测误差条件下的出行时间85分位数均小于在线优化方法，表明协同优化方法具有更强的时间可靠性。
造成两种方法优化性能的主要原因是：协同优化方法是一种以时间单元为导向的全局遍历路径优化算法，其波纹接力赛允许在拥堵节点或路段处等待，避免错误的绕行决策。同时，路径协同优化方法考虑了未来交通环境演变对路径优化的影响，通过判别交通拥堵演变趋势，从而选择提前避开拥堵区域的出行路径，进而缩短路径行程时间。然而，传统算法很难克服动态路网交通环境演变对路径规划的扰动作用，忽略路径规划对交通拥堵演变趋势的依赖性，往往在车辆遇到交通拥堵时才重新调整剩余路径，易产生错误的绕行决策，进而延长路径出行时间。
图6 不同预测误差下的出行时间85分位数
针对时变路网下的新冠患者救护车辆路径规划问题，本文结合新冠患者的传染性及其运输的时效性，以救护车辆出行时间最小为目标函数建立模型，提出了一种考虑未来交通环境演变特性的车辆路径协同优化方法，并设计了改进波纹扩散算法进行求解。同时，本文以南京市现实路网为基础进行了仿真对比实验。结果表明，本文协同优化方法的优化性能比现有在线优化方法更佳，可有效缩短救护车辆出行时间，提高救援效率，从而解决时变路网下的救护车辆路径优化问题。
猜你喜欢波纹路网车辆基于NACA0030的波纹状翼型气动特性探索北京航空航天大学学报(2021年6期)2021-07-20打着“飞的”去上班 城市空中交通路网还有多远环球飞行(2018年7期)2018-06-27车辆小太阳画报(2018年3期)2018-05-14省际路网联动机制的锦囊妙计中国公路(2017年11期)2017-07-31首都路网 不堪其重——2016年重大节假日高速公路免通期的北京路网运行状况中国公路(2017年7期)2017-07-24路网标志该如何指路?中国公路(2017年10期)2017-07-21为什么水面波纹荡漾学与玩(2017年5期)2017-02-16冬天路滑 远离车辆阅读与作文（小学低年级版）(2016年12期)2016-12-22提高车辆响应的转向辅助控制系统汽车文摘(2015年11期)2015-12-02思文苑·经典美文(2008年5期)2008-09-18本文来源：http://www.zhangdahai.com/shiyongfanwen/qitafanwen/2023/0918/656189.html
