基于改進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.