胡 迪，靳文舟

華南理工大學(xué)土木與交通學(xué)院，廣東廣州 510640

需求響應(yīng)公交（demand response transit，DRT）是指無固定運行線路及站點，依據(jù)乘客需求前往預(yù)約地點，為乘客提供出行服務(wù)的一種公共交通服務(wù)模式．線路可偏移式需求響應(yīng)公交是一種改進的新型公交［1］，其結(jié)合了傳統(tǒng)固定線路式公交低成本和需求響應(yīng)公交靈活的特點，通常具有一條連接固定站點的線路，可服務(wù)固定站點上下車的乘客，同時可響應(yīng)線路外的乘客預(yù)約需求．CURRIE等［2］通過研究近70年的需求響應(yīng)公交發(fā)展情況，發(fā)現(xiàn)較多企業(yè)因高昂的運營成本而虧損，無法正常運營．因此，本研究考慮線路可偏移式需求響應(yīng)公交，以更低的運營成本為乘客提供更好的公共交通出行服務(wù)，對提高公共交通系統(tǒng)的服務(wù)質(zhì)量以及促進需求響應(yīng)公交運營企業(yè)發(fā)展具有重要意義．

在線路可偏移式需求響應(yīng)公交的研究方面，LI等［3］以乘客步行、等待及乘車時間最小為目標(biāo)，研究了DRT和常規(guī)公交的適宜乘客需求密度區(qū)間，得到DRT適宜的密度為4～20人/km2．邱豐等［4］建立兩階段車輛調(diào)度模型，可處理乘客實時需求，并進行實例仿真，結(jié)果表明預(yù)約出行比例越高系統(tǒng)總成本越低．龐明寶等［5］研究響應(yīng)公交站點外實時預(yù)約需求的公交調(diào)度系統(tǒng)，建立計劃調(diào)度模型與響應(yīng)實時需求的調(diào)度模型，并以單條線路進行實例分析，認(rèn)為此調(diào)度系統(tǒng)可吸引更多乘客，從而提高企業(yè)經(jīng)濟效益．

在站點選址方面，葉秋君［6］考慮了固定站點乘客、備選站點乘客和運營企業(yè)的權(quán)益，建立了以系統(tǒng)總成本最低為目標(biāo)的站點選址策略模型．靳文舟等［7］利用k-means聚類算法對乘客需求點進行聚類，獲得有限個公交?？空军c，并建立以企業(yè)利潤最大化為目標(biāo)的DRT規(guī)劃模型．龐明寶等［8］考慮到實際路網(wǎng)復(fù)雜性，引入節(jié)點重要度法，研究針對線路可偏移式DRT公交站點的評價方法，可有效評價站點布設(shè)合理性．

求解算法的改進方面，QUADRIFOGLI等［9-10］在模型中設(shè)計插入式算法，通過增加邏輯判斷約束剔除低效解，最高可減少90%的計算時間，提高了求解效率．LIU等［11］設(shè)計分支切割算法求解模型，并使用實例驗證算法的高效性．韓博文［12］將乘客需求分為靜態(tài)需求和動態(tài)需求，建立考慮實時需求的公交調(diào)度模型，并運用遺傳算法和精確算法求解．靳文舟等［13］研究考慮多車型和多運營模式的需求響應(yīng)公交靈活調(diào)度模型，并設(shè)計混合遺傳蟻群算法求解，提高了算法的精度和穩(wěn)定性．

現(xiàn)有對于線路可偏移式需求響應(yīng)公交的研究多以公交企業(yè)運營成本最低、乘客等待時間最少或服務(wù)乘客比例最高為優(yōu)化目標(biāo)建立模型，較少考慮以企業(yè)效益最大化為目標(biāo)的模型；在站點選址方面，多以原有常規(guī)公交線路為基礎(chǔ)，以原公交站點為固定站點，直接響應(yīng)站外乘客需求，服務(wù)范圍有限，而區(qū)域靈活性DRT由于計算量大，為提高求解效率而設(shè)計的算法復(fù)雜度高，導(dǎo)致研發(fā)成本與計算成本過高．為服務(wù)區(qū)域內(nèi)的更多乘客，并降低服務(wù)成本，本研究考慮先以乘客需求確定固定站點和備選站點位置，再確定DRT基準(zhǔn)運行線路，劃定各個站點服務(wù)時段，針對服務(wù)時段內(nèi)有限個站點需求，建立基于站點規(guī)劃優(yōu)化的需求響應(yīng)公交調(diào)度模型．研究內(nèi)容包括:①設(shè)計需求響應(yīng)公交服務(wù)站點選取方法，使用以DBSCAN聚類算法和k-means聚類算法為基礎(chǔ)的D-k-means聚類算法對乘客需求進行處理，根據(jù)聚類結(jié)果確定固定站點和備選站點；②設(shè)計新型預(yù)約機制，系統(tǒng)劃定各區(qū)段的可被服務(wù)時間，乘客可選擇合適的上車時間及站點；③建立線路可偏移式需求響應(yīng)公交調(diào)度優(yōu)化模型．

1 模型建立

1.1 問題描述

本研究提出的線路可偏移式需求響應(yīng)公交服務(wù)模式如圖1，根據(jù)預(yù)先收集的乘客預(yù)約情況，確定乘客預(yù)約需求量較多的固定站點和備選站點位置．在服務(wù)區(qū)域內(nèi)規(guī)劃連接所有固定站點的基準(zhǔn)運營線路，備選站點分布在基準(zhǔn)運營線路之外．公交車輛需依據(jù)乘客提出的乘車時間和地點要求，前往相應(yīng)站點完成接送乘客出行的任務(wù)．

圖1 服務(wù)模式Fig.1 The operation mode

為提高運營調(diào)度效率，為服務(wù)區(qū)域添加服務(wù)時段劃分層，即依據(jù)基準(zhǔn)線路走向和長度，預(yù)估各固定站點間的運行時間，并基于乘客出行時間統(tǒng)計規(guī)律，初步劃分服務(wù)時段與服務(wù)班次，乘客可選擇合適的服務(wù)時間并提交預(yù)約信息，服務(wù)流程如圖2．

圖2 服務(wù)流程Fig.2 The service flow

服務(wù)區(qū)域內(nèi)的乘客在預(yù)約平臺上提出預(yù)約請求，并選擇上下車站點和上車時間．現(xiàn)有若干車輛從公交車場出發(fā)，為該服務(wù)區(qū)域內(nèi)提出預(yù)約請求的部分乘客提供需求響應(yīng)公交出行服務(wù)，需要根據(jù)乘客上下車站點位置和上車時間進行車輛路徑規(guī)劃，同時確定車輛的發(fā)車時刻及預(yù)計到達(dá)各站點的時間，并通知預(yù)約乘客乘車時間和預(yù)計到達(dá)時間．

1.2 模型假設(shè)

本研究的線路可偏移式需求響應(yīng)公交調(diào)度模型有如下基本假設(shè):①乘客需在車輛發(fā)車前提交預(yù)約信息；②乘客提交預(yù)約信息后，不會更改或取消預(yù)約請求；③除了被拒絕的乘客，其他所有乘客將嚴(yán)格按照通知信息在約定時間窗內(nèi)上車，并在預(yù)約下車站點下車；④乘客所需上車及下車時間保持恒定；⑤車輛運行條件良好，不考慮交通擁堵、交通事故及交通信號燈的影響，車輛啟動和停車制動損失時間保持恒定，車輛運行速度恒定；⑥車輛車型與額定載客量已知；⑦車輛均從車場出發(fā)，完成運送任務(wù)后，回到車場；⑧為便于計算，以兩點間直線距離作為車輛運行距離．

1.3 參數(shù)變量

設(shè)xij為0-1變量，當(dāng)有車輛從i站點出發(fā)并到達(dá)j站點時，xij=1，否則xij=0；c0為車輛的單位里程運行成本；Z為調(diào)度優(yōu)化目標(biāo)函數(shù)；V為區(qū)域內(nèi)所有站點的集合；VG為所有固定站點的集合；Q為車輛的額定載客量；li為固定站點i計劃最晚發(fā)車時間；tmax為基準(zhǔn)線路相距最遠(yuǎn)的兩個固定站點間的最長運行時間；ω為拒絕預(yù)約需求數(shù)量的懲罰權(quán)重系數(shù)；dij為計算得到的站點i與站點j間的直線距離；ti為車輛到達(dá)站點i的時間，特殊的是ta和tb分別為車輛到達(dá)相距最遠(yuǎn)的兩固定站點的時間；tc為1名乘客上下車所需的時間；v為車輛在路段上的行駛速度；qi為在站點i上車的乘客數(shù)；di為在站點i下車的乘客人數(shù)；ui為離開站點i后，車上的乘客總數(shù)；N為所有站點總數(shù)；μi為站點序號．

1.4 調(diào)度模型

1.4.1 基準(zhǔn)線路規(guī)劃模型

本研究線路可偏移式需求響應(yīng)公交的基準(zhǔn)線路規(guī)劃模型為

約束條件為

其中，式（1）表示基準(zhǔn)線路規(guī)劃模型的優(yōu)化目標(biāo)是企業(yè)運營成本最小化；式（2）和式（3）表示必有車輛經(jīng)過固定站點，且只經(jīng)過1次；式（4）表示運行線路不會迂回；式（5）表示變量的取值限制．

1.4.2 線路可偏移式需求響應(yīng)公交調(diào)度優(yōu)化模型

本研究建立的線路可偏移式需求響應(yīng)公交調(diào)度優(yōu)化模型為

約束條件為

其中，式（6）表示線路可偏移式需求響應(yīng)公交調(diào)度模型的優(yōu)化目標(biāo)為企業(yè)運營成本和拒絕預(yù)約需求數(shù)量最小化；式（7）和式（8）表示必有車輛經(jīng)過固定站點，且只經(jīng)過1次；式（9）和式（10）表示對于區(qū)域內(nèi)所有站點，車輛至多到達(dá)并離開1次；式（11）表示站點p的前后狀態(tài)一致，即有車輛到達(dá)并離開或無車輛經(jīng)過該站點；式（12）表示運行線路不會迂回；式（13）表示車輛離開站點j后車上的乘客數(shù)量；式（14）表示車上的乘客數(shù)量始終小于車輛的額定載客量，并且大于在該站點上車的乘客數(shù)；式（15）表示被服務(wù)站點i和j之間的時間關(guān)系，車輛到達(dá)站點j的時間不會早于車輛離開站點i的時間、站點i乘客上下車花費時間及路段i、j間行駛時間之和；式（16）表示固定站點i的發(fā)車時間不晚于其最晚發(fā)車時間；式（17）表示基準(zhǔn)線路相距最遠(yuǎn)的兩點間實際運行時間小于限制的最大時間；式（18）表示變量的取值限制．

1.5 模型求解

1.5.1 站點聚類算法

對需求數(shù)據(jù)進行篩選與聚類處理，確定固定站點和備選站點，從而提高需求響應(yīng)公交路徑規(guī)劃效率，并降低計算成本和運營成本．由于k-means算法聚類結(jié)果受極端值影響較大［14］，本研究提出結(jié)合DBSCAN和k-means算法的D-k-means聚類算法，其可分為2個階段:①使用DBSCAN聚類算法對原始需求點數(shù)據(jù)進行預(yù)處理，將需求點分為可聚類的點集與噪聲點點集；②使用k-means算法對可聚類的點集進行聚類計算，將計算結(jié)果作為固定站點和備選站點．D-k-means算法的步驟如下．

輸入?yún)^(qū)域乘客歷史出行點、預(yù)約出行點數(shù)據(jù)集A；參數(shù)鄰域半徑δ和最小數(shù)據(jù)點閾值Minpts，參數(shù)聚類數(shù)目k；

步驟1計算數(shù)據(jù)集中每個點與其他各點間的距離；

步驟2選取數(shù)據(jù)集中任意一點，若該點δ鄰域內(nèi)點的數(shù)量大于閾值Minpts，則將該點標(biāo)記為核心點（class(i)≥1），并將其鄰域內(nèi)點劃為一類（class(i)≥0），否則將該點標(biāo)記為噪聲點（class(i)=-1）；

步驟3重復(fù)步驟2，直至所有點都被劃分為類或被標(biāo)記為噪聲點；

步驟4剔除數(shù)據(jù)集中的噪聲點；

步驟5選取包含核心點在內(nèi)的k個點作為初始中心點；

步驟6計算中心點和其他各點間的距離，將新數(shù)據(jù)集中的每個點劃入與之距離最近的類；

步驟7計算k類數(shù)據(jù)點中新的中心點；

步驟8重復(fù)步驟6和步驟7，直至每一類中每個點與中心點之間的平方距離和收斂，所有數(shù)據(jù)點被劃分入某一類并不再發(fā)生變化；

輸出聚類中心點坐標(biāo)．

1.5.2 模型求解

Gurobi是美國Gurobi公司開發(fā)的大規(guī)模優(yōu)化器，具有良好求解性能，本研究通過編寫python代碼調(diào)用Gurobi優(yōu)化求解器對調(diào)度模型進行求解．模型求解步驟如下．

輸入各站點位置、及乘客上下車人數(shù)與時間等信息；

步驟1調(diào)用Model、GRB和quicksum模塊；

步驟2創(chuàng)建模型；

步驟3使用addVar設(shè)置變量和參數(shù)；

步驟4使用setObjective和MINIMIZE創(chuàng)建企業(yè)運營成本和拒絕預(yù)約需求數(shù)量最小化目標(biāo)函數(shù)；

步驟5使用addConstr添加約束條件；

步驟6使用optimize求解模型最優(yōu)解；

輸出模型結(jié)果．

2 實例分析

為驗證本模型的有效性，以中國廣東省揭西縣南部地區(qū)為例進行案例分析．通過互聯(lián)網(wǎng)和實地調(diào)研的方式從揭西縣南部獲得部分乘客需求點地理位置信息，使用DBSCAN算法對乘客需求點數(shù)據(jù)進行預(yù)處理，將數(shù)據(jù)點劃分為可聚類點和噪聲點，使用Matlab軟件繪制計算結(jié)果，如圖3．

圖3 乘客需求點位置Fig.3 Passengers'demand locations

使用D-k-means算法篩選出6個噪聲點，依據(jù)DBSCAN算法聚類結(jié)果和實際情況，取k=4，得到需求響應(yīng)公交固定站點和備選站點，將固定站點和場站位置輸入基準(zhǔn)運行線路規(guī)劃模型進行求解，得到基準(zhǔn)運行線路長度為36.57 km，如圖4．

圖4 基準(zhǔn)運行線路Fig.4 Thebasic vehicleroute

根據(jù)基準(zhǔn)運行線路的長度和乘客在07∶00—09∶00的預(yù)約需求情況，假設(shè)車輛的運行速度為40 km/h，得到初始車輛調(diào)度時刻表，如表1．將乘客出行需求以站點序號表示，如表2．

表1 初始車輛調(diào)度時刻表Table1 The initial vehicle schedule

表2 乘客出行需求統(tǒng)計1）Table 2 The passenger travel demand statistics

將各時段乘客需求數(shù)據(jù)輸入線路可偏移式需求響應(yīng)公交調(diào)度模型，取拒絕預(yù)約需求數(shù)量的懲罰權(quán)重系數(shù)ω=1，得到車輛運行線路及實際調(diào)度時刻如表3和表4．

表3 上行班次調(diào)度時刻表Table3 Theup-linevehicleschedule

表4 下行班次調(diào)度時刻表Table4 Thedown-linevehicleschedule

以上述64位乘客需求為例進行分析，假設(shè)車輛行駛速度為40 km/h，額定載客量為7人，固定成本為5元，變動成本為1元/km，每名乘客所需上下車時間為15 s，對常規(guī)公交、站點優(yōu)化DRT和區(qū)域靈活式DRT服務(wù)效果進行對比，結(jié)果見表5．其中，常規(guī)公交、線路可偏移式DRT及區(qū)域靈活式DRT的服務(wù)乘客比例分別為92.2%、95.3%及100%；常規(guī)公交的運行線路連接了4個固定站點和6個備選站點（站點5至站點10）；區(qū)域靈活式DRT響應(yīng)了區(qū)域內(nèi)所有乘客的需求．

表5 三種公交服務(wù)模式效果Table5 Effects of the three bus service modes

算例通過服務(wù)乘客比例、運營成本及運行時間指標(biāo)對3個系統(tǒng)的性能進行對比．①常規(guī)公交可服務(wù)于公交站點周邊1 km的乘客，且無需乘客預(yù)約，但其服務(wù)比例較低，為92.2%，無法滿足部分乘客的特殊預(yù)約需求，如第2批次內(nèi)從站點5出發(fā)的乘客和其他站外上下車的乘客；②線路可偏移式DRT的服務(wù)比例為95.3%，無法服務(wù)位置偏遠(yuǎn)的乘客；③區(qū)域靈活式DRT的服務(wù)乘客比例為100%，可為服務(wù)區(qū)域內(nèi)所有乘客提供接送服務(wù)，且不需要乘客前往服務(wù)站點．

以第1批服務(wù)為例對運營成本和運行時間進行說明:常規(guī)公交運營線路總長42.4 km，需調(diào)度上行與下行兩輛車服務(wù)每批次乘客，運營成本為94.8元，單程固定運行時間為64 min，上下行車輛共用時128 min，需另加21名乘客5 min上下車時間，故服務(wù)總運行時間為133 min；站點優(yōu)化DRT上行和下行車輛運行距離分別為41.1 km和37.0 km，運營成本為88.1元，上行和下行運行時間分別為66 min和61 min；區(qū)域靈活DRT的上行和下行車輛運行距離分別為43.7 km和44.6 km，運營成本為98.3元，上下行運行時間均為68 min．可見，站點優(yōu)化DRT服務(wù)模式性能最優(yōu)，且相較于區(qū)域靈活式DRT優(yōu)勢更為明顯，運營成本由401.7元降為365.5元，下降了9%；運行時間由540 min降為513 min，下降了5%．此外，站點優(yōu)化DRT求解時間平均約1 s；區(qū)域靈活式DRT求解時間波動較大，在需求數(shù)量較多時，求解時間較長，達(dá)到220 s．

結(jié) 語

針對需求響應(yīng)公交運營成本高的問題，提出線路可偏移式需求響應(yīng)公交服務(wù)模式，建立相應(yīng)調(diào)度模型；提出了結(jié)合DBSCAN和k-means聚類算法的D-k-means聚類算法對乘客預(yù)約需求進行處理，以獲得固定站點和備選站點位置，乘客可選取合適的站點并提出預(yù)約需求；本模型使用Gurobi求解器進行求解，可獲得最優(yōu)解．實例分析結(jié)果表明，線路可偏移式需求響應(yīng)公交調(diào)度模型可行，算法求解速度較快且穩(wěn)定，生成的調(diào)度方案具有較低的運營成本，可在需求密度較低的區(qū)域為乘客提供服務(wù)質(zhì)量較高的公共交通出行服務(wù)．