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

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

0 引言

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

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

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

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

1 模型建立

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

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

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

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

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

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

本文模型中的符號說明如表1所示。

表1 符號與定義Table 1 Symbols and definitions

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

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

式中：ξij為tij相對標稱值的偏差水平；Γ(k)為不確定性預(yù)算，作用是調(diào)節(jié)行駛時間的不確定性水平。本文設(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 時表示不考慮時間偏差，σ取值越大表示模型解的魯棒性越強，當σ=1 時表示車輛路徑經(jīng)歷最大的行駛時間偏差，模型解最保守。

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

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

2 算法設(shè)計

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

2.1 基于合乘匹配機會的乘客需求聚類

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

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

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

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

圖2 時間窗匹配靈活性場景Fig.2 Time window matching flexibility scenarios

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

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

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

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

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

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

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

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

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

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

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

3 案例分析

3.1 數(shù)據(jù)準備

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

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

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

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

3.2 實驗結(jié)果與分析

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

結(jié)合文獻[5，15]中模型的相關(guān)參數(shù)取值，設(shè)定車輛最大載客量C為4 人，每公里行駛成本cdis為1元，固定成本cfix為20元；忽略上下客時間s，根據(jù)運營數(shù)據(jù)統(tǒng)計設(shè)定車輛運行速度vˉ=20 km·h-1，行駛時間的標稱值，最大偏差量設(shè)定時間為標稱值以量化乘客匹配機會聚類乘客?；诮y(tǒng)計實驗結(jié)果和文獻[15]中相關(guān)參數(shù)取值，設(shè)置禁忌表長度，n為需求數(shù)量；更新參數(shù)時δ以均勻分布形式在[0.0,0.5]區(qū)間范圍內(nèi)隨機生成，更新頻率λ為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 基于匹配機會的聚類效果分析

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

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

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

圖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é)果對比(σ=0.5)Table 4 Comparison of algorithm optimization results(σ=0.5)

3.2.3 行駛時間不確定性影響分析

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

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

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

圖8為預(yù)算系數(shù)σ=0.5時，各規(guī)模案例里程節(jié)省率。較小規(guī)模案例的總里程節(jié)省率在20%左右；隨著規(guī)模增大，合乘方式的里程節(jié)省率增加，大規(guī)模案例中能達到35%。所以在考慮不確定性時間情況下，相比于單獨服務(wù)乘客，合乘方式同樣能夠在節(jié)約車輛資源的同時減少車輛總行駛里程；且參與合乘系統(tǒng)的乘客越多，合乘帶來的總里程節(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ù)下的實驗結(jié)果。由圖可知，隨著預(yù)算系數(shù)的增大，兩案例中里程節(jié)省率均有所下降。說明行駛時間偏差于標稱值時，一些在標稱值下可行的匹配組合變得不可行，車輛需要選擇魯棒性更強的路徑來克服時間不確定性，從而使得總里程增加。

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

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

(2)不同時間窗寬度

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

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

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

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

4 結(jié)論

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

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

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