韓姍姍 鐘石泉 朱 寧

(天津大學管理與經濟學部 天津 300072)

0 引 言

隨著汽車保有量和交通需求的不斷增長，各種交通問題也日益嚴峻。中國國家統(tǒng)計局年鑒顯示[1]，2016年，中國共接報交通事故864.3萬起，涉及人員傷亡的道路交通事故212 864起，造成63 093人死亡、226 430人受傷，直接財產損失高達12.1億元。交通事故發(fā)生的影響因素眾多，嚴重影響出行者的出行效率。在發(fā)生交通事故后，如何正確引導出行者駕駛行為、從而緩解由事故造成的交通系統(tǒng)延遲[2-3]是一項重要的研究內容。建立高效的高速公路和城市道路管理系統(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形式。它是設置在城市交通網中的重要地點的可變信息標志，能夠向駕駛員提供道理交通狀況信息，從而誘導車輛采取合適的車速或推薦行駛路線，促使駕駛員選擇最佳路線。對于交通網絡而言，其設置的目標是使總體的通行能力最大化，提高系統(tǒng)效率。

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

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

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

1 文獻綜述

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

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

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

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

1.2 整數規(guī)劃在交通領域的應用

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

1.3 研究思路

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

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

2 模型

2.1 模型假設

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

首先給出以下假設和定義。

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

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

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

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

5) 覆蓋矩陣。即VMS-事故矩陣(M)：n表示路段數目，VMS-事故鄰接矩陣M被定義為：1個n×n維的矩陣(每一行對應VMS的潛在安裝路段位置，每一列對應事故可能發(fā)生的路段位置)，第(l,s)個元素Ml,s表示l路段上的VMS和s路段上的事故之間的關系，元素值為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條路段的路網示例Fig.2 A network example with six nodes and six links

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

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

2.2 模型參數與變量

模型參數與變量見表1～3。

表1 模型集合符號與含義

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

2.3 模型

根據以上內容建立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)

目標函數式(1)為最大化事故處理的收益(最小化安裝成本和未處理事故的影響)；約束式(2)表示當且僅當事故發(fā)生且存在VMS能夠覆蓋該事故時，事故可以被處理；約束式(3)表示一個路徑上有一個事故被覆蓋，則該路徑被覆蓋；約束式(4)和(5)表示當路徑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ī)模的算例將用來驗證模型及算法的有效性，應用Python和 CPLEX 12.7分別對其進行求解。

3.2 算例：Nguyen-Dupuis路網

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

圖3 Nguyen-Dupuis路網Fig.3 Nguyen-Dupuis network

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

(18)

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

3.2.1 算法效率分析

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

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

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

3.2.2 場景數目靈敏度分析

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

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

由圖5可見，當事故場景數目較少時，求解方案的評價值(即目標函數值)在較大范圍內波動。

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

3.2.3 選址方案分析

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

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

3.3 算例：Sioux-Falls路網

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

圖7 Sioux-Falls路網選址結果Fig.7 The result of VMS location for Sioux-Falls network

4 結束語

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