常玉林，蔡宇航，孫超*，王建

(1.江蘇大學(xué)，汽車與交通工程學(xué)院，江蘇鎮(zhèn)江 212013；2.東南大學(xué)，a.城市智能交通江蘇省重點(diǎn)實(shí)驗(yàn)室，b.交通學(xué)院，南京 211189；3.南通理工學(xué)院，汽車工程學(xué)院，江蘇南通 226002)

0 引言

需求響應(yīng)公交(Demand-Responsive Transit,DRT)根據(jù)乘客需求起訖點(diǎn)規(guī)劃公交路徑，為乘客出行提供“門(mén)到門(mén)”服務(wù)，提高公共交通服務(wù)質(zhì)量與吸引力。為擴(kuò)大軌道和干線公交等公共交通服務(wù)的深度和廣度，緩解乘客“最后一公里”的出行難題，“軌道交通+DRT”的需求響應(yīng)型接駁公交(Demand-Responsive Feeder Transit,DRFT)應(yīng)運(yùn)而生。DRFT改變傳統(tǒng)公交“人等車”為“車找人”，將出行者的現(xiàn)場(chǎng)等待轉(zhuǎn)變?yōu)榫€上排隊(duì)規(guī)劃，減少因信息不對(duì)稱造成的出行焦慮和資源浪費(fèi)[1]。

隨著接駁公交的推廣，能否將其與軌道交通服務(wù)緊密結(jié)合，實(shí)現(xiàn)“出行即服務(wù)”，是目前亟需解決的主要問(wèn)題。學(xué)者們?cè)贒RFT 路徑規(guī)劃模型方面開(kāi)展了廣泛的研究，YANG等[2]通過(guò)均值-方差模型表達(dá)行駛時(shí)間的不確定性，引入了嵌入時(shí)間偏差懲罰模型的彈性需求函數(shù)；孫倩等[3]構(gòu)建隨機(jī)到站時(shí)間服從隨機(jī)分布下的DRFT模型，設(shè)計(jì)啟發(fā)式算法求解，并進(jìn)行數(shù)值實(shí)驗(yàn)驗(yàn)證；HE 等[4]考慮乘客攜帶大件行李和行程時(shí)間的不確定性，構(gòu)建以運(yùn)營(yíng)成本最小為目標(biāo)的混合整數(shù)線性規(guī)劃模型。上述研究考慮的均為理想條件模型。

目前，部分學(xué)者已經(jīng)開(kāi)始關(guān)注如何提高接駁公交效率，對(duì)實(shí)際情景下應(yīng)用開(kāi)展研究。以往研究普遍假設(shè)OD 對(duì)間車輛的行駛速度或行駛時(shí)間是恒定的，已有考慮時(shí)變車速的線路優(yōu)化研究中，多是針對(duì)常規(guī)公交路徑規(guī)劃展開(kāi)的。在關(guān)于DRFT 的研究中，WU等[5]按不同時(shí)間段對(duì)需求進(jìn)行分組，考慮由于道路擁堵而產(chǎn)生延誤，構(gòu)建隨時(shí)變出行時(shí)間的優(yōu)化模型。王正武等[6]考慮路段行程時(shí)間的時(shí)變特性，提出一種在動(dòng)態(tài)行程時(shí)間下的響應(yīng)型接駁公交路徑優(yōu)化方法。LEE等[7]開(kāi)發(fā)一種基于區(qū)域的新型時(shí)空網(wǎng)絡(luò)，根據(jù)區(qū)域間時(shí)變的行駛時(shí)間調(diào)度車輛。

綜上所述，關(guān)于DRFT的模型及應(yīng)用研究已取得較大進(jìn)展。但目前研究中多將DRT 中OD 矩陣的“多對(duì)多”模式變?yōu)椤岸鄬?duì)一”模式，而忽視了接駁出行的特性以及乘客需求的異質(zhì)性，降低了公交的服務(wù)質(zhì)量；已有研究的時(shí)變車速大多采用速度時(shí)間依賴函數(shù)刻畫(huà)，忽略了道路出行時(shí)間的彈性變化，導(dǎo)致丟失部分可行解，一定程度上降低了公交的運(yùn)營(yíng)效率。

因此，本文研究考慮出行目的異質(zhì)性的DRFT車速引導(dǎo)與路徑規(guī)劃協(xié)同優(yōu)化問(wèn)題(DRFT-SG,Speed Guidance)。根據(jù)軌道交通接駁出行目的異質(zhì)性，將前往接駁樞紐站的乘客分為兩類：普通乘客按需請(qǐng)求和通勤乘客按時(shí)請(qǐng)求，并進(jìn)行規(guī)范化處理，統(tǒng)一納入模型；利用時(shí)變的區(qū)間車速表征道路彈性行駛時(shí)間，擴(kuò)大模型解空間，同時(shí)，給出引導(dǎo)車速，提供更加精細(xì)化的運(yùn)營(yíng)服務(wù)。

1 DRFT-SG問(wèn)題描述

1.1 問(wèn)題描述

DRFT 在軌道樞紐的客流吸引范圍內(nèi)，設(shè)置響應(yīng)型接駁公交服務(wù)：前往接駁樞紐站的乘客提交乘車人數(shù)和期望接駁的時(shí)間和地點(diǎn)，在系統(tǒng)進(jìn)行規(guī)劃后告知乘客規(guī)劃的上車和下車時(shí)間，同時(shí)，輸出每輛公交車輛的路徑順序和相鄰請(qǐng)求間的引導(dǎo)車速。本文考慮乘客需求異質(zhì)性，基于車速引導(dǎo)協(xié)同優(yōu)化路徑規(guī)劃，研究問(wèn)題如圖1所示。

圖1 動(dòng)態(tài)響應(yīng)型接駁公交示意Fig.1 Diagram of dynamic-responsive feeder transit

1.2 異質(zhì)性與引導(dǎo)車速

根據(jù)乘客接駁出行需求的異質(zhì)性，將乘客請(qǐng)求分為普通乘客的按需請(qǐng)求(G類)和通勤乘客的按時(shí)請(qǐng)求(C 類)。G 類乘客對(duì)接駁換乘時(shí)間不敏感，一般希望盡快乘車，因此，需要給出期望上車時(shí)間ei；C類乘客更加關(guān)注到站時(shí)間能否滿足換乘需求，通過(guò)對(duì)換乘目標(biāo)車次時(shí)間和自身情況判斷需要到達(dá)樞紐站的換乘時(shí)間，給出期望下車時(shí)間通過(guò)請(qǐng)求上車地點(diǎn)經(jīng)緯度(Xi,Yi)計(jì)算最小乘車時(shí)間Zi和最大乘車時(shí)間Mi=f(Zi)，并預(yù)設(shè)C類請(qǐng)求的上車時(shí)間窗大小WC和G類請(qǐng)求的下車時(shí)間窗大小WG。將異質(zhì)性乘客請(qǐng)求規(guī)范化處理，得到出行上車時(shí)間窗[ei,li] 和下車時(shí)間窗，如圖2 所示。規(guī)范化處理得到統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)，可以將兩類乘客請(qǐng)求信息同時(shí)作為模型輸入數(shù)據(jù)，通過(guò)調(diào)節(jié)參數(shù)WC和WG可以滿足不同乘客的個(gè)性化需求，Mi確保乘客乘車時(shí)長(zhǎng)，約束車輛運(yùn)行距離，提高服務(wù)質(zhì)量。

圖2 異質(zhì)性請(qǐng)求信息規(guī)范化Fig.2 Standardization of heterogeneous request information

通過(guò)分析路網(wǎng)中道路時(shí)變速度的屬性，估計(jì)彈性行駛速度區(qū)間的最大值和最小值。在道路時(shí)變的區(qū)間速度范圍內(nèi)規(guī)劃路徑，得到滿足前后鄰接關(guān)系的規(guī)劃時(shí)間窗及路徑順序。由規(guī)劃時(shí)間窗計(jì)算相鄰請(qǐng)求的引導(dǎo)車速可行域，并以相鄰規(guī)劃時(shí)間窗中值計(jì)算引導(dǎo)車速，如圖3所示。

圖3 引導(dǎo)車速計(jì)算示意Fig.3 Diagram of guide speed calculation

1.3 滾動(dòng)時(shí)域優(yōu)化

滾動(dòng)時(shí)域優(yōu)化采取基于周期和事件驅(qū)動(dòng)的混合調(diào)度策略，按照單位時(shí)域時(shí)長(zhǎng)S將服務(wù)時(shí)間窗口化為[E(s),L(s)]，在每個(gè)時(shí)域開(kāi)始時(shí)進(jìn)行周期驅(qū)動(dòng)靜態(tài)規(guī)劃。根據(jù)滾動(dòng)時(shí)域優(yōu)化思想，按照提交請(qǐng)求時(shí)間劃分，將早于服務(wù)時(shí)間提交的乘客請(qǐng)求視為靜態(tài)請(qǐng)求，服務(wù)時(shí)間內(nèi)提交的乘客請(qǐng)求視為動(dòng)態(tài)請(qǐng)求。根據(jù)規(guī)范上車時(shí)間窗開(kāi)端ei所在時(shí)域，把在當(dāng)前時(shí)域s內(nèi)提交的動(dòng)態(tài)請(qǐng)求分為3類：(1)位于當(dāng)前時(shí)域s內(nèi)的動(dòng)態(tài)即時(shí)請(qǐng)求，由于該時(shí)域已靜態(tài)規(guī)劃，且為了保護(hù)乘客利益不可更改，該類請(qǐng)求觸發(fā)事件驅(qū)動(dòng)，通過(guò)動(dòng)態(tài)插入模型在當(dāng)前時(shí)域已規(guī)劃的路徑內(nèi)進(jìn)行插入；(2)大于時(shí)域s+1 的偽動(dòng)態(tài)請(qǐng)求Nadv；(3) 位于時(shí)域s+1 內(nèi)的動(dòng)態(tài)非即時(shí)請(qǐng)求，該類請(qǐng)求將與共同規(guī)劃，當(dāng)與之和達(dá)到定量更新閾值β時(shí)，進(jìn)行基于事件的周期驅(qū)動(dòng)。

為使相鄰時(shí)域相關(guān)聯(lián)，提高公交滿載率，本文定義截?cái)嗦窂降母拍睿簳r(shí)域s內(nèi)規(guī)劃的路徑，在下一時(shí)域內(nèi)到達(dá)接駁樞紐站，且未滿載，可繼續(xù)添加請(qǐng)求。將每條截?cái)嗦窂睫D(zhuǎn)化為下一時(shí)域的虛擬請(qǐng)求繼續(xù)規(guī)劃，以最后1個(gè)請(qǐng)求的規(guī)劃上車時(shí)間窗作為虛擬請(qǐng)求的上車時(shí)間窗，以路徑的到達(dá)時(shí)間窗作為虛擬請(qǐng)求的下車時(shí)間窗，以路徑已規(guī)劃人數(shù)作為虛擬請(qǐng)求的上車人數(shù)，約束為路線中第1個(gè)服務(wù)的請(qǐng)求。滾動(dòng)時(shí)域下，動(dòng)態(tài)請(qǐng)求乘客劃分過(guò)程如圖4所示，請(qǐng)求3 和請(qǐng)求5 為時(shí)域s-2 的偽動(dòng)態(tài)請(qǐng)求，

圖4 動(dòng)態(tài)請(qǐng)求乘客劃分過(guò)程Fig.4 Dynamically request passenger partitioning process

請(qǐng)求1、請(qǐng)求4 及請(qǐng)求6 為時(shí)域s-1 的動(dòng)態(tài)非即時(shí)請(qǐng)求，請(qǐng)求2和請(qǐng)求7為時(shí)域s的動(dòng)態(tài)即時(shí)請(qǐng)求。

2 模型構(gòu)建

本文研究的車速引導(dǎo)與路徑規(guī)劃協(xié)同優(yōu)化問(wèn)題采用滾動(dòng)時(shí)域優(yōu)化思想，路徑規(guī)劃過(guò)程分為基于周期驅(qū)動(dòng)的靜態(tài)規(guī)劃模型和基于事件驅(qū)動(dòng)的動(dòng)態(tài)插入模型。其中，靜態(tài)規(guī)劃模型適用于需求信息已知的初始線路優(yōu)化，包括該時(shí)域內(nèi)的靜態(tài)預(yù)約請(qǐng)求和偽動(dòng)態(tài)請(qǐng)求，上一時(shí)域的動(dòng)態(tài)非即時(shí)請(qǐng)求；動(dòng)態(tài)插入模型適用于靜態(tài)規(guī)劃路徑后，對(duì)動(dòng)態(tài)即時(shí)請(qǐng)求的優(yōu)化調(diào)整。

2.1 模型假設(shè)

(1)服務(wù)區(qū)域已知。本模型以乘客提交上車地點(diǎn)為輸入，僅限服務(wù)區(qū)域內(nèi)的乘客請(qǐng)求。

(2)服務(wù)時(shí)間已知。設(shè)定服務(wù)時(shí)間為6:00-18:00，該范圍內(nèi)提交的請(qǐng)求視為動(dòng)態(tài)請(qǐng)求。

(3)所有靜態(tài)預(yù)約、動(dòng)態(tài)非即時(shí)請(qǐng)求及偽動(dòng)態(tài)請(qǐng)求均需要被滿足，且僅服務(wù)1次。

(4)通勤乘客提交上車地點(diǎn)與期望到達(dá)時(shí)間，普通乘客提交上車地點(diǎn)與期望出發(fā)時(shí)間。

(5)不設(shè)置車輛數(shù)目，根據(jù)模型輸入請(qǐng)求規(guī)模規(guī)劃路線數(shù)量、車型及發(fā)車時(shí)刻表。

2.2 靜態(tài)規(guī)劃模型

靜態(tài)規(guī)劃模型建模符號(hào)如表1所示。

表1 靜態(tài)規(guī)劃模型符號(hào)說(shuō)明Table 1 Notation for static programming model

式中：Λ為解空間。

目標(biāo)函數(shù)F1、F2為

解空間Λ為

模型為雙目標(biāo)規(guī)劃：式(2)為系統(tǒng)運(yùn)營(yíng)成本F1，包括車輛單位運(yùn)營(yíng)成本和發(fā)車固定成本；式(3)為出行者時(shí)間成本F2，包括C(s)類乘客早于期望到站的時(shí)間差，G(s)類乘客晚于期望上車的時(shí)間差，總體乘客N(s)實(shí)際乘車時(shí)間與最小乘車時(shí)間差。式(4)～式(19)為約束條件：式(4)和式(5)分別表示保證在乘客的時(shí)間窗內(nèi)服務(wù)；式(6)為路徑靈活度約束，到達(dá)樞紐站的時(shí)間窗不小于松弛時(shí)間閾值；式(7)～式(9)為路徑連續(xù)性約束，每條路徑只有一個(gè)開(kāi)端和結(jié)尾；式(10)表示每個(gè)請(qǐng)求有且只有一輛車服務(wù)；式(11)～式(13)為時(shí)間連續(xù)性的變化關(guān)系；式(14)和式(15)分別表示客流遞推關(guān)系和最大容量約束；式(16)消除子回路；式(17)表示兩個(gè)不同請(qǐng)求點(diǎn)被同一輛車輛服務(wù)的順序；式(18)表示引導(dǎo)車速時(shí)域約束；式(19)表示決策變量約束。

2.3 動(dòng)態(tài)插入模型

為保護(hù)已規(guī)劃的乘客利益，避免浪費(fèi)計(jì)算資源，動(dòng)態(tài)即時(shí)請(qǐng)求只在該時(shí)域內(nèi)已規(guī)劃的路徑中插入，而不改變已規(guī)劃路徑的順序。根據(jù)先進(jìn)先出準(zhǔn)則和貪婪規(guī)則，對(duì)每個(gè)動(dòng)態(tài)即時(shí)請(qǐng)求立即進(jìn)行插入。針對(duì)將新的節(jié)點(diǎn)插入到已知路徑中的情景，SOLOMON[8]提出基于最小成本的最鄰近法(Nearest Neighbor algorithms based on minimum Cost,NNC)，即將一個(gè)額外的節(jié)點(diǎn)插入已知線路網(wǎng)絡(luò)中，要求插入后增加的“距離”成本最小。本文動(dòng)態(tài)插入模型在NNC 基礎(chǔ)上改進(jìn)，將“距離”定義為時(shí)空鄰接度mij，包括空間鄰接度和時(shí)間鄰接度，即

式中：λ1和λ2為時(shí)空比例系數(shù)；和為上車端和下車端時(shí)空關(guān)系。

3 滾動(dòng)時(shí)域-文化基因算法

DRFT 車速引導(dǎo)與路徑規(guī)劃協(xié)同優(yōu)化的本質(zhì)為車輛路徑規(guī)劃，是典型的NP-hard 問(wèn)題[9-10]，模型求解時(shí)間隨著請(qǐng)求規(guī)模呈指數(shù)級(jí)增長(zhǎng)，本文設(shè)計(jì)滾動(dòng)時(shí)域-文化基因算法(Rolling Horizon Optimization-Memetic Algorithm,RHO-MA)的啟發(fā)式算法求解該問(wèn)題，如圖5所示。

圖5 RHO-MA算法流程Fig.5 Flow chart of RHO-MA algorithm

RHO 策略通過(guò)周期驅(qū)動(dòng)將服務(wù)時(shí)間窗口化，減小問(wèn)題規(guī)模，利用文化基因算法(Memetic Algorithm,MA)求解每個(gè)時(shí)域內(nèi)的靜態(tài)規(guī)劃問(wèn)題，通過(guò)事件驅(qū)動(dòng)將動(dòng)態(tài)出現(xiàn)的請(qǐng)求分類，并對(duì)即時(shí)請(qǐng)求通過(guò)NNC 算法進(jìn)行插入處理，對(duì)非即時(shí)請(qǐng)求累計(jì)達(dá)到閾值啟動(dòng)周期驅(qū)動(dòng)。

MA 算法由以NSGA-II 作為全局搜索算子和以自適應(yīng)大鄰域搜索算法(Adaptive Large Neighborhood Search,ALNS)作為局部搜索算子組成，通過(guò)全局搜索來(lái)廣闊地探索解空間，對(duì)搜索到較好的區(qū)域通過(guò)局部搜索進(jìn)一步細(xì)化探索，從而快速地逼近局部極值點(diǎn)，兼有全局優(yōu)化和局部搜索能力。

3.1 NSGA-II全局搜索

本文文化基因算法的全局搜索算子借鑒多目標(biāo)進(jìn)化算法NSGA-II進(jìn)行設(shè)計(jì)，采用基于非支配排序和擁擠距離的個(gè)體評(píng)價(jià)機(jī)制。

3.1.1 染色體編碼方式

采用車輛行駛路徑順序的自然數(shù)編碼方式，用自然數(shù)表示該時(shí)域內(nèi)請(qǐng)求，0表示樞紐站，用來(lái)區(qū)分不同車輛的行駛路徑。為提高系統(tǒng)效率，采取多車型求解，染色體編碼時(shí)只限制每條路徑不超過(guò)最大車型容量，根據(jù)規(guī)劃結(jié)果選取合適車型。

3.1.2 初始種群的生成

文獻(xiàn)[11]提出初始種群的生成會(huì)影響到算法的收斂速度和帕累托解的質(zhì)量，一個(gè)滿足問(wèn)題特性且質(zhì)量較好的初始種群對(duì)算法的計(jì)算效率影響很大。本文采取3種方法生成初始種群，對(duì)F1較優(yōu)采用空間鄰接度最小生成初始種群Pop1；對(duì)F2較優(yōu)采用時(shí)間鄰接度最大生成初始種群Pop2；以及為了保持初始種群多樣性而隨機(jī)產(chǎn)生任意的一些解Pop3。計(jì)算在時(shí)域s允許速度區(qū)間下，滿足任意兩個(gè)請(qǐng)求間的時(shí)空關(guān)系≥0 和≥θ，則鄰接矩陣元素Dij=1。根據(jù)鄰接矩陣D，初始解的構(gòu)造步驟如下：

Step 1 篩選鄰接矩陣D所有前鄰接點(diǎn)為0 的請(qǐng)求，即沒(méi)有請(qǐng)求可到達(dá)，以每個(gè)請(qǐng)求作為開(kāi)端生成初始路徑集。

Step 3 當(dāng)前構(gòu)造路徑集中每條路徑的最后一個(gè)請(qǐng)求沒(méi)有滿足約束條件時(shí)，則刪除已規(guī)劃請(qǐng)求，更新鄰接矩陣D，并回到Step 1；否則，回到Step 2，直至規(guī)劃所有請(qǐng)求。

3.1.3 交叉算子

全局搜索通過(guò)父代種群的交叉操作進(jìn)行擾動(dòng)，并得到子代種群，避免陷入局部最優(yōu)。傳統(tǒng)交叉算子隨機(jī)選擇交叉位置，經(jīng)過(guò)交叉往往會(huì)破壞優(yōu)良的基因結(jié)構(gòu)或生成不合法的個(gè)體。針對(duì)DRFT-SG問(wèn)題，設(shè)計(jì)一種考慮路徑優(yōu)選的交叉算子：

3.2 AVNS局部搜索

MA 算法局部搜索算子采用自適應(yīng)變鄰域搜索，通過(guò)改變鄰域結(jié)構(gòu)拓展搜索范圍，以獲得局部最優(yōu)解?？紤]NP-hard 大規(guī)模鄰域結(jié)構(gòu)的特性，在搜索某一鄰域結(jié)構(gòu)需要較多計(jì)算資源，且在種群的不同成熟期每個(gè)鄰域結(jié)構(gòu)適用度不同，因此，本文改進(jìn)了一種基于鄰域選擇概率自適應(yīng)的變鄰域搜索算法(AVNS)。該算法通過(guò)不同搜索時(shí)段鄰域動(dòng)作的搜索效率對(duì)選擇概率值進(jìn)行自適應(yīng)調(diào)整，同時(shí)，引入隨機(jī)選擇概率保證鄰域結(jié)構(gòu)全面性。

3.2.1 鄰域動(dòng)作類型及定義

針對(duì)DRFT-SG 問(wèn)題及編碼方式，改進(jìn)和設(shè)計(jì)了3 種鄰域搜索算子，與已有的2-Opt*和Swap 構(gòu)成5個(gè)鄰域搜索算子用于鄰域搜索，鄰域動(dòng)作及符號(hào)如表2所示。

表2 鄰域動(dòng)作及符號(hào)Table 2 Neighborhood actions and symbols

A1——隨機(jī)刪除個(gè)體中1條短路徑，將該路徑中的請(qǐng)求插入到其他路徑中。

A2——選取某個(gè)路徑中若干連續(xù)行程鏈予以刪除，再將其插入到其他路徑中。

A3——選取2條路徑中若干連續(xù)行程鏈，交換位置。

A4——隨機(jī)選擇2條路徑，將每條路徑從中間的某個(gè)位置斷開(kāi)，并交叉重連，形成2條新的路徑。

A5——隨機(jī)選擇2 個(gè)不同的請(qǐng)求，將其交換位置。

3.2.2 鄰域動(dòng)作選擇及更新

在算法中首先賦予鄰域動(dòng)作相同初始值，在鄰域動(dòng)作更新選擇過(guò)程中，根據(jù)上一次迭代過(guò)程各鄰域動(dòng)作效率，選擇概率的更新與歸一化。為避免局部搜索過(guò)程丟失支配其他個(gè)體的帕累托最優(yōu)解，采取新個(gè)體不被搜索個(gè)體支配即可接收為新解的接收準(zhǔn)則。鄰域動(dòng)作選擇及更新算法偽代碼如表3所示。

表3 鄰域動(dòng)作選擇及更新算法偽代碼Table 3 Pseudocode of neighborhood action selection and update

3.3 搜索強(qiáng)度自適應(yīng)調(diào)節(jié)

當(dāng)ηg較大時(shí)，局部搜索效率較高，屬于在編碼空間上全局探索的進(jìn)化前期階段，此時(shí)，個(gè)體平均適應(yīng)度較低，種群多樣性較高，應(yīng)采用較大的非支配集個(gè)體交叉率pc促進(jìn)新基因產(chǎn)生。隨著種群趨于成熟，局部搜索效率逐漸降低，ηg向0 收斂。為了使優(yōu)良基因結(jié)構(gòu)得以延續(xù)保存，應(yīng)適當(dāng)降低pc，同時(shí)，提高支配集個(gè)體交叉率，從而使較劣個(gè)體可以一直以較大概率對(duì)解空間進(jìn)行搜索，加快更優(yōu)模式的產(chǎn)生，提高算法的尋優(yōu)能力和計(jì)算資源分配。此時(shí)，可調(diào)整局部搜索最大次數(shù)，改善計(jì)算資源低效利用的情況，使當(dāng)局部搜索效率越小時(shí)搜索次數(shù)越少?；谏鲜隹紤]，設(shè)置如下調(diào)節(jié)機(jī)制：第g+1 代非支配集個(gè)體交叉率、支配集個(gè)體交叉率及最大搜索次數(shù)為

式中：Mgen為最大遺傳代數(shù)；|R|為支配層級(jí)個(gè)數(shù)；Ri為支配解所在層級(jí)數(shù)；pcmax、pcmin為最大、最小個(gè)體交叉率；Hmax、Hmin為最大/最小搜索次數(shù)。

4 實(shí)驗(yàn)與結(jié)果分析

利用改編的Sioux Falls 網(wǎng)絡(luò)驗(yàn)證所提出的模型和算法的有效性，并進(jìn)行參數(shù)敏感性分析。進(jìn)一步地，以許昌東站為背景，生成一個(gè)響應(yīng)早高峰的算例，對(duì)模型的適用性進(jìn)行仿真分析。算法編程采用MATLAB R2016b 在RAM16G，CPU3.6 GHz 的個(gè)人PC機(jī)上運(yùn)行。

4.1 數(shù)值實(shí)驗(yàn)

基于Sioux Falls網(wǎng)絡(luò)生成測(cè)試算例，該網(wǎng)絡(luò)有24 個(gè)節(jié)點(diǎn)和38 條雙向路段，各路段權(quán)值為節(jié)點(diǎn)間距離。以節(jié)點(diǎn)10為接駁樞紐站點(diǎn)，如圖6所示。

圖6 Sioux Falls測(cè)試網(wǎng)絡(luò)Fig.6 Sioux Falls test network

以文獻(xiàn)[12]中B&B 算法計(jì)算參數(shù)與求解結(jié)果為參照，通過(guò)構(gòu)造6個(gè)不同規(guī)模的算例場(chǎng)景驗(yàn)證模型和算法的有效性，對(duì)每個(gè)場(chǎng)景反復(fù)測(cè)試，結(jié)果如表4所示。

表4 B&B與RHO-MA求解結(jié)果對(duì)比Table 4 Comparison of B&B and RHO-MA solution results

表4中，運(yùn)營(yíng)成本和計(jì)算時(shí)間結(jié)果顯示了在可接受范圍內(nèi)本文模型的正確性和算法的有效性。由于文獻(xiàn)[12]中的B&B屬于精確算法，在求解小規(guī)模算例(小于20)時(shí)效率更高，但在較大規(guī)模算例(20，25，30)中，本文的啟發(fā)式算法RHO-MA更有優(yōu)勢(shì)，計(jì)算時(shí)間分別降低了62.9%，75.02%，80.22%。在RHO-MA 中，恒定車速與引導(dǎo)車速計(jì)算結(jié)果表明，在需求規(guī)模較大時(shí)，區(qū)間車速提供了更大的解空間，通過(guò)車速引導(dǎo)可以有效提升求解質(zhì)量，降低運(yùn)營(yíng)成本，同時(shí)，需要較大的計(jì)算資源。

4.2 敏感性分析

需求響應(yīng)型接駁公交屬于動(dòng)態(tài)車輛路徑問(wèn)題，影響其適用性的主要參數(shù)是需求規(guī)模和動(dòng)態(tài)度[13]，其中，動(dòng)態(tài)度為動(dòng)態(tài)請(qǐng)求占總請(qǐng)求的比例。通過(guò)按梯度設(shè)定需求密度和動(dòng)態(tài)度[8]，對(duì)模型的雙目標(biāo)進(jìn)行敏感性分析，系統(tǒng)運(yùn)營(yíng)成本和乘客時(shí)間成本結(jié)果如圖7所示。

圖7 系統(tǒng)運(yùn)營(yíng)成本和乘客時(shí)間成本分析Fig.7 System operating cost and passenger time cost analysis

圖7結(jié)果表明：車速引導(dǎo)策略相對(duì)于恒定車速可以有效提升求解質(zhì)量，在帕累托前沿中，運(yùn)營(yíng)成本平均下降8.35%，時(shí)間成本平均下降14.92%；需求密度大于38cust·h-1·km-2時(shí)，帕累托前沿中F1敏感，小于25 cust·h-1·km-2時(shí)，帕累托前沿中F2敏感，針對(duì)不同需求密度和動(dòng)態(tài)度的時(shí)域內(nèi)選擇合理的決策方案，高峰期應(yīng)以服務(wù)質(zhì)量為主，平峰期以運(yùn)營(yíng)成本為主；運(yùn)營(yíng)成本和時(shí)間成本隨需求密度增大呈現(xiàn)先減小后增大的趨勢(shì)，運(yùn)營(yíng)成本在35 cust·h-1·km-2時(shí)達(dá)到最小，時(shí)間成本在30 cust·h-1·km-2左右時(shí)達(dá)到最小，較高的需求密度會(huì)出現(xiàn)部分相似的時(shí)空信息請(qǐng)求，可以通過(guò)聚類分析以減小問(wèn)題規(guī)模[9]；當(dāng)動(dòng)態(tài)度大于0.4 時(shí)，人均運(yùn)營(yíng)成本急劇上升，此時(shí)，動(dòng)態(tài)插入拒絕率高，系統(tǒng)魯棒性差，應(yīng)激勵(lì)乘客提前預(yù)約。

4.3 實(shí)際案例應(yīng)用

4.3.1 算例描述

算例以河南省許昌市為背景，許昌東站為接駁樞紐站，設(shè)計(jì)1 個(gè)需求響應(yīng)接駁的案例，服務(wù)區(qū)域及需求分布如圖8 所示。相關(guān)參數(shù)及數(shù)據(jù)來(lái)源于許昌市城市公共交通有限公司的實(shí)際調(diào)研及文獻(xiàn)[14]，設(shè)置如下：S=0.5 h，WC=WG=0.2 h，=[15,25]km·h-1，λ1=λ2=0.5，公交車的類型信息如表5所示。案例中第3時(shí)域7:00-7:30的規(guī)劃結(jié)果如下，相關(guān)乘客請(qǐng)求信息如表6和表7所示。

表5 公交車類型信息Table 5 Bus type information

圖8 服務(wù)區(qū)域及需求分布Fig.8 Service area and demand distribution diagram

乘客根據(jù)出行目的異質(zhì)性提交上車時(shí)間或下車時(shí)間，通過(guò)規(guī)范化處理得到出行兩端的規(guī)范時(shí)間窗輸入模型，根據(jù)提交請(qǐng)求時(shí)間與規(guī)范上車時(shí)間窗關(guān)系劃分需求類型，進(jìn)行滾動(dòng)時(shí)域規(guī)劃。其中，表6中，需求1～44的規(guī)范化上車時(shí)間窗在7:30之前，屬于第三時(shí)域，需求45 和46 屬于第四時(shí)域；表7 中，需求47和48屬于第一時(shí)域的偽動(dòng)態(tài)請(qǐng)求，49～51屬于第二時(shí)域的動(dòng)態(tài)非即時(shí)請(qǐng)求，52～54 和56～58 屬于第三時(shí)域的動(dòng)態(tài)即時(shí)請(qǐng)求，55和59、60分別屬于第三時(shí)域的動(dòng)態(tài)非即時(shí)和偽動(dòng)態(tài)請(qǐng)求。

4.3.2 結(jié)果分析

案例模型求解的帕累托解集如圖9 所示。以帕累托解2為例，部分乘客端規(guī)劃結(jié)果如表8所示，公交端線路及車速引導(dǎo)優(yōu)化結(jié)果如表9所示。

表8 部分乘客端規(guī)劃結(jié)果Table 8 Planning results for some passengers

表9 公交端規(guī)劃結(jié)果Table 9 Planning results for bus

圖9 帕累托最優(yōu)前沿Fig.9 Pareto optimal frontier

根據(jù)表9 規(guī)劃結(jié)果，路線5 和路徑6 屬于截?cái)嗦窂?，并在第四時(shí)域加入請(qǐng)求46 和請(qǐng)求45。案例中動(dòng)態(tài)度為23.3%，根據(jù)滾動(dòng)時(shí)域策略對(duì)動(dòng)態(tài)請(qǐng)求分類處理，動(dòng)態(tài)請(qǐng)求接受率為85.7%，動(dòng)態(tài)即時(shí)請(qǐng)求接受率為66.7%。結(jié)果表明，RHO-MA 算法對(duì)DRFT-SG 問(wèn)題求解的有效性，既可以根據(jù)預(yù)約需求規(guī)劃出合理的路徑順序及其引導(dǎo)車速，又可以在滾動(dòng)時(shí)域框架下對(duì)動(dòng)態(tài)即時(shí)請(qǐng)求調(diào)整優(yōu)化路徑。

4.3.3 恒定車速與車速引導(dǎo)對(duì)比分析

分別對(duì)考慮時(shí)變速度下的恒定車速20 km·h-1和區(qū)間速度15～25 km·h-1下引導(dǎo)車速的結(jié)果進(jìn)行對(duì)比分析，結(jié)果如表10所示。

表10 考慮恒定車速和引導(dǎo)車速的結(jié)果對(duì)比Table 10 Results of considering constant speed and guided speed

相比于恒定車速，公交車速引導(dǎo)與路徑規(guī)劃協(xié)同優(yōu)化的帕累托解2中，減少使用2輛車，平均滿載率顯著提高(10.8%)，系統(tǒng)運(yùn)營(yíng)成本減少71.43 元(12.85%)，乘客人均時(shí)間成本降低10.79%。結(jié)果說(shuō)明，考慮區(qū)間速度下車速引導(dǎo)可以有效減少系統(tǒng)總成本，提供服務(wù)滿意和綠色低碳的接駁公交運(yùn)營(yíng)策略。

5 結(jié)論

(1)本文分析了接駁出行異質(zhì)需求特點(diǎn)，并進(jìn)行規(guī)范化，提出以區(qū)間車速表征彈性路網(wǎng)的行駛時(shí)間進(jìn)行建模，擴(kuò)大了模型優(yōu)質(zhì)解空間；針對(duì)需求響應(yīng)型接駁公交車速與路徑協(xié)同優(yōu)化模型，設(shè)計(jì)了RHO-MA 算法，并驗(yàn)證其有效性和先進(jìn)性，極大地提高了算法性能。

(2)研究表明：隨需求密度的增加，運(yùn)營(yíng)成本和時(shí)間成本呈現(xiàn)先減小后增大的趨勢(shì)，DRFT 在35 cust·h-1·km-2左右的場(chǎng)景更具優(yōu)勢(shì)；平峰期，低需求密度下乘客時(shí)間成本敏感度更高，高峰期，高需求密度下系統(tǒng)運(yùn)營(yíng)成本更敏感，不同時(shí)段應(yīng)采取不同決策方法；與傳統(tǒng)恒定車速建模相比，考慮車速引導(dǎo)與路徑協(xié)同優(yōu)化在一定程度上可以降低10.79%的乘客時(shí)間成本和12.85%的系統(tǒng)運(yùn)營(yíng)成本。