基于雙層規劃模型下的路徑安排問題研究

楊甜甜，石建軍，劉金超

(1.北京工業大學;2.北京市交通工程重點實驗室)

1 交通網絡描述

在一個多起點多訖點的強連通的交通網絡G(N，A)中，定義N 為網絡節點的集合;A 為有向路段集;r、s 分別為出行起點和訖點;a(l，m)為節點l 到m 的路段;Al和Bl分別為進入和離開節點l 的路段集合;la表示路段a 的起點，ma表示路段a 的終點;對于?t∈［0，T］引入一下變量。

Mrs:起訖點rs 之間所有出行者構成的集合;

τa(t):時刻t 進入路段a 的交通流通過路段a 所需要的實際時間;

θz:出行者z 對禁行的敏感度;

根據元胞傳輸模型(CTM)的特點，我們能夠計算出模擬車輛的路段平均出行時間τa(t)

由式(1)可以得出，出行者從路段a1到達訖點s 的出行時間可以按式(2)進行計算

由先進先出條件，(t－1)+τa(t－1)＜t +τa(t)，當時，

擁堵延誤是指除自由流走行時間外車流通過元胞的附加時間，由此我們可以得出

當交通路網中某一路段產生擁堵時，說明此路段屬于非正常行駛路段，后續車輛不能通過此路段完成正常通行，需進行道路的換行。對此，我們定義禁行區域割集(L·)的概念，即一個路段的集合，當集合中這些路段被移除時，外部出行者將無法通過該禁行區域(如圖1)?；诖?，我們可以抑制交通擁堵的產生，達到緩解擁堵的目的，并進一步改善禁行區域內的交通擁堵，在總體上提高路網的性能。

圖1 禁行區域圖

2 下層目標規劃

當路網中的某些路段處于擁堵狀態時，出行者(駕駛員)在出行過程中就會出現路徑的選擇行為，而這種行為包括出行者原本計劃駛入的路段屬于禁行割集路段以及未駛入但以一定的敏感度重新進行路徑的選擇。

對于做出這些路徑選擇行為的出行者，我們可以做出如下的假設。

(1)對于在交叉口進行路徑選擇的出行者而言，路網結構已經發生變化，出行者在進行路徑選擇的時候不能選擇進行區域內部的路段以及下屬路段。

(2)由于擁堵的發生，出行者無法像往常一樣進行正常行駛并對現實路況進行估計，只能根據經驗進行選擇，而其選擇的依據則是其對各個時刻，當路網不發生擁堵時的的經驗阻抗，這樣，出行者采恩那個盡快的抵達目的地，完成出行過程。

由以上的假設，我們可以給出出行者在禁行期間根據自身經驗在交叉口的平均走行時間的路徑選擇行為。

式(8)目標函數描述了出行者的路段選擇行為，當遇到車輛禁行后，出行者會根據路段經驗平均出行時間在后續的決策點上選擇盡快到達出行訖點的路段，也就是說，在任意時刻根據路段經驗阻抗進行一次全有全無分配。ub(t)=表示路段的流入量與出行者路段選擇結果的集合是等價關系。

中央控制指揮中心(RCCC =route choice control center)利用自身的優勢，給出行者提供未知的路況，輔助出行者進行決策。在交通擁堵狀況下，當出行者需要進行路徑選擇時，中央控制指揮中心接到請求信息后，給出行者下發路徑路況信息，使得出行者在沒有遭遇擁堵排隊之前，提前了解前方路況，在到達擁堵區域之前提前分流，使進入擁堵區域的出行者減少，進一步抑制擁堵的傳播。

基于中央控制指揮中心的分流，做出如下假設。

(1)該控制方式是反應式的，即當駕駛員進行路徑請求的時候才會給出行者下發相應的路徑信息，因此對于控制中心來說，只有當出行者進行路徑請求時，其才會對路網中的車輛進行預測。

(2)沒有向控制中心發送請求信息也沒有接受可變信息誘導的出行者，在其出行過程中，我們可以將其當成定量因素分析，其出行路線不改變。按原計劃進行行駛。

(3)接受RCCC 路徑安排(路徑誘導)信息的出行者，在后續的交叉口根據路段實際走行時間選擇到達目的地的路段集合。所以對于接受由RCCC 安排路徑的出行者來說，在擁堵期間內，他們所行駛的路線已經處于均衡狀態，想單方面通過改變路徑更快的完成行程(降低出行阻抗)是不可能的。

所以接受控制中心路徑安排(路徑誘導)的出行者z∈I·的達到均衡狀態需滿足以下約束條件

根據式(9)、(10)、(11)不等式我們將出行者限定為接受了控制中心路徑誘導的用戶，而這些不等式是基于路段實際阻抗動態用戶均衡條件的變形。其中路段的流入量等價于出行者對路徑選擇結果的集合。即

圖2 車輛誘導示意圖

如圖2 所示，假設在路段1 出行者對控制指揮中心發出路徑請求，控制中心接受并受理出行者的請求，在控制指揮中心作用時段內離開該路段的出行者都將受影響。假設原本計劃通過路徑1→30→11→36→21 到達出行訖點17 的出行者，控制中心接到請求后根據路網檢測得知路段36 發生擁堵并蔓延至路段11，此時，控制中心會在盡量減少出行者用時的情況下，為其安排路徑并在駛出相應路段后重新建立對路徑的選擇，在之后的交叉口選擇使其盡快到達出行終點的路段，如路徑1→30→28→19→21 或是1→3→38→13→44 完成出行。

根據以上假設，我們可以用下面的模型來描述受控制中心路徑誘導影響的出行者在交叉口的路徑選擇行為

向控制中心(RCCC)進行路徑請求的出行者的集合為

用該目標函數的變分不等式可以描述出行者的路徑選擇行為，出行者在控制中心路徑誘導的作用下根據路段實際走行時間，在后續的決策點選擇盡快到達出行訖點的路段集合的行為。

3 上層目標規劃

對于交通管理者來說，其想要達到的是整個系統的路網最優，而若達到這種最優狀態，則需保證在路徑誘導之前使得整個路網的總阻抗達到最小。對于這個問題，我們可以通過區域割集的概念來解決。當禁行區域確定后，我們只需確定哪些交叉口可以通過，哪些屬于禁止的。我們可以用一個變量來描述一個交叉口在路徑誘導控制期間是否通行還是禁止。例如，給定一個交叉口i，xi=1 表示該交叉口在路徑誘導控制期間不能夠正常行駛通過，即i∈L·;而xi=0 表示該交叉口在路徑誘導控制期間可以正常通行，即i∈/L·。

我們把擁堵延誤和自由走行時間作為系統總阻抗，在一定程度上，它們能夠更好更直接的反映交通網絡的擁堵程度和路網狀態。因此交通管理者將最小化系統廣義費用(本文采用系統總行程時間)作為上層目標來研究，以期達到系統最優。則上層問題可以描述為如下優化問題:

s.t.

基于此，我們構建出了出行者和交通管理者在控制指揮中心作用下的路徑誘導的雙層規劃模型。

4 案例分析

4.1 方案設計

為了驗證所提出的規劃模型，文章選取實際路網中的某一區域作為仿真參考區域，如圖3 所示，該路網中有20 個交叉口，30 個路段。仿真長度為12 格、9 格等(一格代表實際路段的長度為200 m)。為了更加細致的描述車輛的運行狀態和交通流的實時分布狀況，路段和交叉口并沒有按同比例進行縮放。路網中各路段的實際長度和仿真長度見表1，其中實際長度的單位為m，仿真長度的單位為格。各參數如下:時間間隔，主路的速度限制為60 km/h，服務流率為1 800 pcu/h/車道，次要道路速度限制為40 km/h，服務流率為1 800 pcu/h/車道。

表1 仿真路網路段長度

圖3 實際路網圖

在仿真過程中，設置了三種情境。見圖3。

情境1:路網中的出行者不接受任何外界信息，在給定目的地后，出行者完全根據自己的經驗進行路線的選擇。情境2:路網中的出行者接受傳統導航給出額路線信息，如出行時間、出行距離、路線的復雜度、平均速度等等。但是出行者得到信息后還是根據自己的經驗進行路線的選擇。情境3:出行者接受來自控制中心(RCCC)給出的信息，并按照RCCC 給出的動態系統最優路線進行行駛。

在三種情境下各在三種不同的交通量下進行仿真:低交通量(14 000 vph)、中等交通量(2 8000 vph)、高交通量(42 000)。見圖4。

圖4 仿真界面圖

4.2 分析及結果仿真結果見表2，表3，表4。

表2 仿真結果(低交通量)

表3 仿真結果(中等交通量)

表4 仿真結果(高交通量)

從仿真結果看以看出，在低交通量的情況下，不同情境下的路網狀態差異很小，這個時候整體路網的交通狀況很好;在中等交通量的情況下，情境2 和情境3 都能夠改善路網狀態，但是情境3 相對于情境2 下平均速度要高，平均出行時間要低;在高交通量的情況下，情境3 下比其他兩個情境下更能夠改善路網狀態。但是當交通量繼續增大時，在情境3 下也不能夠有效的改善路網狀態，因為此時路網中已沒有可替代的路徑可供選擇。

圖5 不同導航裝配率的平均區間速度

圖6 不同導航裝配率的平均區間行程時間

圖7 不同導航裝配率的平均出行距離

從圖5，圖6，圖7 不同裝配率的仿真結果圖可以看出，在情境2 下的最佳傳統導航的裝配率為45%，此時平均速度達到最大值而平均出行時間達到最小。在情境3 下，新型的系統導航儀(基于RCCC)的最佳裝配率為65%，此時平均速度達到最大，平均出行時間達到最小。也就是說，路網性能達到最優，此時的路網最為暢通，交通流分布均衡。

當路網達到最優狀態時平均出行距離并沒有達到最小值，因為為了整體路網的性能，有時會建議車輛繞行，以保證大多數駕駛員的利益。

情境3 下的的最佳裝配率比情境2 的最佳裝配率要高，這意味著，當駕駛員和路網系統管理者進行協商后，可以更加有效的改善路網的性能。

5 結 論

雙層規劃問題是現如今的NP 難題，其模型的搭建求解過程是非常復雜的。對于求解雙層規劃問題，比較廣泛的一類方法是非數值優化方法。本文中使用遺傳算法進行求解。而具體的優化算法及相應的分析還需要相關的編程來實現。

以動態網絡交通流為背景，探討了基于控制中心解決交通網絡擁堵問題。道路發生擁堵會使得出行者進行路徑選擇，出行者的路徑選擇又會產生新的交通問題。而交通管理者希望整體的路網達到系統最優。出行者依據控制指揮中心計算出來的最優系統路徑進行行駛，因此，該問題可以描述為一個雙層規劃問題。上層為交通管理者希望達到的最優目標，下層問題描述出行者的路徑選擇行為。通過案例分析表明了模型的可行性。通過對該雙層規劃問題進行求解以期望采用控制指揮中心給出的路徑能夠使得出行者和交通管理者達到共贏。在達到為車輛安排路徑的基礎上，車輛能夠按照中心給定的路線和速度進行行駛，這可以在宏觀上達到節能減排的作用。并考慮到，隨著技術的革新，無人(自動)駕駛成為一種可能。希望在此基礎上，能夠為以后車輛的自動駕駛安排路徑。

［1］羅朝輝，梁碧清，韋增欣.動態交通方式劃分與系統最優配流模型［J］.河北科技大學學報，2012，33(1):79－82.

［2］高自友.現代物流與交通運輸系統［M］.北京:人民交通出版社，2003.

［3］高自友，任華玲.城市動態交通流分配模型與算法［M］.北京:人民文通出版社，2005.

［4］龍建成.城市道路交通擁堵傳播規律及消散控制策略研究［D］.北京:北京交通大學，2009.