動(dòng)態(tài)車輛共乘問題的雙模式協(xié)作匹配算法

郭羽含 劉永武

(遼寧工程技術(shù)大學(xué)軟件學(xué)院 遼寧葫蘆島 125105)

車輛共乘(ride-sharing)問題指對(duì)一定時(shí)空范圍內(nèi)的可用服務(wù)車輛與無車乘客的出行需求進(jìn)行匹配并對(duì)其行駛路徑進(jìn)行規(guī)劃，以提升運(yùn)輸資源利用率、減少車輛的并發(fā)使用，對(duì)降低運(yùn)輸成本、緩解交通擁堵、降低環(huán)境污染具有重要作用.

根據(jù)車輛提供的服務(wù)特性，一般將車輛共乘問題分為順風(fēng)車模式和出租車模式.其中，順風(fēng)車模式指車主和乘客通過共乘服務(wù)平臺(tái)發(fā)布其各自行程，需最大化車主與乘客的共享路程；而出租車模式指車主以運(yùn)輸乘客賺取利潤(rùn)為目，需最小化車主所在地和乘客所在地間的無共乘路程[1].與順風(fēng)車模式相比，出租車模式僅移除了車主從乘客目的地行駛到自身目的地的過程，因此可看作順風(fēng)車模式的一種特例，故本文針對(duì)順風(fēng)車模式進(jìn)行研究.

基于匹配實(shí)時(shí)性可將共乘問題分為靜態(tài)共乘問題(static ride-sharing)和動(dòng)態(tài)共乘問題(dynamic ride-sharing).靜態(tài)共乘問題僅考慮一個(gè)固定時(shí)間窗口內(nèi)的車主與乘客匹配及路徑規(guī)劃，且車主與乘客的出發(fā)時(shí)間和位置均可預(yù)先獲取，匹配完成后車主根據(jù)規(guī)劃的路徑行駛，沿途不再進(jìn)行后續(xù)匹配活動(dòng)，路徑也不再變更.此種共乘模式限制了車主的實(shí)載率，導(dǎo)致運(yùn)輸資源利用率降低、乘客的匹配等待時(shí)間增加.動(dòng)態(tài)共乘問題考慮一個(gè)動(dòng)態(tài)持續(xù)的過程，車主在行駛過程中可繼續(xù)匹配沿途滿足路程約束和乘客要求的待匹配乘客并持續(xù)優(yōu)化車主的行駛路徑.該模式對(duì)靜態(tài)共乘進(jìn)行了擴(kuò)展，可更好地利用運(yùn)輸資源，降低乘客的等待時(shí)間.

相較于傳統(tǒng)車輛路徑規(guī)劃問題[2-3]和靜態(tài)共乘問題[4]，國(guó)內(nèi)外對(duì)于動(dòng)態(tài)共乘問題的研究較少，文獻(xiàn)[5-6]對(duì)本問題進(jìn)行了綜述，將其研究方向主要?dú)w納為提高車主和乘客的匹配度[7-11]、降低行程開銷[12-15]和減少用戶等待時(shí)間[16-18]等方面.

1) 在提高匹配度方面.Zhang等人[7]設(shè)計(jì)了一種能夠最大化乘客流動(dòng)性的貪婪算法；Stiglic等人[8]以接客點(diǎn)來提高匹配方案的效率和靈活性；Zhan等人[9]建立了一個(gè)最大化服務(wù)乘客數(shù)量、最小化出行成本的動(dòng)態(tài)共乘系統(tǒng)；Enzi等人[10]引入多模式汽車和乘車共享問題，并通過基于列生成的雙層分解算法進(jìn)行求解；Ta等人[11]設(shè)計(jì)了一種基于共享路程比率最大化的匹配模型.

2) 在降低行程開銷方面.劉文彬等人[12]設(shè)計(jì)了一種以最小化車輛繞行距離為優(yōu)化目標(biāo)的線性時(shí)間插入操作方法；Alisoltani等人[13]使用基于動(dòng)態(tài)出行的宏觀模擬來評(píng)估解決方案，考慮了通過出行時(shí)間獲得最優(yōu)解決方案的擁堵效應(yīng)和動(dòng)態(tài)出行方案；?zkan[14]通過制定乘客共享模型證明了聯(lián)合定價(jià)和匹配決策對(duì)系統(tǒng)性能有顯著影響；Schilde等人[15]提出了2套考慮車輛行駛速度影響因素的元啟發(fā)式匹配方案.

3) 在減少用戶等待時(shí)間方面.Cheikh-Graiet等人[16]提出了基于禁忌搜索的元啟發(fā)式動(dòng)態(tài)拼車優(yōu)化算法；曹斌等人[17]提出了一種高效的大規(guī)模多對(duì)多拼車匹配算法；肖強(qiáng)等人[18]基于泊松分布模擬了出租車合乘概率及等待時(shí)間.

由于動(dòng)態(tài)共乘需實(shí)時(shí)計(jì)算數(shù)以萬計(jì)的車主與乘客的匹配訂單，因此對(duì)算法的求解效率和求解質(zhì)量要求極高.雖然近年來已對(duì)動(dòng)態(tài)共乘進(jìn)行了部分研究工作，但在全局最優(yōu)性、動(dòng)態(tài)匹配實(shí)時(shí)性和共乘比率等方面仍存在不足.如文獻(xiàn)[1,11]中提出的自適應(yīng)搜索策略和近似解算法在考慮求解效率時(shí)并未考慮車主和乘客的匹配率；動(dòng)態(tài)共乘問題對(duì)實(shí)時(shí)性要求較高，文獻(xiàn)[19-25]在考慮車主匹配率或總體消耗時(shí)并未考慮車主的實(shí)時(shí)性匹配問題；文獻(xiàn)[20-21,23-33]在優(yōu)化總體行駛距離或總體行時(shí)間時(shí)忽略了車主和乘客間路徑重合度，降低了車主和乘客的共乘路徑，無法高效提高運(yùn)輸效率.表1對(duì)現(xiàn)有的代表性研究進(jìn)行了總結(jié)，并分析了各研究對(duì)時(shí)間窗、繞行距離、總花費(fèi)、匹配率等主要指標(biāo)的考慮情況.

本文針對(duì)固定時(shí)空范圍內(nèi)的動(dòng)態(tài)共乘問題展開研究，將匹配過程分為離線匹配階段和在線匹配階段.首先，提出通用共乘比率和首尾距離度2種評(píng)估標(biāo)準(zhǔn)，以準(zhǔn)確地評(píng)估不同階段的匹配價(jià)值；其次，提出一種基于約束時(shí)間窗和繞行距離約束的距離矩陣生成算法，于匹配前對(duì)車主和乘客集合進(jìn)行篩選，從而降低數(shù)據(jù)規(guī)模，并通過改進(jìn)的距離矩陣生成算法計(jì)算車主與乘客間的距離矩陣；再次，在離線匹配階段提出一種基于帶權(quán)路徑搜索樹的通用共乘比率生成算法以提升求解質(zhì)量，從而提高全局匹配率；最后，于在線匹配階段提出一種首尾距離度的實(shí)時(shí)訂單插入算法，根據(jù)實(shí)時(shí)匹配到的乘客對(duì)離線匹配階段生成的標(biāo)準(zhǔn)路徑進(jìn)行動(dòng)態(tài)更新，在保證實(shí)時(shí)性的情況下進(jìn)一步提升全局匹配率.

Table 1 Related Research Situation of Dynamic Ride-Sharing表1 動(dòng)態(tài)共乘相關(guān)研究情況

本文的主要貢獻(xiàn)有4個(gè)方面：

1) 針對(duì)動(dòng)態(tài)共乘問題形式化定義了2種匹配價(jià)值評(píng)估標(biāo)準(zhǔn)，并建立了一種基于雙模式協(xié)作匹配的數(shù)學(xué)模型，將匹配過程動(dòng)態(tài)描述為離線匹配階段和在線匹配階段；

2) 于離線匹配階段提出了帶權(quán)路徑搜索樹中的單條帶權(quán)路徑理論，并基于此理論構(gòu)建了一種基于帶權(quán)路徑搜索樹的通用共乘比率生成算法；

3) 于在線匹配階段提出了單一首尾距離度評(píng)估標(biāo)準(zhǔn)和基于2種距離系數(shù)的復(fù)合首尾距離度評(píng)估標(biāo)準(zhǔn)，結(jié)合實(shí)時(shí)更新標(biāo)準(zhǔn)路徑的訂單插入算法，構(gòu)建了一種基于首尾距離度的實(shí)時(shí)訂單插入算法；

4) 通過大量真實(shí)算例進(jìn)行了實(shí)驗(yàn)分析，驗(yàn)證了本算法解決動(dòng)態(tài)共乘問題的有效性，并證明了基于雙模式的匹配方法可以大幅增加高價(jià)值共乘路程、降低車輛空載率，從而提升交通資源利用率.

1 問題建模

本節(jié)首先對(duì)動(dòng)態(tài)共乘問題涉及的角色進(jìn)行定義，然后對(duì)離線匹配階段和在線匹配階段及其優(yōu)化目標(biāo)進(jìn)行建模.

1.1 角色定義

定義1.車主.集合D={di,i∈[1,m]∩}表示車主集，其中di代表車主i，車主當(dāng)前狀態(tài)statusi=[ldi,adi,Cdi,Tdi,Ldi]表示每個(gè)車主具有所在地ldi、目的地adi、車容量Cdi、出發(fā)時(shí)間Tdi和初始行駛路徑Ldi五個(gè)屬性.

定義2.乘客.集合R={rj,j∈[1,n]∩}表示乘客集，其中rj代表乘客j，以乘客行程tripsj=[lrj,arj,Trj]表示每個(gè)乘客具有所在地lrj、目的地arj和出發(fā)時(shí)間Trj三個(gè)屬性.

在動(dòng)態(tài)共乘匹配過程中，由于車主di能夠沿途匹配多個(gè)乘客r，即單車主多乘客問題，傳統(tǒng)共乘比率(shared route percentage,SRP)[34]只能處理單車主單乘客問題，在處理單車主多乘客時(shí)會(huì)變得異常復(fù)雜，因而求解匹配結(jié)果也變得尤為困難.本文基于帶權(quán)路徑搜索樹提出了通用共乘比率，可在計(jì)算動(dòng)態(tài)匹配問題時(shí)高效地求得匹配結(jié)果.傳統(tǒng)共乘比率計(jì)算方式為

(1)

其中,dis(lrj,arj)表示乘客rj的所在地lrj和目的地arj間的距離；dis(ldi,lrj)表示車主di的所在地ldi與乘客rj的所在地lrj間的距離；dis(arj,adi)表示乘客rj的目的地arj與車主di的目的地adi間的距離.

定義3.通用共乘比率(general shared route per-centage,GSRP).GSRP是指車主與乘客共乘路徑占車主因接送乘客行駛的總路徑的比率.

對(duì)于任意車主di，給定一個(gè)帶權(quán)路徑搜索樹Tree=(V,E)和權(quán)重函數(shù)ω:E→.其中，V表示為車主di的所在地和目的地與待匹配乘客rj的所在地和目的地組成的節(jié)點(diǎn)集，E表示節(jié)點(diǎn)間的邊集；權(quán)重函數(shù)將2個(gè)節(jié)點(diǎn)間的每條邊映射到實(shí)數(shù)值的權(quán)重上.搜索樹中的單條帶權(quán)路徑swp=〈v1,v2,…,v2(c+1)〉的權(quán)重ω(swp)是構(gòu)成該路徑的所有邊的權(quán)重之和：

(2)

對(duì)于任意的i和j，1≤i≤j≤2(c+1)，其中c為當(dāng)前匹配乘客數(shù)，定義從節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的最短路徑權(quán)重為

(3)

δ(v1,v2(c+1))即為單條帶權(quán)路徑的最短路徑.λ為此最短路徑中的共乘路徑：

λ=swp-〈v1,v2〉-〈v2c+1,v2(c+1)〉.

(4)

通用共乘比率可表達(dá)為

(5)

則GSRP的形式可分解為共乘路徑和單條帶權(quán)最短路徑2段路徑：

(6)

s.t.i,j∈[1,2(c+1)],

(7)

i

(8)

c≤Cdi.

(9)

其中，式(7)限定了i和j的取值范圍；式(8)中〈vi,vi+1,…,vj〉是1條有序的路徑；式(9)是乘客數(shù)小于車輛的最大容量.

離線匹配階段使用GSRP來評(píng)價(jià)車主共享資源的利用效率，并以繞行距離(detour length,DL)[34]對(duì)其進(jìn)行約束，從而平衡車主共享效率和乘客訂單可行性.車主與乘客的GSRP反映了乘客與車主的匹配價(jià)值.車主出行效益取決于乘客與之共乘的共享路徑長(zhǎng)短，因此，該值越大則表示車主的高匹配價(jià)值路程越長(zhǎng)，車主的運(yùn)輸資源利用效率越高，反之則表示車主把大量路程浪費(fèi)在獨(dú)自行駛過程中，空載率越高，運(yùn)輸資源的利用效率越低.

定義4.標(biāo)準(zhǔn)路徑L.L即為離線匹配階段和在線匹配階段在動(dòng)態(tài)匹配過程中規(guī)劃出的行駛路徑，其距離為disL.車主的初始標(biāo)準(zhǔn)路徑為未匹配乘客時(shí)的行駛路徑Ld，其距離為disLd.同理，乘客的初始標(biāo)準(zhǔn)路徑為其獨(dú)自出行的行駛路徑Lr，其距離為disLr.針對(duì)車主的繞行距離定義為dDL，針對(duì)共乘乘客的繞行距離定義為rDL，計(jì)算公式為：

(10)

在線匹配階段使用首尾距離度作為匹配標(biāo)準(zhǔn)，針對(duì)離線匹配后生成的標(biāo)準(zhǔn)路徑，首尾距離度反映了在線匹配階段待匹配乘客所在地和目的地是否在標(biāo)準(zhǔn)路徑附近，以及距離車主所在地和目的地的遠(yuǎn)近，該值越大則表示待匹配乘客的路徑與標(biāo)準(zhǔn)路徑越接近，從而大大減小了車主更新標(biāo)準(zhǔn)路徑的幅度和接送待匹配乘客的繞行距離.

定義5.首尾距離度(location to destination,LTD).LTD表示乘客r所在地和目的地分別與標(biāo)準(zhǔn)路徑各個(gè)部分間以及車主所在地和目的地的最短距離加權(quán)和的倒數(shù).

設(shè)有車主與乘客生成的標(biāo)準(zhǔn)路徑L、待匹配乘客r、乘客所在地lrj與標(biāo)準(zhǔn)路徑L各個(gè)部分間的最短路徑Llr和乘客目的地arj與標(biāo)準(zhǔn)路徑L各個(gè)部分間的最短路徑Lar；乘客所在地lrj與車主所在地ldi間的最短路徑Lldr和乘客目的地arj與車主目的地adi間的最短路徑Ladr.為進(jìn)一步提升算法求解效率，在離線匹配階段未匹配到乘客的情況下，于在線匹配階段使用單一首尾距離度進(jìn)行評(píng)估,如式(11)所示；否則，使用復(fù)合首尾距離度進(jìn)行評(píng)估，如式(12)所示.

(11)

(12)

s.t.Larad?L,

(13)

Lldlr?L,

(14)

θ,η≤1,θ+η=1,

(15)

其中,θ表示乘客r所在地和目的地與車主d所在地和目的地的距離系數(shù)，η表示乘客r所在地和目的地與標(biāo)準(zhǔn)路徑的距離系數(shù)，距離系數(shù)在乘客距離標(biāo)準(zhǔn)路徑的遠(yuǎn)近和乘客乘車的路程間做出權(quán)衡，車主可根據(jù)個(gè)人意愿設(shè)置2種距離系數(shù)來調(diào)整待匹配乘客集合.L表示離線匹配后生成的標(biāo)準(zhǔn)路徑，Larad表示乘客r目的地之后對(duì)應(yīng)的標(biāo)準(zhǔn)路徑的部分，Lldlr表示乘客r所在地之前對(duì)應(yīng)的標(biāo)準(zhǔn)路徑的部分.式(13)表示在計(jì)算乘客r所在地到標(biāo)準(zhǔn)路徑的最短距離時(shí)不計(jì)算目的地之后的部分路徑Larad；式(14)表示在計(jì)算乘客r目的地到標(biāo)準(zhǔn)路徑的最短距離時(shí)不計(jì)算所在地之前的部分路徑Lldlr；式(15)限定了2種距離系數(shù)的取值范圍.本文涉及的變量如表2所示：

Table 2 Variables表2 變量表

1.2 優(yōu)化目標(biāo)

雙模式協(xié)作匹配算法在進(jìn)行數(shù)學(xué)建模時(shí)將優(yōu)化目標(biāo)根據(jù)離線匹配階段和在線匹配階段不同的價(jià)值評(píng)估標(biāo)準(zhǔn)進(jìn)行分析.離線匹配階段以定義3中的通用共乘比率來評(píng)價(jià)車主與乘客的匹配價(jià)值，定義車主i與乘客j匹配價(jià)值為gij；在線匹配階段以首尾距離度來評(píng)價(jià)對(duì)應(yīng)的匹配價(jià)值，此時(shí)車主i和乘客j的匹配價(jià)值為wij.xij和yij分別表示離線匹配階段和在線匹配階段車主與乘客是否匹配.問題目標(biāo)即為通過動(dòng)態(tài)共乘匹配過程得出一種匹配方案使得所有車主乘客匹配對(duì)的價(jià)值總和最大.此時(shí)的目標(biāo)函數(shù)為：

(16)

s.t.xij+yij≤1,?i∈[1,m],?j∈[1,n],

(17)

(18)

(19)

xij,yij∈{0,1},?i∈[1,m],?j∈[1,n],

(20)

dDL≤μ×disLd,

(21)

rDL≤μ×disLr,

(22)

Trj>Tdi(xij+yij),

(23)

D∩R=?.

(24)

其中：式(17)表示每名乘客與每名車主間只能在離線匹配階段或在線匹配階段匹配一次；式(18)表示每名乘客只能匹配到1名車主；式(19)表示每名車主在離線和在線匹配階段匹配到的總乘客數(shù)應(yīng)小于等于車容量；式(20)限定xij和yij的取值范圍，0表示不匹配，1表示匹配；式(21)定義了車主的繞行距離，μ為繞行距離系數(shù)，約束車主的最大繞行距離；式(22)定義了共乘乘客的繞行距離，μ為繞行距離系數(shù)，約束乘客的最大繞行距離；式(23)表示待匹配乘客出發(fā)時(shí)間晚于車主出發(fā)時(shí)間；式(24)表示車主和乘客具有身份唯一性.

動(dòng)態(tài)共乘匹配過程需對(duì)數(shù)以萬計(jì)車主乘客集合進(jìn)行全局匹配，對(duì)算法的求解效率和求解質(zhì)量要求極高，主要面臨3個(gè)求解難點(diǎn)：

1) 全局最優(yōu)性.由于并發(fā)的車主乘客數(shù)量巨大，且在匹配后行駛過程中仍實(shí)時(shí)出現(xiàn)新車主和新乘客，故求解難度高，難以保證匹配速度與質(zhì)量.

2) 共乘比率.在動(dòng)態(tài)共乘匹配過程中，車主能夠沿途匹配多個(gè)乘客，即車主乘客一對(duì)多問題.在面對(duì)一對(duì)多問題時(shí)，計(jì)算單車主單乘客匹配問題的傳統(tǒng)共乘比率會(huì)變得異常復(fù)雜，因而無法獲得較好的求解效果.

3) 動(dòng)態(tài)實(shí)時(shí)性.在計(jì)算車主和乘客間的通用共乘比率時(shí)，由于實(shí)際路網(wǎng)數(shù)量巨大、復(fù)雜度高，同時(shí)需要規(guī)劃出任一車主和乘客每段路徑的最短路徑，子路徑規(guī)劃難度高，故計(jì)算量巨大，無法保證算法的實(shí)時(shí)性.

2 雙模式協(xié)作匹配算法

本節(jié)針對(duì)數(shù)學(xué)建模階段提出的研究難點(diǎn)提出相應(yīng)的解決方案，設(shè)計(jì)了雙模式協(xié)作匹配算法.于2.1節(jié)提出距離矩陣生成算法，在匹配前對(duì)乘客集合進(jìn)行約束處理篩選出車主和對(duì)應(yīng)的待匹配乘客集合，簡(jiǎn)化最短路徑的計(jì)算復(fù)雜度和計(jì)算量，從而保障了后續(xù)匹配過程中的動(dòng)態(tài)實(shí)時(shí)性；于2.2節(jié)離線匹配階段中，針對(duì)動(dòng)態(tài)車輛共乘問題中的全局最優(yōu)化問題，提出了基于單條帶權(quán)最短路徑的帶權(quán)路徑搜索樹，并根據(jù)帶權(quán)路徑搜索樹提出了基于通用共乘比率的價(jià)值矩陣生成算法，解決了基于傳統(tǒng)單車主單乘客共乘比率的價(jià)值矩陣生成算法在處理單車主多乘客時(shí)計(jì)算異常復(fù)雜的問題；于2.3節(jié)在線匹配階段使用基于首尾距離度的價(jià)值矩陣生成算法來代替計(jì)算量巨大的基于共乘比率的價(jià)值矩陣生成算法.本算法總體框架如圖1所示，總體流程如圖2所示：

Fig. 1 Bimodal cooperative matching algorithm frame圖1 雙模式協(xié)作匹配算法總體框架圖

Fig. 2 Bimodal cooperative matching algorithm process圖2 雙模式協(xié)作匹配算法流程圖

2.1 距離矩陣生成算法

本節(jié)針對(duì)動(dòng)態(tài)共乘匹配中在計(jì)算車主與乘客的匹配程度時(shí)計(jì)算量大以及存在大量對(duì)于當(dāng)前車主無效的乘客集合的問題，提出2個(gè)解決方案：

1) 于匹配前為車主篩選出待匹配的乘客集合，無須計(jì)算復(fù)雜的實(shí)際路網(wǎng)，因此模型早期可在不花費(fèi)大量計(jì)算開銷的情況下篩選出部分待匹配乘客R.此階段輸出的是經(jīng)過車主繞行距離約束和時(shí)間約束篩選的待匹配乘客集合Rd，待匹配乘客滿足當(dāng)前車主最基本的匹配約束.

2) 在計(jì)算GSRP和LTD時(shí)，最大的開銷為循環(huán)計(jì)算待匹配乘客與標(biāo)準(zhǔn)路徑上各節(jié)點(diǎn)間的最短距離，因此本文中采用算法1中的距離矩陣來存儲(chǔ)最短距離，可很大程度上降低時(shí)間開銷.距離矩陣生成算法根據(jù)已經(jīng)得到的標(biāo)準(zhǔn)路徑上各節(jié)點(diǎn)計(jì)算與待匹配乘客rj間的最短距離，在計(jì)算距離矩陣時(shí)使用上三角矩陣代替方陣，使得原本的時(shí)間消耗從O(m×n)降為O(m×n/2)，最終得到距離矩陣U.距離矩陣生成算法見算法1.

算法1.基于約束時(shí)間窗和繞行距離約束的距離矩陣生成算法.

輸入：車主集合D、乘客集合R和標(biāo)準(zhǔn)路徑；

輸出：車主的待匹配乘客集合Rd.

①d∈Dandr∈R；

②Dis_matrix(L,r)=U[d][r]；

/*距離矩陣函數(shù)*/

③M=N=[L,lr,ar]；

④ forminM.size

⑤ forninm

⑥ ifm==n

⑦u(m,n)=0；

/*u為U[d][r]中的距離元素*/

⑧ else

⑨u(m,n)=Euclidean_dis(m,n)；

⑩ end if

/*從距離矩陣中獲得節(jié)點(diǎn)間的距離*/

/*超出車主最大繞行距離,不滿足時(shí)間窗約束*/

/*從待匹配乘客集合中移除乘客r*/

在離線匹配計(jì)算共乘比率過程中最大的計(jì)算開銷為最短路徑的計(jì)算.對(duì)于大型算例，Dijkstra算法和Floyd算法計(jì)算開銷過大，本文使用歐氏距離代替實(shí)際路網(wǎng)距離計(jì)算，通過實(shí)驗(yàn)驗(yàn)證基于歐氏距離在共乘比率和匹配率方面不會(huì)產(chǎn)生較大誤差，且能夠提升算法求效率.

(25)

如式(25)所示，任意2點(diǎn)間的歐氏距離小于或等于相同的2點(diǎn)間的實(shí)際路網(wǎng)距離，如乘客與車主間的歐氏距離不滿足當(dāng)前車主di的最大繞行距離約束，則無須計(jì)算實(shí)際路網(wǎng)距離，直接將該乘客排除在車主di的匹配范圍之外.

2.2 離線匹配階段

動(dòng)態(tài)共乘匹配過程由于并發(fā)的車主乘客數(shù)量巨大，且在匹配后行駛過程中仍實(shí)時(shí)出現(xiàn)新車主和新乘客，故很難解決全局最優(yōu)性問題.針對(duì)此問題需高效計(jì)算得到車主與乘客的共乘比率，然而基于傳統(tǒng)單車主單乘客的共乘比率計(jì)算方法無法解決動(dòng)態(tài)共乘匹配過程中的多車主多乘客問題，因此本文的雙模式協(xié)作匹配算法在離線匹配階段主要提出2個(gè)解決方法：

1) 基于帶權(quán)路徑搜索樹提出了通用共乘比率計(jì)算方法，依賴樹形結(jié)構(gòu)的高搜索效率和通用共乘比率的高求解質(zhì)量來解決全局最優(yōu)性問題和共乘比率問題.

2) 于離線匹配階段根據(jù)匹配結(jié)果從帶權(quán)路徑搜索樹中搜索得到匹配方案的最優(yōu)路徑，即為標(biāo)準(zhǔn)路徑，使用標(biāo)準(zhǔn)路徑進(jìn)行下一次的動(dòng)態(tài)匹配，下一名乘客的匹配過程建立在上一名乘客與車主匹配完成規(guī)劃出的標(biāo)準(zhǔn)路徑上，能夠有效地提高乘客間的關(guān)聯(lián)性從而進(jìn)一步增大車主與乘客的匹配率，減小乘客的乘坐距離.

離線匹配階段，車主與乘客的匹配為非實(shí)時(shí)過程，設(shè)計(jì)算法時(shí)更加偏向于考慮求解質(zhì)量和匹配程度.離線匹配算法流程如圖3所示.

Fig. 3 Offline matching algorithm process圖3 離線匹配算法流程圖

設(shè)車主數(shù)量為m，乘客數(shù)量為n，以價(jià)值函數(shù)生成的m×n的價(jià)值矩陣為G，其中元素gij表示車主i和乘客j的價(jià)值.離線匹配算法基于帶權(quán)路徑搜索樹，依賴樹形結(jié)構(gòu)的高搜索效率及GSRP帶來的高求解質(zhì)量.車主di通過共乘服務(wù)平臺(tái)發(fā)布當(dāng)前狀態(tài)statusi，乘客rj通過共乘服務(wù)平臺(tái)發(fā)布行程tripsj,共乘服務(wù)平臺(tái)根據(jù)statusi和tripsj將車主和乘客執(zhí)行算法1，得到車主di的待匹配乘客集合Rd，在車主繞行距離和車容量的約束下進(jìn)行動(dòng)態(tài)匹配.在計(jì)算此階段的標(biāo)準(zhǔn)路徑時(shí)，首先通過算法1求得初始標(biāo)準(zhǔn)路徑上的點(diǎn)與待匹配乘客間的距離矩陣；然后根據(jù)算法2創(chuàng)建關(guān)于待匹配乘客rj和車主di的帶權(quán)路徑搜索樹Tree，將待匹配乘客rj的所在地lrj和目的地arj以及車主di的所在地ldi和目的地adi定義為{key,value}：

(26)

算法2.基于帶權(quán)路徑搜索樹的通用共乘比率生成算法.

輸入：車主集合D、待匹配乘客集合Rd；

輸出：離線階段標(biāo)準(zhǔn)路徑.

① fordinD

② forrinR

③Dis_Matrix(d,r)；

④ 初始標(biāo)準(zhǔn)路徑L；

⑤Tree←Init_Tree()；

/*初始化帶權(quán)路徑搜索樹*/

⑥Tree.root=ld；

/*車主所在地為根節(jié)點(diǎn)*/

⑦ldi.InsertChild()→ldi.cj=lrj；

/*將乘客所在地插入到根節(jié)點(diǎn)，例:

⑧l(xiāng)rj.BrotherNode=lrj,j≠this j；

/*乘客所在地節(jié)點(diǎn)的兄弟節(jié)點(diǎn)，例:

⑨Tree←InsertNode()；

⑩ whilek≤2(c+2) andarj.leaf=

False do

/*為乘客的所在地節(jié)點(diǎn)插入子節(jié)點(diǎn)，例:

/*為乘客的目的地節(jié)點(diǎn)插入子節(jié)點(diǎn)，例:

/*節(jié)點(diǎn)的權(quán)重等于累計(jì)節(jié)點(diǎn)權(quán)重*/

/*共乘路徑和車主行駛總路徑*/

/*gij為G中的元素*/

以ldi為根節(jié)點(diǎn)，按照算法2的規(guī)則依次插入乘客的所在地lrj和目的地arj，形成搜索樹的所有swp=〈v1,v2,…,v2(c+1)〉，從帶權(quán)路徑搜索樹中獲得單條帶權(quán)最短路徑,即為當(dāng)前已匹配乘客生成的標(biāo)準(zhǔn)路徑，由定義3可得GSRP，從而求得待匹配乘客和車主的價(jià)值矩陣G，由KM算法求解價(jià)值矩陣G，得到最優(yōu)匹配方案.當(dāng)前未匹配乘客和新進(jìn)入的待匹配乘客組成下一次的輸入乘客集合，循環(huán)執(zhí)行直至滿載或者進(jìn)入在線匹配階段.非實(shí)時(shí)的離線匹配階段結(jié)束后，得到一條離線匹配階段動(dòng)態(tài)規(guī)劃的標(biāo)準(zhǔn)路徑.

2.3 在線匹配階段

動(dòng)態(tài)匹配過程中的實(shí)時(shí)匹配過程對(duì)匹配的動(dòng)態(tài)實(shí)時(shí)性要求極高，算法需要同時(shí)兼顧全局最優(yōu)化、共乘比率和動(dòng)態(tài)實(shí)時(shí)性，然而在計(jì)算車主和乘客間的共乘比率時(shí)，由于實(shí)際路網(wǎng)數(shù)量巨大、計(jì)算復(fù)雜度高，同時(shí)需要規(guī)劃出任一車主和乘客每段路徑的最短路徑，子路徑規(guī)劃難度高，故計(jì)算量巨大，無法保證算法的實(shí)時(shí)性.因此本文的雙模式協(xié)作匹配算法在線匹配階段主要提出3個(gè)解決方法：

1) 使用首尾距離度代替計(jì)算消耗巨大的通用共乘比率作為價(jià)值評(píng)估標(biāo)準(zhǔn)，首尾距離度綜合考慮乘客的所在地和目的地與車主行駛的標(biāo)準(zhǔn)路徑間的最短距離以及乘客所在地和目的地與車主的所在地和目的地間的最短距離，使用歐氏距離代替實(shí)際路網(wǎng)進(jìn)行計(jì)算，能夠在保證匹配率和共乘比率的前提下高效地計(jì)算出匹配結(jié)果.

2) 根據(jù)離線匹配階段得到的標(biāo)準(zhǔn)路徑和匹配方案選擇使用單一首尾距離度或者復(fù)合首尾距離度來進(jìn)一步提高匹配率，從而滿足動(dòng)態(tài)共乘在線階段的實(shí)時(shí)性要求.

3) 根據(jù)在線匹配階段的匹配方案使用實(shí)時(shí)訂單插入算法將當(dāng)前匹配到的乘客的出發(fā)地和目的地實(shí)時(shí)地更新到標(biāo)準(zhǔn)路徑.

以下為在線匹配階段設(shè)計(jì)過程：在線匹配階段中針對(duì)離線匹配階段生成的標(biāo)準(zhǔn)路徑，若車主已匹配到乘客但處于未滿載狀態(tài)，為擴(kuò)大車主di的共乘比率，車主di在行駛過程中繼續(xù)匹配沿途的乘客rj，根據(jù)車主當(dāng)前的statusi和乘客發(fā)布的tripsj進(jìn)行在線匹配階段的匹配過程，由于車主與乘客的匹配過程實(shí)時(shí)進(jìn)行，因此需著重考慮算法的求解效率，使用基于首尾距離度的價(jià)值矩陣生成算法計(jì)算車主di和待乘客的LTD，從而求得待匹配乘客和車主的價(jià)值矩陣W，由KM算法求解價(jià)值矩陣W，得到最優(yōu)匹配方案，并使用實(shí)時(shí)訂單插入算法將當(dāng)前匹配到的乘客的出發(fā)地和目的地實(shí)時(shí)地更新到標(biāo)準(zhǔn)路徑，車主按照實(shí)時(shí)規(guī)劃的路徑行駛.在線匹配算法流程如圖4所示：

Fig. 4 Online matching algorithm process圖4 在線匹配算法流程圖

由于標(biāo)準(zhǔn)路徑是通過車主所在地和目的地的當(dāng)前最短路徑，如車主選擇接送所在地和目的地均靠近標(biāo)準(zhǔn)路徑的乘客，因此車主在接送新乘客時(shí)不會(huì)產(chǎn)生較大的繞行距離，從而在增加乘客的同時(shí)擴(kuò)大共乘比率.在計(jì)算待匹配乘客與標(biāo)準(zhǔn)路徑各部分間最短距離時(shí)，如乘客的投影點(diǎn)不在標(biāo)準(zhǔn)路徑上，則此時(shí)計(jì)算首尾距離度需考慮額外的繞行距離.具體的路徑分析如圖5和圖6所示.

Fig. 5 The distance between a rider and the standard path圖5 乘客與標(biāo)準(zhǔn)路徑間的距離

Fig. 6 Distance analysis between a rider and standard path圖6 乘客與標(biāo)準(zhǔn)路徑間的距離分析

如圖5所示，經(jīng)離線匹配后得到一條標(biāo)準(zhǔn)路徑：

L=〈ld,lr1,ar1,ad〉,

(27)

此時(shí)乘客r2進(jìn)行匹配，在到達(dá)目的地之前r2所在地與標(biāo)準(zhǔn)路徑有2個(gè)投影點(diǎn)P1和P2，在所在地之后r2目的地與標(biāo)準(zhǔn)路徑有2個(gè)投影點(diǎn)P3和P4.

乘客r2所在地與路徑〈ld,lr1〉間的距離為dis(lr2,ldlr1)；r2所在地與路徑〈lr1,ar1〉間的距離為dis(lr2,lr1ar1)+dis(P2,lr1)，其中dis(P2,lr1)為額外繞行距離，此時(shí)乘客r2所在地與標(biāo)準(zhǔn)路徑的最短距離為dis(lr2,ldlr1).

乘客r2目的地與路徑〈lr1,ar1〉間的距離為dis(ar2,lr1ar1)；r2目的地與路徑〈ar1,ad〉間的距離dis(ar2,ar1ad).此時(shí)乘客r2目的地與標(biāo)準(zhǔn)路徑的最短距離為dis(ar2,ar1ad).

為了在實(shí)時(shí)匹配階段更好地節(jié)省計(jì)算資源，在保證匹配結(jié)果的前提下，此處只計(jì)算到達(dá)乘客r目的地前與標(biāo)準(zhǔn)路徑各部分的最短距離和乘客r所在地后與標(biāo)準(zhǔn)路徑各部分的最短距離，從而避免了出現(xiàn)反向接送乘客的現(xiàn)象.

如圖6所示，可通過式(28)(29)計(jì)算乘客與標(biāo)準(zhǔn)路徑間的最短距離.連接部分標(biāo)準(zhǔn)路徑AB和乘客r得到一個(gè)三角形，如△rAB和△rBA是直角三角形或者銳角三角形，最短距離為乘客r距離AB的直線距離，否則需考慮額外繞行距離.

乘客r所在地與標(biāo)準(zhǔn)路徑的最短距離：

(28)

乘客r目的地與標(biāo)準(zhǔn)路徑的最短距離：

(29)

設(shè)車主數(shù)量為m，乘客數(shù)量為n，經(jīng)過離線匹配后得到車主的當(dāng)前狀態(tài)statusi和乘客行程tripsj，以價(jià)值矩陣生成算法生成m×n的價(jià)值矩陣W，其中元素wij表示車主i和乘客j的匹配價(jià)值.單一首尾距離度矩陣生成算法如算法3所示：

算法3.單一首尾距離度價(jià)值矩陣生成算法.

輸入：車主集合D、待匹配乘客集合Rd；

輸出：?jiǎn)我皇孜簿嚯x度價(jià)值矩陣W.

① 初始化價(jià)值矩陣W；

② fordinD

③ forrinR

④Dis_Matrix(r,Ld)；

/*此時(shí)標(biāo)準(zhǔn)路徑為車主原行駛路徑*/

⑤Llr=shortest_path(lrj,Ld)；

/*乘客所在地與標(biāo)準(zhǔn)路徑最短距離*/

⑥Lar=shortest_path(arj,Ld)；

/*乘客目的地與標(biāo)準(zhǔn)路徑最短距離*/

/*wij為W[d][r]中的元素*/

⑧W[d][r]=wij；

/*單一首尾距離度矩陣*/

⑨ end for

⑩ end for

標(biāo)準(zhǔn)路徑作為引導(dǎo)線來計(jì)算復(fù)合首尾距離度，旨在確保匹配到的乘客在標(biāo)準(zhǔn)路徑附近.綜合考慮離線匹配階段得出的匹配方案和標(biāo)準(zhǔn)路徑，單一首尾距離度矩陣生成算法只選擇乘客所在地和目的地與標(biāo)準(zhǔn)路徑間的最短距離和的倒數(shù)作為首尾距離度，具有較高的求解效率，可用于離線匹配階段未匹配到乘客的情況.但對(duì)于離線匹配階段已匹配到乘客并生成了標(biāo)準(zhǔn)路徑的情況，在進(jìn)行乘客路徑的更新時(shí)可能導(dǎo)致標(biāo)準(zhǔn)路徑發(fā)生較大的變動(dòng)，從而增加不必要的低效路程.故對(duì)于已匹配到乘客的情況，在線匹配階段采用復(fù)合首尾距離度作為評(píng)估標(biāo)準(zhǔn),且繞行距離約束仍然有效.

算法4.復(fù)合首尾距離度價(jià)值矩陣生成算法.

輸入：車主集合D、待匹配乘客集合Rd；

輸出：?jiǎn)我皇孜簿嚯x度價(jià)值矩陣W.

① 初始化價(jià)值矩陣W；

② fordinD

③ forrinR

④Dis_Matrix(r,Ld)；

/*此時(shí)標(biāo)準(zhǔn)路徑為車主原行駛路徑*/

⑤Llr=shortest_path(lrj,Ld)；

/*乘客所在地與標(biāo)準(zhǔn)路徑最短距離*/

⑥Lldr=shortest_path(lrj,ldi)；

/*乘客所在地與車主所在地最短距離*/

⑦Lar=shortest_path(arj,Ld)；

/*乘客目的地與標(biāo)準(zhǔn)路徑的最短距離*/

⑧Ladr=shortest_path(arj,adi)；

/*乘客目的地與車主目的地最短距離*/

/*wij為W[d][r]中的元素*/

⑩W[d][r]=wij；

/*復(fù)合首尾距離度矩陣*/

定義fjk為把匹配乘客rj插入到標(biāo)準(zhǔn)路徑中使目標(biāo)函數(shù)增長(zhǎng)最大的位置后目標(biāo)函數(shù)的改變量.

實(shí)時(shí)訂單插入算法的核心思想為將已匹配乘客插入到能使目標(biāo)函數(shù)增長(zhǎng)最大的位置.算法5描述為：

算法5.實(shí)時(shí)訂單插入算法.

輸入：W；

輸出：標(biāo)準(zhǔn)路徑.

① 選擇wijinW：

② s.t.wij=max(wij)；

③i∈[1，m]∩，j∈[1，n]∩；

④ if (j，L)arg maxfjL

⑤ 將乘客rj更新到標(biāo)準(zhǔn)路徑；

⑥ end if

迭代執(zhí)行算法5，將已匹配到的乘客插入到標(biāo)準(zhǔn)路徑中，直至車輛滿載或已無可選乘客.

3 實(shí)驗(yàn)與分析

本文使用?？谑泻统啥际须p數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，通過算法的求解速度和求解質(zhì)量進(jìn)行評(píng)估.實(shí)驗(yàn)仿真語言為Python3.7，運(yùn)行環(huán)境為Intel?CoreTMi7-10750H CPU @ 2.60 GHz 2.59 GHz，16 GB RAM.

3.1 算 例

實(shí)驗(yàn)數(shù)據(jù)集基于滴滴出行蓋亞數(shù)據(jù)開放計(jì)劃(didi chuxing gaia initiative)，數(shù)據(jù)范圍涵蓋?？谑泻统啥际熊囍鞒丝腿斐鲂熊壽E數(shù)據(jù)，自出行軌跡數(shù)據(jù)中隨機(jī)選取40/200/400/800/2000/4000名參與者，并隨機(jī)指定50%為車主，50%為乘客，其中?？谑泻统啥际?000數(shù)據(jù)規(guī)模的模擬分布如圖7所示.

Fig. 7 Distribution of drivers and riders圖7 車主和乘客分布圖

由于數(shù)據(jù)集本身密集程度對(duì)實(shí)驗(yàn)參數(shù)和實(shí)驗(yàn)結(jié)果的影響較大，因此采用海口市和成都市雙數(shù)據(jù)集生成算例對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)估,算例屬性由表3

Table 3 Properties of Instance表3 算例屬性表

可知.此處只列舉了規(guī)模為200的算例，其余算例分別命名為40H/40C,400H/400C,800H/800C,2000H/2000C,4000H/4000C,其中,數(shù)字表示數(shù)據(jù)規(guī)模，H和C分別表示?？谑袛?shù)據(jù)集和成都市數(shù)據(jù)集.

Fig. 8 Comparison between Euclidean distance and actual distance圖8 歐氏距離與實(shí)際路網(wǎng)對(duì)比圖

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

3.2.1 歐氏距離與實(shí)際路網(wǎng)距離對(duì)比

動(dòng)態(tài)共乘匹配過程對(duì)算法求解的實(shí)時(shí)性要求極高，面對(duì)大規(guī)模需要計(jì)算最短路徑的數(shù)據(jù)時(shí)，實(shí)際路網(wǎng)距離需要花費(fèi)大量路網(wǎng)計(jì)算開銷，很難滿足實(shí)時(shí)性，因此本文使用歐氏距離進(jìn)行計(jì)算，并對(duì)基于歐氏距離的本文算法和使用Dijkstra算法計(jì)算實(shí)際路網(wǎng)距離的本文算法的實(shí)驗(yàn)結(jié)果進(jìn)行評(píng)估.

本文通過對(duì)海口市和成都市40H/40C,200H/200C,400H/400C,800H/800C，2000H/2000C,4000H/4000C規(guī)模的算例使用基于歐氏距離的雙模式協(xié)作匹配算法和基于實(shí)際路網(wǎng)距離的雙模式協(xié)作匹配算法進(jìn)行對(duì)比，其中?？谑泻统啥际袑?shí)際路網(wǎng)數(shù)據(jù)從OpenStreetMap獲得，實(shí)際路網(wǎng)數(shù)據(jù)集包含海口市45 417個(gè)節(jié)點(diǎn)和48 080條邊，成都市37 853個(gè)節(jié)點(diǎn)和40 758條邊，實(shí)驗(yàn)結(jié)果表明所需求解的平均通用共乘比率、匹配率和匹配方案差異較小.實(shí)驗(yàn)參數(shù)為μ=1.5，θ=0.4，η=0.6.實(shí)驗(yàn)結(jié)果如圖8和表4所示.

1) 從圖8所示的算法運(yùn)行時(shí)間對(duì)比圖可知，基于實(shí)際路網(wǎng)距離的本文算法在處理不同規(guī)模的數(shù)據(jù)時(shí)耗時(shí)明顯高于基于歐氏距離的本文算法，且在處理大規(guī)模數(shù)據(jù)集時(shí)運(yùn)行時(shí)間呈現(xiàn)出異常的增長(zhǎng)態(tài)勢(shì)，無法滿足動(dòng)態(tài)車輛共乘的實(shí)時(shí)性要求.由表4可知：基于歐氏距離的本文算法和基于實(shí)際路網(wǎng)距離的本文算法在處理?？谑袛?shù)據(jù)集不同規(guī)模算例時(shí)平均運(yùn)行時(shí)間為81.91 s和4262.64 s，前者僅為后者的1.92%；基于歐氏距離的本文算法和基于實(shí)際路網(wǎng)距離的本文算法在處理成都市數(shù)據(jù)集不同規(guī)模算例時(shí)平均運(yùn)行時(shí)間為79.00 s和4 372.96 s，前者僅為后者的1.81%.

2) 從圖8所示的?？谑泻统啥际须p數(shù)據(jù)集實(shí)驗(yàn)結(jié)果可知，在平均通用共乘比率和匹配率方面，基于歐氏距離的本文算法實(shí)驗(yàn)結(jié)果與基于實(shí)際路網(wǎng)的本文算法實(shí)驗(yàn)結(jié)果差異較小.由表4可知：基于歐氏距離的本文算法和基于實(shí)際路網(wǎng)距離的本文算法在處理?？谑袛?shù)據(jù)集不同規(guī)模算例時(shí)平均通用共乘比率分別為81.75%和78.70%，平均匹配率為83.12%和77.09%，平均相差4.54%；基于歐氏距離的本文算法和基于實(shí)際路網(wǎng)距離的本文算法在處理成都市數(shù)據(jù)集不同規(guī)模算例時(shí)平均通用共乘比率82.51%和79.29%，平均匹配率為83.85%和78.26%，平均相差4.41%.

3) 需要指出，在處理算例為4000H/4000C時(shí)，基于實(shí)際路網(wǎng)距離的算法求解時(shí)間已經(jīng)完全無法滿足動(dòng)態(tài)共乘匹配，因此表4只列出了基于歐氏距離的實(shí)驗(yàn)結(jié)果，在進(jìn)行平均通用共乘比率、平均匹配率和平均運(yùn)行時(shí)間對(duì)比時(shí)也是基于2種數(shù)據(jù)集前5組算例的實(shí)驗(yàn)結(jié)果.

Table 4 Comparison Between Euclidean Distance and Actual Distance表4 歐氏距離與實(shí)際路網(wǎng)對(duì)比表

Fig. 9 Comparison of running time between improved distance matrix and normal distance matrix圖9 改進(jìn)距離矩陣與普通距離矩陣的運(yùn)行時(shí)間對(duì)比

3.2.2 距離矩陣生成時(shí)間對(duì)比

在計(jì)算距離矩陣時(shí)使用上三角矩陣代替方陣的生成，改進(jìn)后的距離矩陣生成算法與普通距離矩陣生成算法的時(shí)間比較由圖9和表5可知.表5記錄了海口市和成都市雙數(shù)據(jù)集下車主乘客對(duì)數(shù)量、普通距離矩陣生成方法和改進(jìn)距離矩陣生成算法的運(yùn)行時(shí)間.

由圖9和表5的實(shí)驗(yàn)結(jié)果可知，改進(jìn)后的距離矩陣生成算法在處理海口數(shù)據(jù)集和成都數(shù)據(jù)集時(shí)均表現(xiàn)出較好的結(jié)果，各組算例中改進(jìn)算法的運(yùn)行時(shí)間平均為普通算法的53%.

Table 5 Running Time Between Improved Distance Matrix and Normal Distance Matrix表5 改進(jìn)距離矩陣與普通距離矩陣的運(yùn)行時(shí)間 s

Fig. 10 Result of sole offline matching圖10 單純離線匹配模式結(jié)果

3.2.3 價(jià)值矩陣生成時(shí)間對(duì)比

本節(jié)對(duì)比單純離線匹配模式、單純?cè)诰€匹配模式和雙模式協(xié)作匹配算法3種不同模式下算法的運(yùn)行時(shí)間和匹配率.本文提出的雙模式協(xié)作匹配算法采用離線匹配模式和在線匹配模式相結(jié)合的混合模式.實(shí)驗(yàn)參數(shù)為：繞行距離系數(shù)μ=1.5，算例為200H/200C.實(shí)驗(yàn)結(jié)果見圖10～12和表6.

Fig. 11 Result of sole online matching圖11 單純?cè)诰€匹配模式結(jié)果

由圖10可知單純離線匹配模式在?？谑泻统啥际须p數(shù)據(jù)集下的評(píng)估表現(xiàn).本模式下，平均匹配率為93.71%.單純離線匹配模式下本文提出了基于帶權(quán)路徑搜索樹的通用共乘比率算法，考慮乘客之間的關(guān)聯(lián)性，乘客的匹配建立在前一名乘客與車主已經(jīng)形成的標(biāo)準(zhǔn)路徑的基礎(chǔ)上，從而兼顧車主的通用共乘比率和已匹配乘客的繞行距離.在匹配次數(shù)較少時(shí)，此模式的運(yùn)行時(shí)間較短，但是隨著匹配乘客逐步增加，標(biāo)準(zhǔn)路徑增長(zhǎng)，算法的運(yùn)行時(shí)間較長(zhǎng)，不能滿足即時(shí)匹配的要求，因此，單純離線匹配模式適用于非即時(shí)的預(yù)約單處理.

由圖11可知單純?cè)诰€匹配模式在?？谑泻统啥际须p數(shù)據(jù)集下的評(píng)估表現(xiàn).單純?cè)诰€匹配模式下本文提出了基于首尾距離度匹配價(jià)值評(píng)估標(biāo)準(zhǔn)代替需要大量計(jì)算開銷的通用共乘比率，針對(duì)離線匹配結(jié)果設(shè)計(jì)了單一首尾距離度和復(fù)合首尾距離度2種評(píng)估方式，使用實(shí)時(shí)訂單插入算法將乘客插入標(biāo)準(zhǔn)路徑，該方案具有較快的處理速度，但是平均匹配率為46.78%，僅為單純離線匹配模式匹配率的49.91%.因此，單純?cè)诰€匹配模式更加適用于即時(shí)訂單處理.

由圖10和圖11可知，單純離線匹配模式具有高匹配率和低匹配速率的特性，單純?cè)诰€匹配模式具有高匹配速率和低匹配率的特性，因此，根據(jù)實(shí)際情況將二者結(jié)合成為一種雙模式協(xié)作匹配算法，該模型包含離線匹配階段和在線匹配階段，在處理非即時(shí)的預(yù)約單時(shí)具有高匹配率且能兼顧匹配速率，在處理即時(shí)的實(shí)時(shí)單時(shí)具有高匹配速率.由圖12可知雙模式協(xié)作匹配算法在海口市和成都市雙數(shù)據(jù)集下的評(píng)估表現(xiàn)，該圖記錄了雙模式協(xié)作匹配算法的連續(xù)4次匹配過程.在匹配時(shí)間方面，雙模式協(xié)作匹配算法前2次匹配為離線匹配階段，因此匹配時(shí)間較單純?cè)诰€匹配模式有一定的增長(zhǎng)；后2次匹配為在線匹配階段，針對(duì)即時(shí)性訂單具有較快的匹配效率，較單純離線匹配模式匹配時(shí)間有了顯著降低.在匹配率方面，離線匹配階段使用通用共乘比率和標(biāo)準(zhǔn)路徑來增加乘客間的關(guān)聯(lián)性，因此匹配率較單純?cè)诰€匹配模式有了顯著提升；在線匹配階段針對(duì)前2次離線匹配階段生成的標(biāo)準(zhǔn)路徑進(jìn)行在線匹配，每一名乘客的匹配建立在前一名乘客與車主形成的標(biāo)準(zhǔn)路徑的基礎(chǔ)上.因此，在離線階段和在線階段的雙模式的協(xié)作匹配下，在線匹配階段的匹配率較單純?cè)诰€匹配階段的匹配率有了一定增長(zhǎng).

Fig. 12 Result of bimodal cooperative matching algorithm圖12 雙模式協(xié)作匹配算法結(jié)果

Table 6 Comparison of Sole Offline Matching, Sole Online Matching and Bimodal Cooperative Matching Algorithm

實(shí)驗(yàn)對(duì)比數(shù)據(jù)由表6可知，單純離線匹配模式在雙數(shù)據(jù)集下，前2次的匹配過程平均運(yùn)行時(shí)間為1.59 s，平均匹配率為89.08%；后2次匹配過程的平均運(yùn)行時(shí)間為607.15 s，平均匹配率為98.24%.由此可看出單純離線匹配模式只有在匹配次數(shù)較小時(shí)能夠兼顧運(yùn)行時(shí)間和匹配率. 單純?cè)诰€匹配模式在雙數(shù)據(jù)集模式下，前2次的匹配過程平均運(yùn)行時(shí)間為0.43 s，平均匹配率為45.92%；后2次匹配過程平均運(yùn)行時(shí)間為0.74 s，平均匹配率為47.65%.單純?cè)诰€模式的平均匹配率為單純離線匹配模式的49.91%.本文采用的雙模式協(xié)作匹配算法的在?？谑泻统啥际?個(gè)數(shù)據(jù)集下都能夠兼顧匹配率和匹配速度，在算法運(yùn)行時(shí)間和求解質(zhì)量上有著顯著的效果，平均運(yùn)行時(shí)間為0.79 s，僅為單純離線匹配模式下的0.26%，平均匹配率為85.53%，相較于單純?cè)诰€匹配模式提升了82.83%.

3.2.4 雙模式協(xié)作匹配算法

本節(jié)介紹雙模式協(xié)作匹配算法在不同數(shù)據(jù)規(guī)模下的運(yùn)行結(jié)果.實(shí)驗(yàn)參數(shù)為：繞行距離系數(shù)μ=1.5，復(fù)合首尾距離度的距離系數(shù)θ=0.4，η=0.6.表7記錄了成都市數(shù)據(jù)集不同算例在離線匹配階段的GSRP的平均值、GSRP超過80%和90%的比率、繞行距離、共乘距離和行駛距離，以及在線匹配階段的LTD.

分析表7可知，雙模式協(xié)作匹配算法的平均GSRP為84.86%.數(shù)據(jù)規(guī)模在800以下時(shí)離線匹配階段的54.25%的平均GSRP低于0.8；數(shù)據(jù)規(guī)模在4 000以下時(shí)離線匹配階段的50.50%低于0.9.離線匹配階段GSRP超過80%和90%的比率與數(shù)據(jù)規(guī)模呈正相關(guān).

Table 7 Bimodal Cooperative Matching Algorithm in Different Data Sizes表7 不同數(shù)據(jù)規(guī)模的雙模式協(xié)作匹配算法

3.2.5 參數(shù)敏感性分析

本節(jié)分析了離線匹配模式下繞行距離系數(shù)對(duì)算法運(yùn)行時(shí)間、平均GSRP和匹配率的影響以及在線匹配模式下距離系數(shù)對(duì)算法運(yùn)行時(shí)間、LTD和匹配率的影響，實(shí)驗(yàn)算例為200H，實(shí)驗(yàn)結(jié)果如圖13所示.

在離線匹配模式下，隨著繞行距離的增大，算法的運(yùn)行時(shí)間呈下降趨勢(shì)，匹配率和平均GSRP呈上升趨勢(shì)；在線匹配模式下，隨著距離系數(shù)θ的增大和η的減小，算法的運(yùn)行時(shí)間呈上升趨勢(shì)，LTD逐漸減小，匹配率先呈上升趨勢(shì)后逐漸下降，在θ=0.4且η=0.6時(shí)達(dá)到峰值，此時(shí)的平均匹配率為82.53%.

3.2.6 路徑演示

本節(jié)通過路徑演示分析實(shí)驗(yàn)結(jié)果的可行性和準(zhǔn)確性.實(shí)驗(yàn)算例為200H/200C，實(shí)驗(yàn)參數(shù)為μ=1.5，θ=0.4，η=0.6.圖14為離線匹配階段雙數(shù)據(jù)集實(shí)驗(yàn)結(jié)果中單條路徑演示；圖15為增加了在線匹配階段的雙模式協(xié)作匹配下雙數(shù)據(jù)集實(shí)驗(yàn)結(jié)果中單條路徑演示；圖16為雙模式協(xié)作匹配下雙數(shù)據(jù)集實(shí)驗(yàn)結(jié)果總體的路徑演示.

分析離線匹配階段的單條路徑和雙模式協(xié)作匹配算法下的單條路徑演示可知，離線匹配后通過在線匹配可有效地為車主匹配到新的高匹配價(jià)值乘客，并證明了在線匹配階段增加乘客時(shí)離線匹配階段規(guī)劃的標(biāo)準(zhǔn)路徑未產(chǎn)生較大的變動(dòng).合理地將乘客插入到標(biāo)準(zhǔn)路徑中，表明本文算法求解具有較高的質(zhì)量和實(shí)用性.

3.3 對(duì)比實(shí)驗(yàn)

本節(jié)對(duì)雙模式協(xié)作匹配算法與一種較新的自適應(yīng)搜索策略[1]進(jìn)行實(shí)驗(yàn)比較求解效率和質(zhì)量.實(shí)驗(yàn)參數(shù)為μ=1.5，θ=0.4，η=0.6.表8記錄了成都市不同規(guī)模數(shù)據(jù)集、雙模式協(xié)作匹配算法的離線匹配階段和在線匹配階段2個(gè)階段的運(yùn)行時(shí)間、匹配率和GSRP，以及自適應(yīng)搜索策略2個(gè)階段的運(yùn)行時(shí)間和SRP.

動(dòng)態(tài)共乘問題主要存在全局最優(yōu)性、共乘比率和動(dòng)態(tài)實(shí)時(shí)性等方面的挑戰(zhàn).本文綜合考慮時(shí)間約束、繞行距離、運(yùn)行時(shí)間和匹配率，并且證明本文算法在運(yùn)行時(shí)間和共乘比率方面優(yōu)于其他算法.具體對(duì)比分析和結(jié)果為：

1) 在雙模式協(xié)作匹配算法的離線匹配階段，基于帶權(quán)路徑搜索樹定義了通用共乘比率，解決了自適應(yīng)搜索策略中使用的傳統(tǒng)共乘比率算法在面對(duì)單車主多乘客時(shí)計(jì)算異常復(fù)雜的問題.由表8可知，在500對(duì)規(guī)模下，本文算法平均共乘比率為80.14%，雙模式協(xié)作算法的總體平均共乘比率為77.32%，自適應(yīng)搜索策略的總體平均共乘比率為59.62%，僅為雙模式協(xié)作匹配算法總體平均共乘比率的77.11%.

2) 在雙模式協(xié)作匹配算法的在線匹配階段，采用首尾距離度代替自適應(yīng)搜素策略中傳統(tǒng)的共乘比率算法作為價(jià)值評(píng)估標(biāo)準(zhǔn)，并根據(jù)離線匹配階段得到的標(biāo)準(zhǔn)路徑和匹配方案選擇使用單一首尾距離度或者復(fù)合首尾距離度來進(jìn)一步提高匹配率，從而保證了在線匹配階段的實(shí)時(shí)性.由表8可知，在不同數(shù)據(jù)規(guī)模下本文模型的運(yùn)行速度相較于自適應(yīng)搜索策略有較大的提升.在10對(duì)算例下，本文算法平均運(yùn)行時(shí)間僅為自適應(yīng)策略的4.10%；在500對(duì)算例下，本文算法平均運(yùn)行時(shí)間僅為自適應(yīng)搜索策略的45.43%.本文算法總體平均運(yùn)行時(shí)間僅為自適應(yīng)搜索策略的44.86%.

Fig. 13 Parameter sensitivity analysis圖13 參數(shù)敏感度分析

Fig. 14 Offline matching stage single route demonstration圖14 離線匹配階段單條路徑演示

Fig. 15 Bimodal cooperative matching algorithm single route demonstration圖15 雙模式協(xié)作匹配算法單條路徑演示

Fig. 16 Bimodal cooperative matching algorithm partial geographical demonstration圖16 雙模式協(xié)作匹配算法部分路徑演示

Table 8 Comparison of the Results of Bimodal Cooperative Matching Algorithm and Adaptive Strategy

3) 自適應(yīng)搜索策略中并未考慮匹配率，因此只列出了本文模型的平均匹配率.雙模式協(xié)作匹配算法在離線匹配階段的不同數(shù)據(jù)規(guī)模下平均匹配率為98.36%，在線匹配階段的不同數(shù)據(jù)規(guī)模下平均匹配率為67.36%，在不同數(shù)據(jù)規(guī)模下的總體平均匹配率為82.86%.

4 總結(jié)與展望

本文提出了一種基于離線匹配和在線匹配的雙模式協(xié)作匹配算法.首先，對(duì)待匹配的乘客進(jìn)行約束處理，以篩選滿足約束的車主乘客對(duì)，并對(duì)距離矩陣的生成方式進(jìn)行了改進(jìn)；其次，在離線匹配階段，提出了一種基于帶權(quán)路徑搜索樹的通用共乘比率生成算法；再次，于在線匹配階段提出了2種基于首尾距離度的實(shí)時(shí)訂單插入算法，采用了一種便于計(jì)算且具有較好評(píng)估能力的評(píng)估標(biāo)準(zhǔn)進(jìn)行匹配價(jià)值評(píng)估；最后，通過實(shí)驗(yàn)對(duì)單純離線匹配模式、單純?cè)诰€匹配模式和雙模式協(xié)作匹配算法進(jìn)行比較，并將雙模式協(xié)作匹配算法與自適應(yīng)搜索策略進(jìn)行比較.實(shí)驗(yàn)表明，本文提出的雙模式協(xié)作匹配算法具有較高的實(shí)用價(jià)值，兼顧算法求解效率和求解質(zhì)量，并且在運(yùn)行時(shí)間和匹配率上均比自適應(yīng)搜索策略更具有優(yōu)勢(shì).此外，基于雙模式的匹配算法通過增加有效共乘路程，降低了車輛空載率，從而大幅提升了交通資源利用率和運(yùn)輸效率.

需要指出的是，本文提出的雙模式協(xié)作方式仍較為單一，在離線匹配和在線匹配的轉(zhuǎn)換方面還存在優(yōu)化的空間.后續(xù)研究將探索對(duì)雙模式協(xié)作的拓展方法，考慮使用強(qiáng)化學(xué)習(xí)和超啟發(fā)式算法提升離線模式和在線模式動(dòng)態(tài)轉(zhuǎn)換的自主性和智能性，從而進(jìn)一步提升匹配效率和匹配質(zhì)量.

作者貢獻(xiàn)聲明：郭羽含負(fù)責(zé)方法設(shè)計(jì)、結(jié)構(gòu)設(shè)計(jì)和論文修改；劉永武負(fù)責(zé)實(shí)驗(yàn)實(shí)現(xiàn)和論文初稿撰寫.