韓 霜，傅 惠

(1.廣東工業(yè)大學(xué)土木與交通工程學(xué)院，廣東 廣州 510006；2.廣東工業(yè)大學(xué) 機電工程學(xué)院，廣東 廣州 510006)

0 引言

當(dāng)前公交出行需求正向個性化、品質(zhì)化方向發(fā)展，國內(nèi)各大城市正大力發(fā)展定制公交以滿足這一需求。定制公交作為多元化公共交通的重要組成部分，是指通過集中整合個體的交通出行需求，為出行起終點、出行時間、服務(wù)需求相同或相似的人群提供專門定制的公共交通服務(wù)方式。定制公交為乘客提供“快捷、準(zhǔn)時、舒適”的高品質(zhì)公交體驗，根據(jù)響應(yīng)模式上的差異，可以分為靜態(tài)預(yù)約式和即時響應(yīng)式定制公交。目前國內(nèi)已經(jīng)開通的定制公交服務(wù)多屬于靜態(tài)預(yù)約模式，主要以通勤人員為服務(wù)對象，其面對的出行需求在時空上相對集中并且往往呈現(xiàn)出方向上的不均衡性。在靜態(tài)預(yù)約模式中，運營企業(yè)多采用大容量公交車并根據(jù)提前征集得到的乘車需求生成線路，乘客按月、周或單次預(yù)訂已開通的線路并乘車，其線路生成的提前期較長且在較長時間內(nèi)保持固定，車輛運行途中一般不進(jìn)行路線調(diào)整。即時響應(yīng)式定制公交既可為通勤人員也可為臨時出行者提供服務(wù)，它多采用中小容量公交車，通過實時信息交換系統(tǒng)整合接收到的乘車請求，綜合考慮車輛行駛中的多種限制條件，迅速規(guī)劃并開行定制公交線路，系統(tǒng)在車輛行駛過程中持續(xù)接收新的乘車請求并判斷可響應(yīng)的請求，然后調(diào)整行車路線并實時調(diào)度車輛完成被響應(yīng)乘客的運送。即時響應(yīng)式定制公交具有較大的靈活性和廣泛的適應(yīng)性，對私家車出行者具有較大的吸引力，有利于充分發(fā)揮定制公交在替代私家車出行、緩解擁堵和降噪減排等方面的積極作用。

定制公交屬于需求響應(yīng)式公交，對于需求響應(yīng)式公交系統(tǒng)的理論研究可以追溯到20世紀(jì)60年代末[1]。Nourbakhsh等對無固定路線和站點的需求響應(yīng)式公交系統(tǒng)進(jìn)行了研究，在理想化的正方形城市中，以運營和乘客成本最小為目標(biāo)，探討了線網(wǎng)最優(yōu)布局、車輛最優(yōu)服務(wù)區(qū)域和發(fā)車間隔[2]。Bakas等研究了帶時間窗并且具有固定車隊規(guī)模情況下的需求響應(yīng)式公交系統(tǒng)的調(diào)度方法[3]。Kim等分析了乘客需求對傳統(tǒng)公交與需求響應(yīng)式公交系統(tǒng)最優(yōu)性的影響，對兩種公交系統(tǒng)的車輛規(guī)格、發(fā)車間隔和車隊規(guī)模，傳統(tǒng)公交的線路間距以及柔性公交的服務(wù)區(qū)域進(jìn)行了優(yōu)化[4]。Boyer等基于司機休息時間、連續(xù)工作時間、加班時間等限制條件研究了靈活公交系統(tǒng)的車輛及司機調(diào)度方案[5]。近年來，專門針對定制公交的研究開始興起，主要集中在定制公交的評價[6]、票價制度[7]及線網(wǎng)規(guī)劃[8-12]等方面。為提高定制公交線路的適應(yīng)性，王健等根據(jù)前1天乘客向公交企業(yè)提交的出行需求優(yōu)化第2天定制公交車輛的調(diào)度[13]。針對動態(tài)出行需求，Bruni等考慮車輛運行過程中需求的變化，提出了需求響應(yīng)式公交系統(tǒng)的魯棒優(yōu)化，在前期線路規(guī)劃中同時考慮已知需求及后續(xù)未知需求可能引起的路線偏離的影響，減少車輛的繞行成本[14]。邱豐等研究了可變線路式公交的調(diào)度，將實時需求插入到根據(jù)預(yù)約需求規(guī)劃的行車計劃中[15]。郭曉俊針對多起點單終點的定制公交線路，分別建立了發(fā)車前根據(jù)預(yù)約需求進(jìn)行線路規(guī)劃、發(fā)車后對線路周邊實時需求進(jìn)行響應(yīng)的優(yōu)化模型[16]。

綜上所述，目前對即時響應(yīng)模式下的定制公交調(diào)度研究比較少，并且針對動態(tài)需求的相關(guān)研究大多直接采用實時需求進(jìn)行車輛調(diào)度決策。由于單次提交的乘車需求隨機性較大，以此為依據(jù)進(jìn)行的調(diào)度難以實現(xiàn)系統(tǒng)整體最優(yōu)，同時也可能出現(xiàn)線路數(shù)量和線路行車方向波動較大的情形，影響公交系統(tǒng)的穩(wěn)定運營，也增加了運營企業(yè)在運營資源管理上的復(fù)雜度。鑒于此，針對即時響應(yīng)模式下的定制調(diào)度，本研究采用兩階段優(yōu)化模型對其調(diào)度進(jìn)行優(yōu)化：首先根據(jù)區(qū)域內(nèi)分時段的高概率出行OD點對(可根據(jù)歷史乘車需求提取出或通過交通大數(shù)據(jù)分析提取)的地理分布，從整體上對定制公交車輛的初始線路進(jìn)行優(yōu)化；其次，以初始線路為基礎(chǔ)、根據(jù)實時乘車請求對車輛的行駛路線和?？繒r間等進(jìn)行靈活調(diào)度，以實現(xiàn)車輛對實時出行請求的及時響應(yīng)。該兩階段調(diào)度方法的優(yōu)勢在于：(1)根據(jù)分時段的高概率出行點對定制公交車輛的初始線路進(jìn)行整體優(yōu)化，在減少營運車輛(線路)的同時維持高覆蓋率；(2)以初始線路為基礎(chǔ)并根據(jù)實時出行需求對車輛進(jìn)行調(diào)度，綜合考慮了實時出行需求以及出行規(guī)律對定制公交車輛調(diào)度決策的影響，有利于提高車輛與乘客的匹配率，增加服務(wù)的乘客數(shù)量并提高服務(wù)水平。

1 即時響應(yīng)式定制公交調(diào)度決策過程

即時響應(yīng)式定制公交調(diào)度決策是行駛線路預(yù)規(guī)劃與車輛實時調(diào)度的綜合體。由于即時響應(yīng)式定制公交需要整合高度分散和隨機的乘客出行需求，基于提高定制公交系統(tǒng)效益和服務(wù)水平的考慮，本研究提出在調(diào)度中首先根據(jù)區(qū)域內(nèi)分時段的高概率出行OD點對(如商業(yè)中心、大型社區(qū)等)預(yù)先優(yōu)化定制公交車輛的初始路線；當(dāng)某條線路接收到的實時出行請求達(dá)到一定數(shù)量時，則啟動該線路的運營，以初始線路為基礎(chǔ)，根據(jù)可響應(yīng)的實時出行請求調(diào)整車輛行駛路徑并調(diào)度車輛按照決策的時間點運送乘客。即時響應(yīng)式定制公交調(diào)度決策過程如圖1所示。

圖1 即時響應(yīng)式定制公交調(diào)度決策過程Fig.1 Decision procedure of real-time responsive customized bus dispatch

在車輛初始線路規(guī)劃階段，根據(jù)區(qū)域內(nèi)分時段的高概率出行點的地理位置、OD關(guān)系以及上/下車站點順序預(yù)先規(guī)劃車輛初始線路，對該時段內(nèi)需要的定制公交車輛數(shù)量(線路數(shù)量)、車輛初始經(jīng)停站點和?？宽樞虻冗M(jìn)行決策。車輛初始線路規(guī)劃有利于運輸企業(yè)以最少的車輛(線路)覆蓋服務(wù)區(qū)域內(nèi)的主要出行點，提高運營線路與出行需求的適應(yīng)度。在車輛實時調(diào)度階段，以初始線路作為參考路徑，可選擇初始線路中的全部或部分站點作為車輛行駛過程中的必經(jīng)站點；在此基礎(chǔ)上，結(jié)合實時乘車請求的時間和空間分布、上/下車站點關(guān)系、上/下車時間點、車輛容量等限制條件進(jìn)行序貫決策，判斷是否能夠?qū)⒛硞€乘車請求加入到行車計劃中；最后，根據(jù)可響應(yīng)的乘車請求調(diào)整車輛行駛路徑并調(diào)度車輛按決策的到站時間運送乘客。在定制公交調(diào)度中，往往需要平衡運輸企業(yè)的經(jīng)濟(jì)效益(利潤或運營成本)和乘客出行品質(zhì)(服務(wù)水平)。

上述兩階段調(diào)度方法，從整體(全區(qū)域車輛規(guī)劃)和局部(單車調(diào)度)兩個層面去平衡運輸企業(yè)和乘客利益，既保持了即時響應(yīng)式定制公交的靈活性，也使得其線路方案能夠在時空維度上整體把握需求規(guī)律，有利于定制公交系統(tǒng)以較少的線路覆蓋區(qū)域內(nèi)的主要出行需求，并且其調(diào)度方案兼顧了實時需求與后續(xù)最可能需求，規(guī)避了僅依靠實時需求進(jìn)行決策帶來的弊端。

2 即時響應(yīng)式定制公交調(diào)度優(yōu)化建模

2.1 問題描述

本研究的即時響應(yīng)式定制公交調(diào)度可以描述為：乘客通過實時信息交換平臺提交上/下車站點、上/下車時間點(即服務(wù)的時間窗)及乘車人數(shù)等乘車請求；定制公交系統(tǒng)根據(jù)實際限制條件分析得出可以響應(yīng)的乘車請求，允許車輛晚于乘客要求的上/下車時間點到達(dá)，但晚于下車時間到達(dá)將產(chǎn)生延誤成本；定制公交系統(tǒng)信息平臺向乘客反饋決策結(jié)果，然后按照決策獲得的時間和地點調(diào)整車輛的行駛路線，調(diào)度車輛及時運送乘客。

為便于建模，做出如下假設(shè)：

(1)乘客均通過定制公交信息平臺提交乘車請求，包括上/下車位置、上/下車時間點和乘車人數(shù)。

(2)各個站點都僅有一個上車或下車請求，若一個站點同時具有多個上車或下車請求，在模型中將其拆分為地理位置相同的多個站點。

(3)任意站點間的行駛距離已知，站點間的距離為路網(wǎng)中各站點間的最短行駛距離。

(4)除車輛啟動和停車階段外，定制公交車輛以勻速行駛。

(5)定制公交票價為按次收費的均價。

2.2 車輛初始線路優(yōu)化模型

為方便模型的表達(dá)，定義集合及參數(shù)如下：N為規(guī)劃區(qū)域內(nèi)分時段的高概率出行點集合，N={1,…,n1}，N=N+∪N-，N+為上車點集合，N-為下車點集合；{0}為車輛的虛擬車場；L為定制公交車輛集合，L={1,…,l1}；dij為路網(wǎng)中站點i與站點j之間的最短行駛距離；dmax為定制公交車輛初始線路的最大長度限值；M為每輛車初始線路中的最大站點數(shù)；alij為0-1變量，車輛l從站點i開往站點j時取值為1，否則取值為0。

定制公交車輛初始線路優(yōu)化模型如下：

minZ1=|L|，

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

alij∈{0, 1}， ?l∈L,i∈N,j∈N，

(8)

公式(1)表示定制公交系統(tǒng)的運營車輛數(shù)量最小，|L|為集合L中元素的個數(shù)；公式(2)表示定制公交車輛的初始行駛距離不超過最大值；公式(3)表示每個高概率出行點都必須被定制公交車輛覆蓋；公式(4)表示駛?cè)肱c駛離中間站點的定制公交車輛數(shù)量相等；公式(5)和公式(6)表示車輛需要從虛擬車場出發(fā)并且最終回到虛擬車場，公式(7)表示除虛擬車場外，車輛經(jīng)停的初始站點數(shù)量不超過M；公式(8)是決策變量的取值約束。

2.3 車輛實時調(diào)度決策模型

定制公交車輛實時調(diào)度決策模型如下：

(9)

(10)

(11)

s.t.

(12)

(13)

(14)

?j∈Nm+∪Ns+,F(j)∈Nm-∪Ns-,

(15)

tj+2ts+tjF(j)≤tF(j), ?j∈Nm+∪Ns+,

F(j)∈Nm-∪Ns-，

(16)

(17)

(18)

(19)

xij∈{0, 1}， ?i,j∈Nm∪Ns。

(20)

公式(9)表示使定制公交車輛晚于乘客要求的時間送達(dá)造成的延誤成本最小；公式(10)表示定制公交車輛的利潤最大化；公式(11)表示因未響應(yīng)乘客而導(dǎo)致的懲罰成本最??；公式(12)表示車輛必須訪問必經(jīng)站點；公式(13)表示車輛可以訪問或者不訪問可選站點；公式(14)表示車輛訪問中間站點以后必須離開；公式(15)表示定制公交車輛若訪問了上車站點j，則必須訪問其對應(yīng)的下車站點，F(xiàn)(j)為上車站點j對應(yīng)的下車站點；公式(16)表示車輛必須先訪問上車站點才能訪問其對應(yīng)的下車站點；公式(17)表示車輛在車乘客總數(shù)不超過車輛最大載客量；公式(18)和(19)表示車輛從虛擬車場駛出并最終回到虛擬車場；公式(20)為決策變量的取值約束。

3 模型求解算法

3.1 車輛初始線路優(yōu)化模型的遺傳算法設(shè)計

定制公交車輛初始線路優(yōu)化模型是一個線性整數(shù)規(guī)劃模型，本文采用遺傳算法進(jìn)行求解。遺傳算法的主體框架與基本遺傳算法類似，故在此僅對遺傳算法的編碼、初始種群以及遺傳算子進(jìn)行簡要說明。

(1)編碼

定制公交車輛的初始線路是由多個站點按照一定順序排列形成的序列，本文采用自然數(shù)1，2，…，m表示服務(wù)區(qū)域內(nèi)的高概率上車站點，其對應(yīng)的下車站點則采用m+1，m+2，…，2m進(jìn)行編號。在遺傳算法中，染色體采用實數(shù)編碼并用二維矩陣存儲，矩陣的每一行代表一輛車的初始線路，如圖2所示。

圖2 車輛初始線路優(yōu)化模型的編碼Fig.2 Coding of vehicle initial route optimization model

(2)初始種群

初始種群的質(zhì)量將影響遺傳算法的搜索效率，為提高初始種群中的染色體質(zhì)量并保證種群多樣性，采用以下方法生成初始種群中的染色體：

① 隨機擾亂高概率出行點對的排列順序；

② 選擇第一對高概率出行點，構(gòu)成第1輛車的第一對經(jīng)停站點；

③ 選擇下一對高概率出行點，以插入后行駛距離增加值最小為原則將其插入第l(l=1,2,…,l1) 輛車的經(jīng)停路徑，判斷是否滿足所有約束，如果滿足則調(diào)整該車輛的初始路徑，否則將該高概率出行點對插入下一輛車的經(jīng)停路徑, 不斷重復(fù)上述過程，直至找到滿足約束的最佳插入位置；

④ 依次選擇余下的高概率出行點對，重復(fù)步驟③，直至將所有高概率出行點對都插入車輛的初始路徑中。

(3)交叉算子

為了加強遺傳算法的全局搜索性能，擴(kuò)大算法的搜索范圍，交叉算子采用整條路徑交換的形式：首先隨機選取兩個父代染色體，隨機在兩個父代染色體中各選一條車輛初始路徑，然后進(jìn)行交換；最后對子代染色體進(jìn)行修整，使得子代染色體滿足約束條件。

(4)變異算子

變異算子主要用于小范圍調(diào)整站點順序：首先隨機挑選出進(jìn)行變異的父代染色體，然后在該染色體中隨機選擇一對高概率出行點作為變異點，將該高概率出行點對重新插入其他車輛的路徑，并對變異后的子代染色體進(jìn)行修整，以保證染色體滿足約束條件。

3.2 車輛實時調(diào)度決策模型的NSGA-II算法設(shè)計

定制公交車輛實時調(diào)度決策模型是一個多目標(biāo)的非線性整數(shù)規(guī)劃模型，采用帶精英策略的快速非支配排序遺傳算法(NSGA-II)進(jìn)行求解。本研究NSGA-II算法的基本框架以及快速非支配排序、虛擬適應(yīng)度計算以及精英保留策略與文獻(xiàn)[17]～[18]相似，以下僅對編碼和遺傳算子進(jìn)行簡要說明。

(1)編碼

車輛實時調(diào)度形成的最終行駛路徑是由已確定的必經(jīng)站點和新一輪決策中加入的可響應(yīng)站點組成的序列。在每一輪優(yōu)化中，都只需確定乘客新提交的乘車請求中哪些乘車請求可以被響應(yīng)，即哪些OD對能夠加入到原有的行車計劃中。采用二進(jìn)制編碼對車輛實時調(diào)度決策模型的染色體進(jìn)行編碼，1代表相應(yīng)的OD對被響應(yīng)，0則反之。

(2)遺傳算子

車輛實時調(diào)度模型的交叉算子為二進(jìn)制編碼規(guī)則下的兩點交叉，變異算子為二進(jìn)制編碼規(guī)則下的單點變異。

4 案例分析

選取廣州市內(nèi)的50個高概率出行點(主要為學(xué)校、住宅小區(qū)、商業(yè)設(shè)施、公共服務(wù)設(shè)施等)及其OD關(guān)系進(jìn)行實時響應(yīng)式定制公交調(diào)度決策的模擬， OD點對及經(jīng)緯度如表1所示。

各出行點間的路網(wǎng)最短距離采用百度API計算獲得。車輛初始線路優(yōu)化模型的參數(shù)設(shè)置如下：車輛初始線路徑長度不超過35 km，初始站點數(shù)量不超過12個。通過試算，確定遺傳算法參數(shù)如下：種群規(guī)模為50，交叉概率0.6，變異概率為0.4，進(jìn)化代數(shù)為500。經(jīng)過計算，需要6輛車(6條線路)覆蓋所有的高概率出行點， 每條線路的經(jīng)停站點如表2所示。

表1 高概率出行OD點對Tab.1 OD pairs in high-probability travel

表2 車輛的初始路徑方案Tab.2 Scheme of vehicles’ initial routes

當(dāng)線路接收到一定數(shù)量的出行請求時，該線路即開始運營，其車輛的調(diào)度決策基于站點進(jìn)行序貫更新。因篇幅有限，本研究僅列出車輛5(線路5)的實時調(diào)度結(jié)果。模型中相關(guān)參數(shù)設(shè)定如下：車輛行駛速度為35 km/h，車輛啟/停時間為2 s/次，車輛有效座位數(shù)為26，車輛變動成本為80元/時，固定成本折合到單位車時為40元；每個乘客上/下車時間為1 s/人；σ1為5 000，σ2為200；票價為10元/次。NSGA-II算法參數(shù)如下：種群規(guī)模為20，迭代次數(shù)為100，交叉概率0.9，變異概率為0.1。隨機產(chǎn)生3批乘車請求，如表3所示。為方便計算，將車輛5初始線路中的實際經(jīng)停站點按照訪問順序重新用1-12編號，實時響應(yīng)的乘車請求從13開始依次編號，奇數(shù)為上車點，偶數(shù)為下車點。經(jīng)計算，車輛5的路線調(diào)整方案如表4所示，車輛到達(dá)各個站點的時間如圖3所示(單位：分)。進(jìn)一步對數(shù)據(jù)進(jìn)行分析可知：車輛5共搭載乘客29人，未響應(yīng)乘客數(shù)為17人；由于在響應(yīng)時間上采用柔性匹配，車輛在部分站點出現(xiàn)送達(dá)延誤，最大延誤發(fā)生在站點24，延誤時間為12.6 min，平均延誤時間為5.2 min，在非緊急出行中，該延誤在可接受范圍之內(nèi)。案例分析的結(jié)果說明采用所提出的兩階段調(diào)度方法能夠取得較好的調(diào)度效果。

表3 車輛5的實時乘車請求Tab.3 Real-time riding requests of vehicle 5

表4 車輛5的線路調(diào)整方案Tab.4 Route adjustment scheme of vehicle 5

注：圓括號內(nèi)的數(shù)字表示編號不同但地理位置相同的站點。

圖3 車輛5到達(dá)站點的時間(單位:分鐘)Fig.3 Arrival time of vehicle 5(unit:min)

5 結(jié)論

調(diào)度是影響即時響應(yīng)式定制公交運營的關(guān)鍵技術(shù)，本研究兼顧運輸企業(yè)和乘客利益，綜合考慮定制公交出行需求規(guī)律及實時出行請求對調(diào)度決策的影響，建立了即時響應(yīng)式定制公交兩階段調(diào)度模型，即初始線路優(yōu)化模型和車輛實時調(diào)度決策模型：首先以運營車輛數(shù)最小為目標(biāo)對定制公交系統(tǒng)的初始線路進(jìn)行整體優(yōu)化。在此基礎(chǔ)上根據(jù)實時出行請求，以乘客延誤成本最小、運輸企業(yè)利潤最大以及未服務(wù)乘客造成的損失最小為目標(biāo)進(jìn)行車輛實時調(diào)度。該方法具有以下特點：以較少的車輛(線路)覆蓋區(qū)域內(nèi)的主要出行點；同時考慮實時出行請求以及需求規(guī)律對車輛進(jìn)行實時調(diào)度，調(diào)度方案既滿足了當(dāng)前的實時需求也兼顧了后續(xù)最可能出現(xiàn)的出行需求，提高車輛與出行需求的匹配率。根據(jù)模型的特點，分別設(shè)計了求解模型的遺傳算法和NSGA-II算法。最后，選取廣州市內(nèi)的部分高概率出行點進(jìn)行了案例分析，計算結(jié)果表明本文提出的兩階段調(diào)度模型以及設(shè)計的算法能夠提供合理的實時調(diào)度方案。即時響應(yīng)式定制公交調(diào)度是一個復(fù)雜的技術(shù)問題，本文的車輛實時調(diào)度決策模型僅針對各線路進(jìn)行單獨的調(diào)度決策，沒有考慮線路交叉情況下的乘客需求響應(yīng)問題，并且在調(diào)度中也未能考慮車輛行駛速度的動態(tài)性，這將是下一步研究的方向。