需求響應(yīng)型公交車輛調(diào)度及路徑優(yōu)化

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

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

0 引言

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

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

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

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

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

1 模型構(gòu)建

1.1 問題描述

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

1.2 問題假設(shè)

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

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

(2)每輛車任務(wù)的始發(fā)與結(jié)束都發(fā)生在配送中心。

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

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

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

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

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

目標(biāo)函數(shù)為：

(1)

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

約束條件為：

(2)

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

(3)

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

(4)

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

(5)

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

1.3 車輛動態(tài)路徑優(yōu)化模型

車輛動態(tài)路徑優(yōu)化階段，每輛車可響應(yīng)周邊實時乘車請求。以里程變化最小為目標(biāo)，決策變量為每輛車經(jīng)過各站點順序，到達(dá)、出發(fā)時刻，建立模型求解。

目標(biāo)函數(shù)為：

(6)

式中，d為總運(yùn)行里程；dl為第l輛車的運(yùn)行里程。

約束條件為：

(7)

(8)

N(s),

(9)

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

(10)

(11)

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

(12)

(13)

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

(14)

2 算法設(shè)計

2.1 兩階段調(diào)度優(yōu)化模型算法流程

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

圖1 二階段調(diào)度優(yōu)化流程Fig.1 Process of 2-stage scheduling optimization

2.2 算法說明

(1)編碼

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

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

(2)初始種群

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

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

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

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

(3)適應(yīng)度函數(shù)

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

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

(15)

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

(4)LNS局部搜索操作

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

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

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

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

3 案例分析

3.1 算法描述

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

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

3.2 有效性試驗

為驗證算法的有效性，對需求進(jìn)行靜態(tài)車輛調(diào)度，設(shè)置初始種群規(guī)模為100，交叉概率pc=0.9，變異概率pm=0.05，最大迭代次數(shù)為200。從圖4可以看出，迭代次數(shù)為100 次左右時，得到最優(yōu)解并進(jìn)入收斂狀態(tài)。

圖4 迭代次數(shù)Fig.4 Iteration times

算法連續(xù)3 次得到的最優(yōu)解結(jié)果如表1所示，結(jié)果偏差為3.1%，在可接受范圍內(nèi)，試驗結(jié)果表明，該算法對問題求解的穩(wěn)定性較好。

表1 最優(yōu)解結(jié)果Tab.1 Optimal solution result

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

從48 個需求站點中，根據(jù)需求頻率選取20 個高概率需求點，針對區(qū)域內(nèi)高概率需求站點進(jìn)行車輛靜態(tài)調(diào)度，各高概率站點編號及其經(jīng)緯度如表2所示。

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

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

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

圖6 有無策略最優(yōu)路徑圖Fig.6 Optimal path with/without strategy

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

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

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

(16)

選取該次調(diào)度結(jié)果中的5條線路，其靜態(tài)調(diào)度方案見表4，乘客平均候車時間為5.4 min。分析該區(qū)測試數(shù)據(jù)中該5條線路的歷史運(yùn)營信息，得出乘客平均候車時間為6.23 min，為傳統(tǒng)公交乘客平均候車時間。乘客平均候車時間縮短13.4%。

表4 靜態(tài)階段調(diào)度方案Tab.4 Static stage scheduling scheme

靜態(tài)調(diào)度完成后，將生成的路徑存入可執(zhí)行調(diào)度計劃矩陣中，為動態(tài)優(yōu)化提供調(diào)用策略。

3.4 動態(tài)路徑優(yōu)化分析

分3個時段統(tǒng)計車輛運(yùn)行中8:05:00—8:20:00產(chǎn)生的49 個隨機(jī)出行需求，將其OD插入可執(zhí)行調(diào)度計劃矩陣中，利用精確動態(tài)規(guī)劃算法進(jìn)行第1輪動態(tài)優(yōu)化，所得車輛運(yùn)行路線見圖8。

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

(17)

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

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

表5 動態(tài)階段調(diào)度方案Tab.5 Dynamic stage scheduling scheme

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

表6 兩階段調(diào)度結(jié)果分析Tab.6 Analysis of 2-stage scheduling result

4 結(jié)論

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

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

由于系統(tǒng)采用的運(yùn)營數(shù)據(jù)較少，客流請求量少，因此產(chǎn)生的孤立請求較多。該模型側(cè)重考慮乘客體驗，系統(tǒng)的滿載率及響應(yīng)率都不夠高。對于今后如何選取運(yùn)行區(qū)域可以使兩者達(dá)到最優(yōu)將繼續(xù)深入研究。