郭羽含 劉永武

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

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

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

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

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

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

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

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

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

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

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

本文的主要貢獻有4個方面：

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

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

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

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

1 問題建模

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

1.1 角色定義

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

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

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

(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是指車主與乘客共乘路徑占車主因接送乘客行駛的總路徑的比率.

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

(2)

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

(3)

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

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

(4)

通用共乘比率可表達為

(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來評價車主共享資源的利用效率，并以繞行距離(detour length,DL)[34]對其進行約束，從而平衡車主共享效率和乘客訂單可行性.車主與乘客的GSRP反映了乘客與車主的匹配價值.車主出行效益取決于乘客與之共乘的共享路徑長短，因此，該值越大則表示車主的高匹配價值路程越長，車主的運輸資源利用效率越高，反之則表示車主把大量路程浪費在獨自行駛過程中，空載率越高，運輸資源的利用效率越低.

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

(10)

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

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

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

(11)

(12)

s.t.Larad?L,

(13)

Lldlr?L,

(14)

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

(15)

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

Table 2 Variables表2 變量表

1.2 優(yōu)化目標

雙模式協(xié)作匹配算法在進行數(shù)學建模時將優(yōu)化目標根據(jù)離線匹配階段和在線匹配階段不同的價值評估標準進行分析.離線匹配階段以定義3中的通用共乘比率來評價車主與乘客的匹配價值，定義車主i與乘客j匹配價值為gij；在線匹配階段以首尾距離度來評價對應的匹配價值，此時車主i和乘客j的匹配價值為wij.xij和yij分別表示離線匹配階段和在線匹配階段車主與乘客是否匹配.問題目標即為通過動態(tài)共乘匹配過程得出一種匹配方案使得所有車主乘客匹配對的價值總和最大.此時的目標函數(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ù)應小于等于車容量；式(20)限定xij和yij的取值范圍，0表示不匹配，1表示匹配；式(21)定義了車主的繞行距離，μ為繞行距離系數(shù)，約束車主的最大繞行距離；式(22)定義了共乘乘客的繞行距離，μ為繞行距離系數(shù)，約束乘客的最大繞行距離；式(23)表示待匹配乘客出發(fā)時間晚于車主出發(fā)時間；式(24)表示車主和乘客具有身份唯一性.

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

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

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

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

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

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

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

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

2.1 距離矩陣生成算法

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

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

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

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

輸入：車主集合D、乘客集合R和標準路徑；

輸出：車主的待匹配乘客集合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é)點間的距離*/

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

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

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

(25)

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

2.2 離線匹配階段

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

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

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

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

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

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

(26)

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

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

輸出：離線階段標準路徑.

① fordinD

② forrinR

③Dis_Matrix(d,r)；

④ 初始標準路徑L；

⑤Tree←Init_Tree()；

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

⑥Tree.root=ld；

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

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

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

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

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

⑨Tree←InsertNode()；

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

False do

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

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

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

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

/*gij為G中的元素*/

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

2.3 在線匹配階段

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

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

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

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

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

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

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

Fig. 5 The distance between a rider and the standard path圖5 乘客與標準路徑間的距離

Fig. 6 Distance analysis between a rider and standard path圖6 乘客與標準路徑間的距離分析

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

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

(27)

此時乘客r2進行匹配，在到達目的地之前r2所在地與標準路徑有2個投影點P1和P2，在所在地之后r2目的地與標準路徑有2個投影點P3和P4.

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

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

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

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

乘客r所在地與標準路徑的最短距離：

(28)

乘客r目的地與標準路徑的最短距離：

(29)

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

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

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

輸出：單一首尾距離度價值矩陣W.

① 初始化價值矩陣W；

② fordinD

③ forrinR

④Dis_Matrix(r,Ld)；

/*此時標準路徑為車主原行駛路徑*/

⑤Llr=shortest_path(lrj,Ld)；

/*乘客所在地與標準路徑最短距離*/

⑥Lar=shortest_path(arj,Ld)；

/*乘客目的地與標準路徑最短距離*/

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

⑧W[d][r]=wij；

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

⑨ end for

⑩ end for

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

算法4.復合首尾距離度價值矩陣生成算法.

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

輸出：單一首尾距離度價值矩陣W.

① 初始化價值矩陣W；

② fordinD

③ forrinR

④Dis_Matrix(r,Ld)；

/*此時標準路徑為車主原行駛路徑*/

⑤Llr=shortest_path(lrj,Ld)；

/*乘客所在地與標準路徑最短距離*/

⑥Lldr=shortest_path(lrj,ldi)；

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

⑦Lar=shortest_path(arj,Ld)；

/*乘客目的地與標準路徑的最短距離*/

⑧Ladr=shortest_path(arj,adi)；

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

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

⑩W[d][r]=wij；

/*復合首尾距離度矩陣*/

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

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

算法5.實時訂單插入算法.

輸入：W；

輸出：標準路徑.

① 選擇wijinW：

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

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

④ if (j，L)arg maxfjL

⑤ 將乘客rj更新到標準路徑；

⑥ end if

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

3 實驗與分析

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

3.1 算 例

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

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

由于數(shù)據(jù)集本身密集程度對實驗參數(shù)和實驗結(jié)果的影響較大，因此采用海口市和成都市雙數(shù)據(jù)集生成算例對實驗結(jié)果進行評估,算例屬性由表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 歐氏距離與實際路網(wǎng)對比圖

3.2 匹配實驗結(jié)果分析

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

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

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

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

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

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

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

Fig. 9 Comparison of running time between improved distance matrix and normal distance matrix圖9 改進距離矩陣與普通距離矩陣的運行時間對比

3.2.2 距離矩陣生成時間對比

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

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

Table 5 Running Time Between Improved Distance Matrix and Normal Distance Matrix表5 改進距離矩陣與普通距離矩陣的運行時間 s

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

3.2.3 價值矩陣生成時間對比

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

Fig. 11 Result of sole online matching圖11 單純在線匹配模式結(jié)果

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

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

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

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

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

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

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

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

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

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

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

3.2.6 路徑演示

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

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

3.3 對比實驗

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

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

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

2) 在雙模式協(xié)作匹配算法的在線匹配階段，采用首尾距離度代替自適應搜素策略中傳統(tǒng)的共乘比率算法作為價值評估標準，并根據(jù)離線匹配階段得到的標準路徑和匹配方案選擇使用單一首尾距離度或者復合首尾距離度來進一步提高匹配率，從而保證了在線匹配階段的實時性.由表8可知，在不同數(shù)據(jù)規(guī)模下本文模型的運行速度相較于自適應搜索策略有較大的提升.在10對算例下，本文算法平均運行時間僅為自適應策略的4.10%；在500對算例下，本文算法平均運行時間僅為自適應搜索策略的45.43%.本文算法總體平均運行時間僅為自適應搜索策略的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) 自適應搜索策略中并未考慮匹配率，因此只列出了本文模型的平均匹配率.雙模式協(xié)作匹配算法在離線匹配階段的不同數(shù)據(jù)規(guī)模下平均匹配率為98.36%，在線匹配階段的不同數(shù)據(jù)規(guī)模下平均匹配率為67.36%，在不同數(shù)據(jù)規(guī)模下的總體平均匹配率為82.86%.

4 總結(jié)與展望

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

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

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