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

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

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

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

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

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

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

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

1 問題描述及模型假設(shè)

1.1 問題描述

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

由此定位，對(duì)基于長(zhǎng)客公交化需求的最優(yōu)路徑問題進(jìn)行研究。可以描述為：已知服務(wù)起點(diǎn)和終點(diǎn)，按照長(zhǎng)途客運(yùn)服務(wù)需求，長(zhǎng)途客車從起點(diǎn)出發(fā)，以服務(wù)效率最大化為優(yōu)化目標(biāo)，在有服務(wù)需求的高速公路路網(wǎng)中搜索有效的行車路線，最終順利到達(dá)終點(diǎn)，完成運(yùn)輸任務(wù)。

1.2 模型假設(shè)

因高速路網(wǎng)形式復(fù)雜，一路段可與其他兩、三條路段相交或相連，且一般為雙向連通。為簡(jiǎn)化高速網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，明確每個(gè)節(jié)點(diǎn)和路段的計(jì)算方式，現(xiàn)對(duì)長(zhǎng)客公交化服務(wù)需求可靠性研究做以下假設(shè)。

(1)路網(wǎng)采取有向賦權(quán)圖來表示，對(duì)應(yīng)的網(wǎng)絡(luò)為有向賦權(quán)網(wǎng)絡(luò)。

(2)高速網(wǎng)絡(luò)中的互通交叉口、高速出口及具有一定規(guī)?；蛴幸?guī)劃發(fā)展成一定規(guī)模的服務(wù)站均可作為節(jié)點(diǎn)。

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

(4)根據(jù)節(jié)點(diǎn)對(duì)周邊各節(jié)點(diǎn)的出行需求來計(jì)算每個(gè)節(jié)點(diǎn)對(duì)實(shí)現(xiàn)長(zhǎng)客公交化服務(wù)需求的權(quán)重值，并分配到連接兩節(jié)點(diǎn)間的路段上。

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

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

2 模型構(gòu)建

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

為保證長(zhǎng)途客運(yùn)實(shí)現(xiàn)公交化后能最大可能地滿足各個(gè)區(qū)域?qū)ζ浞?wù)的需求，需要路網(wǎng)中找到一條能夠滿足各點(diǎn)服務(wù)需求的最有效路徑，通常也稱為最優(yōu)路徑。對(duì)于高速路網(wǎng)，若確定了服務(wù)的起點(diǎn)和服務(wù)目的地，最優(yōu)路徑就是在指定網(wǎng)絡(luò)中兩結(jié)點(diǎn)間找一條整體服務(wù)需求最大的路徑，屬于“單源-單匯”類型，也稱為最“短”路問題。

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

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

(1)

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

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

(2)

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

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

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

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

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

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

(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)上行駛的時(shí)間；rij表示路段(i,j)上的服務(wù)需求值。

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

實(shí)現(xiàn)長(zhǎng)客公交化后，各個(gè)路段會(huì)有不同程度的需求，因此，長(zhǎng)途客運(yùn)通行時(shí)，需判斷路段的需求值，路段預(yù)測(cè)服務(wù)需求值與交通通行關(guān)系如表1所示。當(dāng)rij在服務(wù)需求等級(jí)Ⅴ級(jí)范圍內(nèi)，路段需求較高，對(duì)長(zhǎng)途客運(yùn)經(jīng)過該路段通行的要求高；當(dāng)rij在需求等級(jí)Ⅲ～Ⅳ范圍內(nèi)時(shí)，需求值降低，對(duì)長(zhǎng)途車輛經(jīng)過該段通行的要求僅滿足一般水平；當(dāng)rij在需求等級(jí)Ⅰ～Ⅱ級(jí)范圍內(nèi)，基本對(duì)長(zhǎng)途客運(yùn)經(jīng)過該段通行的需求不大，車輛實(shí)際運(yùn)行時(shí)可不經(jīng)過該路段。

表1 路段預(yù)測(cè)服務(wù)需求值與交通通行關(guān)系Table 1 The relationship between the predicted service demand value of the road section and the traffic flow

2.3 效率函數(shù)的使用

(9)

3 求解算法

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

設(shè)有向賦權(quán)圖G={V,E,W}，根據(jù)鄰接矩陣規(guī)則，假設(shè)u、v為兩個(gè)頂點(diǎn)，當(dāng)uv?E時(shí)，規(guī)定W(uv)=+∞。

針對(duì)本文需求模型，改進(jìn)Dijkstra算法步驟如下。

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

S0={u0},i=0。

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

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

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

算法結(jié)束時(shí)，從u0到v的距離由最終標(biāo)記l(v)展示給出，并可依次根據(jù)各個(gè)頂點(diǎn)旁邊的(ui)追回到從頂點(diǎn)v到u0的最終最短路。

根據(jù)上述算法，則求解長(zhǎng)客公交化服務(wù)需求最優(yōu)路徑算法的實(shí)現(xiàn)步驟如下。

(1)輸入道路網(wǎng)絡(luò)圖，設(shè)定服務(wù)的起訖點(diǎn)為O、D。

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

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

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

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

具體流程如圖1所示。

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

4 算例

以中國(guó)某高速公路網(wǎng)局部網(wǎng)絡(luò)為研究對(duì)象，路網(wǎng)結(jié)構(gòu)如2所示。

圖2 某高速公路網(wǎng)局部網(wǎng)絡(luò)圖Fig.2 The partial network diagram of a freeway network

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

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

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

(1)忽略對(duì)高速公路在長(zhǎng)途客運(yùn)公交化上的服務(wù)需求，計(jì)算結(jié)果如表3所示。車輛的最優(yōu)路徑如圖3所示。

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

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

(2)參照表1中的信息，當(dāng)交通運(yùn)行狀態(tài)為在時(shí)間條件允許情況下，可考慮通過時(shí)。即區(qū)域?qū)Ω咚俟吩陂L(zhǎng)途客運(yùn)公交化上的服務(wù)需求具有一般水平，此種情況下的計(jì)算結(jié)果如表4所示。

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

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

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

(3)參照表1信息，當(dāng)僅考慮高服務(wù)需求水平，即區(qū)域?qū)Ω咚俟吩陂L(zhǎng)途客運(yùn)公交化上的服務(wù)需求具有較高水平，盡量保證每條路段均有通過時(shí)的計(jì)算結(jié)果如表5所示。

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

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

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

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

5 結(jié)論

對(duì)面向長(zhǎng)途客運(yùn)公交化服務(wù)中的路徑優(yōu)化問題進(jìn)行了研究，建立了考慮服務(wù)需求的數(shù)學(xué)模型，通過對(duì)模型求解，得出如下結(jié)論。

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

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

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

本文對(duì)高速公路長(zhǎng)途客運(yùn)公交化的理論及建模問題進(jìn)行了研究，研究中并未對(duì)高速公路沿線布設(shè)公交站問題進(jìn)行研究。在高速公路沿線布設(shè)公交站的理論與方法將是未來研究的重點(diǎn)內(nèi)容。