考慮出發時間的組合出行動態路徑選擇模型

孟夢，邵春福，曾靖靜，林徐勛

(1. 北京交通大學 城市交通復雜系統理論與技術教育部重點實驗室，北京，100044；2. 南洋理工大學 土木與環境工程學院 基建系統中心，新加坡，639798；3. 上海交通大學 安秦經濟與管理學院，上海，200052)

自Merchant 等[1]提出動態交通分配(dynamic traffic assignment,DTA)的概念以后，DTA 建模越來越成為交通分配領域的研究熱點。根據出行者路徑選擇的假定不同，DTA 模型可以分為2 類：確定動態分配(deterministic dynamic traffic assignment)模型[2]和隨機動態分配(stochastic dynamic traffic assignment)[3-4]模型。確定動態交通分配模型假定所有出行者完全掌握路網交通狀況，能夠準確地選擇路網中最有利的路徑，且每個出行者的計算能力和水平相同的。隨機動態交通分配模型假定出行者對路網了解程度不同，出行者感知的路段阻抗與實際值之間存在一個隨機變量，出行者會在多條路徑中選擇自己感知的最有利路徑出行，因而更能反映現實中出行者的出行選擇行為。近年來專家學者們逐漸認識到在早晚高峰期間，出行者不但對出行路徑進行選擇，更重要的是要對選擇出發時刻進行選擇。若出行者的路徑選擇滿足用戶平衡原則，這類問題就是考慮出發時間選擇的動態用戶平衡(departure time and dynamic user equilibrium, DDUE)問題。根據研究方法的不同，現有DDUE 模型可以分為3 類：解析模型[5-7]、仿真模型[8]和元胞模型[9]。由于解析模型能夠很好地分析解的特性，且求解精度高，易于編程，因而一直是學者們熱烈探討的方向。Hendrickson 等[10]指出：在同時考慮出行時間選擇與出行路徑選擇問題時，出行費用不僅包括路徑出行費用，還應該包括計劃延誤成本。任華玲等[11]建立了DDUE變分不等式模型，模型既考慮路段變量，又考慮OD需求變量，求解過程較為復雜。Huang 等[6]在確定性路徑選擇的假設下，從路徑建模的角度研究了排隊現象的DDUE 模型。Lim 等[7,12]進一步考慮了隨機路徑選擇行為，利用Logit 模型建立了基于路徑的DDUE模型，將DDUE 問題延伸為考慮出行時間的動態隨機用戶平衡(departure time and dynamic stochastic user equilibrium,DDSUE)，更能反映實際交通行為。上述模型均假定路網中只有一種交通方式，李曙光等[13]考慮了多方式交通網絡下的DDSUE 問題，但仍假定出行者在一次出行中只選擇一種交通方式。隨著交通網絡的日益完善，人們經常需要換乘一種或多種交通方式來完成出行，組合出行模式逐漸成為出行者的日常出行模式。組合出行模式下，出行者不僅要選擇出行路徑，還要同時選擇交通方式。因此，研究組合出行模式下的DDSUE 建模具有重要的理論及現實意義。本文作者基于超級網絡的理論和擴展技術，建立適于描述組合出行模式的交通超級網絡，將傳統的出行路徑擴展為可以考慮多方式間換乘行為的超級路徑；假定每個OD 對(origin-destination pair)之間存在小汽車、公交車、地鐵和自行車4 種交通方式，出行者可以通過交通管理部門獲得多方式網絡中的交通運行情況。出行者可以選擇單一交通模式出行，也可以選擇組合交通模式出行。從路徑建模的角度分析了DDSUE 平衡條件，運用變分不等式理論，建立了組合出行模式下的DDSUE 模型，并基于隨機動態網絡加載的方法給出模型的求解算法，實現組合出行模式下考慮出行時間的隨機動態用戶平衡分配。

1 符號定義及超級網絡

在前期研究中，本文作者探討了基于超級網絡理論和擴展技術的多方式交通網絡結構模型構建方法，為描述組合出行行為奠定了基礎[14]。基于超級網絡和擴展理論，將圖1 所示的普通路網轉化為圖2 所示的超級交通網絡。圖2 中實線表示行駛路段，虛線表示換乘路段，點線表示上下網路段。路段上的權值可以代表行駛時間、出行費用、舒適度等多種屬性。出行者可以通過一條超級路徑實現普通網絡上不同方式和線路間的換乘行為，如圖2 中所示的路徑1→6→17→10→23 為小汽車換乘地鐵的一條超級路徑。

圖1 多方式交通網絡Fig.1 Multi-modal transportation network

圖2 超級網絡Fig.2 Super network

考慮交通網絡G=(N，L)，N 為節點集，L 為路段集；O 為起始節點集，O ? N，D 為終訖節點集，D ? N；o 為起始節點，o ∈ O，d 為終訖節點，d ∈ D；Pod為OD 對od 間的路徑集合，每一條路徑p 為一條有效的“交通方式-出行路徑”的超級路徑，p ∈Pod；[s0，s1]為研究時段，s ,t ∈[s0, s1]；TodOD 對od 間的出行需求；θt和θr為模型的校正參數，分別反映出行者對出行時間和出行路徑的費用感知誤差程度。

2 DDSUE 平衡條件

為設計求解算法，采用離散化的方法進行分析與建模。考慮研究時段[s0，s1]足夠長，能使得所有該時段出發的車輛在該時段內駛出路網。將時段[s0，s1]劃分為S 個時段，每個小時段記為s(1≤s≤S)，長度為Δ，則Δ=(s1-s0)/S。劃分標準為：在同一個小時段進入路段的車輛不能在同一個小時段內離開該路段。引用Logit 模型來描述出行者出行時間的選擇偏好

式中：eod(s)和μod(s)分別為s 時刻OD 對od 間的出發量和出發密度；cod(s)為OD 對od 間的期望的最小出行費用。根據期望效用理論，cod(s)可以表示為

式中：cp(s)為s 時刻OD 對od 間路徑p 的出行費用。不考慮出行的貨幣費用影響，路徑p 的出行費用由路徑出行時間和計劃延誤成本組成，有

式中：τp(s)為s 時刻出發的路徑p 的出行時間；fd(s)為計劃延誤成本。

令初始時刻 OD 對 od 間的出行量為e1od( s )= eod(1)，則

將式(4)代入式(1)中，整理得

式中：ep(s)和μp(s)分別為s 時刻OD 對od 間路徑p 的駛入率和被選擇的概率。根據樹形選擇理論[15]，θr≥θt≥0。

定義(組合出行模式下考慮出發時間的隨機動態用戶平衡條件)在平衡態的多方式交通網絡中，沒有出行者能夠單方面改變出行時間和出行超路徑來減少其期望的最小出行費用，并且出行時間和出行路徑的選擇分別滿足Logit 模型式(1)和式(6)。

3 動態約束條件

3.1 路段狀態方程

動態交通流分配問題中，采用交通負荷(traffic load)來表示路段的狀態變量。離散化的路段狀態方程的基本形式為

式中：ga(s)和ea(s)分別為s 時刻路段a 的流出率和流入率；xa(s)為s 時刻路段a 的交通負荷。式(7)表示了時間間隔s 路段a 上車輛數的邊際變化等于時間間隔s 路段a 進出口流率之差。

基于超級網絡的思想，以路徑建模為出發點，將式(7)擴展到路徑狀態層面，有

式中：gp(s)和ep(s)分別為s 時刻路徑p 的流出率和流入率；ep(s)為s 時刻路徑p 的交通負荷。式(8)表示了時間間隔s 路徑p 上車輛數的邊際變化等于時間間隔s 路徑p 進出口流率之差。

3.2 路段出行時間

現有關于動態路段出行時間的研究方法主要有2種：一是點排隊模型，二是物理排隊模型。本文研究普適路網的動態交通流分布情況，認為道路通行能力能滿足交通需求，僅在高峰時期的瓶頸路段處出現交通擁擠，故選擇點排隊模型描述交通流的運行情況。點排隊模型將路段分為自由運行段和出口排隊段，車輛在自由運行段上以自由流速度行駛，在出口處形成排隊，不考慮車輛的物理長度對交通流的影響，經典的點排隊路段出行時間函數為

式中：τa(s)為s 時刻出發的路段a 的出行時間；xa(s)為s 時刻路段a 上的流量；Qa為路段a 的通行能力。

將路段出行時間模型擴展到路徑上。現有的路徑出行時間函數大多假設不同路段之間互相獨立，互不干擾，路徑出行時間為關聯路段出行時間的總和，較少考慮一條路徑中的瓶頸路段的影響。在DTA 建模時，這種假設容易出現路段流量遠遠大于道路通行能力的情況，不符合實際交通情況。而現實中，路網的瓶頸路段會嚴重影響路網暢通水平。假定出行者可以通過交通管理部門獲得多方式網絡中的交通運行情況，某種交通方式出現交通擁堵會影響出行者的路徑選擇。因此，通過遍歷圖法確定有效路徑集合后，需要確定有效路徑的實際通行能力。本文引用經濟學的“木桶理論”，找出路徑中的瓶頸路段，計算路徑通行能力，進而得到出行時間。根據木桶原理，決定路徑通行能力的是該路徑上最小的路段通行能力的路段，針對路徑p={a1，a2，…，ai，ai+1，…，an}有

得到瓶頸路段后，借鑒點排隊模型的思想，路徑的出行時間包括路段的自由流行駛時間和瓶頸路段出口的排隊時間。如圖3 所示，a2為瓶頸路段，a1和a3為自由行駛路段，因此路徑出行時間可以表示為

圖3 路徑點排隊模型Fig.3 Path point-queue model

3.3 路段特性函數

李曙光等[13]證明了基于點排隊模型的路段出行時間函數滿足DTA 建模的先進先出(FIFO)約束和因果性約束，下面給出模型的其他約束條件。

為描述動態交通流的流量傳播特性，離散化的路段流量傳播函數可以表示為

式中：ga(s)和ea(s)分別為s 時刻路段a 的流出率和流入率。時間間隔長度Δ足夠小時，式(12)近似于連續時間的動態交流傳播函數。

在路段點排隊模型的前提假設下，當時間間隔s內進入路段a 的總流入量小于路段通行能力Qa時，車輛以自由流速度行駛，路段a 不會形成排隊，則出口的流出率為

反之，當時間間隔s 內進入路段a 的總流入量大于路段通行能力Qa時，由于通行能力的限制，路段a的出口處會形成排隊，則出口的流出率為該路段的通行能力，即

綜合式(13)和式(14)，可以得到路段出口流出率的計算公式，即

將上述路段特性函數擴展到路徑角度，則需要滿足守恒約束，有

式中：路段an-1為路段an的緊前路段。在滿足路徑傳播約束后，從路徑的角度研究路徑流入率與流出率之間的關系，有

式中：gp(s)和ep(s)分別為s 時刻路徑p 的流出率和流入率。

3.4 一般約束條件

除了上述動態約束條件外，模型還要滿足一般的約束條件，包括流量守恒約束、邊界條件約束和非負約束。流量守恒約束：假定交通需求固定且已知，DDSUE 模型的流量守恒約束包括2 個方面：一是研究總時段內的交通流量守恒，即式(18)；二是單個小時段內的交通流量守恒，即式(19)。邊界條件約束：假定路網在初始時刻沒有交通負荷，即式(20)。非負約束：始終保證路徑流入量與路段負荷是一個非負數，即式(21)。等式左側括號中的變量為對應的對偶變量。

4 模型與算法

4.1 變分不等式模型

建立如下變分不等式模型

定理 當θt→∞時，式(1)表示的出發時刻選擇模型接近于確定性出發時刻選擇模型。當θr→∞時，式(6)表示的路徑選擇模型接近于確定性路徑選擇模型。

證 根據式(1)，任選2 個出發時刻s′和s″，相比可得

對式(23)等式兩邊同時取對數，可以得到

同理任選2 條路徑p′和p″，可以得出當θr→∞時，式(6)表示的路徑選擇模型接近于確定性路徑選擇模型，即：路網達到平衡時，沒有出行者能夠單方面改變路徑來減少其出行費用，所有出行者的費用相等。

4.2 求解算法

動態交通分配模型需要考慮交通流的動態傳播情況，既需要算法的收斂判斷，又需要對終止時刻進行判斷。因此，基于隨機動態交通網絡加載的方法，采用一般迭代的方法進行求解，具體步驟如下：

step1: 初始化

a. 通過遍歷圖法確定每個OD 對od 間的有效路徑集合Pod，并通過式(10)計算路徑的通行能力；

b. 設定初始時段的出發量eod(s1)，時間段長度Δ及收斂參數ε；

d. 設置迭代次數n=1，初始時間段s=1；

step2: 動態隨機網絡加載

b. 通過式(3)計算路徑出行費用，其中分段線性計劃延誤成本為

c. 通過式(2)計算OD 對od 間的最小期望出行費用{cod(n)(s)}；

d. 通過式(5)計算OD 對od 間的出發率eod(n)(s)，通過式(6)計算OD 對od 間路徑p 的駛入率；

e. 通過式(8)和式(15)計算OD對od間的路徑流量xp(s)；

f. 判斷：若s＜S，則s=s+1，轉到step 2.a；

step3: 收斂判斷

5 算例

算例路網如圖1 所示，根據超級網絡的思想，構建算例路網的超級網絡，如圖2 所示。有1 個OD 對(1，6)，4 種交通方式(小汽車、自行車、地鐵、公交)，1條地鐵線和2 條公交線。OD 對間存在6 種出行模式，m=a，b，c，d，e，f 分別表示小汽車出行、公交車出行、小汽車換乘地鐵出行、公交車換乘地鐵出行、自行車換乘地鐵出行和自行車換乘公交出行。模式a 和b 為單一出行模式，模式c，d，e 和f 為組合出行模式。1 和6 分別表示起點和終點。弧段1～4 為上網弧；弧段5～9 為小汽車行駛弧；弧段10 為地鐵行駛弧；弧段11～12 為自行車行駛弧；弧段13～16 為公交行駛弧，其中13～14 為公交1 號線行駛弧，15～16 為公交2 號線行駛弧；弧段17～21 為換乘弧；弧段22～24 為下網弧。其中，上下網路段僅是為了表達出行過程需要，并不具有實際出行時間。

表1 有效路徑集合Table 1 Efficient path set

表2 行駛路段和換乘路段參數Table 2 Parameters of drive link and transfer link

圖4 所示為算例路網中出發時間與路徑出發率之間的選擇結果。從圖4 可以看出：不同路徑出發時間選擇的函數曲線趨勢相同，大部分出行者都選擇在高峰時間400～700 s 之間出發；由于小汽車出行模式的較為便捷，故選擇小汽車出行模式出行的出行者的高峰時間最晚(約700 s)，而自行車換乘公交出行、公交車出行、公交車換乘地鐵出行受換乘影響較多，故這三類出行者會提早出發(早于300 s)，其他出行模式均在300～600 s 之間出發較多。

圖4 出發時間與路徑出發率的選擇關系Fig.4 Relationship between departure flow and time

圖5 所示為算例路網中出發時間與費用之間的關系。從圖5 可以看出：圖4 與圖5 之間存在著密切的關聯關系，各出行模式的出行費用均呈現先降低，到達一定程度后保持穩定，隨后逐漸增加的趨勢。這是因為：由于懲罰費用函數系數不同，出行者在提早出發時會受到早到的費用懲罰；隨著出發時刻逐漸接近準點達到時間，出行者受到的懲罰費用越來越小，在可到達時間窗內，總費用維持在最小費用；隨著出行者出發時刻的推后，出行者會受到晚到的費用懲罰，故出行者越晚出發，其出行費用越大。因為晚到懲罰費用系數高于早到懲罰費用系數，同樣時間長度的提前或推后，早到的出行費用要小于晚到的出行費用。如算例中，同樣距離600 s 準點時刻的300 s 時間差，300 s 的出行者的出行費用要小于900 s 出行的出行費用。

圖5 出發時間與路徑費用的選擇關系Fig.5 Relationship between departure cost and time

針對路徑1 和路徑3，分析時間間隔長度與流入量之間的關系。分別對時間間隔長度Δ為10，20，30，40 和50 s 進行計算，結果如圖6(a)和6(b)所示。從圖6 可以看出：時間間隔的長度對出發時刻與路徑出發率影響不大，在離散時間間隔較小時，路徑出發率可以認為是連續曲線。結合圖6(a)和(b)可以再次證明圖4 所得結論：常規路網條件下，小汽車出行模式較組合出行模式的費用低，出行者的高峰出發時刻較晚。

圖6 不同時間間隔下出發時間與路徑出發率的選擇關系Fig.6 Relationship between departure flow and time withvarious value of time increment

圖7 θt 不同時K od*，( s, p )和( s )的變化Fig.7K od*,( s, p )and( s )with different θt

圖8 θr 不同時K od*，K( s , p )和K( s )的變化Fig.8K od*,K( s, p )andK( s )with different θr

6 結論

1) 給定一個初始出發量和理想到達時間，模型可以確定平衡條件下出行者的出發時刻和出行路徑。

2) 常規路網條件下，小汽車出行模式較組合出行模式的費用低，出行者的高峰出發時刻較晚。各出行模式的出行費用均呈現先降低，到達一定程度后保持穩定，隨后逐漸增加的趨勢。

3) 考慮了多方式交通網絡中瓶頸路段的限制，在滿足交通需求的前提下，最大限度的利用路網通行能力，控制交通流向，提高了多方式交通網絡的運行效率，達到緩解交通擁堵的目的。

[1] Merchant D K, Nemhauser G L. A model and an algorithm for the dynamic traffic assignment[J].Transportation Science, 1976,12：62-77.

[2] Ban X, Liu H X,Ferris M C, et al.A link-node complementarity model and solution algorithm for dynamic user equilibria with exact flow propagations [J]. Transportation Research Part B,2008,42(9)：823-842.

[3] Yao X H, ZHAN F B, Lu Y M, et al. Effects of real-time traffic information systems on traffic performance under different network structures[J]. Journal of Central South University of Technology,2012,19(2)：586-592.

[4] Yang X B, Si B F, Huan M. Mixed traffic flow modeling near Chinese bus stops and its applications[J]. Journal of Central South University of Technology,2012,19(9)：2697-2704.

[5] Chen H K, Chang M S. Dynamic user optimal departure time route choice with hard time windows[J]. Journal of Transportation Engineering,ASCE,2000,126：413-418.

[6] Huang H J, Lam W H K. Modeling and solving dynamic user equilibrium route and departure time choice problem in network with queues[J]. Transportation Research Part B, 2002, 36(3)：253-273.

[7] Lim Y, Heydecker B. Dynamic departure time and stochastic user equilibrium assignment[J]. Transportation Research Part B,2005,39(2)：97-118.

[8] Ziliaskopoulos A K, Rao L.A simultaneous route and departure time choice equilibrium model on dynamic networks[J].International Transactions in Operational Research, 1999, 6：21-37.

[9] Szeto W Y, Hong K L O. A cell-based simultaneous route and departure time choice model with elastic demand[J].Transportation Research Part B,2004,38(7)：593-612.

[10] Hendrickson C, Kocur G. Schedule delay and departure time decision in deterministic[J]. Transportation Science, 15(1)：62-77.

[11] 任華玲, 高自友. 考慮出發時間選擇的動態用戶最優模型[J].交通運輸系統工程與信息,2007,7(3)：83-89.REN Hualing, GAO Ziyou. Dynamic user optimal model with departure time application of bilevel programming in dynamic traffic assignment[J]. Journal of Transportation Systems Engineering and Information Technology,2007,7(3)：83-89.

[12] 溫凱歌, 曲仕茹. 基于Logit 模型的動態交通分配研究[J]. 交通與計算機,2006,24(1)：12-14.WEN Kaige, QU Siru. Dynamic traffic assignment model based on Logit model[J]. Computer and Communications, 2006,24(1)：12-14.

[13] 李曙光, 白秋產, 周慶華. 具有變需求的多模式隨機動態同時的路徑和出發時間問題研究[J]. 公路交通科技,2007,24(8)：128-131.LI Shuguang, BAI Qiuchan, ZHOU Qinghua. A Multi-mode stochastic dynamic simultaneous route and departure time choice with elastic demand[J]. Journal of Highway and Transportation Research and Development,2007,24(8)：128-131.

[14] 孟夢, 邵春福, 曾靖靜, 等. 降級路網組合出行交通流分配模型與算法[J]. 中南大學學報(自然科學版) , 2014, 45(2)：643-649.MENG Meng, SHAO Chunfu, ZENG Jingjing, et al. Traffic assignment model and algorithm with combined modes in a degradable transportation network[J]. Journal of Central South University(Science and Technology),2014,45(2)：643-649.

[15] 黃海軍, 李志純. 組合出行方式下的混合均衡分配模型及求解算法[J].系統科學與數學,2006,26(3)：352-361.HUANG Haijun, LI Zichun. Mixed equilibrium model and solution algorithm in transportation networks with combined mode[J]. Journal of System Science and Mathematical Science,2006,26(3)：352-361.