呂明， 丁文龍， 李赤謀， 陳豐， 張寧

(1.中交文山高速公路建設發(fā)展有限公司， 文山 663099； 2.同濟大學道路與交通工程教育部重點實驗室， 上海 201804; 3.加州大學洛杉磯分校土木與環(huán)境工程學院， 洛杉磯 90095)

隨著中國城市化及城鎮(zhèn)化進程的不斷發(fā)展，城際之間以及市郊的出行需求持續(xù)增加，而傳統(tǒng)的出行方式已經不能滿足乘客日益增長的出行需求。在這種背景之下，長途客運公交受到越來越多出行者的青睞。長途客車公交是依托于城市道路網及高速公路網，為來往于城際之間的乘客提供便捷、迅速、高效服務的可在高速服務區(qū)上下客的公交系統(tǒng)[1]。長途客運公交不但方便了乘客的出行，而且和傳統(tǒng)公交相比，長途客運公交在中遠途旅客運輸中則更加安全。

長途客運公交隸屬于公共交通的范疇。目前很多學者都從不同角度對這一領域展開了多方面的研究。程立勤[2]根據城鄉(xiāng)客流需求特征和城鄉(xiāng)發(fā)展實際，提出了公交主干線、公交次干線和公交支線分層的城鄉(xiāng)公交網絡結構優(yōu)化方法，使城鄉(xiāng)公交線網優(yōu)化更符合城鄉(xiāng)一體化的發(fā)展實際；并進一步提出了利用公交走廊進行“先主后次，先粗后細，分層調整，逐層優(yōu)化”的城鄉(xiāng)公交線網優(yōu)化方法。陸化普等[3]、徐行方等[4]對環(huán)渤海京津唐、長江三角洲和珠江三角洲三大經濟區(qū)域城際鐵路線網規(guī)劃進行研究，對其客運量做了初步預測，而后對城際客流基本特征、客運需求、出行規(guī)律等因素進行分析，得出要加大城際列車的開行密度即實現城際列車公交化的結論。鄧天民等[5]結合旅客自身特征、旅客的出行特征以及運輸方式特征等角度，通過構建非集計的多元Logistic模型，來對中長途客運旅客的出行選擇行為進行了研究。

很多學者還對客運公交運營管理問題進行了研究。Nesheli等[6]以乘客總出行及換乘時間最短為目標函數，采用建模和仿真的方法對客運公交運營管理問題進行研究。 Fonseca等[7]構建了一個基于時間成本和調度成本為目標的雙目標優(yōu)化模型，以此來對公共交通調度優(yōu)化中的成本問題進行研究。Wu等[8]構建了一個雙層規(guī)劃模型對客運公交選線問題進行了研究。Dakic等[9]以乘客出行時間最小為目標函數，構建了客運公交運行管理優(yōu)化模型。Gardner等[10]對公共交通運營管理中從起點到終點的旅行時間分布問題進行了研究，并運用馬爾可夫鏈進行優(yōu)化建模。

部分學者還對公共衛(wèi)生事件影響下的公交出行及公交調度問題進行了研究。周繼彪等[11]針對新冠肺炎疫情影響下寧波市城市交通系統(tǒng)中存在的問題，制定了基于問題驅動的公共交通防疫策略。李健等[12]提出了一種公共衛(wèi)生事件影響下的公共交通運行管理系統(tǒng)框架，在此基礎上設計了不同的模型和算法。茹小磊等[13]對公共衛(wèi)生事件影響下的城市公交管控策略進行了研究。Chen等[14]以乘客出行期間接觸次數最少為目標函數，構建了新冠肺炎疫情影響下的定制公車運行管理優(yōu)化模型。

除此之外，很多學者還對乘坐公交出行的旅客的選擇行為進行了研究。馮煥煥等[15]通過前景理論和乘客最優(yōu)理論構建了居民乘坐公共交通的出行選擇行為模型，并通過實地調研數據對模型的有效性進行了驗證。楊艷妮等[16]通過多層多項Logit模型對公共交通票價對乘客的出行選擇行為進行了研究，通過研究得出了不同出行群體的時間價值(volue of time, VOT),在此基礎上對不同變量的敏感性進行了分析。王子甲等[17]在基于多元數據融合的基礎上通過多項Logit選擇模型對軌道、公交復合網絡中乘客的選擇行為進行了研究，研究結果表明乘客在出行選擇方面更加傾向于選擇出行總時間最短的路徑。鐘異瑩等[18]在計劃行為理論的基礎上，構建了公共交通出行選擇行為模型，并通過重慶市居民的出行數據對模型的結果進行了分析。

通過對文獻進行梳理，發(fā)現絕大多數文獻側重于公交線網規(guī)劃、公交運營管理、公共衛(wèi)生事件下的公交出行管理以及公共交通乘客選擇行為方面的研究，但是針對長途客運展開的研究相對而言還很不充分。因此現對長途客運公交化服務中的高速公路網絡路徑選擇問題進行研究。研究過程中，采用單源-單匯的路徑選擇方法，在給定服務需求下限和時間上限的條件下，使用Dijkstra算法找到不同需求狀態(tài)下的最優(yōu)路徑，在保證需求服務的前提下，進一步找出服務效率最高的路徑。研究成果可以為長途客運公交的發(fā)展提供一定的理論支撐。

1 問題描述及模型假設

1.1 問題描述

隨著交通運輸體系和城鎮(zhèn)化的不斷發(fā)展，市郊和城際客運交通需求也不斷增加。高速公路作為全國公路網的核心組成部分，在長途客運中起著舉足輕重的作用。在此條件下，通過發(fā)揮具有運量大、速度快、安全性高的長途客運公交的優(yōu)勢來提升高速公路在客流運輸中所起的作用，對方便居民日常出行具有重大意義。

由此定位，對基于長客公交化需求的最優(yōu)路徑問題進行研究?？梢悦枋鰹椋阂阎掌瘘c和終點，按照長途客運服務需求，長途客車從起點出發(fā)，以服務效率最大化為優(yōu)化目標，在有服務需求的高速公路路網中搜索有效的行車路線，最終順利到達終點，完成運輸任務。

1.2 模型假設

因高速路網形式復雜，一路段可與其他兩、三條路段相交或相連，且一般為雙向連通。為簡化高速網絡拓撲結構，明確每個節(jié)點和路段的計算方式，現對長客公交化服務需求可靠性研究做以下假設。

(1)路網采取有向賦權圖來表示，對應的網絡為有向賦權網絡。

(2)高速網絡中的互通交叉口、高速出口及具有一定規(guī)模或有規(guī)劃發(fā)展成一定規(guī)模的服務站均可作為節(jié)點。

(3)本文中各個區(qū)域均使用就近的交通節(jié)點代替。

(4)根據節(jié)點對周邊各節(jié)點的出行需求來計算每個節(jié)點對實現長客公交化服務需求的權重值，并分配到連接兩節(jié)點間的路段上。

(5)每條路段之間是相互獨立的，任意一條邊的需求狀態(tài)不會引起其他路段狀態(tài)的改變。

(6)無向邊路段兩個方向的狀態(tài)相同。

2 模型構建

2.1 最優(yōu)路徑模型構建

為保證長途客運實現公交化后能最大可能地滿足各個區(qū)域對其服務的需求，需要路網中找到一條能夠滿足各點服務需求的最有效路徑，通常也稱為最優(yōu)路徑。對于高速路網，若確定了服務的起點和服務目的地，最優(yōu)路徑就是在指定網絡中兩結點間找一條整體服務需求最大的路徑，屬于“單源-單匯”類型，也稱為最“短”路問題。

研究最“短”路徑問題通常將其抽象為圖論概念下的網絡問題，問題的核心就成為求網絡圖中的最優(yōu)路徑問題。最短路徑不單指“純距離”意義上的最短路徑，而是綜合了服務需求和時間意義上的最優(yōu)路徑問題。

對于有向圖G={V,E,W}，其中，V={v1,v2,…,vn}為圖G的節(jié)點集；E為圖G的弧集，表示為eij=(vi,vj)，圖G中每一條弧eij上的權值為w(eij)=wij,且wij≥0。wij表達式為

(1)

假定路徑的起點為vs，終點為vt，P為從vs到vt的一條路，vs到vt的距離w(P)滿足關系

w(P)=min{w(P)|P為vi到vj的路}

(2)

2.2 基于長客公交化需求的最優(yōu)路徑模型構建

交通運輸網由點和連接點之間的路徑構成[19],因此可以用圖與網絡理論來對高速路網進行建模[20]。假定某高速路網結構為G={V,E,W},w(eij)=wij表示該路段e的需求權數。對于實現長途客運公交化的高速路網，其長客通行與以往的交通通行狀態(tài)有一定的區(qū)別，在建立路徑優(yōu)化模型前，首先對長途客運車輛的出行做以下假設。

(1)假設各條高速公路均由雙向車道構成，行駛過程通暢，無交通管制。

(2)假定長途車輛在某一路段上的行駛速度恒定。

(3)整體路網均可使用，無通行限制。

基于此，以通過路徑所需的服務效率為優(yōu)化目標，建立服務需求路徑選擇問題的數學模型為

(3)

(4)

(5)

xij=0,1;i=1,2,…,n;j=1,2,…,n

(6)

(7)

Tr,s≤Tmax，r,s∈V

(8)

式中：Tr,s表示車輛在路段(r,s)上行駛的時間；rij表示路段(i,j)上的服務需求值。

模型中，式(3)為目標函數，表示選擇的路網中路徑服務效率最大化；約束式(4)表示xij的取值構成從源節(jié)點到目的節(jié)點的一條可行需求路徑，保證了從指定的出發(fā)點能夠連續(xù)不間斷地找到指定的終點；約束式(5)表示服務路徑中不含回路；約束式(6)表示決策變量取值約束，xij=0或1；約束式(7)表示長途客運車輛通行的路段xij在路段服務需求值rij不小于指定閾值Rmin的范圍；約束公式(8)表示車輛在路段(r, s)上的行程時間不大于服務時間閾值Tmax。

實現長客公交化后，各個路段會有不同程度的需求，因此，長途客運通行時，需判斷路段的需求值，路段預測服務需求值與交通通行關系如表1所示。當rij在服務需求等級Ⅴ級范圍內，路段需求較高，對長途客運經過該路段通行的要求高；當rij在需求等級Ⅲ～Ⅳ范圍內時，需求值降低，對長途車輛經過該段通行的要求僅滿足一般水平；當rij在需求等級Ⅰ～Ⅱ級范圍內，基本對長途客運經過該段通行的需求不大，車輛實際運行時可不經過該路段。

表1 路段預測服務需求值與交通通行關系Table 1 The relationship between the predicted service demand value of the road section and the traffic flow

2.3 效率函數的使用

(9)

3 求解算法

Dijkstra算法求解最短路徑問題，通常使用基于網絡結構的相關矩陣，即對于含有n個節(jié)點的網絡，運算時需要定義n×n階矩陣，并根據節(jié)點之間的連接情況賦予特定的權值[21]。針對指定兩點間的最優(yōu)路徑搜索，Dijkstra是目前公認最好的算法，該算法完全基于路網圖，主觀因素少，是目前解決最優(yōu)路徑問題采用的理論基礎。

設有向賦權圖G={V,E,W}，根據鄰接矩陣規(guī)則，假設u、v為兩個頂點，當uv?E時，規(guī)定W(uv)=+∞。

針對本文需求模型，改進Dijkstra算法步驟如下。

(1)令l(u0)=0,u∈V-{u0},l(v)=+∞,

S0={u0},i=0。

(3)判斷R(uiv)是否滿足要求，如果滿足要求，則進行步驟(4)，否則轉入步驟(2)。

(4)若l(v)取到l(ui)+d(uiv)，則在v旁邊記下(ui)；計算min{l(v)}，并將達到最小值的該頂點記為ui+1；令Si+1=Si∪{ui+1}。

(5)若i=p(G)-1，則停止。否則i=i+1，并轉入步驟(2)。

算法結束時，從u0到v的距離由最終標記l(v)展示給出，并可依次根據各個頂點旁邊的(ui)追回到從頂點v到u0的最終最短路。

根據上述算法，則求解長客公交化服務需求最優(yōu)路徑算法的實現步驟如下。

(1)輸入道路網絡圖，設定服務的起訖點為O、D。

(2)確定服務鄰接矩陣R和行程時間鄰接矩陣C，設定路段服務閾值Rmin和路徑救援行程時間閾值Tmax。

(3)建立長途客運公交化服務模型，更新路網，得到更新后的鄰接矩陣。

(4)采用Dijkstra 算法搜索出最優(yōu)路徑PO,D。

(5)按照設定的路徑救援行程時間閾值，判斷滿足要求的最優(yōu)路徑PO,D(s)。

具體流程如圖1所示。

圖1 長途客運公交化服務需求最優(yōu)路徑算法總流程圖Fig.1 Flow chart of the optimal path algorithm for long-distance passenger transit service demand

4 算例

以中國某高速公路網局部網絡為研究對象，路網結構如2所示。

圖2 某高速公路網局部網絡圖Fig.2 The partial network diagram of a freeway network

假設服務起點為1，終點為6，路網基礎數據見表2，現按照交通需求等級不同分別搜索1～6之間的最優(yōu)路徑。其中，最優(yōu)路到徑應滿足兩個條件：①達到高速公路對長途客運實現公交化的需求值下限；②滿足總行程時間最短。路網當中路段的長度，車輛運行的速度，服務需求值以及車輛在路段中的行駛時間如表2所示。

表2 局部路網信息統(tǒng)計Table 2 The information statistics of local road network

采用Dijkstra算法搜索出1～6之間在不同的需求狀態(tài)下的最優(yōu)路徑。

(1)忽略對高速公路在長途客運公交化上的服務需求，計算結果如表3所示。車輛的最優(yōu)路徑如圖3所示。

表3 需求值下限為0時的可生成路徑及行駛時間Table 3 The route and travel time of the lower limit of the demand value is 0

圖3 需求值下限為0時的最優(yōu)路徑示意圖Fig.3 The optimal path of the lower limit of the demand value is 0

(2)參照表1中的信息，當交通運行狀態(tài)為在時間條件允許情況下，可考慮通過時。即區(qū)域對高速公路在長途客運公交化上的服務需求具有一般水平，此種情況下的計算結果如表4所示。

表4 需求值下限為0.7時的可生成路徑及行駛時間Table 4 The route and travel time of the lower limit of the demand value is 0.7

在需求值下限為0.7情況下車輛最短行駛時間為10.744 min，最優(yōu)路徑如圖4所示。

圖4 需求值下限為0.7時的最優(yōu)路徑示意圖Fig.4 The optimal path of the lower limit of the demand value is 0.7

(3)參照表1信息，當僅考慮高服務需求水平，即區(qū)域對高速公路在長途客運公交化上的服務需求具有較高水平，盡量保證每條路段均有通過時的計算結果如表5所示。

表5 需求值下限為0.8時的可生成路徑及行駛時間Table 5 The route and travel time of the lower limit of the demand value is 0.8

在需求值下限為0.8的情況下，通過計算一共得到兩條路徑。而編號為1的路徑行駛時間為11.079 min，小于路徑編號為2的行駛時間。相比較，路徑1要更優(yōu)。最優(yōu)路徑如圖5所示。

圖5 需求值下限為0.8時的最優(yōu)路徑示意圖Fig.5 The optimal path of the lower limit of the demand value is 0.8

通過具體算例對不同需求狀況下的車輛路徑最優(yōu)問題進行了分析，對本文所構建模型和設計算法的有效性進行了驗證。分別計算得到了需求值下限為0、0.7和0.8時滿足需求的路徑和最優(yōu)路徑，并計算得到了不同路徑的行程時間以及最優(yōu)路徑情況下車輛的行駛時間。

5 結論

對面向長途客運公交化服務中的路徑優(yōu)化問題進行了研究，建立了考慮服務需求的數學模型，通過對模型求解，得出如下結論。

(1)對基于長途客運公交化服務的高速公路網絡路徑選擇問題進行優(yōu)化模型，設計了Dijkstra算法對模型進行求解，并通過具體算例驗證了模型和算法的有效性。

(2)以時間效率作為目標優(yōu)化函數，通過設定不同的需求值下限的值，來對模型進行求解，通過對模型求解可以得到不同服務需求情況下的最優(yōu)路徑，在保證需求服務的前提下，可以得到出行時間最短的路徑。

(3)實際當中可以將高速公路網中各個服務區(qū)所在地的起終點作為本文所建模型的起終點，將有長客客運出行和有服務需求的各服務區(qū)作為模型中的節(jié)點，在兼顧時間效益、經濟效益的前提下選擇服務水平最佳的路徑出行，以此來提升道路的服務水平。

本文對高速公路長途客運公交化的理論及建模問題進行了研究，研究中并未對高速公路沿線布設公交站問題進行研究。在高速公路沿線布設公交站的理論與方法將是未來研究的重點內容。