多分區(qū)響應(yīng)型接駁公交路徑與發(fā)車時(shí)間的協(xié)調(diào)優(yōu)化

王正武 ，譚笑 ，高愿 ，程向昕

(1.長(zhǎng)沙理工大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410114；2.長(zhǎng)沙理工大學(xué) 智能道路與車路協(xié)同湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410114)

為解決軌道公交等干線公交換乘站周邊區(qū)域乘客出行的“最后一公里”問(wèn)題，響應(yīng)型接駁公交(Responsive Feeder Transit，RFT)被提出。目前，RFT 系統(tǒng)已成為智慧公交的研究熱點(diǎn)之一，吸引了許多學(xué)者的關(guān)注。如QIU 等[1]比較分析了靈活公交、半靈活公交、固定公交的服務(wù)性能；ZHENG等[2]比較分析了低密度居民區(qū)域靈活公交的路線偏移和站點(diǎn)偏移策略；PAN 等[3?4]建立不規(guī)則服務(wù)區(qū)域RFT 的混合數(shù)規(guī)劃模型來(lái)進(jìn)行路徑優(yōu)化；韓博文等[5?6]均考慮既有靜態(tài)需求、也有動(dòng)態(tài)需求的需求響應(yīng)公交，構(gòu)建了兩階段調(diào)度優(yōu)化及其啟發(fā)式求解算法；YU 等[7]探討了實(shí)時(shí)需求下循環(huán)接駁公交的線路優(yōu)化問(wèn)題；王力生等[8]運(yùn)用圖論和動(dòng)態(tài)規(guī)劃方法分別構(gòu)建了RFT 路徑優(yōu)化模型；鄧連波等[9]構(gòu)建了常規(guī)接駁公交的線網(wǎng)優(yōu)化模型；FERNAN‐DEZ 等[10]提出基于網(wǎng)絡(luò)設(shè)計(jì)來(lái)優(yōu)化需求響應(yīng)公交的車輛路徑；王正武等[11?12]構(gòu)建了多換乘站和多車場(chǎng)協(xié)調(diào)的路徑優(yōu)化模型；王正武等[13]構(gòu)建了同時(shí)接送模式RFT 系統(tǒng)車輛路徑與發(fā)車時(shí)間的協(xié)調(diào)優(yōu)化模型；王正武等[14]構(gòu)建了RFT 分區(qū)內(nèi)的路徑協(xié)調(diào)優(yōu)化模型；CHANDRA 等[15?19]分別從服務(wù)質(zhì)量、票價(jià)、運(yùn)營(yíng)成本、乘客滿意度、乘客利益、運(yùn)營(yíng)商利潤(rùn)、系統(tǒng)成本、票價(jià)收入、乘客數(shù)、乘客出行時(shí)間、車輛運(yùn)行時(shí)間等中選擇一個(gè)或多個(gè)指標(biāo)構(gòu)建目標(biāo)函數(shù)來(lái)優(yōu)化車輛路徑或調(diào)度。到目前為止，現(xiàn)有研究主要關(guān)注的是一個(gè)分區(qū)的RFT 系統(tǒng)，很少考慮對(duì)較大服務(wù)區(qū)域進(jìn)行劃分，按分區(qū)優(yōu)化車輛路徑與調(diào)度[14]；幾乎沒(méi)有考慮邊界上需求的協(xié)調(diào)分配，實(shí)際上，邊界上乘客需求歸屬的分區(qū)不同，各分區(qū)的車輛路徑與調(diào)度方案就不同；而且，很少考慮乘客滿意度、運(yùn)營(yíng)商利潤(rùn)等的沖突，構(gòu)建多目標(biāo)優(yōu)化模型獲取Pareto 最優(yōu)解來(lái)供管理者決策。針對(duì)上述問(wèn)題，本文以多分區(qū)RFT 系統(tǒng)為研究對(duì)象，同時(shí)考慮分區(qū)邊界上的、分區(qū)內(nèi)的預(yù)約需求，兼顧運(yùn)營(yíng)商利潤(rùn)、乘客滿意度，構(gòu)建預(yù)約需求下RFT 系統(tǒng)多分區(qū)協(xié)調(diào)的、車輛路徑與發(fā)車時(shí)間協(xié)調(diào)的多目標(biāo)優(yōu)化模型，從而有效提高RFT系統(tǒng)的運(yùn)行性能。

1 多目標(biāo)協(xié)調(diào)優(yōu)化模型的構(gòu)建

1.1 問(wèn)題描述

在包含Z個(gè)分區(qū)的RFT 系統(tǒng)中(如圖1 所示)，其分區(qū)已劃定，且邊界線已知；乘客預(yù)約需求點(diǎn)的集合為I(換乘站編號(hào)為0)，所有需求點(diǎn)i∈I的坐標(biāo)(xi,yi),乘客數(shù)ni,可容忍時(shí)間窗[ETi,LTi],預(yù)約時(shí)間窗[eTi,lTi],預(yù)約上車時(shí)間(eTi+lTi)/2均已知；車內(nèi)乘客的可容忍等待時(shí)間為Emax；分區(qū)邊界上需求點(diǎn)的集合Ib,分區(qū)z內(nèi)需求點(diǎn)的集合為Iz,I=Ib∪Iz，在滿足乘客時(shí)間窗、車輛容量等約束下，通過(guò)分區(qū)邊界上乘客的合理分配、車輛路徑和發(fā)車時(shí)間的優(yōu)化，同時(shí)盡量使乘客滿意度、運(yùn)營(yíng)商利潤(rùn)最大。

圖1 多分區(qū)RFT系統(tǒng)示意圖Fig.1 Schematic diagram of multi-partition RFT system

1.2 基本假設(shè)

1) 乘客只能在預(yù)約需求點(diǎn)上車，在換乘站下車(只考慮接，送是其逆過(guò)程)；

2)乘客需求一旦被系統(tǒng)響應(yīng)便不會(huì)取消預(yù)約；所有乘客均在預(yù)約上車時(shí)間到達(dá)需求點(diǎn)，當(dāng)乘客上車后接駁車輛立即發(fā)車；接駁車輛沿需求點(diǎn)間的最短路行駛，其運(yùn)行速度恒為V；

3) 所有需求均應(yīng)被響應(yīng)，同一需求點(diǎn)只能被服務(wù)一次；如果車輛提早到達(dá)需求點(diǎn)則需在需求點(diǎn)等待乘客上車；同一需求點(diǎn)內(nèi)乘客的預(yù)約時(shí)間窗相同且都為軟時(shí)間窗，不同時(shí)間窗的乘客屬于不同的需求點(diǎn)。

1.3 模型構(gòu)建

乘客滿意度是乘客對(duì)公交服務(wù)滿意程度的衡量，本文以車輛到達(dá)需求點(diǎn)和換乘站的準(zhǔn)時(shí)性作為衡量指標(biāo)。一般地，車輛若提早到達(dá)需求點(diǎn)i，則需在需求點(diǎn)i等待乘客上車，車內(nèi)乘客的滿意度隨等待時(shí)間的增加而降低；若車輛晚點(diǎn)到達(dá)需求點(diǎn)i，則需求點(diǎn)i乘客需等待上車，上車乘客的滿意度也隨等待時(shí)間的增加而降低。設(shè)分區(qū)z班次k開始服務(wù)需求點(diǎn)i的時(shí)間為Tikz；yikz∈{0,1}，若分區(qū)z班次k服務(wù)需求點(diǎn)i則為1，否則為0。需求點(diǎn)i的乘客滿意度Sikz是車上乘客滿意度S1ikz和上車乘客滿意度S2ikz。若車輛早到，則車上乘客等待；若車輛晚到，則上車乘客等待。故根據(jù)文獻(xiàn)[5]有：

若車輛到達(dá)需求點(diǎn)i時(shí)車內(nèi)乘客數(shù)為ci，若服務(wù)區(qū)域內(nèi)所有需求點(diǎn)所有乘客的平均滿意度Z1根據(jù)加權(quán)平均確定，則可表示為：

運(yùn)營(yíng)商利潤(rùn)Z2為運(yùn)營(yíng)收益與運(yùn)營(yíng)成本之差，運(yùn)營(yíng)成本包括車輛發(fā)車及行駛成本E1(元)、車輛早到與晚到的懲罰成本E2(元)，運(yùn)營(yíng)收益即票價(jià)收入E3(元)，票價(jià)采用一票制。設(shè)分區(qū)z班次k的發(fā)車時(shí)間為fkz，需求點(diǎn)i到j(luò)的最短距離為dij，分區(qū)z班次k早到或晚到需求點(diǎn)i的懲罰成本為Wizk，班次總數(shù)為K，λ是票價(jià)，γ是車輛行駛距離與經(jīng)濟(jì)成本的轉(zhuǎn)換系數(shù)，C0為發(fā)車成本，ξ1,ξ2分別為早到和晚到的懲罰成本；分區(qū)z班次k到達(dá)需求點(diǎn)i前途經(jīng)的需求點(diǎn)集合PREikz，u為需求點(diǎn)每位乘客的上車時(shí)間；xijkz∈{0,1}，若分區(qū)z班次k途經(jīng)需求點(diǎn)i、j之間的最短路，則為1，否則為0。則運(yùn)營(yíng)商利潤(rùn)Z2為：

式(4)右邊第1～3 項(xiàng)分別為收益、行駛成本和發(fā)車成本之和、懲罰成本。式(5)表示，服務(wù)于需求點(diǎn)i的車輛在預(yù)約時(shí)間窗內(nèi)到達(dá)，則早到或晚到懲罰Wizk為0，否則按與預(yù)約時(shí)間窗的時(shí)間差進(jìn)行懲罰；式(6)是服務(wù)于需求點(diǎn)i的車輛到達(dá)需求點(diǎn)i的時(shí)間計(jì)算式。

設(shè)ypkz∈{0,1}，若邊界上的需求點(diǎn)p(p∈Ip)由分區(qū)z班次k服務(wù)需求點(diǎn)i則為1，否則為0；yqkz∈{0,1}，若班次k服務(wù)分區(qū)z內(nèi)的需求點(diǎn)q(q∈Iz)則為1，否則為0；Q為車輛容量，Tmax為最大行程時(shí)間。參考文獻(xiàn)[19]，優(yōu)化時(shí)選擇乘客滿意度和運(yùn)營(yíng)商利潤(rùn)等2 個(gè)優(yōu)化指標(biāo)，故多分區(qū)協(xié)調(diào)的、車輛路徑與發(fā)車時(shí)間協(xié)調(diào)的多目標(biāo)優(yōu)化模型可表示為：

式(7)為優(yōu)化目標(biāo)，即同時(shí)兼顧乘客滿意度、運(yùn)營(yíng)商利潤(rùn)；式(8)為車輛容量約束；式(9)表示每一個(gè)需求點(diǎn)只被一輛車服務(wù)；式(10)表示車輛從起點(diǎn)出發(fā)要返回起點(diǎn)；式(11)為分區(qū)z班次k從需求點(diǎn)i至其近鄰的下游i+1的時(shí)間關(guān)聯(lián)約束；式(12)為需求響應(yīng)公交最大行程時(shí)間約束。

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

多分區(qū)協(xié)調(diào)的、車輛路徑與發(fā)車時(shí)間協(xié)調(diào)的多目標(biāo)優(yōu)化模型是在車輛路徑與發(fā)車時(shí)間優(yōu)化的基礎(chǔ)上再協(xié)調(diào)分配邊界上的乘客需求，模型求解的關(guān)鍵還是車輛路徑與發(fā)車時(shí)間的多目標(biāo)協(xié)調(diào)優(yōu)化，因帶精英策略的快速非支配排序遺傳算法的非劣解在目標(biāo)空間分布均勻，且收斂性和魯棒性好，比較適合于求解車輛路徑問(wèn)題[20]，故本文基于帶精英策略的快速非支配排序遺傳算法來(lái)設(shè)計(jì)求解算法，算法流程如圖2所示。

圖2 算法流程圖Fig.2 Algorithm flowchart

為同時(shí)優(yōu)化發(fā)車時(shí)間和車輛路徑，圖2所示的流程是基于參考文獻(xiàn)[13]的雙遺傳算法設(shè)計(jì)的，內(nèi)循環(huán)是在發(fā)車時(shí)間確定的條件下進(jìn)行路徑優(yōu)化，外循環(huán)是選擇可接受的發(fā)車時(shí)間集。本文算法中，需求點(diǎn)和發(fā)車間隔均采用自然數(shù)編碼[21]。雙目標(biāo)問(wèn)題中，設(shè)個(gè)體i和j的目標(biāo)值分別為Z1i,Z2i,Z1j和Z2j，若對(duì)任意個(gè)體j≠i，均有Z1i>Z1j且Z2i>Z2j，則個(gè)體i為非支配個(gè)體；重復(fù)比較，可得到非支配個(gè)體集，形成第1 級(jí)非支配層；忽略第1 級(jí)非支配個(gè)體，重復(fù)比較，可得到第2級(jí)非支配層；依此類推，整個(gè)種群被分層。通過(guò)精英策略操作，從當(dāng)前父代和子代中挑選出Pop 規(guī)模的種群，選擇時(shí)從第1 級(jí)非支配層開始、同一非支配層從擁擠度[20]最大的開始。在同一非支配層，根據(jù)每一目標(biāo)函數(shù)值的升序?qū)€(gè)體排序，設(shè)邊界個(gè)體的擁擠度為∝,非邊界個(gè)體i的初始擁擠度id為0，則id的迭代式為id=|Z1i+1-Z1i-1|+|Z2i+1-Z2i-1|。

3 算例分析

換乘站O 的坐標(biāo)為(3.50,3.50)，預(yù)約需求情況見表1，分區(qū)情況如圖1 所示。Tmax=25 min，V=30 km/h，u=6 s/人；λ=1.2 元；Q=15，C0=10 元/臺(tái)，γ=1.2元/km，ξ1和ξ2分別為1.2,1.1，Emax=4 min。

表1 乘客預(yù)約信息Table 1 Passenger reservation information

3.1 不同發(fā)車時(shí)間方案的比較

在乘客需求等一定條件下，運(yùn)用本文模型獲取分區(qū)協(xié)調(diào)的、發(fā)車時(shí)間和車輛路徑協(xié)調(diào)的運(yùn)營(yíng)方案，也獲取發(fā)車時(shí)間固定下分區(qū)協(xié)調(diào)的車輛路徑方案(發(fā)車時(shí)間事先固定)，不同發(fā)車時(shí)間方案的計(jì)算結(jié)果及其比較如圖3和表2所示。由圖3可知，發(fā)車時(shí)間與路徑協(xié)調(diào)優(yōu)化下的Pareto解集對(duì)應(yīng)的點(diǎn)均位于發(fā)車時(shí)間固定僅路徑優(yōu)化下的左下方，說(shuō)明相同利潤(rùn)下，協(xié)調(diào)優(yōu)化的滿意度均高于發(fā)車時(shí)間固定的；相同滿意度下，協(xié)調(diào)優(yōu)化的利潤(rùn)均高于發(fā)車時(shí)間固定的，協(xié)調(diào)優(yōu)化的效果顯著。由表2可知，若追求利潤(rùn)最大，與發(fā)車時(shí)間固定的路徑優(yōu)化相比，發(fā)車時(shí)間與路徑協(xié)調(diào)優(yōu)化的利潤(rùn)和滿意度分別增加了1.1%和0.01；若追求滿意度最大，利潤(rùn)和滿意度分別增加了8.4%和0.05；若獲取利潤(rùn)與滿意度均較佳的方案(對(duì)應(yīng)圖3 的A2 和B2)，利潤(rùn)和滿意度分別增加了4.7%和0.07。

表2 不同發(fā)車時(shí)間方案計(jì)算結(jié)果的比較Table 2 Comparison of calculation results of different departure time schemes

圖3 不同發(fā)車時(shí)間方案的Pareto解集Fig.3 Pareto solution set of different departure time schemes

3.2 邊界上需求點(diǎn)不同分配方式的比較

在乘客需求等一定條件下，運(yùn)用本文模型獲取分區(qū)協(xié)調(diào)的、發(fā)車時(shí)間和車輛路徑協(xié)調(diào)的運(yùn)營(yíng)方案，也獲取邊界上需求固定分配條件下的發(fā)車時(shí)間和車輛路徑方案，邊界上需求點(diǎn)不同分配方式的計(jì)算結(jié)果及其比較如圖4 和表3 所示。由圖4可知，邊界上需求協(xié)調(diào)分配的Pareto解集對(duì)應(yīng)的點(diǎn)均位于固定分配的Pareto解集的左下方，說(shuō)明相同利潤(rùn)下，協(xié)調(diào)分配的滿意度要明顯高于固定分配的；相同滿意度下，協(xié)調(diào)分配的利潤(rùn)要明顯高于固定分配的，協(xié)調(diào)分配的效果顯著。由表3 可知，若追求運(yùn)營(yíng)商利潤(rùn)最大，與固定分配相比，協(xié)調(diào)分配的利潤(rùn)增加了7.4%，但滿意度有所降低；若追求滿意度最大，利潤(rùn)增加了5.3%，但滿意度相同；若獲取利潤(rùn)與滿意度均較佳的方案(圖4 中的A2 和C2)，協(xié)調(diào)分配的利潤(rùn)和滿意度分別增加了5.5%和0.02，說(shuō)明邊界上需求協(xié)調(diào)分配的利潤(rùn)增加較明顯，但滿意度變化趨勢(shì)不明顯。

圖4 邊界上需求點(diǎn)不同分配方式的Pareto解集Fig.4 Pareto solution set of different distribution modes of demand points on the boundary

表3 邊界上需求點(diǎn)不同分配方式計(jì)算結(jié)果的比較Table 3 Comparison of calculation results under different allocation methods of demand points on the boundary

3.3 車輛容量的影響分析

在乘客需求等一定條件下，只改變車輛容量(車輛容量改變，其發(fā)車成本也將隨之改變)，分析容量變化對(duì)運(yùn)營(yíng)商利潤(rùn)、乘客滿意度、行駛總里程的影響。設(shè)定車輛基準(zhǔn)容量為15人/車(發(fā)車成本為10元/臺(tái))，分析容量增至25人/車(發(fā)車成本為13元/臺(tái))后對(duì)優(yōu)化方案的影響，計(jì)算結(jié)果分別見表4和圖5。

圖5 接駁車容量變化下的Pareto解集Fig.5 Pareto solution set under the change of feeder capacity

表4 車輛容量變化下計(jì)算結(jié)果的比較Table 4 Comparison of calculated results between vehicle capacity changes

由圖5可知，容量15座下的Pareto解集對(duì)應(yīng)的點(diǎn)均位于容量25座下的左下方，說(shuō)明相同利潤(rùn)下，15座的滿意度要明顯高于25座的；相同滿意度下，15 座的利潤(rùn)要明顯高，15 座的更適合當(dāng)前條件下的接駁服務(wù)。由表4可知，若追求利潤(rùn)最大，與25座的相比，容量15 座接駁車的利潤(rùn)和滿意度分別增加了2.63%，0.08；若追求滿意度最大，利潤(rùn)和滿意度分別增加了0.8%，0.06；若獲取利潤(rùn)與滿意度均較佳的方案(對(duì)應(yīng)圖5 中的A2 和D2)，利潤(rùn)和滿意度分別增加了2%，0.08，說(shuō)明車輛容量的大小會(huì)顯著影響系統(tǒng)性能。

4 結(jié)論

1) 兼顧運(yùn)營(yíng)商利潤(rùn)和乘客滿意度，構(gòu)建了邊界上需求點(diǎn)協(xié)調(diào)分配的、發(fā)車時(shí)間和車輛路徑協(xié)調(diào)的多目標(biāo)優(yōu)化模型及其帶精英策略的快速非支配排序遺傳算法。

2) 算例結(jié)果表明，發(fā)車時(shí)間方案、邊界上需求的分配方式、車輛容量對(duì)多分區(qū)RFT 系統(tǒng)的多目標(biāo)協(xié)調(diào)有顯著影響。相同利潤(rùn)下，發(fā)車時(shí)間與路徑協(xié)調(diào)優(yōu)化的滿意度均高于發(fā)車時(shí)間固定僅路徑優(yōu)化的；與邊界上需求的固定分配相比，邊界上需求的協(xié)調(diào)分配能獲得更高的滿意度；相同滿意度下也類似。考慮車輛容量對(duì)利潤(rùn)和滿意度的影響，接駁區(qū)域內(nèi)一定需求量下應(yīng)有最適宜的接駁車輛容量，宜配備合適的車型。

3) 進(jìn)一步研究工作是分區(qū)范圍與數(shù)量、車輛路徑與調(diào)度的多目標(biāo)協(xié)調(diào)優(yōu)化。