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

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

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

0 引言

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

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

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

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

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

1 模型構(gòu)建

1.1 問題描述

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

1.2 問題假設(shè)

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

(1)各個(gè)站點(diǎn)最多有1個(gè)請(qǐng)求，若1個(gè)站點(diǎn)同時(shí)具有多個(gè)請(qǐng)求，在模型中將其拆分為地理位置相同的多個(gè)站點(diǎn)。

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

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

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

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

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

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

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

(1)

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

約束條件為：

(2)

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

(3)

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

(4)

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

(5)

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

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

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

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

(6)

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

約束條件為：

(7)

(8)

N(s),

(9)

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

(10)

(11)

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

(12)

(13)

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

(14)

2 算法設(shè)計(jì)

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

算法包括靜態(tài)車輛調(diào)度和動(dòng)態(tài)路徑優(yōu)化二階段。其中靜態(tài)調(diào)度是一個(gè)線性整數(shù)規(guī)劃模型，本研究基于LNS策略的遺傳算法進(jìn)行求解，采用破壞、修復(fù)算子，提升求解質(zhì)量，主體框架與傳統(tǒng)遺傳算法類似。動(dòng)態(tài)路徑優(yōu)化采取精確規(guī)劃算法，將獲得的動(dòng)態(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)型公交的初始線路是由多個(gè)站點(diǎn)按照一定順序排列成的，1,2,…,n表示服務(wù)區(qū)域內(nèi)的高概率上車站點(diǎn)，其對(duì)應(yīng)下車站點(diǎn)采用n+1,n+2,…,2n進(jìn)行編號(hào)。染色體采用整數(shù)編碼，當(dāng)站點(diǎn)數(shù)為N，最大使用車輛數(shù)為L時(shí)，染色體長度為(N+L-1)，且N+1,N+2,…,N+l-1將站點(diǎn)數(shù)劃分為3段，即產(chǎn)生L條運(yùn)行路線，如圖2所示。

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

(2)初始種群

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

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

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

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

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

為保證各條配送路徑都可滿足車容量及乘客時(shí)間窗約束，使用懲罰函數(shù)f(l)進(jìn)行求解，由于相較于違反容量約束更容易違反時(shí)間窗約束，因此將違反容量約束權(quán)重α設(shè)為10，違反時(shí)間窗約束權(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違反時(shí)間約束的乘客之和。適應(yīng)度函數(shù)為懲罰函數(shù)倒數(shù)。

(4)LNS局部搜索操作

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

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

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

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

3 案例分析

3.1 算法描述

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

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

3.2 有效性試驗(yàn)

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

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

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

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

3.3 高概率點(diǎn)提取策略有效性分析

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

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

設(shè)置迭代次數(shù)為200，種群規(guī)模100，對(duì)比是否采用提取高概率站點(diǎn)策略的迭代(圖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é)果表明，高概率點(diǎn)提取策略對(duì)路徑優(yōu)化及乘客時(shí)間節(jié)省影響明顯。

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

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

(16)

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

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

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

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

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

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

(17)

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

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

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

如表6所示，該路徑優(yōu)化模型響應(yīng)乘客需求率高，車輛滿載率提升17.92%，運(yùn)營成本變動(dòng)合理，人均成本減少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個(gè)階段：車輛靜態(tài)調(diào)度、線路動(dòng)態(tài)優(yōu)化階段。提出了利用LNS-遺傳算法的車輛路徑規(guī)劃方法，為優(yōu)化路徑設(shè)計(jì)了精確動(dòng)態(tài)規(guī)劃算法的動(dòng)態(tài)優(yōu)化模型，結(jié)合已有初始運(yùn)行路徑，及時(shí)響應(yīng)實(shí)時(shí)請(qǐng)求，真正實(shí)現(xiàn)需求響應(yīng)這一重要特色。

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

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