自動駕駛環境下交通均衡分配模型及算法

劉詩序, 賀朝陽, 朱建超, 王叔雨, 王皓宇

(1. 福州大學土木工程學院，福建 福州 350108; 2. 上海市隧道工程軌道交通設計研究院，上海 200235)

0 引言

隨著城市的發展，越來越多的土地用于建設機動車的道路和停車設施，步行和非機動車出行吸引力下降，也變得更加危險，而自動駕駛汽車(autonomous vehicles，AVs)的出現將改變人們的出行方式. AVs不僅可以改善交通運行狀況[1]，提高安全性和燃油效率，而且還可以減少駕駛人的工作量，為弱勢群體的出行提供便利[2-4]. AVs通常還會改善汽車的排隊行為，而且隨著人工智能和工業技術的發展，在可預見的未來實現汽車自動化是可能的[5]. 自動駕駛汽車是通過消除駕駛中的人為錯誤來減少交通事故風險，而人們對其大規模使用的潛力及其對交通影響的了解卻很少[6]. 因此，對自動駕駛汽車的交通研究非常有價值.

在交通均衡分配領域，學者們通常依據用戶均衡(user equilibrium, UE)原理研究網絡流量模式，UE原理最初由Wardrop提出，隨后學者們在交通網絡均衡建模方面進行了深入研究. UE原理假設每個出行者都將自己的出行成本降至最低，并且沒有人能夠通過單方面更改其路徑來進一步降低個人成本[7]. 由于AVs可以獲取交通狀況的準確信息，因此可以基于UE原理分析自動駕駛環境中的網絡均衡問題，學者們針對AVs和普通車輛混行的網絡均衡問題做了一些研究[8, 9].

但是，對于AVs均衡問題的研究普遍沒有考慮停車需求，由于停車活動是出行過程中必不可少的環節，它會對交通網絡均衡產生影響. 普通汽車網絡均衡考慮停車需求的研究較多[10-11]，而AVs在這方面的研究很少. 考慮停車選擇的AVs交通模式與普通車有很大不同，具有3個新特點： 對出行者而言，不需要花費時間去尋找停車場，AVs自動駕駛尋找停車場； AVs不需要在目的地附近停車，可選擇遠離目的地和市中心的區域停車； AVs可以就近(相對于目的地)將出行者放下，然后自主尋找停車場，這樣出行者節省了從停車場到目的地的步行時間[12]. Liu[13]首次建立AVs的出發時間和停車選擇的聯合均衡模型，Zhang等[14]在此基礎上還研究了早晚通勤模式. 他們研究的是共享AVs出行[13-14]，在可預見的未來，AVs應該存在兩種運營方式： 私有和共享[15]，考慮到便捷性、可靠性、成本等因素，很多學者認為消費者更傾向于擁有私人AVs[16-18]. Levin[19]在私人AVs和公交車、普通車輛混行中不僅考慮了停車選擇，還考慮了交通方式選擇，但他的研究假設AVs只能回家停車，在實際中，當家庭停車場太遠時，AVs可以選擇公共停車場. Zhang等[12]在私人AVs環境中考慮了停車費對網絡均衡結果的影響，但他認為出行者在起點就先進行停車場選擇，這可能出現即使總出行成本最低，但載人階段出行成本相較于其他方案不是最小的現象，這對于追求出行時間最短的用戶來說是不合理的.

城市交通擁堵主要發生在通勤時段，特別是在早高峰期，大多數出行者需要按時抵達目的地. 因此，本文針對這種情況，將整個出行過程劃分為兩個階段： 從起點到目的地，和從目的地到停車場，研究兩個階段同時均衡的問題. 基于此，本文考慮AVs行駛過程中空載和載人狀態的差異，首先針對路段成本函數的Jacobian矩陣對稱情形建立相應的數學規劃模型，而后推廣至更一般的Jacobian矩陣不對稱情況，并給出算法的解滿足均衡條件的證明.

1 自動駕駛環境下交通均衡分析

1.1 路徑選擇過程

普通車輛與AVs的交通模式是不同的，主要體現在停車選擇上. 普通車輛的出行過程可以概括為： 從起始節點出發→選擇停車場停車→步行至目的地，如圖1. AVs的出行過程可概括為： 從起始節點出發→抵達目的地放下出行者→空載尋找停車場停車，如圖2.

圖1 普通車輛路徑選擇過程Fig.1 Regular vehicle routing process

圖2 AVs路徑選擇過程Fig.2 AVs routing process

因此，AVs的出行過程分為兩個階段： 第一階段是載人階段，從起始節點出發將出行者送至目的地； 第二階段是空載階段，從目的地出發空載行駛尋找停車場停車. 需要注意的是，本文將兩個選擇過程分開分析，目的是突出AVs與普通汽車之間的不同，其整個決策過程仍是同時完成的，即出行者事先規劃好出行路徑以及選擇好停車場，因此，本文研究的是AVs的靜態均衡問題，所建立的模型不體現決策的先后順序. 另外，本文討論的停車場包括家庭停車場和公共停車場兩類.

1.2 交通網絡及成本函數

假設網絡G=(N,A1)，其中N為所有節點集合，A1為所有實際路段集合.令P為停車場集合(p∈P)，包含兩類停車場，家庭私人停車場和公共停車場； 令R為所有出發地的集合(r∈R)；S表示所有目的地的集合(s∈S).Krs表示OD(起點O到終點D的距離)對r-s間的所有路徑的集合，Lsp表示OD對s-p間的所有路徑的集合.需要說明的是，在實際問題中起始節點集合、目的地集合和停車場集合可能存在交集，即同一節點既可能是起始節點，還可能是目的地或停車場.

令載人AVs出行需求量為qrs，空載AVs出行需求量為qsp, r，有如下關系

(1)

(2)

(3)

(4)

載人AVs和空載AVs雖然是同種車型，但在道路上運行狀態存在差異. 因為出行者希望盡可能地減少自己的出行時間，所以行駛速度較快. 而AVs空載尋找停車場過程中，出行者并不在車內，他們更關注AVs的能源消耗. 一般地，出行時間的增加意味著出行距離的增加或車速的降低，這可能導致能源消耗成本增加[12].

假定路段a∈A1上的路段行駛時間(行駛成本)函數是單調遞增函數

ti, a=ti, a(x1, a,x2, a)

(5)

式中：ti, a表示路段a上的路段行駛時間函數，i=1時表示載人AVs，i=2時表示空載AVs.

由于AVs出行的第二階段主要以能源消耗為路徑選擇依據，假設能源消耗是路段行駛時間的單調遞增函數，能源消耗g2, a(x1, a,x2, a)可以表示為

g2, a(x1, a,x2, a)=G(t2, a(x1, a,x2, a))

(6)

將路段行駛的能源消耗轉換為路段行駛時間

h2, a(x1, a,x2, a)=α·g2, a(x1, a,x2, a)

(7)

式中：h2, a(x1, a,x2, a)表示路段a上的空載AVs的能源消耗轉化成的行駛時間；α為能源消耗與時間之間的轉換系數.

(8)

(9)

對于空載AVs，出行成本不僅要考慮能源消耗，還要考慮停車費用. 本文將停車場分為家庭停車場和公共停車場，區別是家庭停車場僅供個人使用不對外開放，而公共停車供所有車輛使用. 對于擁有家庭停車場的出行者，在自己的家庭停車場停車的費用為0，而對于其他節點出發的出行者不允許在此處停車，停車費用可視為無窮大. 公共停車場的停車費用假定為定值. 停車成本可表示為

Cr, p=β·cr, p

(10)

式中：Cr, p表示從起始節點r出發選擇停車場p的停車成本；cr, p表示從起始節點r出發選擇停車場p的停車費用；β是費用與時間之間的轉換系數.需要說明，式(9)的出行成本與AVs從哪里出發無關，而式(10)與起始節點有關，為了后續的統一表達以及建模方便，式(9)也考慮了起始節點.

1.3 均衡分析

由于AVs可以獲取完全的路網信息，假設其路徑選擇服從Wardrop用戶最優原則，因此路網可以達到確定性的用戶均衡狀態.

載人AVs總是選擇從起點到目的地的最短路徑使得出行成本最低，均衡條件可以表示為

(11)

式中：μrs表示網絡達到均衡狀態時OD對r-s間的最小出行成本.

空載AVs總是選擇從目的地到停車場的最短路徑使得出行成本與停車成本之和最小，均衡條件可以表示為

(12)

式中：μsp, r表示網絡達到均衡狀態時OD對s-p間的最小出行成本；λs, r表示網絡達到均衡狀態時OD對s-p間的最小凈出行成本，包括路徑出行成本和停車成本兩部分.

2 對稱型均衡模型

2.1 模型

首先假設路段成本函數的Jacobian矩陣是對稱的，即

(13)

在OD需求量固定的前提下，參考已有普通車輛路段行駛成本相互影響的網絡均衡建模方法[7, 20]，建立AVs的路徑和停車選擇的聯合均衡數學規劃模型

(15)

式中：w和v為積分變量，分別對應載人AVs和空載AVs流量.

建立拉格朗日函數，容易證明模型與均衡條件(11)～(12)等價，證明過程可參考文獻[7].

2.2網絡變換

上述模型是考慮路段流量相互影響，并且包含停車場選擇的組合均衡模型. 為了求解方便，可以在網絡中添加虛擬訖節點r′，任何從起始節點流出的流量都會流入相應的虛擬訖節點.

圖3 一般等價網絡Fig.3 Equivalent network

令A2表示虛擬路段的集合，A=A1∪A2，對于空載AVs的路段出行成本可以改寫為

(16)

因此數學規劃模型(14)～(15)可以改寫為

(18)

(19)

(20)

觀察變換前后的目標函數，兩者本質上是相同的. 變換路網后的均衡問題是標準的UE問題，所以模型存在唯一解，即路段流量和停車場需求量是唯一的. 標準UE的求解方法比較成熟，此處不再贅述. 下一節討論另一種情況： 路段成本函數的Jacobian矩陣不對稱.

3 非對稱型均衡配流

3.1 算法

實際中，上述問題的Jacobian矩陣常常是非對稱的，找不到一個等價的極小值問題，使得它就是該問題的均衡解[21]. 本節直接提出適用于本文交通均衡問題的對角化迭代算法，這種算法類似于求解標準UE問題的方向搜索算法，它是基于一系列的標準UE子問題，即每次迭代都要計算下列子問題：

第一步: 初始化.令n=0，設置網絡屬性、出行成本函數等基本參數，設置初始可行流x(n).

第二步: 求解“對角”問題.使用MSA算法求解上述標準的UE子問題，設產生的流量為x(n+1).

第三步: 收斂性檢查.若x(n)≈x(n+1)，停止； 否則置n=n+1，轉入第二步.

收斂檢查，可以使用下式判斷

其中，MSA算法具體步驟可參考Mounce[22]的論文，收斂檢驗方法如下

需要注意的是，要使上述問題有唯一解，路段成本函數的Jacobian矩陣必須正定[7]，正定的條件是： 1) 兩種行駛狀態下的路段行駛成本函數是其流量的增函數； 2) 兩種行駛狀態下的路段行駛成本主要受自身流量的影響. 一般的交通網絡中這兩個條件是成立的，從而可以推出上述問題有唯一解.

3.2 解的特性

3.2.1充分性——若x(n)=x(n+1)，則x(n)是用戶均衡解

考慮上述對角子問題的一階條件，即

(21)

(22)

(23)

當收斂條件成立時，即

(24)

(25)

(26)

此時有

(27)

(28)

則(25)～(26)變為

(29)

(30)

式(29)～(30)表明x(n)是一個平衡解，證畢.

3.2.2必要性——若x(n)是用戶均衡解，則x(n)=x(n+1)

若x(n)是用戶均衡解，根據用戶均衡原則，x(n)滿足(29)～(30)，即滿足均衡條件所對應的UE子問題. 通過第二步迭代計算，該UE子問題可以得到一個均衡解x(n+1).而由于Jacobian陣是正定的，UE子問題有唯一解，所以x(n)=x(n+1).

4 算例

圖4 交通網絡結構Fig.4 Transportation network

本算例網絡結構如圖4，共有兩個OD對，如圖中實心圓，分別為OD和O′D′，需求量分別為qOD=1 000 pcu·h-1和qO′D′=1 500 pcu·h-1, pcu(passenger car unit)表示標準車當量數. 共有四個停車場，其中停車場1(P1)和停車場3(P3)為家庭停車場，停車場2(P2)和停車場4(P4)為公共停車場.

路段行駛時間函數采用下列形式

表1 路段屬性

表2 停車費

圖5 收斂指標變化Fig.5 Convergence change

基于上述條件，令外部收斂因子ε1=0.1，內部收斂因子ε2=0.000 1. 當η1=0.6、η2=0.9時，圖5顯示了對角化算法外部迭代收斂情況. 在外部迭代計算13次后，算法達到收斂標準，說明算法是有效的.

起點O產生的需求包括載人和空載AVs兩種，對于載人AVs前往終點D共有6條有效路徑，在均衡狀態，有3條路徑被選擇，分別為2-5-8-11(路段編號)、2-5-9-12和2-6-10-12，出行成本為26.2 min； 對于空載AVs前往各停車場共有15條有效路徑，在均衡狀態，全部選擇停車場3，出行成本為28.7 min. 起點O′產生的需求中，載人AVs前往終點D′共有6條有效路徑，在均衡狀態，共有3條路徑被選擇，分別為14-17-20-23、14-17-21-24和14-18-22-24，出行成本為25.2 min； 對于空載AVs前往各停車場共有10條有效路徑，在均衡狀態，選擇了停車場1和4，出行成本為26.5 min.

圖6顯示了當η1=0.6、η2=0.9和η1=0.7、η2=0.7時，隨著停車場2的費用減少，周圍8個路段的流量變化情況，虛線表示遠離停車場2的路段流量，實線表示流向停車場2的路段流量. 在分別測試了多個折減系數對路段流量的影響后，圖6所示路段流量變化趨勢基本相同，僅折線的拐點和變動幅度有區別，造成這種現象的原因也是相同的.

(a) η1=0.6、η2=0.9

(b) η1=0.7、η2=0.7

本文以圖6(a)為例進行說明，圖6(a)列出了兩組有代表性的非對稱情況路段流量變化的實驗結果，停車場2的費用剛開始減少時對周圍路段沒有影響(0%～31%)，緊接著周圍路段流量發生劇烈變化(31%～52%)，然后個別路段趨于穩定，隨后個別路段流量出現微小的變化(52%～73%)，最后停車場2的費用繼續減少對路段流量不再產生影響.

圖7顯示非對稱情況下，隨著停車場費用的減少，4個停車場需求量的變化情況. 可以發現停車場2的費用剛開始減少對各停車場需求量沒有影響(0%～31%)，隨著費用的持續下降，選擇停車場2的流量逐漸增多，其他停車場的需求量會減少(31%～52%)，停車費繼續下降對各停車場需求量不再產生影響.

如果把本算例的網絡看成一個城市的交通網絡，那么停車場2相當于市中心的公共停車場. 產生上述流量變化可以歸結為停車場費用和路段行駛時間兩方面原因，停車場費用的減少勢必會吸引大量的空載AVs涌入，同時會增加停車場附近路段的負荷，增加路段行駛時間. 所以當停車場費用為主導因素時，隨著停車場2的費用減少，流向停車場2的路段流量普遍上升，而遠離停車場2的路段流量普遍下降，如圖6所示，同時停車場2的需求量急劇增加，其他3個停車場的需求量全部減小，如圖7所示. 當停車場費用影響不起作用時，路徑流量和停車場需求量不再變化.

圖8顯示了個人出行總成本的變化情況. 可以發現隨著停車場費用減少，總出行成本有相同的變化趨勢. 剛開始對總出行成本沒有影響(0%～31%)，緊接著總出行成本波動變化(31%～52%)，隨后出行成本與停車費用呈現線性變化關系. 產生波動變化的原因和上述停車需求變化原因相同.

圖7 停車需求量變化情況(η1=0.6、η2=0.9)Fig.7 Change of parking demand(η1=0.6、η2=0.9)

圖8個人總出行成本變化情況(η1=0.6、η2=0.9)Fig.8 Change of individual total travel cost(η1=0.6、η2=0.9)

5 結語

本文在全自動駕駛環境下，假設載人和空載AVs將達到各自的均衡狀態，基于此建立了路徑選擇與停車選擇的聯合交通均衡模型及算法，并證明了算法解滿足載人和空載AVs的用戶均衡原則. 算例分析表明，載人和空載AVs的均衡狀態的確存在差異，且差異的大小與兩者之間的相互影響程度有關. 此外，隨著停車費的降低，中心停車場的需求量以及流向中心停車場的路段流量急劇增加，個人出行成本呈現總體下降趨勢. 這意味著人們在享受AVs帶來便利的同時，還需面臨AVs停車過程造成局部路段擁堵帶來的挑戰.

短期內仍難以實現AVs的全覆蓋，所以同時考慮普通車輛混行也有很大現實意義，后續可以研究普通車輛和自動駕駛車輛多方式網絡均衡問題. 另外，AVs可以實時獲取路網數據，所以后續還可以研究自動駕駛環境下的動態交通分配問題.