即時響應式定制公交調度優化

韓 霜，傅 惠

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

0 引言

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

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

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

1 即時響應式定制公交調度決策過程

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

圖1 即時響應式定制公交調度決策過程Fig.1 Decision procedure of real-time responsive customized bus dispatch

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

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

2 即時響應式定制公交調度優化建模

2.1 問題描述

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

為便于建模，做出如下假設：

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

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

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

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

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

2.2 車輛初始線路優化模型

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

定制公交車輛初始線路優化模型如下：

minZ1=|L|，

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

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

(8)

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

2.3 車輛實時調度決策模型

定制公交車輛實時調度決策模型如下：

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

3 模型求解算法

3.1 車輛初始線路優化模型的遺傳算法設計

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

(1)編碼

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

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

(2)初始種群

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

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

② 選擇第一對高概率出行點，構成第1輛車的第一對經停站點；

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

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

(3)交叉算子

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

(4)變異算子

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

3.2 車輛實時調度決策模型的NSGA-II算法設計

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

(1)編碼

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

(2)遺傳算子

車輛實時調度模型的交叉算子為二進制編碼規則下的兩點交叉，變異算子為二進制編碼規則下的單點變異。

4 案例分析

選取廣州市內的50個高概率出行點(主要為學校、住宅小區、商業設施、公共服務設施等)及其OD關系進行實時響應式定制公交調度決策的模擬， OD點對及經緯度如表1所示。

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

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

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

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

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

表4 車輛5的線路調整方案Tab.4 Route adjustment scheme of vehicle 5

注：圓括號內的數字表示編號不同但地理位置相同的站點。

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

5 結論

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