考慮軌跡相似度的綜合客運(yùn)樞紐出租車合乘方法研究

吳玥琳，袁振洲*，陳秋芳，肖清榆，王文成，魏 來

(1.北京交通大學(xué)綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實(shí)驗(yàn)室，北京100044；2.越南河內(nèi)交通大學(xué)工程學(xué)院，河內(nèi)100803，越南)

0 引言

乘客等候出租車時間過長已成為綜合客運(yùn)樞紐運(yùn)營的一大問題.出租車時常僅搭載1～2名乘客造成運(yùn)力資源浪費(fèi)，無法疏解等待乘客.出租車合乘能有效提高出租車使用效率，節(jié)約運(yùn)力資源，減少旅客排隊(duì)等待出租車的時間.因此，研究樞紐合乘問題具有很強(qiáng)的實(shí)踐價值.

學(xué)者對合乘問題已有相關(guān)成果：Martinez等提出基于折扣的合乘模式，利用合乘費(fèi)用優(yōu)惠吸引更多的人參與合乘[1]；程杰等考慮乘客對性別偏好建立動態(tài)合乘模型，利用遺傳算法求解[2]；丁冉以總時間和總費(fèi)用最小為目標(biāo)，收益、容量等為約束建立動態(tài)合乘匹配模型[3].優(yōu)化算法方面：Coslovich針對動態(tài)合乘問題提出路徑干擾的實(shí)時兩階段插入法[4]，肖強(qiáng)等利用隸屬度函數(shù)對乘客和出租車的合乘進(jìn)行動態(tài)模糊識別[5]，邵增珍等建立了基于松弛路程、線路擬合度、車輛剩余容量等匹配度指標(biāo)，形成算法解決靜態(tài)合乘匹配任務(wù)分派問題[6].

現(xiàn)有研究集中于路網(wǎng)合乘，對樞紐合乘問題研究較少且在乘客對行駛軌跡形態(tài)要求方面未充分考慮.事實(shí)上，路網(wǎng)合乘問題是根據(jù)出租車原始行程作為基準(zhǔn)匹配乘客，因乘客需求不集中，可行方案較少.而樞紐合乘問題無原始路線基準(zhǔn)且乘客需求量大，使得乘客間可行匹配組合遠(yuǎn)多于路網(wǎng)合乘，優(yōu)化復(fù)雜度較大.另外，路線作為重要的匹配條件，現(xiàn)有研究大多注重需求起終點(diǎn)的相近和路線長短的約束，較少研究行駛軌跡的形態(tài)相似性以滿足乘客的心理預(yù)期.

據(jù)此，本文將車輛數(shù)最小和總行駛距離最短為目標(biāo)函數(shù)，考慮乘客對行駛軌跡預(yù)期添加軌跡相似性度量約束，構(gòu)建考慮軌跡相似度的出租車合乘模型.提出兩階段算法，第1階段基于出發(fā)時間和方向角對需求進(jìn)行聚類，第2階段設(shè)計(jì)蟻群算法求解模型得到合乘方案.實(shí)驗(yàn)結(jié)果證明：所提模型與算法能夠同時優(yōu)化車輛數(shù)和總里程，減少乘客繞行比例和等待時間，加快樞紐旅客疏散；在軌跡形態(tài)方面為合乘匹配研究提出新的角度和思路，為綜合客運(yùn)樞紐的出租車合乘組織提供一定的實(shí)踐依據(jù).

1 問題建模

1.1 模型假設(shè)

考慮綜合客運(yùn)樞紐乘坐出租車的實(shí)際情況，結(jié)合本文研究需求，假定：

(1)參與合乘乘客的所有需求信息可提前在線獲取.

(2)出租車比乘客提前到達(dá)候車區(qū)，乘客均到達(dá)后即駛離樞紐.

(3)車輛行駛勻速且所有出租車速度相同.

(4)路網(wǎng)道路通暢，不考慮行駛過程中擁堵等隨機(jī)擾動影響.

1.2 模型建立

引入有向網(wǎng)絡(luò)G={N,A}，N是點(diǎn)集合，A是邊集合，i,j,u是每個乘客的需求終點(diǎn)索引，i,j,u∈N，0表示樞紐點(diǎn).a(i,j)表示點(diǎn)i行駛至點(diǎn)j，a(i,j)∈A，利用軌跡點(diǎn)作為行駛軌跡的表現(xiàn)形式，i至j途經(jīng)軌跡點(diǎn)不反映在網(wǎng)絡(luò)G當(dāng)中，而是作為a(i,j)的屬性數(shù)據(jù).不考慮出租車返回樞紐的情況，將集合N中的需求終點(diǎn)按照與樞紐的距離升序排列.dij是i至j最短距離，rij是i至j的最短軌跡，途經(jīng)點(diǎn)集是需求i的最早出發(fā)時間，τ是乘客最長等待時間；是i的最晚到達(dá)時間，ti是到達(dá)i的實(shí)際時間，s是每個需求點(diǎn)的服務(wù)時間；V是行駛速度；K是所需出租車集合，k是出租車索引，k∈K，c是車輛容量；θsim是軌跡相似性度量指標(biāo)(見1.3節(jié))，λ為相似性度量閾值；xijk為0-1決策變量，車輛k通過a(i,j)，xijk=1，否則，xijk=0，xiuk,xujk的定義與取值同xijk.

為應(yīng)對樞紐高峰時期出租車運(yùn)力不足及避免周邊交通壓力，以所需出租車數(shù)量最小為目標(biāo)；同時，為兼顧運(yùn)輸效率，選取總行駛里程最小為目標(biāo)，構(gòu)建雙目標(biāo)模型為

目標(biāo)函數(shù)：式(1)最小化出租車所需數(shù)量，式(2)最小化所有車輛的行駛總里程.約束條件：式(3)和式(4)確保每個乘客能且只能乘坐一輛出租車；式(5)和式(6)表示所需出租車均從樞紐出發(fā)，服從先近后遠(yuǎn)的規(guī)則；式(7)確保流量平衡；式(8)為容量約束，即每輛出租車搭載乘客不超過c；式(9)和式(10)是時間窗約束，為減少乘客的排隊(duì)時間，加快旅客疏散，要求每位乘客在前乘坐出租車離開，即同乘一輛出租車乘客的最晚出發(fā)時間與最早出發(fā)時間的差值不超過τ；式(10)要求乘客在之前抵達(dá)終點(diǎn)；式(11)是軌跡相似度約束，表示合乘前后的軌跡相似性度量指標(biāo)需大于閾值λ，表示合乘后k車到達(dá)j點(diǎn)之間的所有路徑軌跡，表示合乘前樞紐點(diǎn)0到j(luò)點(diǎn)的路徑；式(12)是決策變量0-1整數(shù)約束.

1.3 軌跡相似性度量

以包圍面積作為度量依據(jù).圖1灰色部分是軌跡r1和r2的包圍面積[7]，本文均是對起終點(diǎn)相同的兩條軌跡進(jìn)行比較，故所圍區(qū)域閉合.

為統(tǒng)一量綱，將軌跡之間的平均距離表示為面積與較短軌跡長度的比值，即

式中：dave(r1,r2)是兩條軌跡間的平均距離；l(r1)，l(r2)分別表示r1,r2的長度；S(r1,r2)是r1與r2所圍成的面積.dave(r1,r2)越小表示兩條軌跡重合度越大，匹配概率越大.

圖1 包圍面積Fig.1 Boundary area

利用高斯核函數(shù)對距離指標(biāo)值dave(r1,r2)標(biāo)準(zhǔn)化，得到軌跡相似度指標(biāo)為

式中：θsim(r1,r2)是標(biāo)準(zhǔn)化后的軌跡相似度指標(biāo)，θsim∈(0,1)；σ是帶寬，控制原指標(biāo)值的作用范圍.θsim越大表示軌跡重合度越大，匹配概率越大.

圖2為軌跡匹配成功后如何更新路線.設(shè)λ為軌跡相似度閾值，匹配規(guī)則如下：

圖2 路徑更新Fig.2 Route update

(1)θsim(r0,j,r0,i,j)≥λ,需求i,j軌跡匹配成功，d0,j=d0,i+di,j,r0,j=r0,i,j.

(2)θsim(r0,j,r0,i,j)＜λ,需求i,j匹配失敗.

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

上述模型屬于VRP(Vehicle Route Problem)，作為NP-hard問題，難以找到算法在多項(xiàng)式時間內(nèi)解決.傳統(tǒng)路網(wǎng)合乘問題可根據(jù)出租車原始行程作為基準(zhǔn)來匹配附近可能的乘客需求，本文不具備該基準(zhǔn)，使得乘客匹配可行組合數(shù)量龐大，并且車輛數(shù)作為目標(biāo)函數(shù)增加了問題的復(fù)雜性.文獻(xiàn)已證明聚類將大規(guī)模VRP問題分解成小規(guī)模子問題，再采用蟻群算法求解能夠節(jié)省計(jì)算時間且求解結(jié)果更優(yōu)[8]，因此將算法分為兩階段：

(1)乘客需求聚類.將乘客需求進(jìn)行聚類以縮小優(yōu)化的搜索范圍.結(jié)果如圖3所示.

(2)合乘匹配.使用雙目標(biāo)蟻群算法進(jìn)行匹配優(yōu)化.結(jié)果如圖4所示.

圖3 聚類示意Fig.3 Clustering schematic

圖4 匹配示意Fig.4 Matching schematic

2.1 需求聚類

行駛路徑和時間窗是出行需求的核心組成要素.本文所有乘客的起點(diǎn)相同(樞紐站)，決定路徑的是方向和終點(diǎn).若乘客的路線方向相近，終點(diǎn)之間的距離對本文由近及遠(yuǎn)的行駛模式影響較小，因此選擇(出發(fā)時間，方向角)向量進(jìn)行聚類.設(shè)ω為終點(diǎn)方向角集合，ω={ω1,ω2,…,ωi,…,ωn}，ωi=(iy-Oy)(ix-Ox),ωi∈(-π,π),(ix,iy)是i的坐標(biāo)，i∈?+，(Ox,Oy)是樞紐站的坐標(biāo).k-mediods方法適用于低緯度聚類并能降低聚類對孤立點(diǎn)的敏感度，故使用該方法進(jìn)行聚類，利用DB指標(biāo)[9]來確定聚類數(shù)目.

2.2 雙目標(biāo)蟻群算法設(shè)計(jì)

聚類后每個簇需要進(jìn)行匹配優(yōu)化.蟻群算法對解決VRP系列問題有較好的性能.為加快收斂速度，用最近鄰近算法得出可行解作為蟻群算法的初始解和初始信息素.

圖5為匹配算法整體流程，Iiter為迭代索引，Iiter_m為最大迭代次數(shù)，Uupper為出租車需求數(shù)量的上限.搜索最短總里程的過程中，可能通過增加車輛數(shù)減少系統(tǒng)總里程，故先確定最優(yōu)解出租車數(shù)量的上限，再對總里程進(jìn)行優(yōu)化.

圖5 基于蟻群算法的匹配優(yōu)化整體流程Fig.5 Matching optimization process based on ant colony algorithm

(1)初始解計(jì)算.

初始化信息素為

式中：δ0是初始信息素；L1是最近鄰近算法得到的總里程.最近鄰近算法為隨機(jī)選擇第1個需求點(diǎn)i，在剩余滿足約束的需求點(diǎn)集合中，選擇距離該點(diǎn)最近的需求點(diǎn)，以此類推，直到該車達(dá)到容量限制或者無需求點(diǎn)可選為止，增加一輛空車重復(fù)以上步驟，當(dāng)所有點(diǎn)均被服務(wù)后計(jì)算所需車輛數(shù)||K和系統(tǒng)總里程L1.

(2)確定最優(yōu)解出租車數(shù)量上限.

利用蟻群算法的初代確定出租車最優(yōu)數(shù)量的上限，具體算法如下：

Input最近鄰近算法計(jì)算所得，螞蟻數(shù)量M，所有乘客需求信息①設(shè)置ACO所有參數(shù),Uupper=|K|②form=1toM③ 螞蟻m進(jìn)行搜索④ if搜索成功 & 車輛數(shù)小于等于Uupper⑤ then⑥ Uupper=Uupper-1⑦ end if⑧end for OutputUupper

(3)信息素更新與轉(zhuǎn)移規(guī)則.

信息素更新，選擇每次迭代中的前兩條最短路徑所經(jīng)過的a(i,j)進(jìn)行全局更新.

轉(zhuǎn)移規(guī)則，若每輛出租車第1位乘客的終點(diǎn)離樞紐較近能夠加大后續(xù)匹配成功率，所以每增加一輛新出租車時，僅在剩余可供選擇的需求集的前半部分產(chǎn)生第1個需求點(diǎn).考慮時間窗越寬匹配概率越大，安排出租車去服務(wù)下一個需求點(diǎn)的轉(zhuǎn)移公式為

3 案例分析

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

以北京南站為例，收集2019年3月15日22:00-23:00，在出租車調(diào)度站等候出租車乘客的需求信息，共計(jì)456條.包括終點(diǎn)目的地、到達(dá)出租車停靠點(diǎn)的時間，以及可接受最晚到達(dá)目的地的時間.部分?jǐn)?shù)據(jù)如表1所示.

表1 部分乘客信息表Table 1 Partial passenger information

3.2 實(shí)驗(yàn)過程

不同聚類數(shù)所對應(yīng)DB指標(biāo)值如圖6所示，當(dāng)聚類數(shù)為13時達(dá)到拐點(diǎn)，此后聚類個數(shù)的增加所對應(yīng)DB指標(biāo)下降減緩.故將13作為目標(biāo)聚類數(shù)目，聚類結(jié)果如表2所示.

圖6 不同聚類數(shù)下的DB指標(biāo)值Fig.6 DB values of different number of clusters

表2 聚類結(jié)果Table 2 Clustering results

聚類后，通過高德API獲取簇中所有需求點(diǎn)的最短距離及最短軌跡矩陣，軌跡數(shù)據(jù)包括約578萬條GPS坐標(biāo)(取樣1 s/條).為節(jié)約計(jì)算內(nèi)存，利用Douglas-Peucker方法進(jìn)行拐點(diǎn)識別簡化軌跡[10].圖7為北京南站至各終點(diǎn)的軌跡，以及終點(diǎn)之間的軌跡(以簇3為例)，軌跡中所有的道路拐點(diǎn)均被精確提取.

參數(shù)設(shè)置如表3所示，經(jīng)靈敏度分析(3.3.1節(jié))，閾值λ=0.9.利用MATLAB進(jìn)行計(jì)算，得出分簇結(jié)果如圖8和圖9所示，整體結(jié)果如表4所示.

圖7 簇3所有需求點(diǎn)軌跡及拐點(diǎn)識別Fig.7 All trajectories and inflection-points of cluster 3

表3 參數(shù)設(shè)置Table 3 Parameter settings

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

3.3.1 軌跡相似度閾值靈敏度分析

λ取值0.70～0.98時，目標(biāo)函數(shù)總里程與車輛數(shù)的變化情況如圖8所示，閾值越大，目標(biāo)函數(shù)值越大.整體而言：λ取值在0.70～0.84時，對車輛數(shù)變化影響微弱，在145上下浮動，總里程小幅穩(wěn)定增長；λ取值在0.92～0.98時，車輛數(shù)和總里程增幅均較大，此時λ對目標(biāo)函數(shù)的影響程度較大；λ取值在0.86～0.90時，是車輛數(shù)和總里程數(shù)的拐點(diǎn)區(qū)域，在此范圍內(nèi)取值時，可保證繞行比例較小的同時避免目標(biāo)函數(shù)增長過快.

3.3.2 結(jié)果對比

圖9為λ=0.9時，各簇所需車輛數(shù)和節(jié)省里程比例.節(jié)省里程比例最高的是簇3，最低的是簇11，結(jié)合需求數(shù)量，簇3與簇11車輛數(shù)優(yōu)化亦為最佳與最差.說明，各簇的匹配結(jié)果與其聚類情況關(guān)系緊密，簇中方向角和出發(fā)時間跨度越小匹配效果越好，反之亦然.

圖10是乘客繞行比例箱線圖，整體繞行比例較??；各簇的平均繞行比例低于1.1，75%乘客繞行比例小于1.2，最大為1.4，最小為1.0.本文方法能夠有效減弱繞行情況.

圖8 軌跡相似度閾值靈敏度分析Fig.8 Trajectory similarity threshold sensitivity analysis

圖9 各簇計(jì)算車輛數(shù)和節(jié)約里程比例Fig.9 Calculated number of taxis and saving mileage ratios for all clusters

圖10 所有乘客的繞行比例箱線圖Fig.10 Detour ratios boxplot of all passengers

表 4 整體計(jì)算結(jié)果及對比Table 4 Overall results and compare

由表4可知：車輛數(shù)由合乘前的456輛縮減至161輛，合乘成功率為91%，總里程比合乘前縮減近50%；乘客平均繞行比例為1.07，等待時間為1.95 min.整體效果較好，集約系統(tǒng)資源的同時保障了乘客的利益.

將結(jié)果與無軌跡相似約束模型、單目標(biāo)優(yōu)化模型的結(jié)果進(jìn)行對比.刪去軌跡相似約束之后，車輛數(shù)和總里程有小幅降低，平均繞行比例增加至1.23.無軌跡形態(tài)要求略微提高了合乘成功率，但易使行駛路線繞行增加.

JAC指標(biāo)旨在量化路段重合情況，計(jì)算公式[11]為

模型計(jì)算的JAC平均值為0.545，無軌跡相似約束計(jì)算出JAC平均值為0.401，說明添加軌跡相似度約束的合乘路徑更接近乘客對行駛路徑的預(yù)期.單目標(biāo)優(yōu)化中的目標(biāo)函數(shù)是最小化行駛總里程.僅追求總里程最小時車輛數(shù)增加至175輛，比原有結(jié)果增加了8%，且乘客平均繞行比例、等待時間、JAC指標(biāo)的結(jié)果改善甚微.說明雙目標(biāo)優(yōu)化能在保證系統(tǒng)優(yōu)化同時，縮減出租車使用規(guī)模.

4 結(jié)論

本文提出基于軌跡相似性度量的合乘匹配方法.在引入軌跡相似度進(jìn)行約束，保證規(guī)劃路徑滿足乘客心理預(yù)期的基礎(chǔ)上，以最小車輛數(shù)和最少總里程為目標(biāo)建立雙目標(biāo)優(yōu)化模型.設(shè)計(jì)先聚類后匹配的兩階段算法進(jìn)行求解.結(jié)果表明，經(jīng)靈敏度分析，閾值在0.86～0.90時，能兼顧規(guī)劃路線繞行比例較小及目標(biāo)函數(shù)達(dá)到較優(yōu)水平.對比其他方法，本文方法對優(yōu)化車輛數(shù)和總里程有良好的效果，保證乘客等待時間較低，軌跡相似性度量約束能有效提高合乘后路徑的JAC值.對出租車合乘發(fā)展有一定實(shí)踐意義.