基于改进CCRP的区域性交通拥堵疏导算法

吴正言 付海军

[摘    要] 为了提高交通疏导方案的有效性，在对通行能力约束的路径规划（CCRP）算法改进的基础上，提出了一种区域性交通拥堵的疏导算法。该算法的特色在于：引入惩罚函数，以提高疏导路径的通行质量并减少拥堵风险;将突发交通拥堵点作为疏散原点动态纳入交通疏导过程，以增加对突发交通拥堵点的疏导能力。实证表明，所提出的算法可将疏导交通流分配到拥堵危险较低且通行质量较好的路径上，并提高了对突发交通拥堵的应变能力。

[关键词] 交通运输系统工程;交通疏导;区域性交通拥堵

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2019. 21. 066

[中图分类号] TP312    [文献标识码]  A      [文章编号]  1673 - 0194（2019）21- 0167- 03

0      引    言

为了预防和减轻大范围交通拥堵的不良后果，需要在鉴别出区域性交通拥堵初步形成有利时机，及时有效地采取交通疏导措施，是避免城市大范围交通拥堵的有效措施。区域性交通拥堵疏导方法的核心是疏导路径规划和流量分配。有效的区域性交通拥堵疏导方法，不仅要降低疏导路径产生交通拥堵的风险，而且要使疏导算法的计算代价小，满足实时性的要求。目前，路径规划的核心思想主要是最短路算法，而交通分配主要采用均衡配流[1-2]，运用系统最优[3]、系统最优与用户最优的协调[4]、以及最小费用最大流[5]等方法，所规划的路径无法保证绕过交通拥堵区域，而且算法的计算代价高，实时性差，虽采用启发式算法，但由于维数高、求解困难[6]，难以满足交通疏导的要求。具有通行能力约束的路径规划方法（Capacity Constrained Route Planner，CCRP）[7-8]是最著名的非均衡配流启发式算法，实时性好，能生成近似最优的分配方案。但该方法缺少对路网通行质量和对突发交通拥堵点疏散的考虑，致使所生成的交通组织方案的适应性差。本文以CCRP算法为基础，并考虑路网的通行质量因素，将疏导交通流分配到通行质量高的最短路径上，并增加了对突发交通拥堵点的处置能力，最后进行实例验证。

1      区域交通拥堵疏导算法描述

区域路网拥堵交通疏导路网中交叉口和路段的通行能力具有非负整数约束，路段具有非负的行程时间，且其行程时间包括交叉口的延误。疏导起点为区域交通拥堵点，目的地为拥堵区域周围的畅通交叉口，假定各起点需疏导的车辆数为已知，并假设可实时接收到路网的状况信息，包括路网中的拥堵交叉口、路段以及突发交通拥堵点等。由于交通拥堵的疏导路径处于饱和状态，交通流基本不超车，因此，假定路段的交通量具有先入先出的特性。區域性交通拥堵疏导算法输出拥堵风险较低且疏导时间最短的疏导方案，主要包括一系列由疏导原点到目的地的路径，以及路径交通量的时间行程安排，其中路径交通量的时间行程安排要遵守路径中交叉口和路段的通行能力约束。区域交通拥堵疏导算法的目标是，在确保疏导路径交通拥堵风险较小的前提下，使疏导的总时间最小。

2      区域性交通拥堵疏导算法

2.1   输入变量的确定

（1）路网G（N，E），N表示交叉口集合，E表示路段集合。

任意交叉口n∈N，具有两个属性：通行能力NC（n）和需疏导交通量NO（n）。

任意路段e∈E，具有两个属性：通行能力EC（e）和当量行程时间Tt（e）。所谓路段的当量行程时间是为了考虑交通疏导的拥堵风险性因素和通行质量因素，在实际路段的行程时间中引进惩罚函数所得的行程时间，即

Tt（e）=CTt（e）+δ·M①

式中，CTt（e）为路段e的短时预测行程时间，M为惩罚因子，是充分大的数。δ为惩罚系数，δ∈[0，1]。δ的取值应根据路网的实际情况合理确定：如果路段e通行质量较好，则δ的取值接近于0;反之，如果e位于拥堵区域或通行质量较差，则δ的取值接近于1。

（2）疏导原点集合S，S？哿N。

（3）疏导目的地集合D，D？哿N。

2.2   算法核心步骤

CCRP算法主要运用迭代的方法。在每一次迭代中，首先搜索疏导原点集合到疏导目的地集合的行程时间最短路径R。其次，计算路径R的实际分配交通量，该交通量受路径的剩余通行能力与原点剩余交通量的约束。再次，路径的交叉口和路段在相应的时刻为实际分配的交通量保留所需的备用通行能力。如此循环往复，直到所有的疏导交通量到达目的地为止。区域交通拥堵疏导算法应使疏导交通流的拥堵风险降至最低，而CCRP算法没有考虑路网的疏导拥堵风险性因素和道路的通行质量问题，并缺乏对突发交通拥堵的疏导能力。

为了增强区域交通拥堵疏导算法的可行性和适应性，本论文对CCRP算法进行了改进，在引入惩罚函数规避拥堵和通行质量差区域的前提下，增加对突发性拥堵的疏导能力，进而提出区域性交通拥堵疏导算法。核心步骤如下：

（1）基于路段当量行程时间，寻找原点集S到终点集D的最短路径R

（2）计算路径的分配交通量

flow=min（NO（RI S），AEC（e■，ti），ANC（ni+1，ti+Tt（e■））②

式中，NO表示疏导原点的待疏导交通量，RI S表示路径R的原点，i∈{1，2，…，k-1}。

（3）计算路径R中路段及交叉口在对应时间点的剩余通行能力，如果AEC（e■，ti）=0或ANC（ni+1，ti+Tt（e■）=0，则表示路段或交叉口的交通量已达到其可能通行能力，后面分配的交通量必须多等待1个时间单位，因此，对应路段的行程时间自动增加1个时间单位。

（4）如果由于突发的意外情况，致使路径R上点j发生严重的交通拥堵，若j∈e（nini+1），则增设j为路网虚拟交叉口，若j∈N，则j为路网的实际交叉口。为疏导此交叉口j的拥堵交通量，则将交叉口j并入疏导原点集，作为临时疏导原点：

S=SUj③

（5）将疏散完毕的交叉口从疏导原点集中去除。

（6）反复执行（1）到（5），直到疏导原点集S中的交通量疏导完毕为止。

3      算法验证

为了验证所提出算法的有效性，采用CCRP原文献中的局部路网作为研究对象。该路网包含了14个节点，抽象为如图1所示的节点图，其中的圆形节点对应于路网的交叉口，节点间的连边对应于路网中的路段。疏散原点集合包括节点1和节点2，疏散目的地集合包括节点13和节点14，并假定疏散目的地节点的容量没有限制。为了验证算法所生成疏散路径的安全性和必要的应变性，假设节点3和节点9附近为拥堵区域，节点8为突发交通拥堵点。

按区域性交通拥堵疏导算法产生的疏导方案如表1所示。

从中可以看出，该算法生成的路径充分考虑通行质量和可行性因素，可以绕过拥堵交叉口3和9区域，可以降低疏导路径的疏导拥堵风险性，生成方案的可行性较好。同时，将突发的拥堵点8视为虚拟的疏导原点，并对其向疏导目的地进行路径优化和交通量的分配，具有必要的应变性和调整能力。可见，本论文所提出的区域性交通拥堵疏导算法可弥补CCRP算法在疏导可行性上的不足，并增强了对突发拥堵点的疏导处置能力。

4      结    语

针对地震应急疏散的特殊性，在CCRP算法的基础上，考虑了疏散路径的安通行质量要求，并增加了对突发交通拥堵的自动优化生成疏散路径的能力，提出了地震疏散路径规划算法。实证分析表明，EERP算法所规划的路径具有安全性和可通行性好的特点，且对突发交通拥堵具有必要的应变性。

主要参考文献

[1]Elba Urbina，Brian Wolshon. National Review of Hurricane Evacuation Plans and Policies：A Comparison and Contrast of State Practices[J]. Transportation Research Part A：Policy and Practice，2003，37（3）：257-275.

[2]L D Han. Global Optimization of Emergency Evacuation Assignments[J].  Interfaces，2006，36（6）： 502-513.

[3]LIU Ying，LAI Xiao rong，CHANG Gang-Len.Two-Level Integrated Optimization System for Planning of Emergency Evacuation[J]. Journal of Transportation Engineering， 2006，132（10）：800-807.

[4]Fang Yuan.  Evacuation Modeling and Operations Using Dynamic Traffic Assignment and Most Desirable Destination Approaches[C]//TRB 2005 Annual Meeting，2005，1-21.

[5]陳岳明，萧德云. 基于动态交通分配的路网应急疏散模型[J]. 清华大学学报：自然科学版，2009，49（8）： 1102-1105.

[6]HENRY X. Liu，HE XiaoZheng， BAN Xuegang （Jeff）.  A Cell-based Many-to-One Dynamic System Optimal Model and Its Heuristic Solution Method for Emergency Evacuation[C]//The 86th TRB Annual Meeting，2006，1-19.

[7]R. B. Yang Wen， Moshe Ben-Akiva，Scott Smith. On-line Deployment of Dynamic Traffic Assignment： Evaluation and Lessons[C]//The 87th Annual Meeting of the Transportation Research Board， 2007，1-23.

[8]李清泉，李秋萍，方志祥. 一种基于时空拥挤度的应急疏散路径优化方法[J]. 测绘学报， 2011（4）： 517-523.