吳正言 付海軍

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

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

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

[中圖分類號(hào)] TP312? ? [文獻(xiàn)標(biāo)識(shí)碼]? A? ? ? [文章編號(hào)]? 1673 - 0194（2019）21- 0167- 03

0? ? ? 引? ? 言

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

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

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

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

2.1? ?輸入變量的確定

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

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

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

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

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

（2）疏導(dǎo)原點(diǎn)集合S，S？哿N。

（3）疏導(dǎo)目的地集合D，D？哿N。

2.2? ?算法核心步驟

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

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

（1）基于路段當(dāng)量行程時(shí)間，尋找原點(diǎn)集S到終點(diǎn)集D的最短路徑R

（2）計(jì)算路徑的分配交通量

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

式中，NO表示疏導(dǎo)原點(diǎn)的待疏導(dǎo)交通量，RI S表示路徑R的原點(diǎn)，i∈{1，2，…，k-1}。

（3）計(jì)算路徑R中路段及交叉口在對(duì)應(yīng)時(shí)間點(diǎn)的剩余通行能力，如果AEC（e■，ti）=0或ANC（ni+1，ti+Tt（e■）=0，則表示路段或交叉口的交通量已達(dá)到其可能通行能力，后面分配的交通量必須多等待1個(gè)時(shí)間單位，因此，對(duì)應(yīng)路段的行程時(shí)間自動(dòng)增加1個(gè)時(shí)間單位。

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

S=SUj③

（5）將疏散完畢的交叉口從疏導(dǎo)原點(diǎn)集中去除。

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

3? ? ? 算法驗(yàn)證

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

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

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

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

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

主要參考文獻(xiàn)

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