事故條件下高速公路可變情報板選址研究*

韓姍姍 鐘石泉 朱 寧

(天津大學(xué)管理與經(jīng)濟(jì)學(xué)部 天津 300072)

0 引 言

隨著汽車保有量和交通需求的不斷增長，各種交通問題也日益嚴(yán)峻。中國國家統(tǒng)計局年鑒顯示[1]，2016年，中國共接報交通事故864.3萬起，涉及人員傷亡的道路交通事故212 864起，造成63 093人死亡、226 430人受傷，直接財產(chǎn)損失高達(dá)12.1億元。交通事故發(fā)生的影響因素眾多，嚴(yán)重影響出行者的出行效率。在發(fā)生交通事故后，如何正確引導(dǎo)出行者駕駛行為、從而緩解由事故造成的交通系統(tǒng)延遲[2-3]是一項重要的研究內(nèi)容。建立高效的高速公路和城市道路管理系統(tǒng)則能更好地滿足出行者需求，緩解交通事故影響。高級出行者信息系統(tǒng)(advanced traveler information system， ATIS)在這一過程中扮演著重要的作用。

可變情報板(variable message sign，VMS)，也被稱為可變情報板 (changeable message sign，CMS)、電子信息版(electric message sign，EMS)、動態(tài)信息板(dynamic message sign，DMS)，是一種常見的ATIS形式。它是設(shè)置在城市交通網(wǎng)中的重要地點的可變信息標(biāo)志，能夠向駕駛員提供道理交通狀況信息，從而誘導(dǎo)車輛采取合適的車速或推薦行駛路線，促使駕駛員選擇最佳路線。對于交通網(wǎng)絡(luò)而言，其設(shè)置的目標(biāo)是使總體的通行能力最大化，提高系統(tǒng)效率。

VMS按信息內(nèi)容的形式可以分為文字式、圖形式和圖形文字混合式3種；按作用時效(長期性使用還是臨時性使用)則分為固定式VMS和移動式VMS2類；常用的固定式VMS則可以按形狀分為門架式(A-VMS)和懸臂式(F-VMS)兩類，見圖1。研究表明[4]，不同類型、不同技術(shù)的VMS在運行特性、復(fù)雜程度和顯示能力方面是不同的。

圖1 2種可變情報板Fig.1 Gantry and cantilever mounted VMS

VMS的選址問題，涉及到交通路網(wǎng)、VMS選址、VMS展示信息及司機(jī)反應(yīng)等多個主體，是一個十分復(fù)雜問題。然而在很多情況下，由于人力、物力等資源限制，VMS的安裝數(shù)量受到預(yù)算限制，選址也沒有系統(tǒng)性的方法。因此，對VMS選址優(yōu)化問題的研究具有重要的現(xiàn)實意義。本文首先回顧了VMS選址領(lǐng)域的研究成果，針對現(xiàn)有研究中的不足提出了新的VMS選址模型，建立了一個0-1混合整數(shù)規(guī)劃模型，應(yīng)用Benders分解算法進(jìn)行求解，最后以Nguyen-Dupuis和Sioux-Falls路網(wǎng)為例驗證了模型和算法的有效性。

1 文獻(xiàn)綜述

1.1 可變情報板選址問題研究

VMS作為ATIS的重要形式，在減少事故和旅行時間[5-6]、緩解交通擁堵[7]、提高路網(wǎng)性能、誘導(dǎo)司機(jī)駕駛行為[8]等方面都有著重要作用。VMS的影響主要是通過向司機(jī)展示相關(guān)信息來完成的，而司機(jī)接受VMS信息后的重要反應(yīng)指標(biāo)之一就是服從率。關(guān)于VMS展示信息的內(nèi)容、類型和位置對于司機(jī)的影響，眾多學(xué)者給出了相關(guān)研究，包括駕駛過程中的決策影響因素[10]、風(fēng)險影響因素[11]的研究，以及可變情報板展示信息對司機(jī)的影響[12-13]、對司機(jī)服從率的影響[14]等。然而這一部分內(nèi)容在VMS選址優(yōu)化問題中的應(yīng)用卻相對較少。

Li等[15]提出，不恰當(dāng)?shù)氖褂肰MS可能會使交通條件更加惡化。Li和Gan等[15-16]基于網(wǎng)絡(luò)均衡模型對VMS選址問題進(jìn)行了探討。在方法上，Gan等[16]建立了一個雙層規(guī)劃模型，其貢獻(xiàn)是考慮了VMS和交通流網(wǎng)絡(luò)分布之間的相互作用；Li等[15]建立了一個混合整數(shù)非線性規(guī)劃模型，求解在給定預(yù)算下，使得系統(tǒng)總旅行時間最優(yōu)的VMS選址和展示信息方案。然而他們并沒有考慮VMS在事故場景下的特殊意義，沒有將事故處理納入VMS選址的影響條件中。

Abbas和McCoy[17]最早開始研究事故條件下VMS的選址問題，給出了該問題的分析框架；Fu等[18]進(jìn)一步擴(kuò)展了Abbas等提出的優(yōu)化模型，在其基礎(chǔ)上進(jìn)一步考慮了單獨路段上的事故率，使用Logit選擇模型刻畫司機(jī)面對VMS提供事故信息時的路徑變換行為，評估了在多時段不同交通分配方式下的VMS收益；Chiu和Huynh[19]則通過考慮在事故條件下受影響用戶的長期期望成本，來確定VMS的安裝數(shù)量和位置。模型假定事故的發(fā)生在空間和時間上都遵循泊松分布，采用DynaSmart-P仿真工具模擬VMS對司機(jī)路線選擇上的影響，將VMS選址優(yōu)化問題模擬為1個有補償?shù)碾S機(jī)整數(shù)規(guī)劃問題(stochastic program with recourse，SPR)。Huynh等[19]在固定式VMS的研究基礎(chǔ)上，進(jìn)一步考慮了在事故條件下，如何放置便攜式VMS能最小化事故對交通網(wǎng)絡(luò)的影響。以上研究雖然考慮到了事故場景，但對VMS本身特性挖掘不夠，例如，沒有考慮到VMS作用的有效路段、不同司機(jī)在不同位置接收VMS信息的效果(收益)也不同的等等。

1.2 整數(shù)規(guī)劃在交通領(lǐng)域的應(yīng)用

整數(shù)規(guī)劃是運籌學(xué)的一個重要分支，在管理、金融、交通、物流等領(lǐng)域都有廣泛的應(yīng)用。混合整數(shù)規(guī)劃指部分決策變量限制為整數(shù)的整數(shù)規(guī)劃問題，是整數(shù)規(guī)劃的一種。由于交通領(lǐng)域選址、分配、物流優(yōu)化等問題的特性，整數(shù)規(guī)劃應(yīng)用在許多交通領(lǐng)域問題中。例如，供應(yīng)鏈網(wǎng)絡(luò)設(shè)計[20]，設(shè)施選址問題[21]，路由和調(diào)度問題[22]，等等。整數(shù)規(guī)劃模型的解法包括精確算法和啟發(fā)式算法等。Branch and Cut，Benders分解[23]和它的改進(jìn)形式[24]經(jīng)常被用來解大規(guī)模混合整數(shù)規(guī)劃問題。另一方面，啟發(fā)式算法如遺傳算法[25]、蟻群算法[26]等也常常被用來求解大規(guī)模問題。

1.3 研究思路

綜上所述，關(guān)于VMS布設(shè)問題的研究還存在以下問題：①關(guān)于VMS選址優(yōu)化問題的研究相對較少；②事故場景作為VMS使用的主要場景之一，考慮其影響因素的研究也相對較少；③大部分研究對司機(jī)面對VMS信息時的行為刻畫的不夠，有些甚至直接假定司機(jī)完全接受VMS信息。在實際當(dāng)中，不同位置、不同內(nèi)容的信息對司機(jī)造成的影響也是不同的。

針對以上問題，本文所建立的模型考慮了不同的可變情報板信息對不同用戶行為的影響。除此之外，還考慮了高速公路網(wǎng)絡(luò)中同時發(fā)生的多事故因素，將事故條件下高速公路可變情報板選址問題處理成一個大規(guī)模混合整數(shù)規(guī)劃模型，以可變情報板安裝成本最小和事故處理收益最大為目標(biāo)求解可變情報板的最優(yōu)選址方案，并設(shè)計了具有高效率和高精確度的算法完成了對不同規(guī)模的算例的求解。

2 模型

2.1 模型假設(shè)

根據(jù)VMS的作用可知，VMS的合理放置地點應(yīng)該能夠使VMS能更好地處理事故信息。當(dāng)事故發(fā)生時，通過VMS的信息傳播作用，相關(guān)司機(jī)能夠及時收到信息并做出決策，從而緩解交通擁堵。本文基于以上研究，及VMS在實際生活中的使用情況，提出了在事故場景下，高速公路上的VMS選址優(yōu)化問題。旨在解決如何合理評價不同VMS選址方案的優(yōu)劣、以及如何了解不同的事故場景對選址方案都有哪些影響等問題。

首先給出以下假設(shè)和定義。

1) 路網(wǎng)的OD矩陣、路段-路徑矩陣信息已知。

2) VMS放置位置和事故發(fā)生位置以路段區(qū)分。假設(shè)1個路段最多放置1個VMS，1個路段在同1時刻最多考慮發(fā)生一起事故。

3) 當(dāng)事故發(fā)生路段上游，存在VMS且展示了該事故的相關(guān)信息，則稱該事故所在路段被覆蓋了，或該事故被處理了。

4) 對于同一個事故而言，不同路段放置VMS，司機(jī)接受該VMS顯示信息的程度不同，進(jìn)而導(dǎo)致該VMS產(chǎn)生的效果和收益也不同。類似地，相同VMS作用于不同事故的收益不同。以圖2為例，VMS放置位置為l1，其對l3和l5處發(fā)生事故的處理效果不同。

5) 覆蓋矩陣。即VMS-事故矩陣(M)：n表示路段數(shù)目，VMS-事故鄰接矩陣M被定義為：1個n×n維的矩陣(每一行對應(yīng)VMS的潛在安裝路段位置，每一列對應(yīng)事故可能發(fā)生的路段位置)，第(l,s)個元素Ml,s表示l路段上的VMS和s路段上的事故之間的關(guān)系，元素值為1則表示l路段上的VMS能夠覆蓋s路段上的事故，元素值為0則表示無法覆蓋。以圖2為例，其VMS-事故矩陣如下。

如圖2所示，如果事故發(fā)生在路段l1和l4上，這2條路段沒有上游位置能夠放置VMS，所以矩陣的第1列和第4列均為0；如果事故發(fā)生在l5，VMS的覆蓋范圍是2，即其上游1條路段位置可以放置VMS，那么它的潛在VMS安裝位置即為l1和l4，所以矩陣的第5列第1行和第4行的元素都是1。

圖2 6個節(jié)點6條路段的路網(wǎng)示例Fig.2 A network example with six nodes and six links

高速公路VMS選址的目的是，針對高速公路事故等突發(fā)情況，及時將相關(guān)信息傳遞給需要該信息的出行者，緩解交通壓力，提高交通系統(tǒng)效率，因此，本文在模型的目標(biāo)函數(shù)中主要考慮了3個部分：VMS的安裝成本、VMS的事故處理覆蓋率和處理事故后所帶來的收益(事故處理的收益是指由VMS處理事故所帶來的系統(tǒng)損失的減少)。通過最小化安裝成本和事故未覆蓋率、最大化事故處理收益，來確定最優(yōu)的VMS選址方案。

很顯然，我們希望所有的事故都能得到處理。但這會需要安裝更多的VMS，進(jìn)而導(dǎo)致成本上升。即，需要在VMS的安裝成本和事故覆蓋率之間尋找1個平衡點?；诩僭O(shè)(4)，由于事故持續(xù)時間、嚴(yán)重程度、司機(jī)個人特性等因素，不同司機(jī)接受不同位置的VMS信息時效果也是不同的。因此引入收益因子ρspl，表示在路徑p上的事故s被路徑p上的VMS l處理所帶來的收益(損失的減少)。利用該因子來刻畫不同位置的VMS展示信息對司機(jī)影響的不同，進(jìn)而導(dǎo)致VMS帶來的收益的不同。綜上，可以建立一個VMS選址問題模型(VMS-LP)，求解高速公路事故條件下VMS的安裝位置，最小化VMS安裝成本、最小化事故未處理的懲罰以及最大化事故處理收益。

2.2 模型參數(shù)與變量

模型參數(shù)與變量見表1～3。

表1 模型集合符號與含義

表2 模型決策變量符號與含義

2.3 模型

根據(jù)以上內(nèi)容建立VMS選址問題模型。原問題(original problem ，OP)如下。

(1)

(2)

(3)

σsp≤Κys,?s,p

(4)

σsp≤ΚΔpszp,?s,p

(5)

(6)

(7)

σsp≥0,?s,p

(8)

ys,xl,ηl,zp∈{0,1},s∈S,l∈L,p∈P

(9)

注意到約束式(6)是非線性約束，不利于求解，且xl，ηl均為0-1變量，因此可以線性化。引入變量μl=ηl·xl，則約束式(6)等價于下列約束

?s,p

(10)

?l∈N(s,p):

μl≤ηl

(11)

μl≤xl

(12)

μl≥ηl+xl-1

(13)

μl∈{0,1},l∈L

(14)

目標(biāo)函數(shù)式(1)為最大化事故處理的收益(最小化安裝成本和未處理事故的影響)；約束式(2)表示當(dāng)且僅當(dāng)事故發(fā)生且存在VMS能夠覆蓋該事故時，事故可以被處理；約束式(3)表示一個路徑上有一個事故被覆蓋，則該路徑被覆蓋；約束式(4)和(5)表示當(dāng)路徑p上的事故s被覆蓋后，可以得到一個收益σsp；約束式(6)和(7)表示收益σsp按照路徑p上路段事故處理收益計算，且最多取一個收益最大的路段；約束式(8)和(9)為決策變量的取值范圍約束。約束式(10)～(14)為約束式(6)的等價約束。

3 算法與算例

3.1 算法流程

(15)

(sp 1)

(sp 2)

(sp 3)

σsp≥0,?s,p

(sp 4)

令δ,ε,κ分別為(sp 1)到(sp 3)的對偶變量，則子問題的對偶問題(dual subproblem DSP)為

(16)

(dsp 1)

δsp,εsp,κsp≤0,?s,p

(dsp 2)

(17)

(mp 1)

(mp 2)

(mp 3)

?l∈N

(s,p)

μl≤ηl

(mp 4)

μl≤xl

(mp 5)

μl≥ηl+xl-1

(mp 6)

ys,xl,ηl,μl,zp∈{0,1},s∈S,l∈L,p∈P

(mp 7)

(mp 8)

約束式(mp 8)即為Benders切，完整的算法流程如下。

步驟1。初始化，為初始可行解，初始上界UB=+∞，初始下界LB=-∞。

如果UB-LB=0或者UB-LB

如果UB-LB>0或者UB-LB>e，執(zhí)行下次迭代，返回步驟1。

在下文中，2個不同規(guī)模的算例將用來驗證模型及算法的有效性，應(yīng)用Python和 CPLEX 12.7分別對其進(jìn)行求解。

3.2 算例：Nguyen-Dupuis路網(wǎng)

Nguyen-Dupuis路網(wǎng)[28]包含13個節(jié)點、19個路段、25條路徑和4個OD對，是交通研究領(lǐng)域中常見的算例路網(wǎng)，見圖3。

圖3 Nguyen-Dupuis路網(wǎng)Fig.3 Nguyen-Dupuis network

為更好地驗證算法和模型的有效性，本文依據(jù)隨機(jī)優(yōu)化方法[29]，依次模擬了多個不同事故場景的發(fā)生情況。令ξ表示1個具體事故場景，T表示總的事故場景數(shù)。則事故發(fā)生參數(shù)Οs(?s∈S)取決于該事故場景，表示為Οs(ξ)。原單一場景下的目標(biāo)函數(shù)則轉(zhuǎn)化為使所有場景下的總成本的期望值最小，用Eξ[Q(x,ξ)]表示。其中對每一個ξ有

(18)

假定某條路段s發(fā)生事故的概率是pro，即Οs=1的概率是pro，每一個事故場景ξ就是在規(guī)定的事故概率條件下隨機(jī)產(chǎn)生的、事故發(fā)生情況的模擬結(jié)果。在這樣的概率下重復(fù)模擬T次，即為總的事故場景數(shù)。為合理判斷和估計算法效率和選址方案[30]，下文中未作特殊說明時取pro=0.2。

3.2.1 算法效率分析

為了更好地考察算法的計算效率，給出以下2個定義：①總運行時間：指從包含數(shù)據(jù)讀取、模型建立和求解的全部運行時間；②實際計算時間：僅指模型的求解時間。

圖4表示驗證算例的場景數(shù)目與運行時間和模型計算時間的關(guān)系?？梢钥吹剑?種計算時間都隨著場景數(shù)目的增加而增多。實際運行時間急劇增長，說明程序在數(shù)據(jù)讀取和模型建立部分還有待改善。而模型求解時間的增長較為緩慢，則說明求解模型的算法具有較高的求解效率，可以應(yīng)用到更大規(guī)模該類問題的求解中。

圖4 不同場景規(guī)模的計算時間和運行時間Fig.4 Computational and running times for different scenario sizes

3.2.2 場景數(shù)目靈敏度分析

圖5為不同場景規(guī)模的目標(biāo)函數(shù)值情況。

圖5 不同場景規(guī)模的目標(biāo)函數(shù)值情況Fig.5 Objective values for different scenario sizes

由圖5可見，當(dāng)事故場景數(shù)目較少時，求解方案的評價值(即目標(biāo)函數(shù)值)在較大范圍內(nèi)波動。

出真實的事故發(fā)生情況，模型只是針對少數(shù)特定情況下的事故場景進(jìn)行求解。當(dāng)給出的事故場景中發(fā)生的事故較多，則需要安裝的VMS數(shù)量以及對事故未處理的懲罰就較高；反之事故較少，目標(biāo)函數(shù)值則過小。此時求解得到的選址方案存在極強的特殊性，參考價值不大。當(dāng)事故場景數(shù)足夠大后(>120)，目標(biāo)函數(shù)值則逐漸趨于穩(wěn)定，說明此時的目標(biāo)函數(shù)能夠模擬出大部分的事故場景情況，得到的VMS選址方案能在最大程度上覆蓋事故。這一結(jié)果表明了模型的有效性，且求解方案可以直接指導(dǎo)VMS的現(xiàn)實選址問題。

3.2.3 選址方案分析

為進(jìn)一步分析選址方案的影響因素，研究分別取路段事故率在0.2，0.4和0.6的條件進(jìn)行了實驗。可以看到，隨著事故率的上升，VMS的安裝數(shù)量也有所上升；此外，路網(wǎng)中存在著一些核心路段結(jié)構(gòu)，見圖6，路段3，4，17即為核心路段，其在3組實驗中均被放置了VMS?？赡艿脑蚴牵阂环矫?，這些路段為大部分事故路段的上游，在這些路段上放置VMS能在較多的事故場景下發(fā)揮作用(即拓?fù)浣Y(jié)構(gòu)導(dǎo)致的其為核心路段)；另一方面，這些路段屬于大部分路徑的重疊路段，能作用于大部分流量。核心路段的識別對于VMS的現(xiàn)實選址方案有著重要意義；最后，當(dāng)事故率達(dá)到0.6，VMS覆蓋范圍為其下游兩條路段單位時，選址方案已經(jīng)能夠覆蓋所有路段，此時事故率再增加也不會改變選址結(jié)果，路網(wǎng)處于全面覆蓋狀態(tài)。

圖6 路段事故率對VMS的影響(組圖)Fig.6 The effect of accident rate on VMS

3.3 算例：Sioux-Falls路網(wǎng)

為了驗證算法應(yīng)對較大規(guī)模的算例的求解能力，本文針對Sioux-Falls路網(wǎng)進(jìn)行了求解。Sioux-Falls路網(wǎng)包含24個節(jié)點、76條路段和552個OD對，是交通領(lǐng)域中應(yīng)用較多的經(jīng)典路網(wǎng)之一。應(yīng)用Benders分解算法對VMS-LP問題進(jìn)行求解，求得最終的VMS選址結(jié)果見圖7。

圖7 Sioux-Falls路網(wǎng)選址結(jié)果Fig.7 The result of VMS location for Sioux-Falls network

4 結(jié)束語

本文針對高速公路可變情報板選址這一問題，提出了一個基于事故覆蓋的選址模型。模型考慮了可變情報板安裝成本、事故未處理的懲罰和事故處理的收益等多方面限制條件，建立了一個大規(guī)?；旌险麛?shù)規(guī)劃模型。針對不同位置的可變情報板信息對出行者效用不同的現(xiàn)實問題，在模型中引入了收益因子和覆蓋矩陣等重要參數(shù)，使得決策者在給定相應(yīng)事故特征和路網(wǎng)特征之后，便能決策出可變信息牌的最佳位置。模型應(yīng)用Benders分解算法求得精確解，并以經(jīng)典路網(wǎng)Nguyen-Dupuis和Sioux-Falls路網(wǎng)為例驗證了模型及算法的計算效率。在未來研究中，可以進(jìn)一步考慮在模型中刻畫出行者不同服從率的影響；考慮不同誘導(dǎo)信息種類造成的影響因子的不同；采用更實際的數(shù)據(jù)考量模型效果等等。