基于時刻表的公交配流算法研究

劉志謙，宋 瑞

（北京交通大學(xué)交通運輸學(xué)院，北京 100044）

基于時刻表的公交配流算法研究

劉志謙，宋 瑞

（北京交通大學(xué)交通運輸學(xué)院，北京 100044）

目前公交配流多基于發(fā)車頻率，配流結(jié)果時刻信息度不高。為促進基于時刻表的公交網(wǎng)絡(luò)配流研究，建立了改進的Logit模型，在傳統(tǒng)Logit模型中引入公交路徑獨立系統(tǒng)以克服多條相似公交路徑的相互影響。同時，建立了容量限制下基于時刻表的隨機用戶均衡模型（VRT-SUE），該模型考慮了車次容量限制并實現(xiàn)了SUE模型在公交網(wǎng)絡(luò)上的配流。實例公交網(wǎng)絡(luò)配流結(jié)果顯示，改進的Logit模型比傳統(tǒng)Logit配流結(jié)果更加合理，VRT-SUE模型滿足車容量限制同時配流結(jié)果達到網(wǎng)絡(luò)均衡狀態(tài)，兩種模型均可用于城市公交網(wǎng)絡(luò)運營管理設(shè)計。

交通工程;時刻表;公交網(wǎng)絡(luò);公交配流;模型算法

現(xiàn)階段，對于公交客流分配模型的研究，國內(nèi)外主要集中在3個方面:①基于運輸系統(tǒng)的客流分配;②基于發(fā)車頻率的客流分配;③基于時刻表的客流分配。

國內(nèi)研究中，高自友等［1］提出了公交網(wǎng)絡(luò)中具有彈性需求和能力限制條件下的隨機用戶平衡配流模型（SUE）;宇仁德、曲金玉等［2］提出了一種公交網(wǎng)絡(luò)分配模型，該模型重點處理有換乘的部分網(wǎng)絡(luò)并在有換乘發(fā)生的節(jié)點處考察乘客的路線選擇行為，在此基礎(chǔ)上提出了公交網(wǎng)絡(luò)分配原則及算法;張林峰等［3］考慮了站點泊車容量和運送能力雙重限制條件下的公交網(wǎng)絡(luò)系統(tǒng)隨機平衡分配問題;在國外，Dial等設(shè)計了啟發(fā)式算法，結(jié)合等車時間和旅行時間利用計算機搜尋最短公交路徑［3］;Spiess（1984）提出了“策略”概念，建立了最小旅行時間配流模型;Tong（1999）建立了一個隨機動態(tài)客流分配模型，并將此模型應(yīng)用到香港地鐵系統(tǒng);Friedrich和Wekeck（2002）采用分枝定界法來構(gòu)造路徑集［4］;Friedrich（2005）對其所在小組（2002）提出的基于時刻表的公交配流模型進行了擴展［5］;Cepeda（2006）建立了在擁擠公交網(wǎng)絡(luò)下基于頻率的路徑選擇模型［6］;Hamdouch 和 Lawphongpanich（2008）考慮公交時刻表和個體車輛的容量限制，建立了一個公交客流分配的用戶平衡模型［7］。

國內(nèi)學(xué)者對基于運輸系統(tǒng)和基于發(fā)車頻率的客流分配模型研究較多，對基于時刻表的客流分配模型研究較少。基于時刻表的公交網(wǎng)絡(luò)中，客流分配模型考慮了精確的時刻表信息，對交通供給的時空結(jié)構(gòu)進行建模，分配結(jié)果可以顯示每一車次的車輛上分配的客流量。為促進基于時刻表的公交配流理論研究，對基于時刻表的公交網(wǎng)絡(luò)配流算法進行初步的探討。

1 基本概念

公交網(wǎng)絡(luò):公交網(wǎng)絡(luò)由多條公交線路和一系列公交站點組成。一般地，用集合G=（N，φ）表示公交網(wǎng)絡(luò)，其中，N表示所有公交站點的集合;φ是連接所有公交站點的公交線路集合。文中的公交線路包括常規(guī)公交、城市軌道交通及快速公交（BRT）。

連接:一條連接就是被附加一系列時間策略的OD點之間的一條路徑，它是從出行始發(fā)地到乘車站臺的步行、乘車過程、不同線路間的換乘步行以及從下車站臺到目的地的步行連接的完整序列，如圖1所示的起點O與終點D之間的連接。通常所說的公交路徑僅僅指包括所經(jīng)過站點和線路的物理道路，而一個連接除包括了公交路徑的屬性外，還具有出發(fā)時間、到達時間、換乘次數(shù)、總費用等屬性。

連接片段:一個連接片段就是一個連接的一部分，它可以是一段步行或是不換乘的一段乘車過程，是組成連接的基礎(chǔ)，它具有一個連接的全部屬性。

吸引連接集合C:對于實際的公交網(wǎng)絡(luò)，并不是所有OD對之間的連接都會吸引到充分的客流量。對于給定的OD對，根據(jù)其連接的一些屬性，如換乘次數(shù)、出發(fā)時間等限制條件，可以定義它們之間的吸引連接集合C。例如，可以限制OD對間的連接的離開時刻早于8:00，或者連接包括的換乘次數(shù)不能超過3，所有滿足這些限制條件的連接便組成了OD對間的吸引連接集合C。

圖1 連接與連接片段Fig.1 Connection and connection segment

2 改進的Logit模型

2.1 改進的Logit模型

基于連接的時間屬性，可以計算出特定時間間隔I內(nèi)OD間的連接阻抗。阻抗函數(shù)的主要參數(shù)變量是感知旅行時間，它是特定時間量，如車內(nèi)旅行時間、換乘等待時間以及換乘懲罰因子nc等的線性組合:

由于一天之中的交通需求是不斷變化的，一條連接的效用在很大程度上取決于考慮的時間間隔I，這一問題通過時間負效用建模，依賴時間間隔I。

原則上，這種分配模型是合理的，因為它包含了乘客個人的、對連接效用的不完全感知。該模型類似于隨機網(wǎng)絡(luò)流量加載。但很多例子顯示，這種模型并不能很好的反映出多條相似連接間的相互影響。在此引用Friedrich和Wekeck改進的Logit模型，它通過引入一條連接的獨立系數(shù)到式（3）中來解決上述問題，獨立系數(shù)滿足一系列的限制條件［4］。

考慮上述因素，連接c∈C的獨立系數(shù)定義為:

式中:hc為非負函數(shù);hc（c′）≤ 1，當(dāng) c′=c時，hc（c′）=hc（c）=1，?c，c′∈C 。hc體現(xiàn)了其它連接對連接c的客流影響。一般規(guī)律是:兩條連接的相似度越高，相互間的影響越強烈。在這里，hc的公式如下:

很顯然，參數(shù)sk分別控制著時間距離、感知旅行時間差、費用差的影響大小。如果連接c和c′之間的時間距離大于s1，則式（5）中的第一項消失，同時 hc（c′）=hc′（c）=0 。其他兩個函數(shù)同理。

自然地，sk依賴于連接集合C。經(jīng)驗表明:s1的最佳取值為任意乘客在起點站點的平均等車時間。另外，假設(shè)連接之間的相互影響是不對稱的。令:

時間間隔I內(nèi)，連接c上分配的客流量

2.2 模型選擇及適用性

改進的Logit模型由于引入了公交路徑的獨立系數(shù)，克服了多條相似線路之間的相互影響，因此配流結(jié)果比傳統(tǒng)的Logit模型更加符合實際，這是選擇該模型的主要優(yōu)勢。但改進的Logit模型未能很好考慮車次容量的限制，配流結(jié)果不能保證滿足車容量限制，因此只能在實際公交站點客流量不大的情況下具有較好的應(yīng)用性。要應(yīng)用于客流量巨大的配流時該模型還需進一步修正。

3 容量限制下基于時刻表的隨機用戶均衡配流模型（VRT-SUE）

3.1 容量限制下基于時刻表的共線問題

非擁擠的基于時刻表的公交網(wǎng)絡(luò)中，時刻表通常描述車輛的時刻運動。在站點的等待時間是離散函數(shù)，并且依賴于乘客到達站點的模式，因此這種情況下不存在共線問題［8-9］。但當(dāng)車內(nèi)乘客數(shù)超過容量時，一些乘客會選擇放棄乘坐該次車輛而等待下次或其他線路車輛，此時便存在所謂的共線問題。

3.2 連接的廣義費用

乘客在站點等待乘車的過程可以簡要描述如下:在給定時間間隔I內(nèi)，考慮一位乘客從出發(fā)地到目的地，起點為r，終點為t，該乘客離開r時通過連接片段s到達下一個站點j。乘客在r決定選擇哪條連接片段時，面臨的問題與共線問題很相似，具體選擇哪條連接片段與其廣義旅行時間費用有很大關(guān)系。連接片段的廣義旅行時間費用函數(shù)為:

式中:ts（vs）為連接片段s的廣義旅行時間費用函數(shù);為連接片段s的等車時間;為連接片段s的車內(nèi)旅行時間;為連接片段s的總乘坐時間，包括車內(nèi)時間和等待時間;為連接片段s的換乘次數(shù);ds為連接片段s的乘客過載延誤，它隨著s上總客流量的增加而增大，即ds=ds（vs）是一個非負函數(shù)，設(shè)時間間隔為I，期望出發(fā)時間 xE∈ I，如果xs=xE=0，否則隨著連接實際出發(fā)時間xs與期望出發(fā)時間的差值的增加而增大;為連接c中連接片段s的貨幣量化，如s的旅行費用。參數(shù) α，β，φ，d根據(jù)實際情況自定義，γ，ρ，ω 為旅行時間值的轉(zhuǎn)換因子。

由于所有的變量tc，ts能夠同時決定，基于時刻表的公交網(wǎng)絡(luò)客流分配類似于共線問題［7］，因此連接的廣義旅行時間費用函數(shù)為:

3.3 擁擠公交網(wǎng)絡(luò)中的客流量約束

網(wǎng)絡(luò)中各條連接上的客流量需滿足以下約束條件:

1）對于OD對w，其交通需求gw分配到各條連接上時應(yīng)該滿足:

式中:vc為連接c的客流量。

2）每條連接片段s，對于每條特定連接c∈e，需滿足以下客流分配:

式中:W為網(wǎng)絡(luò)中的所有OD對集合;vs為連接片段s的客流量。

3）每條連接片段上分配的客流量需要滿足車輛容量限制:

3.4 VRT-SUE 分配模型

當(dāng)各條連接的客流分配滿足式（15）時，隨機均衡客流分配條件［1］。

式中:c，c′是一OD對之間可以任意選擇的兩條連接，θ＞0，θ值根據(jù)實際情況自定義，用來度量乘客對連接的廣義旅行時間費用實際值的感知差異。通常，在基于時刻表的公交網(wǎng)絡(luò)中，θ值比在基于運輸系統(tǒng)或基于頻率的公交網(wǎng)絡(luò)中要小一些。θ→∞時，VRT-SUE的客流分配近似于UE客流分配。

由式（10）可以得到:

由式（16）可以看出，隨著總客流需求量的增加，兩條連接之間的客流分配比例保持不變，直到其中一條連接的某條或幾條連接片段到達容量限制。

考慮下面的VRT-SUE客流分配問題時:

式（17a）的拉格朗日函數(shù)為:

式（17a）的Kuhn-Tucker條件為:

式中:χw，εc，μwc為式（17b）～ （17e）的拉格朗日乘子。

可以得到下述Logit連接客流分配模型:

式中:vc為OD對w的連接c上分配的客流量。

對每條連接片段，εs=-θγds是帶有瓶頸的VRT-SUE公交客流分配模型的條件。如果θ值非常大，式（17a）將由于其第二項可省略而類似UE客流分配。

3.5 VRT-SUE 算法設(shè)計

將式（19）改寫為:

VRT-SUE算法步驟設(shè)計如下:

Step1:初始化。令n=1，對于?w∈W，搜尋吸引連接集合C以及所有的s∈S，令M（n）w=1;

Step3:令n=n+1，返回Step2;

Step4:對于?c∈C，計算=v（E（n），M（n）），對于 ?s ∈ S，計 算，對于?c∈C，計算

3.6 模型選擇及適用性

VRT-SUE模型克服了改進的Logit模型不能保證滿足車容量限制的不足，并將SUE分配原理應(yīng)用于公交網(wǎng)絡(luò)的配流，配流結(jié)果更加科學(xué)，實用性較強，這是選擇該模型的主要優(yōu)勢。VRT-SUE模型能夠適用于實際大城市公交網(wǎng)絡(luò)的配流計算，但隨著網(wǎng)絡(luò)規(guī)模的增大，計算時間也會相應(yīng)的增加。

4 基于時刻表的公交網(wǎng)絡(luò)配流實例

本章建立了一個如圖2的5條公交線路的公交網(wǎng)絡(luò)，各條公交線路的相關(guān)屬性見表1，公交客流OD矩陣客流量大小見表2，各條公交線路的時刻表信息由于篇幅限制未在此列出。

圖2 實例公交線網(wǎng)Fig.2 The example of transit network

表1 實例線路屬性Tab.1 Properties of example network

表2 實例OD對及客流量Tab.2 OD flows of example network

利用VC++6.0和Access2000設(shè)計開發(fā)了基于時刻表的公交網(wǎng)絡(luò)配流模擬系統(tǒng)Transit，Transit首先應(yīng)用Friedrich和Wekeck提出的分枝定界法搜尋出 OD對的吸引連接集合［4］，然后利用改進的Logit模型及VRT-SUE模型進行客流分配。網(wǎng)絡(luò)配流結(jié)果如表3（由于篇幅限制，在此只列出部分配流結(jié)果）。圖3以S2為起點，S4、S10、S12點為終點對比了改進的Logit模型和VRT-SUE模型配流結(jié)果。

表3 網(wǎng)絡(luò)實例客流分配結(jié)果Tab.3 Transit assignment results of example network

圖3 改進的Logit模型與VRT-SUE模型對比Fig.3 The comparison of improved Logit and VRT-SUE

從表3可以看出，對于旅行時間、換乘次數(shù)以及旅行費用相等的連接，改進的Logit模型對其配流的結(jié)果相等，如S2到S4的客流，在分析的時間間隔I=［7:00，9:00］內(nèi)，每條連接的客流為 100人，而VRT-SUE模型的配流結(jié)果中，每條連接的客流量大小不同，最大的為101人，而最小的為98人，這主要是由于ζI

s的差異形成的，文中xE=8:00，所以出發(fā)時間越接近8:00的連接分配的客流量越大，這能夠比較好的刻畫乘客出行的高峰時間特征，在實際的公交配流規(guī)劃中xE的取值應(yīng)該經(jīng)過統(tǒng)計調(diào)查確定。對于旅行時間、換乘次數(shù)以及旅行費用不相等的連接，改進的Logit模型和VRT-SUE模型對各條連接的配流結(jié)果均不相等，客流量大小反映出了連接的廣義時間費用對乘客出行的影響。如S2～S12的各條連接中，旅行時間最小為72 min，其連接客流量為151人，旅行時間最大為75 min，其連接客流量為113人，兩者的換乘次數(shù)及旅行費用均相等，可見，在換乘次數(shù)及旅行費用均相等的情況下，乘客更傾向與選擇旅行時間較短的公交出行。而對于VRTSUE客流分配，旅行時間為72 min的連接由于出發(fā)時間7:43更接近于xE=8:00，因此其分配的客流量更大，為152人，因此，VRT-SUE模型比改進的Logit模型對時間更加敏感。VRT-SUE模型更能體現(xiàn)出發(fā)時間對乘客出行的影響，也可以從圖3中看出。圖3（b）中，改進的Logit模型連接最大客流量為134人，最小客流量為133人，VRT-SUE模型連接最大客流量為135人，最小客流量為131人，隨著時間的變化，VRT-SUE模型的配流變化比該進的Logit模型大。圖3（c）的情況上文也已經(jīng)討論過。總之，VRT-SUE模型比改進的Logit模型更能體現(xiàn)時間屬性對乘客公交出行的影響。另外，改進的Logit模型存在配流結(jié)果可能超出車輛容量的潛在缺陷，VRT-SUE模型克服了這一缺陷，其配流結(jié)果更加符合實際。模型的參數(shù)取值不同，會使得分配結(jié)果有一定的差異，各個參數(shù)的具體取值需要根據(jù)實際經(jīng)驗及相關(guān)研究而定。

5 結(jié)論

對于城市廣義公交系統(tǒng)，建立了兩種基于時刻表的公交網(wǎng)絡(luò)配流模型:改進的Logit模型和VRTSUE模型。實例測試顯示:

1）兩個模型都能很好體現(xiàn)連接出發(fā)到達時間、旅行時間及費用等對乘客出行的影響。

2）VRT-SUE模型克服了改進的Logit模型配流結(jié)果可能超出容量限制的缺陷，對出發(fā)時間的敏感程度大于改進的Logit模型。

在中小城市中，公交網(wǎng)絡(luò)和公交客流量的規(guī)模相對較小，兩種模型都能夠?qū)ζ溥M行快速的公交客流分配，分配結(jié)果能夠用于公交運營管理和網(wǎng)絡(luò)優(yōu)化;隨著城市規(guī)模的增大，公交網(wǎng)絡(luò)的規(guī)模和復(fù)雜度也相應(yīng)加大，公交客流量急劇增長，乘客對公交出行時間的敏感度也越來越高，在此情況下，VRT-SUE模型比改進的 Logit模型具有更強的實用性，但VRT-SUE模型配流的時間花銷也隨之增大。

將基于時刻表的公交配流模型與基于發(fā)車頻率等公交配流模型進行對比分析，以及對兩種模型的優(yōu)化是進一步的研究方向。

［1］ 高自友，宋一凡，四兵峰，等.公交網(wǎng)絡(luò)中基于彈性需求和能力限制條件下的SUE配流模型及算法（1）［J］.北方交通大學(xué)學(xué)報，2000，24（6）:1-7.

［2］ 宇仁德，曲金玉，姜海山.一種公交網(wǎng)絡(luò)分配模型［J］.山東工程學(xué)院學(xué)報，2001，15（2）:47-50.

［3］ 張林峰，范炳全，馬良，等.基于雙重限制的公交網(wǎng)絡(luò)SUE配流模型及算法［J］.系統(tǒng)工程學(xué)報，2005，20（3）:278-284.

［4］ Friedrich，Wekeck.A schedule-based Transit Assignment Model addressing the Passengers’Choice among competing Connections［C］//Italy，Ischia:Proceedings of Conference“The Schedule-Based approach in Dynamic Transit Modeling:Theory and Applications.”2002:159-173.

［5］ Friedrich.Multi-Day Dynamic Transit Assignment［C］//Proceedings of Conference on Schedule-based dynamic transit modeling SBDTM，Ischia，Italy:2005.

［6］ Cepeda M，Cominetti R，F(xiàn)lorian M.A frequency-based assignment model for congested transit networks with strict capacity constraints:characterization and computat-on of equilibria［J］.Transportation Research Part B，2006，40:437-459.

［7］ Younes Hamdouch，Siriphong Lawphongpanich.Schede-based transit assignment model with travel strategies and capacity constraints［J］.Transportation Research Part B，2008，42:663-684.

［8］ Tong C O，Wong S C.A stochastic transit assignment model using a dynamic schedule-based network［J］.Transportation Research 1999，33:107-121.

［9］ Tong C O，Wong S C.A predictive dynamic traffic assignment model in congested capacity-constrained road networks ［J］.Transportation Research，2000，34:625-644.

Algorithms of Schedule-Based Transit Flow Assignment

LIU Zhi-qian，SONG Rui
（School of Traffic＆ Transportation，Beijing Jiaotong University，Beijing 100044，China）

Transit flow assignment models proposed presently are mainly frequency-based，which has poor schedule information.Aiming at improving the research on schedule-based transit flow assignment，the modified Logit model that adopts transit route independence system in the traditional Logit model is established，avoiding the mutual influence of similar routes.At the same time，a volume restrained ＆ timetable based stochastic user equilibrium（VRT-SUE）model is established，which considers the limitation of vehicle capacity and realizes the flow assignment on transit network using SUE model.The case study result of transit network flow assignment shows that the improved Logit model has better effects than traditional Logit model does;VRT-SUE can satisfy the constrain of vehicle capacity，meanwhile the flow assignments can achieve an equilibrium state in network.Both of the proposed models could be applied to the design and operation management of urban transit network.

traffic engineering;schedule;transit network;transit assignment;model algorithm

U491.1

A

1674-0696（2010）01-0114-07

2009-08-18;

2009-09-30

“863”國家高科技資助項目（2006AA11Z203，2007AA11Z208）

劉志謙（1986-），男，四川閬中人，碩士研究生，研究方向:交通運輸規(guī)劃與管理。E-mail:05251041@bjtu.edu.cn。