基于改進CCRP的區(qū)域性交通擁堵疏導算法

吳正言 付海軍

[摘? ? 要] 為了提高交通疏導方案的有效性，在對通行能力約束的路徑規(guī)劃（CCRP）算法改進的基礎(chǔ)上，提出了一種區(qū)域性交通擁堵的疏導算法。該算法的特色在于：引入懲罰函數(shù)，以提高疏導路徑的通行質(zhì)量并減少擁堵風險;將突發(fā)交通擁堵點作為疏散原點動態(tài)納入交通疏導過程，以增加對突發(fā)交通擁堵點的疏導能力。實證表明，所提出的算法可將疏導交通流分配到擁堵危險較低且通行質(zhì)量較好的路徑上，并提高了對突發(fā)交通擁堵的應(yīng)變能力。

[關(guān)鍵詞] 交通運輸系統(tǒng)工程;交通疏導;區(qū)域性交通擁堵

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

[中圖分類號] TP312? ? [文獻標識碼]? A? ? ? [文章編號]? 1673 - 0194（2019）21- 0167- 03

0? ? ? 引? ? 言

為了預(yù)防和減輕大范圍交通擁堵的不良后果，需要在鑒別出區(qū)域性交通擁堵初步形成有利時機，及時有效地采取交通疏導措施，是避免城市大范圍交通擁堵的有效措施。區(qū)域性交通擁堵疏導方法的核心是疏導路徑規(guī)劃和流量分配。有效的區(qū)域性交通擁堵疏導方法，不僅要降低疏導路徑產(chǎn)生交通擁堵的風險，而且要使疏導算法的計算代價小，滿足實時性的要求。目前，路徑規(guī)劃的核心思想主要是最短路算法，而交通分配主要采用均衡配流[1-2]，運用系統(tǒng)最優(yōu)[3]、系統(tǒng)最優(yōu)與用戶最優(yōu)的協(xié)調(diào)[4]、以及最小費用最大流[5]等方法，所規(guī)劃的路徑無法保證繞過交通擁堵區(qū)域，而且算法的計算代價高，實時性差，雖采用啟發(fā)式算法，但由于維數(shù)高、求解困難[6]，難以滿足交通疏導的要求。具有通行能力約束的路徑規(guī)劃方法（Capacity Constrained Route Planner，CCRP）[7-8]是最著名的非均衡配流啟發(fā)式算法，實時性好，能生成近似最優(yōu)的分配方案。但該方法缺少對路網(wǎng)通行質(zhì)量和對突發(fā)交通擁堵點疏散的考慮，致使所生成的交通組織方案的適應(yīng)性差。本文以CCRP算法為基礎(chǔ)，并考慮路網(wǎng)的通行質(zhì)量因素，將疏導交通流分配到通行質(zhì)量高的最短路徑上，并增加了對突發(fā)交通擁堵點的處置能力，最后進行實例驗證。

1? ? ? 區(qū)域交通擁堵疏導算法描述

區(qū)域路網(wǎng)擁堵交通疏導路網(wǎng)中交叉口和路段的通行能力具有非負整數(shù)約束，路段具有非負的行程時間，且其行程時間包括交叉口的延誤。疏導起點為區(qū)域交通擁堵點，目的地為擁堵區(qū)域周圍的暢通交叉口，假定各起點需疏導的車輛數(shù)為已知，并假設(shè)可實時接收到路網(wǎng)的狀況信息，包括路網(wǎng)中的擁堵交叉口、路段以及突發(fā)交通擁堵點等。由于交通擁堵的疏導路徑處于飽和狀態(tài)，交通流基本不超車，因此，假定路段的交通量具有先入先出的特性。區(qū)域性交通擁堵疏導算法輸出擁堵風險較低且疏導時間最短的疏導方案，主要包括一系列由疏導原點到目的地的路徑，以及路徑交通量的時間行程安排，其中路徑交通量的時間行程安排要遵守路徑中交叉口和路段的通行能力約束。區(qū)域交通擁堵疏導算法的目標是，在確保疏導路徑交通擁堵風險較小的前提下，使疏導的總時間最小。

2? ? ? 區(qū)域性交通擁堵疏導算法

2.1? ?輸入變量的確定

（1）路網(wǎng)G（N，E），N表示交叉口集合，E表示路段集合。

任意交叉口n∈N，具有兩個屬性：通行能力NC（n）和需疏導交通量NO（n）。

任意路段e∈E，具有兩個屬性：通行能力EC（e）和當量行程時間Tt（e）。所謂路段的當量行程時間是為了考慮交通疏導的擁堵風險性因素和通行質(zhì)量因素，在實際路段的行程時間中引進懲罰函數(shù)所得的行程時間，即

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

式中，CTt（e）為路段e的短時預(yù)測行程時間，M為懲罰因子，是充分大的數(shù)。δ為懲罰系數(shù)，δ∈[0，1]。δ的取值應(yīng)根據(jù)路網(wǎng)的實際情況合理確定：如果路段e通行質(zhì)量較好，則δ的取值接近于0;反之，如果e位于擁堵區(qū)域或通行質(zhì)量較差，則δ的取值接近于1。

（2）疏導原點集合S，S？哿N。

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

2.2? ?算法核心步驟

CCRP算法主要運用迭代的方法。在每一次迭代中，首先搜索疏導原點集合到疏導目的地集合的行程時間最短路徑R。其次，計算路徑R的實際分配交通量，該交通量受路徑的剩余通行能力與原點剩余交通量的約束。再次，路徑的交叉口和路段在相應(yīng)的時刻為實際分配的交通量保留所需的備用通行能力。如此循環(huán)往復(fù)，直到所有的疏導交通量到達目的地為止。區(qū)域交通擁堵疏導算法應(yīng)使疏導交通流的擁堵風險降至最低，而CCRP算法沒有考慮路網(wǎng)的疏導擁堵風險性因素和道路的通行質(zhì)量問題，并缺乏對突發(fā)交通擁堵的疏導能力。

為了增強區(qū)域交通擁堵疏導算法的可行性和適應(yīng)性，本論文對CCRP算法進行了改進，在引入懲罰函數(shù)規(guī)避擁堵和通行質(zhì)量差區(qū)域的前提下，增加對突發(fā)性擁堵的疏導能力，進而提出區(qū)域性交通擁堵疏導算法。核心步驟如下：

（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中路段及交叉口在對應(yīng)時間點的剩余通行能力，如果AEC（e■，ti）=0或ANC（ni+1，ti+Tt（e■）=0，則表示路段或交叉口的交通量已達到其可能通行能力，后面分配的交通量必須多等待1個時間單位，因此，對應(yīng)路段的行程時間自動增加1個時間單位。

（4）如果由于突發(fā)的意外情況，致使路徑R上點j發(fā)生嚴重的交通擁堵，若j∈e（nini+1），則增設(shè)j為路網(wǎng)虛擬交叉口，若j∈N，則j為路網(wǎng)的實際交叉口。為疏導此交叉口j的擁堵交通量，則將交叉口j并入疏導原點集，作為臨時疏導原點：

S=SUj③

（5）將疏散完畢的交叉口從疏導原點集中去除。

（6）反復(fù)執(zhí)行（1）到（5），直到疏導原點集S中的交通量疏導完畢為止。

3? ? ? 算法驗證

為了驗證所提出算法的有效性，采用CCRP原文獻中的局部路網(wǎng)作為研究對象。該路網(wǎng)包含了14個節(jié)點，抽象為如圖1所示的節(jié)點圖，其中的圓形節(jié)點對應(yīng)于路網(wǎng)的交叉口，節(jié)點間的連邊對應(yīng)于路網(wǎng)中的路段。疏散原點集合包括節(jié)點1和節(jié)點2，疏散目的地集合包括節(jié)點13和節(jié)點14，并假定疏散目的地節(jié)點的容量沒有限制。為了驗證算法所生成疏散路徑的安全性和必要的應(yīng)變性，假設(shè)節(jié)點3和節(jié)點9附近為擁堵區(qū)域，節(jié)點8為突發(fā)交通擁堵點。

按區(qū)域性交通擁堵疏導算法產(chǎn)生的疏導方案如表1所示。

從中可以看出，該算法生成的路徑充分考慮通行質(zhì)量和可行性因素，可以繞過擁堵交叉口3和9區(qū)域，可以降低疏導路徑的疏導擁堵風險性，生成方案的可行性較好。同時，將突發(fā)的擁堵點8視為虛擬的疏導原點，并對其向疏導目的地進行路徑優(yōu)化和交通量的分配，具有必要的應(yīng)變性和調(diào)整能力?？梢?，本論文所提出的區(qū)域性交通擁堵疏導算法可彌補CCRP算法在疏導可行性上的不足，并增強了對突發(fā)擁堵點的疏導處置能力。

4? ? ? 結(jié)? ? 語

針對地震應(yīng)急疏散的特殊性，在CCRP算法的基礎(chǔ)上，考慮了疏散路徑的安通行質(zhì)量要求，并增加了對突發(fā)交通擁堵的自動優(yōu)化生成疏散路徑的能力，提出了地震疏散路徑規(guī)劃算法。實證分析表明，EERP算法所規(guī)劃的路徑具有安全性和可通行性好的特點，且對突發(fā)交通擁堵具有必要的應(yīng)變性。

主要參考文獻

[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]陳岳明，蕭德云. 基于動態(tài)交通分配的路網(wǎng)應(yīng)急疏散模型[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]李清泉，李秋萍，方志祥. 一種基于時空擁擠度的應(yīng)急疏散路徑優(yōu)化方法[J]. 測繪學報， 2011（4）： 517-523.