考慮行駛時(shí)間不確定性的合乘路徑魯棒優(yōu)化方法

袁振洲，陳思媛，吳玥琳，李浩然，肖清榆

(1.北京交通大學(xué)，綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室，北京 100044；2.湖南省交通科學(xué)研究院有限公司，長(zhǎng)沙 410004）

0 引言

合乘指2 名及以上具有相似行程的乘客共同乘坐1輛汽車，是一種介于小汽車和公共交通之間的綠色出行方式。合乘提供了更便捷、可負(fù)擔(dān)的按需服務(wù)，使乘客能迅速匹配車輛的同時(shí)節(jié)約出行成本，并能夠減少車輛行駛里程。然而對(duì)實(shí)際應(yīng)用情況的考慮不足，過于理想化的路徑優(yōu)化可能造成計(jì)劃路線和實(shí)際路線的送達(dá)時(shí)間產(chǎn)生偏差，同時(shí)增加車輛不必要的繞行。因此，研究合乘的合理匹配與考慮時(shí)間不確定的路徑優(yōu)化問題能夠提高乘客滿意度并節(jié)約車輛資源，為合乘服務(wù)推廣起到積極作用。

目前已有學(xué)者對(duì)不同合乘問題構(gòu)建了優(yōu)化模型。Chen 等[1]以降低乘客出行費(fèi)用為目標(biāo)設(shè)計(jì)了社區(qū)拼車模型。程杰等[2]綜合考慮性別匹配限制并以乘客和駕駛員利益為優(yōu)化目標(biāo)建立了動(dòng)態(tài)出租車合乘模型。在考慮不確定性因素方面，Miao等[3]考慮時(shí)空相關(guān)的需求不確定性，構(gòu)建了出租車調(diào)度優(yōu)化的數(shù)據(jù)驅(qū)動(dòng)魯棒模型。對(duì)于需求信息已知且確定的合乘系統(tǒng)而言，行駛時(shí)間的隨機(jī)性成為合乘匹配和路線的主要影響因素。Long 等[4]考慮與時(shí)間無(wú)關(guān)和與時(shí)間相關(guān)的兩種行駛時(shí)間隨機(jī)變量，并使用隨機(jī)優(yōu)化方法求解靜態(tài)合乘模型。Li等[5]研究了一個(gè)車輛和乘客均有需求起終點(diǎn)的合乘系統(tǒng)，構(gòu)建不確定行駛時(shí)間的魯棒模型，但在計(jì)算不確定時(shí)間下的節(jié)點(diǎn)到達(dá)時(shí)間忽略了乘客時(shí)間窗會(huì)吸收偏差的情況。

合乘模型的算法研究上，張璽君等[6]通過改進(jìn)遺傳算法，設(shè)計(jì)站點(diǎn)片段交叉和監(jiān)督式變異等操作求解模型。近年來(lái)，“聚類第一路徑第二”的求解思路廣泛應(yīng)用于合乘問題中并取得較好效果：肖強(qiáng)等[7]對(duì)出租車按行駛目的地模糊聚類并實(shí)現(xiàn)乘客模糊識(shí)別，能夠有效提高出租車合乘成功率；吳玥琳等[8]基于乘客出發(fā)方向和時(shí)間對(duì)乘客需求聚類，并考慮軌跡相似度約束求解樞紐合乘路徑；Peng等[9]考慮合乘路徑潛在的服務(wù)時(shí)間節(jié)省和乘客等待緩沖時(shí)間以聚類乘客需求，設(shè)計(jì)精確算法求解。但目前對(duì)聚類算法的考慮主要基于需求點(diǎn)之間的地理關(guān)系，未考慮系統(tǒng)效益和乘客的出行時(shí)間窗需求。

綜上，現(xiàn)有合乘路徑優(yōu)化研究多假設(shè)行駛時(shí)間為定值，而現(xiàn)實(shí)中時(shí)間波動(dòng)會(huì)由于合乘模式出現(xiàn)累加效應(yīng)，最終對(duì)應(yīng)用結(jié)果產(chǎn)生極大影響。此外現(xiàn)有研究較少?gòu)某丝统鲂杏?jì)劃和系統(tǒng)角度描述合乘匹配機(jī)會(huì)，可能會(huì)忽略潛在的合乘路徑。因此，本文從系統(tǒng)運(yùn)營(yíng)角度以最小化車輛總里程和使用車輛數(shù)為目標(biāo)，考慮實(shí)際行駛時(shí)間的不確定性，構(gòu)建不確定性可調(diào)節(jié)的合乘路徑魯棒優(yōu)化模型。并設(shè)計(jì)兩階段算法，第1階段引入匹配機(jī)會(huì)指標(biāo)聚類乘客需求，基于乘客接送時(shí)間窗口限制的可行合乘路徑，從系統(tǒng)成本節(jié)約和乘客出行需求角度出發(fā)，考慮車輛總里程節(jié)省率以及乘客時(shí)間窗匹配的靈活性，設(shè)計(jì)量化兩乘客間合乘匹配機(jī)會(huì)的公式；第2階段采用基于順序插入啟發(fā)式的禁忌搜索算法求解合乘路徑，以在節(jié)省運(yùn)營(yíng)成本的前提下提供滿足乘客偏好的合乘服務(wù)，從而推動(dòng)出租車合乘在現(xiàn)實(shí)應(yīng)用中的有效運(yùn)營(yíng)。

1 模型建立

1.1 問題描述及基本假設(shè)

本文考慮一個(gè)城市路網(wǎng)中的合乘出行服務(wù)系統(tǒng)，系統(tǒng)提供服務(wù)的車輛同質(zhì)且容量固定，系統(tǒng)中乘客需求均有時(shí)間窗[ei,li]要求且為靜態(tài)需求，提供的合乘方案需滿足所有合乘乘客起終點(diǎn)時(shí)間窗要求，并保證車輛接送乘客過程不會(huì)超載。與傳統(tǒng)研究將行駛時(shí)間視為定量不同，為更符合現(xiàn)實(shí)應(yīng)用，本文的行駛時(shí)間tij是在區(qū)間內(nèi)變化的隨機(jī)變量，具體取值規(guī)律見1.2節(jié)?；炯僭O(shè)如下：

(1)所有乘客需求信息是預(yù)知的，乘客默認(rèn)接受合乘。

(2)系統(tǒng)能即時(shí)響應(yīng)乘客需求，且擁有足夠多的車輛以滿足所有乘客需求。

(3)車輛初始和結(jié)束位置設(shè)在虛擬車場(chǎng)，所以車輛能夠即時(shí)到達(dá)首個(gè)服務(wù)起點(diǎn)。

(4)車輛在乘客需求點(diǎn)時(shí)間窗前到達(dá)需要等待至?xí)r間窗開始后服務(wù)。

本文模型中的符號(hào)說明如表1所示。

表1 符號(hào)與定義Table 1 Symbols and definitions

1.2 時(shí)間不確定的合乘路徑魯棒優(yōu)化模型

魯棒優(yōu)化能在僅已知變量的數(shù)值范圍或集合情況下進(jìn)行優(yōu)化，求解時(shí)將模型中隨機(jī)變量相關(guān)約束進(jìn)行魯棒對(duì)等轉(zhuǎn)換，使解對(duì)于集合中任意變量可行。為有效描述行駛時(shí)間隨機(jī)變量，本文以預(yù)算不確定集合[10]為基礎(chǔ)，引入行駛時(shí)間的區(qū)間約束，假定i至j所需的時(shí)間tij在單側(cè)區(qū)間內(nèi)變化?？紤]到在實(shí)際情況中，并非所有車輛的行駛路徑都具有相同的不確定性水平，車輛需要接送的需求點(diǎn)越多，可能會(huì)經(jīng)歷越大的時(shí)間偏差。為表示不確定性水平的差異，本文為每輛車的路徑行駛時(shí)間定義了不同的預(yù)算不確定多面體集合，即

式中：ξij為tij相對(duì)標(biāo)稱值的偏差水平；Γ(k)為不確定性預(yù)算，作用是調(diào)節(jié)行駛時(shí)間的不確定性水平。本文設(shè)定車輛k的不確定性預(yù)算Γ(k)與其經(jīng)過的弧總數(shù) |A(k)|成正比，引入可調(diào)節(jié)的預(yù)算系數(shù)σ(0≤σ≤1)，定義Γ(k)=(σ|A(k)|)+，表示Γ(k)為預(yù)算系數(shù)σ和車輛k路徑弧總數(shù) |A(k)|乘積的四舍五入取整值。σ=0 時(shí)表示不考慮時(shí)間偏差，σ取值越大表示模型解的魯棒性越強(qiáng)，當(dāng)σ=1 時(shí)表示車輛路徑經(jīng)歷最大的行駛時(shí)間偏差，模型解最保守。

基于上述對(duì)行駛時(shí)間變量的處理，從合乘系統(tǒng)角度考慮車輛運(yùn)營(yíng)成本，以車輛總行駛里程最短和所需車輛數(shù)量最小為目標(biāo)，構(gòu)建不確定性時(shí)間的合乘模型為

目標(biāo)函數(shù)：式(2)表示系統(tǒng)整體消耗最小，即所有車輛的行駛總里程和實(shí)際所需車隊(duì)規(guī)模。約束條件：式(3)與式(4)表示車輛均從虛擬車場(chǎng)出發(fā)并返回車場(chǎng)；式(5)和式(6)確保任意節(jié)點(diǎn)有且僅有一輛車服務(wù)；式(7)確保車輛服務(wù)任意乘客必須訪問其起點(diǎn)和終點(diǎn)；式(8)確保節(jié)點(diǎn)流量平衡；式(9)和式(10)為容量約束，行駛過程中經(jīng)過任意節(jié)點(diǎn)載客量不超過C，節(jié)點(diǎn)j載客量至少要大于上一節(jié)點(diǎn)i載客量與該點(diǎn)j需求量之和；式(11)～式(14)為不確定時(shí)間下的時(shí)間窗魯棒對(duì)等約束；式(15)為決策變量0-1 整數(shù)約束。本節(jié)拓展了Munari 等[11]構(gòu)建的VRPTW(帶時(shí)間窗的車輛路徑問題)魯棒雙指標(biāo)緊湊公式，是基于Agra 等[12]定義的遞歸公式(式(18))的線性轉(zhuǎn)換，可以大幅減少魯棒對(duì)等轉(zhuǎn)換所需額外變量的數(shù)量，約束確保路徑中節(jié)點(diǎn)間行駛時(shí)間至少要大于上下車服務(wù)時(shí)間s與行駛時(shí)間tij之和，并約束起終點(diǎn)服務(wù)順序，要求車輛在時(shí)間窗內(nèi)抵達(dá)。

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

車輛路徑問題(VRP)已被證明為NP-hard 問題[13]，本文模型屬于不確定性VRP 問題，同樣為NP-hard 問題，線性轉(zhuǎn)換魯棒約束后可構(gòu)造為混合整數(shù)規(guī)劃模型。當(dāng)求解規(guī)模足夠小時(shí)，可以利用精確算法求得精確解；當(dāng)規(guī)模增大時(shí)，需求匹配組合數(shù)量和解空間呈指數(shù)級(jí)增長(zhǎng)，精確算法計(jì)算耗時(shí)難以滿足實(shí)際問題需要。因此，本節(jié)為合乘路徑魯棒優(yōu)化問題設(shè)計(jì)了結(jié)合聚類和禁忌搜索的啟發(fā)式算法：第1 階段通過量化合乘匹配機(jī)會(huì)聚類乘客需求，將合乘問題分解為多個(gè)子問題，在保證合乘方案質(zhì)量的基礎(chǔ)上減少算法搜索空間；第2階段使用基于順序插入啟發(fā)式算法的禁忌搜索算法求解每個(gè)子問題的合乘魯棒路徑方案。

2.1 基于合乘匹配機(jī)會(huì)的乘客需求聚類

乘客起終點(diǎn)間的時(shí)空距離與出行時(shí)間窗計(jì)劃是需求匹配的關(guān)鍵要素，而合乘后是否能節(jié)省車輛里程又直接影響目標(biāo)值。根據(jù)2 名乘客的起終點(diǎn)服務(wù)順序可以得到4條合乘路徑，如圖1所示，其中路徑1 指車輛先抵達(dá)乘客a起點(diǎn)后再接乘客b，隨后先將a送至終點(diǎn)后再送b至終點(diǎn)。本文設(shè)定只有滿足所有乘客起終點(diǎn)時(shí)間窗約束且能節(jié)省車輛里程的為可行合乘路徑，否則匹配機(jī)會(huì)為0。從乘客出行需求角度看，2 名乘客起點(diǎn)時(shí)間窗匹配靈活性越高，合乘路徑的魯棒性越高，匹配機(jī)會(huì)越大；從系統(tǒng)角度看，里程節(jié)省越多則匹配機(jī)會(huì)越大。

圖1 乘客合乘路徑Fig.1 Carpooling routes of passengers

由此，從上述乘客和系統(tǒng)角度設(shè)計(jì)合乘匹配機(jī)會(huì)量化公式為

式中：Zab為2名乘客的合乘匹配機(jī)會(huì)，為所有可行路徑∈Pab的匹配機(jī)會(huì)加和值，由車輛里程節(jié)省和時(shí)間窗匹配靈活性兩方面構(gòu)成；為合乘路徑節(jié)省的車輛行駛里程；doada和dobdb分別為單獨(dú)服務(wù)乘客a和b所需里程；為第2名乘客b的起點(diǎn)時(shí)間窗寬度；為2 名乘客起點(diǎn)服務(wù)時(shí)間窗匹配靈活性。可行路徑下的靈活性Fab與連續(xù)服務(wù)乘客間的時(shí)間窗時(shí)空范圍相關(guān)；為b的起點(diǎn)時(shí)間窗；和分別為從a出發(fā)到達(dá)b的最早和最晚時(shí)間。本文定義不同場(chǎng)景的靈活性如圖2所示，陰影部分代表從a起點(diǎn)以最早和最晚出發(fā)時(shí)間出發(fā)到達(dá)b起點(diǎn)時(shí)與b時(shí)間窗的重疊或相接情況，表示從a出發(fā)后服務(wù)b乘客的可冗余時(shí)間。

圖2 時(shí)間窗匹配靈活性場(chǎng)景Fig.2 Time window matching flexibility scenarios

以匹配機(jī)會(huì)為邊權(quán)重，構(gòu)建乘客的有權(quán)無(wú)向網(wǎng)絡(luò)如圖3所示，節(jié)點(diǎn)間無(wú)邊連接表示2 名乘客匹配機(jī)會(huì)為0。通過圖聚類算法中的社區(qū)發(fā)現(xiàn)算法可以利用網(wǎng)絡(luò)信息聚類乘客，社區(qū)劃分質(zhì)量由模塊度指標(biāo)衡量，本文采用基于模塊度最大的社區(qū)發(fā)現(xiàn)算法[14]。算法首先將網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)設(shè)為一個(gè)單獨(dú)社區(qū)，每次迭代選擇產(chǎn)生最大模塊度值的兩個(gè)社區(qū)合并，直至整個(gè)網(wǎng)絡(luò)融合成一個(gè)社區(qū)。這種自底向上的過程最終能得到一個(gè)樹圖，從樹圖的所有層次劃分中選擇模塊度值最大的作為網(wǎng)絡(luò)社區(qū)的有效劃分。算法基于貪心策略能快速將乘客劃分為不同社區(qū)，使得同一社區(qū)內(nèi)的乘客匹配機(jī)會(huì)較大，而不同社區(qū)間的乘客幾乎沒有匹配機(jī)會(huì)。

圖3 乘客需求聚類示意Fig.3 Passenger demand clustering schematic

2.2 基于順序插入的禁忌搜索算法設(shè)計(jì)

考慮到初始解對(duì)禁忌搜索的后續(xù)性能有較大的影響，以最大時(shí)間偏差情況構(gòu)造初始可行解，設(shè)計(jì)改進(jìn)的啟發(fā)式順序插入法，具體如下：

Step 1 構(gòu)造新的空路徑p(k)，選擇lor最早截止的乘客r作為種子乘客。

Step 2 將未被服務(wù)的乘客插入至p(k)，選擇額外行駛距離最小的乘客進(jìn)行插入。插入過程如圖4所示，優(yōu)先確定起點(diǎn)的最佳插入位置i*(使路徑總里程最短)，再為終點(diǎn)確定i*后的最佳插入位置，該方法能有效將計(jì)算復(fù)雜度O(r2)減少至O(r)。

圖4 乘客需求插入過程示意Fig.4 Passenger demand insertion process schematic

Step 3 繼續(xù)插入未被服務(wù)的乘客，直至沒有能滿足時(shí)間窗和容量等約束條件的可插入乘客，當(dāng)前可行路徑p(k)構(gòu)造完畢。

Step 4 循環(huán)前述3個(gè)步驟，直至所有乘客被服務(wù)，得到的總路徑數(shù)即為使用車輛數(shù)。

禁忌搜索算法從初始解出發(fā)，將初始解的車輛數(shù)作為優(yōu)化上限，當(dāng)達(dá)到最大迭代次數(shù)ε或最優(yōu)解連續(xù)φ次未改善時(shí)停止。搜索過程接受不可行解，路徑解的目標(biāo)函數(shù)f(s)除了車輛固定成本和行駛里程以外，還包括車輛路徑p(k)∈P違反約束的懲罰總和，即容量約束式(10)違反項(xiàng)q(s)與不確定時(shí)間下的時(shí)間窗約束式(13)違反項(xiàng)w(s)；計(jì)算w(s)時(shí)利用式(18)[12]遞歸得到預(yù)算Γ(k)下路徑p(k)={v0,v1,…,vi} 中節(jié)點(diǎn)vi的最早可能到達(dá)時(shí)間Wvi,Γ(k)，從而計(jì)算違反要求時(shí)間窗的總和。f(s)=cfix(s)+cdis(s)+αq(s)+βw(s)，其中，α和β為非負(fù)的懲罰權(quán)重，在每次迭代中動(dòng)態(tài)調(diào)整更新：初始值設(shè)為1，若違反約束，則乘以(1+δ)；否則，除以(1+δ)，δ初始為0.5[15]。

使用U(s)={(r,k):乘客r由k車服務(wù)}屬性集描述合乘路徑解P，通過路線間交換移動(dòng)，將乘客r從當(dāng)前車輛k路徑中移除并插入至隨機(jī)車輛k′路徑的最佳位置，從而將屬性(r,k)隨機(jī)替換為(r,k′)，得到P的鄰域N(s)。每次迭代選擇鄰域內(nèi)的最佳未禁忌移動(dòng)得到解P′，并禁忌對(duì)應(yīng)屬性(r,k)，只要P′是更優(yōu)可行解則更新當(dāng)前最優(yōu)解。為了強(qiáng)化搜索，每λ次迭代會(huì)隨機(jī)更新δ值，并執(zhí)行路線內(nèi)重定位的強(qiáng)化機(jī)制，將乘客r從當(dāng)前車輛k路徑中移除并重新插入最佳位置。

3 案例分析

3.1 數(shù)據(jù)準(zhǔn)備

本文以雄安新區(qū)合乘模式為案例，新區(qū)為建設(shè)綠色交通體系，目前正致力于研究一種“定點(diǎn)不定線”的需求響應(yīng)型合乘出行服務(wù)。不同于傳統(tǒng)合乘模式的不定點(diǎn)不定線形式，雄安合乘方式通過在路網(wǎng)中布設(shè)合乘站點(diǎn)，將乘客點(diǎn)對(duì)點(diǎn)需求引導(dǎo)為站點(diǎn)對(duì)站點(diǎn)需求，但同樣提供不固定線路的靈活性服務(wù)。選取建設(shè)核心區(qū)容城縣城為研究對(duì)象，對(duì)實(shí)際合乘站點(diǎn)處理后構(gòu)建路網(wǎng)如圖5所示，共包含45個(gè)實(shí)際站點(diǎn)。

圖5 路網(wǎng)及合乘站點(diǎn)分布Fig.5 Network and distribution of carpooling stations

基于路網(wǎng)合乘站點(diǎn)隨機(jī)生成乘客起終點(diǎn)不重復(fù)的OD 站點(diǎn)對(duì)數(shù)據(jù)，為方便模型處理，本文將乘客的起終點(diǎn)轉(zhuǎn)換為虛擬需求點(diǎn)，屬于同一合乘站點(diǎn)的兩虛擬點(diǎn)間路徑距離為0，從而將問題轉(zhuǎn)化為基于乘客需求點(diǎn)的傳統(tǒng)合乘。案例包含隨機(jī)生成的10，20，30，40，50位乘客不同規(guī)模數(shù)據(jù)，需求量均為1。對(duì)實(shí)際全年運(yùn)營(yíng)數(shù)據(jù)分析，需求訂單的等候時(shí)間分布在5～15 min，為符合實(shí)際情況，乘客需求的整數(shù)時(shí)間窗寬度在[5,15]范圍內(nèi)隨機(jī)生成。最后，每位乘客的起點(diǎn)時(shí)間窗設(shè)置為[eor,eor+]，終點(diǎn)為[eor+tordr,eor+tordr+]；其中，eor為乘客起點(diǎn)最早服務(wù)時(shí)間(本案例設(shè)為0)，tordr為乘客起點(diǎn)至終點(diǎn)的最短路所需的標(biāo)稱行駛時(shí)間。每組數(shù)據(jù)分別進(jìn)行多次迭代次數(shù)的參數(shù)實(shí)驗(yàn)，以得到穩(wěn)定的求解結(jié)果便于實(shí)驗(yàn)分析。

實(shí)驗(yàn)部分首先基于確定性小規(guī)模案例將本文算法和CPLEX 求解器進(jìn)行對(duì)比，再通過與不聚類情形下的魯棒優(yōu)化結(jié)果對(duì)比驗(yàn)證聚類算法的有效性，最后針對(duì)魯棒模型的預(yù)算系數(shù)分析行駛時(shí)間不確定性對(duì)各規(guī)模與不同時(shí)間窗案例的影響。本文使用通用數(shù)學(xué)模型求解器GAMS 24.7.3 實(shí)現(xiàn)模型后利用CPLEX 求解器求解；乘客需求聚類與禁忌搜索算法均采用Python編程實(shí)現(xiàn)，不聚類情形直接利用禁忌搜索算法求解所有乘客合乘路徑。所有實(shí)驗(yàn)均在Intel(R)Core(TM)i5-8265U CPU 1.8 GHz、8 G RAM、Windows10操作系統(tǒng)環(huán)境下運(yùn)行。

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

3.2.1 參數(shù)設(shè)定

結(jié)合文獻(xiàn)[5，15]中模型的相關(guān)參數(shù)取值，設(shè)定車輛最大載客量C為4 人，每公里行駛成本cdis為1元，固定成本cfix為20元；忽略上下客時(shí)間s，根據(jù)運(yùn)營(yíng)數(shù)據(jù)統(tǒng)計(jì)設(shè)定車輛運(yùn)行速度vˉ=20 km·h-1，行駛時(shí)間的標(biāo)稱值，最大偏差量設(shè)定時(shí)間為標(biāo)稱值以量化乘客匹配機(jī)會(huì)聚類乘客?；诮y(tǒng)計(jì)實(shí)驗(yàn)結(jié)果和文獻(xiàn)[15]中相關(guān)參數(shù)取值，設(shè)置禁忌表長(zhǎng)度，n為需求數(shù)量；更新參數(shù)時(shí)δ以均勻分布形式在[0.0,0.5]區(qū)間范圍內(nèi)隨機(jī)生成，更新頻率λ為10。10，20，30，40，50 位乘客規(guī)模案例數(shù)據(jù)的禁忌搜索最大迭代次數(shù)ε分別設(shè)置為400，500，600，700，800 次，φ分別設(shè)置200，300，300，400，400。

3.2.2 基于匹配機(jī)會(huì)的聚類效果分析

如果設(shè)定車輛路徑具有相同的不確定性預(yù)算Γ(k)，本文模型可以使用求解器求解。然而，由于引入了預(yù)算系數(shù)σ設(shè)定依賴車輛路徑弧總數(shù)|的可調(diào)預(yù)算Γ(k)，該問題的不確定性水平具有路徑依賴性，難以直接使用求解器求解。因此對(duì)比實(shí)驗(yàn)僅基于確定性合乘模型(σ=0的魯棒模型)進(jìn)行，且由于CPLEX 求解20 位乘客40 節(jié)點(diǎn)規(guī)模問題時(shí)計(jì)算時(shí)間超過1 h，因此本節(jié)僅以10位乘客20節(jié)點(diǎn)小規(guī)模問題為例對(duì)比CPLEX 與聚類啟發(fā)式算法。表2中聚類算法均為10次實(shí)驗(yàn)的平均結(jié)果，可以發(fā)現(xiàn)，聚類算法在10次實(shí)驗(yàn)中均能夠穩(wěn)定且快速地找到精確解，但CPLEX耗時(shí)是聚類算法的90倍，說明本文算法兼具精確性和穩(wěn)定性，并能有效提升計(jì)算效率。

表2 10位乘客案例優(yōu)化結(jié)果對(duì)比(σ=0)Table 2 Comparison of optimization results of 10 passengers case(σ=0)

實(shí)驗(yàn)進(jìn)一步測(cè)試聚類算法對(duì)各規(guī)模案例的適用效果，聚類后各案例的社區(qū)數(shù)量為4～7個(gè)。匹配機(jī)會(huì)高的乘客在圖網(wǎng)絡(luò)中距離緊密，以20 位乘客規(guī)模為例，圖6為乘客需求聚類結(jié)果。設(shè)定預(yù)算系數(shù)σ=0.5，圖7為在不聚類情況下，直接使用禁忌搜索的算法收斂情況，目標(biāo)函數(shù)在迭代50 次以后趨于穩(wěn)定，最優(yōu)解連續(xù)300次未改善后得到優(yōu)化結(jié)果，表3為合乘路徑求解結(jié)果?？梢钥闯?，不聚類合乘匹配結(jié)果與聚類后的結(jié)果相似，說明本文的乘客聚類方法能夠有效量化乘客匹配機(jī)會(huì)。

圖6 20位乘客案例聚類結(jié)果Fig.6 Clustering results of 20 passengers case

圖7 20位乘客案例不聚類算法收斂曲線(σ=0.5)Fig.7 Convergence curve of non clustering algorithm for 20 passengers case(σ=0.5)

表3 20位乘客案例合乘路徑解(σ=0.5)Table 3 Carpooling routes solution of 20 passengers case(σ=0.5)

表4 算法優(yōu)化結(jié)果對(duì)比(σ=0.5)Table 4 Comparison of algorithm optimization results(σ=0.5)

3.2.3 行駛時(shí)間不確定性影響分析

(1)不同乘客規(guī)模

各規(guī)模案例的目標(biāo)函數(shù)值與所需車輛數(shù)魯棒優(yōu)化結(jié)果如表5所示?？梢园l(fā)現(xiàn)，隨著預(yù)算系數(shù)取值從0增加到1，時(shí)間不確定性水平逐漸提高，目標(biāo)函數(shù)值均有所增大；乘客規(guī)模較少的案例所需車輛數(shù)增加1～2輛，而乘客規(guī)模較多的案例所需車輛數(shù)增加4～7輛；乘客平均等待時(shí)間由于提供服務(wù)車輛數(shù)增加而整體呈現(xiàn)下降趨勢(shì)。預(yù)算系數(shù)取值的增加代表得到的合乘路徑解魯棒性逐漸提高，可見對(duì)于合乘路線優(yōu)化問題來(lái)說，預(yù)算系數(shù)越高則需要安排更多車輛來(lái)滿足乘客時(shí)間窗，從而逐步增加系統(tǒng)運(yùn)營(yíng)成本。

表5 不同規(guī)模下兩階段算法魯棒優(yōu)化結(jié)果Table 5 Robust optimization results of two-stage algorithm with different scales

圖8為預(yù)算系數(shù)σ=0.5時(shí)，各規(guī)模案例里程節(jié)省率。較小規(guī)模案例的總里程節(jié)省率在20%左右；隨著規(guī)模增大，合乘方式的里程節(jié)省率增加，大規(guī)模案例中能達(dá)到35%。所以在考慮不確定性時(shí)間情況下，相比于單獨(dú)服務(wù)乘客，合乘方式同樣能夠在節(jié)約車輛資源的同時(shí)減少車輛總行駛里程；且參與合乘系統(tǒng)的乘客越多，合乘帶來(lái)的總里程節(jié)省效益越大，效果越好。

圖8 不同規(guī)模案例車輛總里程節(jié)省率結(jié)果(σ=0.50)Fig.8 Results of vehicle mileage saving rate in different scale cases(σ=0.5)

以10 位乘客和50 位乘客規(guī)模數(shù)據(jù)為例，圖9為不同預(yù)算系數(shù)下的實(shí)驗(yàn)結(jié)果。由圖可知，隨著預(yù)算系數(shù)的增大，兩案例中里程節(jié)省率均有所下降。說明行駛時(shí)間偏差于標(biāo)稱值時(shí)，一些在標(biāo)稱值下可行的匹配組合變得不可行，車輛需要選擇魯棒性更強(qiáng)的路徑來(lái)克服時(shí)間不確定性，從而使得總里程增加。

此外，圖9中小規(guī)模案例里程節(jié)省率僅下降約2%，而大規(guī)模案例的里程節(jié)省率會(huì)下降約10%。說明當(dāng)所需服務(wù)乘客數(shù)量較多時(shí)，合乘路徑對(duì)時(shí)間不確定性更加敏感。進(jìn)一步證明魯棒優(yōu)化在合乘模式實(shí)際推廣中重要性。

圖9 兩規(guī)模案例的車輛總里程節(jié)省率結(jié)果Fig.9 Results of vehicle mileage saving rate with two scale cases

(2)不同時(shí)間窗寬度

以50 位乘客規(guī)模數(shù)據(jù)為例，更改需求點(diǎn)時(shí)間窗寬度分別為5，10，15 min，得到不同忍耐水平的案例，采用兩階段算法得到魯棒優(yōu)化結(jié)果如表6所示。同樣地，目標(biāo)函數(shù)值和所需車輛數(shù)隨著預(yù)算系數(shù)增大而逐步增加，但窄時(shí)間窗案例增幅更大，車輛數(shù)增加11輛。乘客平均等車時(shí)間變化情況也與各規(guī)模案例結(jié)果相似，隨著系統(tǒng)使用車輛數(shù)增多而逐漸下降。不同預(yù)算系數(shù)下，時(shí)間窗越寬的案例所需車輛數(shù)越少，乘客的寬松時(shí)間窗特性允許車輛在路徑中接送更多乘客，即時(shí)間窗寬度會(huì)影響路徑規(guī)劃結(jié)果，乘客忍耐時(shí)間越長(zhǎng)，越有利于合乘方案的制定。

表6 不同時(shí)間窗寬度兩階段算法魯棒優(yōu)化結(jié)果Table 6 Robust optimization results of two-stage algorithm with different time window length

圖10為各案例的里程節(jié)省率結(jié)果。可以看出：窄時(shí)間窗案例對(duì)不確定時(shí)間更敏感，里程節(jié)省率下降15%以上；而服務(wù)較長(zhǎng)忍耐時(shí)間的乘客時(shí)合乘方案更穩(wěn)健，里程節(jié)省率浮動(dòng)范圍在5%以內(nèi)。說明在乘客具有寬時(shí)間窗的情況下，考慮不確定時(shí)間的方案無(wú)需過多額外成本，就可以達(dá)到高水平的路徑魯棒性；然而，在窄時(shí)間窗的情況下提高合乘方案的魯棒性要更昂貴的額外成本。

圖10 不同時(shí)間窗寬度下車輛總里程節(jié)省率結(jié)果Fig.10 Results of vehicle mileage saving rate with different window length

4 結(jié)論

(1)案例實(shí)驗(yàn)結(jié)果表明，本文聚類方法能保證合乘路徑解的質(zhì)量，以乘客匹配機(jī)會(huì)為基礎(chǔ)的聚類結(jié)果與直接求解的合乘匹配結(jié)果相近，同時(shí)能提高85%以上的算法效率，還能適當(dāng)避免低匹配機(jī)會(huì)乘客的合乘組合，縮減乘客平均等車時(shí)間和繞行比例。

(2)隨著預(yù)算系數(shù)的增大，路徑解的魯棒性逐漸增強(qiáng)，但會(huì)降低1%～10%的里程節(jié)省率，且需要額外使用車輛來(lái)服務(wù)已不可行的匹配組合。相比非合乘服務(wù)，合乘方式能減少30%～50%的所需車輛數(shù)，節(jié)省20%～43%的車輛總里程。乘客需求規(guī)模越大，合乘節(jié)約系統(tǒng)成本的效益越好，同時(shí)路徑方案受時(shí)間不確定性的影響越大。說明服務(wù)大規(guī)模乘客時(shí)更需要考慮不確定時(shí)間，以優(yōu)化路徑解的魯棒性。

(3)時(shí)間窗寬度會(huì)影響合乘路徑方案的制定，窄時(shí)間窗案例的路徑方案更敏感，需要增加11 輛車并降低15%的里程節(jié)省率。而服務(wù)寬時(shí)間窗需求時(shí)，可以考慮較高水平的時(shí)間不確定性，且總行駛距離和使用的車輛數(shù)量增加不多。