需求響應型公交車輛調度及路徑優化

管德永，吳曉芳，趙 杰，王 玨

(1.山東科技大學 交通學院，山東 青島 266000；2.南京市城市與交通規劃設計研究院股份公司山東分公司，山東 青島 266000；3.青島真情巴士集團有限公司，山東 青島 266400)

0 引言

當前城市化進程發展迅速，居民出行OD發生經常性變化，傳統公交很難快速適應[1]，很多公交線路過長，沿線公交停靠站較多，同時沿線部分公交站點乘客數量不均[2]，公交系統資源沒有得到充分利用，發展新型交通模式愈加迫切。城市中居民多以中短距離出行為主，出租車靈活性高，但運載量較小；地鐵運載量大，卻不夠靈活。城市公交系統具有覆蓋面廣、運載量大、靈活性高等特點[3]，因此應結合城市已有公交系統，實現車輛根據乘客的需求靈活設置停靠站點和行駛路徑，使其具備更高的靈活性。

需求響應公交是根據收集乘客在客戶端發出的請求，為出行起終點、出行時間等相似的乘客提供專門出行服務[4]的靈活性公交。具體特性仍為“公交”性，采用固定站點、完全不固定線路，為片區內市民提供的一種可實時呼叫或預約，系統實時聚合匹配，實時生成動態線路的新型公共出行服務。其介于私家車和傳統公交之間的新型服務特性，能夠滿足乘客多樣化出行要求，尤其是高品質出行要求，轉變部分私家車出行的交通出行方式，改為公交出行。深圳、北京、西安等城市開始推行該公交模式，注冊用戶不斷增加，獲得了市場認可[5]。但準時性差、運營成本高[6]等問題不斷涌現，在部分站點、路網較全，人口量少的城市區域，甚至遇到了線路遭冷落、上座率不高、報名線路人數不夠無法開設等困境[7]。因此，深入研究需求響應公交的調度與優化，提升需求響應公交的服務水平具有重要意義。

Nourbakhsh[8]等對低密度需求矩形區域內發車間隔、線路設置進行了研究。Huang等[9]提出了一種動態插入方法來處理動態階段的模型，綜合了運營商與乘客的動態決策過程，解決了低需求區域的乘客出行需求。韓霜等[10]建立的基于改進遺傳算法的調度決策模型能夠生成數量最少且覆蓋區域內所有高概率點的線路。在車輛路徑優化問題中，王正武等[11-12]設計了雙遺傳算法，對同時接送模式下的需求響應型車輛調度優化進行了試驗對比分析，相對于單獨接/送模式，同時接送模式在車座利用率、成本節約方面具體更好的優越性。魯春燕[13]為解決遺傳算法搜索效率不高的難題，提出了一種基于局部優化的遺傳算法，在解決問題時并未考慮到較為復雜的帶時間窗的路徑優化問題。賴元文等[14]設計模擬退火-自適應布谷鳥算法，改善尋優過程中跳出局部最優解而全局尋優的能力，結果表明通過模型計算出的結果均優于現有調度方案。

綜上所述，現有研究對于乘客需求的響應往往是依靠經驗確定，存在主觀性，缺少定量研究[15]，部分研究一般假設系統只運行單輛公交，同一需求點乘客具有相同的出行需求，且車輛容量無限大[16]，研究情境過于理想化，尚未考慮我國實際道路網結構，忽略了乘客出行個性化時間窗要求[17]。

因此，本研究通過對站點歷史乘車請求頻次提取出高概率點，對乘客需求時空分布和出發地與目的地(OD)分析，提出在車容量、乘客需求時間約束下的二階段需求響應型公交車輛調度及路徑優化模型，先生成能夠覆蓋所有高概率站點的靜態車輛調度決策，后生成能夠滿足實時預約需求的動態優化路徑。

1 模型構建

1.1 問題描述

本研究將需求響應公交的服務模式抽象為多車輛從固定車場出發，依次經過各個具有時間約束的需求點，運行途中系統每隔固定時間對車輛調度方案進行更新，并回到車場的最短路徑規劃問題。需求點包含上下車站點，根據該區數據實際情況，將上車需求頻次大于60次的站點定義為高概率上車站點，下車需求頻次大于60次的站點定義為高概率下車站點。

1.2 問題假設

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

(1)各個站點最多有1個請求，若1個站點同時具有多個請求，在模型中將其拆分為地理位置相同的多個站點。

(2)每輛車任務的始發與結束都發生在配送中心。

(3)任意站點間的行駛距離為站點間的最短行駛距離。

(4)默認乘客在站點處等待。

(5)每輛車到達需求點的時刻為開始服務的時刻。

(6)不考慮道路擁堵情況，車輛平均行駛速度相同。

該模型主要的約束條件是乘客時間和車容量。參照每個站點的服務人數、時間屬性，建立數學模型進行求解。

目標函數為：

(1)

式中，D為車輛總運行里程；dij為站點間最短行駛距離；i和j為需求站點；N為所有需求站點集合，表示為車輛總運行里程最小。

約束條件為：

(2)

式中，alij和aljk為0-1決策變量，若車輛l從站點i(j)開往站點j(k)取1，否則取0；dmax為初始線路允許的最大行駛距離；L為所有公交車輛集合；約束條件表述為公交初始行駛路徑不能超過最大距離，所有需求站點必須被公交車輛覆蓋，駛入j站和駛離j站的車輛數相等。

(3)

式中，0為車場；al0j和ali0為0-1決策變量，表示車輛從車場出發并最終回到車場。

(4)

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

(5)

式中，M為每車初始線路允許開行的最大站點數，表示經停的初始站點數量不超過M，決策變量取值約束為0或1。

1.3 車輛動態路徑優化模型

車輛動態路徑優化階段，每輛車可響應周邊實時乘車請求。以里程變化最小為目標，決策變量為每輛車經過各站點順序，到達、出發時刻，建立模型求解。

目標函數為：

(6)

式中，d為總運行里程；dl為第l輛車的運行里程。

約束條件為：

(7)

(8)

N(s),

(9)

式中，N(m)為車輛必經站點集合；N(s)為車輛可選站點集合；j，k，h為需求站點；xjk，xkh為0-1決策變量；式(7)表示車輛必須訪問必經站點；式(8)表示車輛可以訪問可選站點；式(9)表示車輛訪問中間站點后必須離開。

(10)

(11)

式中，F(j)上車站點j對應的下車站點；N(m+)為車輛必經上車站點；N(m-)為車輛必經下車站點；N(s+)為車輛可選上車站點；N(s-)為車輛可選下車站點；tj為車輛進入站點j的時間；t(s)為車輛每次啟/停時間；xij和xkF(j)為0-1決策變量；tjF(j)為從站點j到站點j對應下車站點的行程時間，tF(j)為車輛進入站點j對應下車站點的時間。式(10)表示車輛若訪問了上車站點j，則必須訪問其對應的下車站點F(j)；式(11)表示車輛必須先訪問上車站點才能訪問其對應的下車站點。

(12)

(13)

xij∈{0,1},?i,j∈N(m)∪N(s)，

(14)

2 算法設計

2.1 兩階段調度優化模型算法流程

算法包括靜態車輛調度和動態路徑優化二階段。其中靜態調度是一個線性整數規劃模型，本研究基于LNS策略的遺傳算法進行求解，采用破壞、修復算子，提升求解質量，主體框架與傳統遺傳算法類似。動態路徑優化采取精確規劃算法，將獲得的動態需求插入到初始路徑中，不斷更新路徑，圖1為二階段調度優化流程。

圖1 二階段調度優化流程Fig.1 Process of 2-stage scheduling optimization

2.2 算法說明

(1)編碼

需求響應型公交的初始線路是由多個站點按照一定順序排列成的，1,2,…,n表示服務區域內的高概率上車站點，其對應下車站點采用n+1,n+2,…,2n進行編號。染色體采用整數編碼，當站點數為N，最大使用車輛數為L時，染色體長度為(N+L-1)，且N+1,N+2,…,N+l-1將站點數劃分為3段，即產生L條運行路線，如圖2所示。

圖2 車輛線路編碼示意圖Fig.2 Schematic diagram of vehicle line code

(2)初始種群

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

Step 1：隨機擾亂高概率出行OD對的排列順序。

Step 3：選擇下一對高概率OD，以插入后運行距離變化量最小為原則將其插入第l(l=1,2,…,l1)輛車的經停路徑，判斷是否滿足車容量約束和乘客時間窗約束，如果滿足則調整該車輛的初始路徑，否則將該高概率出行點對插入下一輛車的經停路徑，不斷重復上述過程，直至找到滿足約束的最佳插入位置。

Step 4：依次選擇余下的高概率出行OD對，重復Step 3直至將所有高概率出行點對都插入車輛的初始路徑中。

(3)適應度函數

為保證各條配送路徑都可滿足車容量及乘客時間窗約束，使用懲罰函數f(l)進行求解，由于相較于違反容量約束更容易違反時間窗約束，因此將違反容量約束權重α設為10，違反時間窗約束權重β設為100，因目標函數越小越好，將適應度函數設為懲罰函數的倒數，即1/f(l)。懲罰函數公式為：

f(l)=D(l)+αq(l)+βw(l)，

(15)

式中，f(l)為懲罰函數；D(l)為車輛l的總運行里程；q(l)為車輛l違反的容量約束；w(l)為車輛l違反時間約束的乘客之和。適應度函數為懲罰函數倒數。

(4)LNS局部搜索操作

LNS局部搜索采用破壞算子通過相似性計算公式，從當前解移除若干顧客，再使用修復算子，在滿足車容量約束和顧客時間約束下，將被移除的顧客重新插回到使車輛行駛距離增加最少的位置中，具體操作步驟如下。

Step 1：對初始解(12345)使用破壞算子，將初始解中的幾個相似站點(3和5)進行移除，剩下的站點(124)依舊按照初始順序排序。

Step 2：使用修復算子對移除后的解(124)進行修復，即將移除的2個站點(3和5)隨機選擇1個站點，在滿足約束的條件下重新插回124中。

Step 3：將生成的可能解(1234，1243，1324)進行比較，并從中選擇1個最優的解，如(1243)，然后再將5插入到1243中，將生成的新解(51243，15243，12543，12435)進行比較，并從中選擇1個最好的解，作為當前解，直至找到最優解。

3 案例分析

3.1 算法描述

采用MATLAB編程，對某區9月份的11 909條請求數據進行測試，通過分析該區動態巴士出行時空規律，共提取乘客該月內28 d早8:00的232條數據，對其出行OD分析獲得48 個需求站點，通過對站點間最短路距離的測量，得到站點間距離矩陣，研究區域站點分布見圖3。將車場定為第1個坐標點，坐標點1～48為乘客站點，車輛最大座位數為28，車輛平均行駛速度為25 km/h，乘客上下車時間1 s/人[18]，車輛起停時間2 s/次，車輛允許初始行駛路徑長度20 km，車輛運行成本18 元/km，違反最大載客量懲罰系數為10，違反時間窗約束懲罰系數為100。

圖3 研究區域站點分布圖Fig.3 Station distribution in study area

3.2 有效性試驗

為驗證算法的有效性，對需求進行靜態車輛調度，設置初始種群規模為100，交叉概率pc=0.9，變異概率pm=0.05，最大迭代次數為200。從圖4可以看出，迭代次數為100 次左右時，得到最優解并進入收斂狀態。

圖4 迭代次數Fig.4 Iteration times

算法連續3 次得到的最優解結果如表1所示，結果偏差為3.1%，在可接受范圍內，試驗結果表明，該算法對問題求解的穩定性較好。

表1 最優解結果Tab.1 Optimal solution result

3.3 高概率點提取策略有效性分析

從48 個需求站點中，根據需求頻率選取20 個高概率需求點，針對區域內高概率需求站點進行車輛靜態調度，各高概率站點編號及其經緯度如表2所示。

表2 高概率出行站點編號及經緯度Tab.2 Number，latitude and longitude of high probability travel stations

設置迭代次數為200，種群規模100，對比是否采用提取高概率站點策略的迭代(圖5)和最優路徑(圖6)，看出采用策略的總成本更小，可以較少車輛滿足大部分需求。

圖5 有無策略迭代Fig.5 Iteration with or without strategy

圖6 有無策略最優路徑圖Fig.6 Optimal path with/without strategy

從表3分析出，運行車輛采取該策略與未采取策略的平均總成本分別為1.04×104元和4.38×106元。結果表明，高概率點提取策略對路徑優化及乘客時間節省影響明顯。

表3 高概率點策略對比結果Tab.3 Comparison of high probability point strategies

平均候車時間為所有乘客發出請求時間與所請求車輛到達站點時間差的均值，表達式為：

(16)

選取該次調度結果中的5條線路，其靜態調度方案見表4，乘客平均候車時間為5.4 min。分析該區測試數據中該5條線路的歷史運營信息，得出乘客平均候車時間為6.23 min，為傳統公交乘客平均候車時間。乘客平均候車時間縮短13.4%。

表4 靜態階段調度方案Tab.4 Static stage scheduling scheme

靜態調度完成后，將生成的路徑存入可執行調度計劃矩陣中，為動態優化提供調用策略。

3.4 動態路徑優化分析

分3個時段統計車輛運行中8:05:00—8:20:00產生的49 個隨機出行需求，將其OD插入可執行調度計劃矩陣中，利用精確動態規劃算法進行第1輪動態優化，所得車輛運行路線見圖8。

公交平均行程時間為所有乘客在車上時間的均值，包含停車時間，表達式為：

(17)

式中，T為公交平均行程時間；Q為乘客總數；q為各乘客；tqs為乘客q上車時刻；tqd為乘客q的下車時刻。

分析該區域內所對應5條線路的歷史運營數據，統計分析得乘客的平均行程時間為23 min，為傳統公交乘客平均行程時間。第2階段優化后動態階段調度方案見表5，線路2共響應12 位乘客的實時需求，搭載乘客19 人，未響應乘客數1 人，對應公交車輛運行線路由19，7，14，12，17，3更為19，7，14，12，17，3，4。其中被響應的乘客平均行程時間20.6 min，乘客平均行程時間縮短10.4%。

表5 動態階段調度方案Tab.5 Dynamic stage scheduling scheme

如表6所示，該路徑優化模型響應乘客需求率高，車輛滿載率提升17.92%，運營成本變動合理，人均成本減少1.08元，節省了公司運營成本，提升了乘客滿意度，得到了較好的結果。

表6 兩階段調度結果分析Tab.6 Analysis of 2-stage scheduling result

4 結論

建立了二階段模型來研究需求響應型公交的運營決策，包含2個階段：車輛靜態調度、線路動態優化階段。提出了利用LNS-遺傳算法的車輛路徑規劃方法，為優化路徑設計了精確動態規劃算法的動態優化模型，結合已有初始運行路徑，及時響應實時請求，真正實現需求響應這一重要特色。

針對公交車輛調度及路徑優化，提出了通過分析歷史出行規律提取高概率需求點來降低需求離散度的方法。選取某區動態巴士運營區域9月份11 909條真實數據，根據實際運營情況，提煉了某時刻232條有效數據。通過編程數值試驗發現，該遺傳算法對于路徑的求解結果偏差較小，穩定性較好。提取高概率點后，運營成本及乘客體驗度均得到了明顯優化。二階段調度優化模型能夠最大化地利用好車輛資源，進一步節約運營成本，具有可行性和較高的使用價值，為車輛調度及路徑優化提供了應用指導。

由于系統采用的運營數據較少，客流請求量少，因此產生的孤立請求較多。該模型側重考慮乘客體驗，系統的滿載率及響應率都不夠高。對于今后如何選取運行區域可以使兩者達到最優將繼續深入研究。