即時車輛共乘問題的多策略解空間圖搜索算法

郭羽含 張 宇 沈學利 于俊宇

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

車輛共乘(ride-sharing)，也稱車輛合乘，指對一定時空范圍內的車主和乘客進行匹配組合和路徑規劃，以降低車輛空載率，從而提升運輸效率、緩解交通擁堵、降低環境污染并節省出行資源.車輛共乘根據車主屬性可分為順風車模式(hitch-mode)和出租車模式(taxi-mode).在順風車模式中，車主和乘客均指定自身所在地和目的地，需最大化車主乘客對的匹配價值之和.而在出租車模式中，車主以運輸乘客賺取利潤為目的，即只有當前所在地而無自身目的地，該種模式下僅需最小化車主所在地與乘客所在地間的低效能路程.即時車輛共乘則指車主和乘客在發布出行信息后即時出發，需盡可能最小化其等待時間，因此需在相對較短時間內生成車主乘客匹配方案，對計算速度有一定敏感性.本文針對順風車模式的即時車輛共乘進行研究.相對于經典路徑規劃問題[1-2]，國內外對于車輛共乘問題的研究較少，文獻[3-4]對本問題進行了綜述，將其研究方向主要歸納為問題模型[5-12]和求解算法[13-19]2方面.在問題模型方面，Baldacci等人[5]提出一種最小化總行駛距離的精確算法模型.Ece等人[6]設計了一種最小化總行駛時間的模型.齊觀德等人[7]對乘客候車時間進行了模擬和預測.Schilde等人[8]針對時間性和隨機性因素對行駛速度的影響提出2套元啟發式解決方案.譚家美等人[9]研究了信任水平對動態共乘匹配效果在仿真模型上的影響.Stiglic等人[10]以一種基于會面點的模型來提高匹配方案的效率和靈活性.Ta等人[11]建立了一種最大化共享路程比率的模型.肖強等人[12]基于泊松分布對出租車合乘概率及等待時間進行了模擬.在求解算法方面，Agatz等人[13]提出一種Rolling Horizon策略.Kleiner等人[14]設計了一種基于拍賣機制的激勵兼容DRS解決方案.邵增珍等人[15]以一種2階段聚類啟發式優化算法解決該問題.Pelzer等人[16]使用了一種基于分區的動態共乘匹配算法.楊志家等人[17]針對車輛共乘問題設計一種2階段的分布式估計算法.Alonso-Mora等人[18]構建了一種實時大容量乘坐共享數學模型的約束優化算法.郭會等人[19]提出基于個性化需求的匹配算法.其他一些研究工作則針對更為具體的案例進行了分析以彌補通用模型中的空白，如Calvo等人[20]和Ma等人[21]分別對城市公共交通問題構建了出租車共享系統，Winter等人[22]結合移動地理傳感器網絡對車輛共乘進行了研究.Amey[23]通過數據驅動的方法在組織級數據規模上估計了車輛共乘的可行性.付瑤等人[24]發現通過城市出行需求量和交通需求聚集度可以確定交通模式是否可以達到穩定狀態.

文獻中提出的模型在評估匹配質量方面主要使用3個指標之一：1)最小化總行駛距離[5,10,13-16,20,23];2)最小化總行駛時間[6-9,21];3)最大化共享路徑比率[11,19].然而，指標1和指標2忽略了車主和乘客間行程的相似性，無法高效利用交通資源，且降低了車主的收入和乘客的滿意度.指標3無法控制繞行距離，導致車主額外駕駛路徑可能過長，嚴重降低了實際應用中的可行性.

車輛共乘匹配問題需對所有乘客與車主通過價值函數生成乘客車主對的價值二分圖，然后使用二分圖最大權匹配算法求出最優匹配方案及匹配后子圖權邊總和[7].在大型城市的高峰時段，算法需要在短時間內匹配數以萬計的車主與乘客，因此對算法的求解效率要求極高.二分圖最大權匹配算法時間復雜度較高，因而當算例較大時，該方法的運行時間將成超線性趨勢增長.而文獻中提出的近似算法也未能較好地解決求解大算例時的效率問題.

本文針對固定時空范圍內的即時車輛共乘匹配問題展開研究，提出一種多策略解空間圖搜索算法(multi-strategy solution space graph search algorithm).首先在模型層面提出一種約束繞行距離的價值評估方法，然后以一種并行化的價值矩陣生成方案來改進原本低效的生成方法，最后設計多種策略指導算法在解空間圖中進行高效搜索.實驗結果表明，該算法的求解質量可達最優解的95%以上，且求解效率明顯優于實驗中對比的其他算法.

本研究的主要貢獻有3個方面：

1) 提出了一種基于共享路程比率(shared route percentage, SRP)和繞行距離的價值評估方法.該方法側重資源利用率的同時兼顧了司機的收益期望.

2) 提出了離散排列問題的解空間圖理論，并基于此理論構建了一種多策略搜索算法來解決即時共乘問題，并闡述了其正確性.

3) 基于大量算例進行了實驗測試，證明了本算法可以高效求解大型算例并提供高質量的匹配方案.

1 問題建模

1.1 問題形式化

在固定時空范圍內，以無向加權全連通圖G=P,E表示一個道路網絡.其中，頂點集P={pi|i∈[1,nnode]∩}為道路節點集合，其中元素數量為nnode；無向邊集合E={(pi,pj)|i∈[1,nnode]∩,j∈[1,nnode]∩,i≠j}，其中元素數量為nedge.邊(pi,pj)的距離為eij.以集合D={di|i∈[1,m]∩}表示車主集，其中di代表車主i，每個車主具有所在節點ldi和目的節點adi.以集合R={rj|j∈[1,n]∩}表示乘客集，其中rj代表乘客j，每個乘客具有所在節點lrj和目的節點arj.車主和乘客具有身份唯一性，因此D∩R=?.匹配車主與乘客時，以共享路徑比率來評價車主與乘客的匹配價值，定義車主i與乘客j匹配的價值為vij.問題的目標即為求得一種匹配方案，使得所有車主乘客匹配對的價值總和最大.因此，可將本問題的目標函數定義為

(1)

(2)

(3)

xij∈{0,1},?i,j,

(4)

其中，xij表示車主i與乘客j是否匹配，vij表示車主i與乘客j的匹配價值.式(2)～(4)為匹配互斥性約束，式(2)表示每個乘客至多與一個車主匹配，式(3)表示每個車主至多與一個乘客匹配，式(4)限定x取值范圍，0表示不匹配，1表示匹配.研究涉及的變量如表1所示：

Table 1 Variables表1 變量表

Continued (Table 1)

1.2 價值評估

本文使用共享路程比率[7](SRP)作為對車主這一主要資源的利用效率的評價標準，并以繞行距離(detour length, DL)對其進行約束，以達到共享效率和方案可行性的平衡.車主與乘客的SRP為乘客的期望路程與車主的總路程的比值.SRP反映出共享資源的利用效率.乘客的期望路程是共享的、高價值的，而車主獨自行駛的路程是非共享的、低價值的，因此，該值越大則表示車主的低價值路程相對越短，共享資源利用效率越高，反之則表示車主把大量路程浪費在共享路程之外，對共享資源的利用效率低下.

設有車主dj和乘客存在于道路圖G中，則該車主與乘客的共享路程比率為

(5)

(6)

lri≠ari,

(7)

ldi≠adi,

(8)

CDL=dis(ldj,lri)+dis(lri,ari)+dis(ari,adj)-
dis(ldj,adj),CDL≤μ×dis(lri,ari)，

(9)

其中，dis表示2點之間的路徑長度，l表示車主或乘客的所在節點，a表示車主或乘客的目標節點，p表示節點，μ表示車主的利潤率.式(6)約束了圖的邊必定是非負邊.式(7)(8)為起點終點互斥性約束，一個車主或乘客的起點和終點應是不同的.式(9)表示車輛的繞行距離及約束，其中CDL表示車主的繞行距離，μ為車主載乘客行駛每公里的收益與車主行駛每公里的花費之比率，式(9)能夠約束車主的共享過程處于收益狀態之內.

2 多策略單步移動解空間圖搜索算法

2.1 算法理論基礎

本問題的解可表達為

S=(s1,s2,…,snsolution),

(10)

s.t.si∈DT,

(11)

si≠sj,i≠j,

(12)

其中,S表示問題的一個解向量，即一種全局匹配方案,si表示S在向量維度i的值;DT表示S中元素的可取值集合.本文定義該類解的問題為離散排列向量解問題(discrete permutation vector solution problem, DPVSP)，簡稱離散排列問題.當集合DT中的元素數量等于解向量S的維度nsolution時，稱該問題為簡單離散排列向量解問題(simple discrete permutation vector solution problem, SDPVSP)，否則稱為拓展的離散排解向量解問題(extend discrete permutation vector solution problem, EDPVSP)，以下首先討論SDPVSP的求解方法，然后再論述在EDPVSP下對該求解方法的拓展.

定義1.對SDPVSP的解Sα.通過交換解向量中第i和第j位置的值轉化為一個新解Sβ，定義這種操作為單步交換操作(single step exchange oper-ation, SSEO)，過程為

(13)

1) 對于DT元素數量大于向量維度nsolution的情況，將SSEO拓展為

(14)

其中DT-T表示DT與S各維度值的集合T的差集.拓展SSEO過程為，任意2個位置交換，或是某位置與DT中未被該解使用的離散值進行交換.經過拓展之后，仍滿足上述性質.

2) 對于DT元素數量小于向量維度nsolution的情況，則對式(11)添加拓展元素null,則：

(15)

將約束式(12)變更為

si=sj,i≠j?si=sj=null,

(16)

對SSEO操作追加約束，則：

SSEOi,js.t.si≠null∨sj≠null.

(17)

式(16)表示null元素的可重用性，null元素可被重復使用；式(17)表明null元素的自身不可交換性，null元素不可與其他位置的null交換.

解空間圖的解節點數量增多時，解空間圖的結構會變得異常復雜，因而搜索高質量解也變得尤為困難.本文基于SDPVSP和單步交換操作解空間圖(SSEOSSG)，提出一種多策略解空間圖搜索算法，簡稱解空間圖搜索算法.該算法能夠對解空間圖進行快速且高效的搜索.

2.2 并行初始化價值矩陣與最短路徑算法

設車主數量為m，乘客數量為n，以價值函數生成m×n的價值矩陣V，其中元素vij表示車主i和乘客j的價值.定義匹配方案矩陣X(m×n)，矩陣中元素xij表示車主i與乘客j是否匹配且滿足匹配互斥約束性.以下步驟均基于上述假設.

計算共享路程比率SRP過程中最大的計算開銷為最短路徑的計算.求解無負邊的最短路徑算法主要有Dijkstra算法和Floyd算法.對于本問題，Dijkstra算法的時間復雜度相較于Floyd算法更低.然而對于大型算例，Dijkstra算法計算開銷仍然過大，因此本文對Dijkstra算法進行拆解并與價值矩陣的循環進行合并，可以在很大程度上降低時間開銷.

原價值矩陣生成算法流程如算法1所示：

算法1.原價值矩陣生成算法.

輸入：車主集合D,m=len(D)、乘客集合R,n=len(R);

輸出：價值矩陣V.

① 初始化價值矩陣V[m][n];

② fordinD

③ forrinR

④Dis1=shortest_path(loc(r),dst(r));

/*r所在節點至目的節點的最短路徑*/

⑤Dis2=shortest_path(loc(d),loc(r));

/*d所在節點至r所在節點的最短路徑*/

⑥Dis3=shortest_path(dst(r),dst(d));

/*r目的節點至d目的節點的最短路徑*/

⑦V[d][r]=SRP(Dis1,Dis2,Dis3);

/*根據Dis1,Dis2,Dis3求出d和r的SRP*/

⑧ end for

⑨ end for

Dijkstra算法可拆解為2個元操作：

1) 路徑元操作.求所在節點至所有節點的最短路徑.

2) 檢索元操作.檢索所在節點至目標節點的最短路徑.

算法1的主要時間消耗在路徑元操作.在對乘客進行遍歷時，由于車主的所在節點和目標節點不變，因此可將路徑元操作轉移車主循環層級，即行②～⑨，這樣可以減少n-1次路徑元操作的計算次數，大幅降低時間開銷.由于乘客循環和車主循環的順序不影響結果，當車主數量少于乘客時，將車主作為外層循環也可降低路徑元操作的計算次數.算法過程如算法2.

算法2.改進的價值矩陣生成算法.

總之，培養留守兒童良好的學習習慣需要家庭、學校、社會同關注、齊參與，我們教師作為留守兒童的“家庭外監護人”，在他們的家庭教育缺失的情況下，要通過不斷地探索，讓他們感受到教師的關愛，培養他們的自信心、自尊心，培養他們的自主學習的習慣，讓他們在初中三年的學習和生活中溫暖、充實、有收獲。

輸入：司機集合D,m=len(D)、乘客集合R,n=len(R);

輸出：價值矩陣V.

① 初始化價值矩陣V[m][n];

② ifm

③ fordinD

④Dis2Map=shortest_path(loc(d),all); /*d所在節點至所有節點的最短路徑*/

⑤Dis3Map=shortest_path(all,dst(d));

/*所有節點至d目標節點的最短路徑*/

⑥ forrinR

/*r所在節點至目的節點的最短路徑*/

⑧Dis2=dis2Map[loc(d)][loc(r)];

/*從Dis2表中檢索d所在節點至r所在節點的最短路徑*/

⑨Dis3=dis3Map[dst(r)][dst(d)];

⑩V[d][r]=SRP(Dis1,Dis2,Dis3);

/*根據Dis1,Dis2,Dis3求出d和r的SRP*/

/*所有節點至r所在節點的最短路徑*/

/*r目標節點至所有節點的最短路徑*/

時間復雜度分析：在時間上，設道路圖中的節點數量為nnode，邊數量為nedge，乘客數量為n，車主數量為m，則對于原算法，單次Dijkstra算法使用鄰接表和堆結構的時間復雜度為O(nedge×lbnnode)，需要執行m×n次，故總體時間復雜度為O(m×n×nedge×lbnnode)，通過縮減循環，實際總體執行Dijkstra算法的次數為min(m,n)，故時間復雜度為O(nedge×lbnnode×min(m,n)).同時需要強調的是，以上處理并未增加空間開銷.

2.3 大值優先算法生成初始解

算法在解空間圖從1個初始節點開始迭代，初始節點的選擇對算法的迭代速度有較大影響.為了保證算法對大算例的求解效率，初始解的生成方式必須是快速而高效的.本文設計一種大值優先算法來構造初始解，其過程如下：

對給定價值矩陣V，初始化解決方案數組X的所有元素置為0.對價值矩陣V的行進行遍歷，對當前行所有數值進行排序，從最大值開始進行遍歷，對于當前大值，判斷匹配方案X中的該索引列的總和是否等于0，若是則將X中的該行該列置為1并跳過本行循環，否則對該行的下一個大值進行判斷.重復上述過程，直到滿足矩陣X的所有行之和都為1或者所有列之和都為1.算法過程如算法3所示.

算法3.大值優先算法.

輸入：價值矩陣V；

輸出：匹配方案X.

① 初始化X=zeros[m×n] /*X為m×n的矩陣，且初值為0*/

② forrowinV

③ ifsum(X.rows)>0 orsum(X.cols)>0 break;

④ end if /*如果X的所有行都大于0或者所有列都大于0則結束*/

⑤new_row=order_desc(row); /*對該行進行降序排序*/

⑥ forlocationinnew_row/*對排序列進行遍歷*/

⑦ ifsum(X.col(location))=0

⑧X[location]=1;

⑨ continue; /*如果當前值在價值矩陣中的位置，對應在匹配方案中的位置列之和為0，則將匹配方案中該位置置為1，并跳過此行*/

⑩ end if

2.4 迭代算子

迭代算子是迭代優化算法的重要組成部分，對于離散排列向量解問題中，任何迭代算子的實質都是做1步或者多步SSEO操作.

本文使用解集覆蓋性和收斂性對算子的特性進行分析.解集覆蓋性越廣，則算法對解集合的覆蓋程度的期望越高，從而具有對解空間圖更廣的搜索范圍，可在一定程度上避免解陷入局部最優.收斂性則指解向更優解移動的速度，具有該性質保證了算法在宏觀上是收斂的，該性質越強，算法的收斂速度越快，但越容易陷入局部最優.解集覆蓋性和收斂性是宏觀互斥的.

1) 隨機交換算子(random exchange operator, REO)

隨機交換算子選取矩陣解X中的任意2行中匹配的位置的列進行交換.該交換算子的實質是使當前解在解空間圖中向隨機方向做1次SSEO，該算子的解集覆蓋性非常強，但收斂性較弱.

數學公式描述為

選擇

?xij,xkl:

(18)

s.t.xij=1,xkl=1,

(19)

(20)

i≠k,j≠l.

(21)

執行:

xij=0,xkl=0,xil=1,xkj=1.

(22)

時間復雜度分析：整個過程無循環，時間復雜度為O(1).

2) 上山交換算子(up-hill exchange operator, UEO)

該算子隨機尋找矩陣解X某行，找到該行的匹配位置xij與某個價值比匹配位置大的xil，找到xil對應列l的匹配位置xkl，對xij和xkl所在行或列進行試探交換(行列的交換結果相同)，如果2個位置交換后總體價值與交換前總體價值之差值非負，則提交交換操作.該算子的實質是向限制方向做1次SSEO.該算子的收斂性較強，解集覆蓋性較弱.

數學公式描述為

選擇

?xij,xkl:

(23)

s.t.xij=1,xkl=1,

(24)

(25)

i≠k,j≠l,

(26)

vil≥vij.

(27)

如果

vil+vkj≥vij+vkl

(28)

執行:

xij=0,xkl=0,xil=1,xkj=1.

(29)

時間復雜度分析：過程中需對矩陣解X的行進行檢索，時間復雜度為X行數O(n).

3) 概率上山交換算子(probability up-hill exchange operator, PUEO)

概率上山算子在隨機找到第1行的匹配位置后，依據該行所有位置與當前匹配位置的差值，擇取所有差值為正值的位置并依據差值做概率分布來隨機選取下個位置，2個位置如果交換后價值增加，則進行交換.該算子的實質是向限制方向做1次SSEO.該算子的收斂性比上山交換算子更強，解集覆蓋性則較弱.

數學公式描述為

選擇

?xij,xkl:

(30)

s.t.xij=1,xkl=1,

(31)

(32)

i≠k,j≠l,

(33)

vil≥vij，

(34)

(35)

如果

vil+vkj≥vij+vkl

(36)

執行:

xij=0,xkl=0,xil=1,xkj=1.

(37)

其中pil表示位置il被選中的概率，當匹配位置價值vij等于最大值時，pij為所有等于最大值位置的數量的倒數，在其他情況下則為該位置與匹配位置價值插值與所有大于匹配位置的價值與匹配位置差值之和的比率.

時間復雜度分析：過程中需對矩陣解X的行進行檢索，時間復雜度為X行數O(n).

Fig.1 Random operator strategy flowchart圖1 隨機算子策略流程圖

2.5 搜索策略

在迭代算子中已經提出，算子的解集覆蓋性和收斂性是互斥的，因此本文定義一種結構來指導如何使用算子，通過調度多種算子來綜合算法宏觀的解集覆蓋性和收斂性，使其2方面都達到較好的效果.本文把這種結構稱為搜索策略.

搜索策略的終止條件在對比試驗中可設為達到最優解一定比率停止，而在實際情況中可設置為固定迭代次數.

1) 隨機算子策略(random operator strategy, ROS)

該策略隨機使用3種算子，隨機算子保證了算法的解集覆蓋性，而另外2種算子則保證了算法的收斂性.流程圖如圖1所示.

2) 終點加速策略(end-charging strategy, ECS)

該策略隨機使用隨機算子和上山算子，在最后的數次迭代中，使用收斂性最強的的概率上山算子.隨機使用隨機算子和上山算子使得算法宏觀的解集覆蓋性較強，在終點前的加速又保證其收斂性.流程圖如圖2所示：

Fig.2 End-charging strategy flowchart圖2 終點加速策略流程圖

3) 自適應策略(adaptive strategy, AS)

自適應策略基于當前解的迭代軌跡來指導解的搜索.策略監督解的收斂趨勢，定義軌跡為每次迭代的解值的記錄.由于迭代次數通常數量龐大而單次效果微小，因此只需每隔軌跡步長代數記錄1次.自適應策略根據最近記憶長度次迭代值來分析當前收斂趨勢，求記憶的軌跡中前幾次值的均值與最近1次的值的差值，如果該差值高于高閾值，說明解正處于

收斂高勢期，這時的解需要快速向最優解收斂，因此此時采用收斂性最強的概率上山算子，如果處于高低閾值之間，則說明解處于勻勢上升期，使用上山算子即可，如果差值低于低閾值，說明解已經陷入局部最優，此時應該使用發散代數次隨機算子發散解，使其隨機移動到解空間的其他位置，跳出局部最優峰值后繼續收斂.流程圖如圖3所示：

Fig.3 Adaptive strategy flowchart圖3 自適應策略流程圖

3 實驗與分析

本文使用模擬數據進行實驗，采用的評估指標是算法運行時間和解的質量.模擬數據中，道路圖數據通過OpenStreetMap Overpass API[注]http://www.overpass-api.de/獲取，數據范圍涵蓋成都市2環內路網，并對道路節點進行了篩選和處理，節點與邊的數量均為10 000，路網源數據的可視化如圖4所示；車主乘客數據基于滴滴蓋亞數據開放計劃(didi chuxing gaia initiative[注]https://gaia.didichuxing.com)，自成都市二環內局部區域軌跡數據中隨機選取20/100/200/400/1000/2000/4000/6000名參與者，并隨機指定50%為車主，50%為乘客，其中1 000和2 000數據規模的模擬分布圖如圖5所示.仿真語言為Python3.5，實驗運行環境為2.50 GHz Intel Core i5-7300HQ CPU，8 GB RAM.最優解由KM算法[25]得出.

Fig.4 Visualization of path network original data圖4 路網源數據可視化

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

3.1 價值矩陣生成時間對比

并行的價值矩陣生成算法與普通的價值矩陣生成算法的時間比較見圖6和表2.表2記錄了乘客車主對數量、普通價值矩陣生成算法和并行的價值矩陣生成算法的運行時間.

Fig.6 Graph of running time between concurrence value matrix generation and normal generation圖6 并行價值矩陣生成與普通生成的運行時間圖

Table 2 Table of Running Time Between Parallel Value Matrix Generation and Normal Generation
表2 并行價值矩陣生成與普通生成的運行時間表

ParticipantNumber∕pairRunning Time∕sParallel GenerationNormal Generation100.946.67504.67144.121009.42563.1220018.492267.7850047.5613712.901000108.36

通過實驗結果可以看出，該算法大幅度節省了時間.在處理500對乘客車主的算例時，改進算法的運行時間僅為普通算法的0.35%.

3.2 隨機算子策略

圖7和表3展示了對隨機算子策略的評估結果.表3記錄了乘客車主對數量、5組達到最優解95%的較優解的時間、占最優解價值的比率及其均值、最優算法時間.

Fig.7 Random operator strategy contrast graph圖7 隨機算子策略對照圖

分析所得數據，可以發現隨機算子策略獲取近似解速度較快，且隨著數據規模的增大，該策略與最優算法的時間消耗差異明顯.實驗結果表明：隨機算子策略可以顯著提升給出較優方案的時間.在求解規模為500對的算例時，隨機算子策略的運行時間為最優算法的61.85%，當算例增大到3 000對時，隨機算子策略所需時間僅為最優算法的25.04%.

Table 3 Random Operator Strategy Data Size Table表3 隨機算子策略數據規模表

Notes: PN represents participant number; OART represents optimal algorithm running time.

3.3 終點加速策略

3.3.1 終點加速策略中終點距離的影響

本節測試終點距離對算法的影響，對終點距離的實驗都是在1 000對乘客與車主的數據規模之下的，實驗結果如表4所示.表4記錄了終點距離代數、5組達到最優解95%的較優解的時間、占最優解價值的比率及其均值.

實驗結果表明這個參數并不會顯著地影響該策略的速度，運行時間存在的少許差異可能是運行過程的隨機性或者是誤差造成的.

Table 4 Charge Length for End-Charging Strategy Table 表4 終點加速策略終點長度表

Notes: CL represents charging length.

3.3.2 終點加速策略在不同實驗規模下的效果

經過終點長度的實驗后，選擇長度50作為接下來在不同數據規模下該策略的運行時間的實驗，結果如表5所示，對照圖如圖8所示.表5記錄了乘客車主對數量、5組達到最優解95%的較優解的時間、占最優解價值的比率及其均值、最優算法時間.

Table 5 End-charging Strategy in Different Data Size Table表5 終點加速策略數據規模表

Notes: PN represents participant number; OART represents optimal algorithm running time.

Fig.8 End-Charging strategy contrast graph圖8 終點加速策略對照圖

終點加速策略也比最優算法運行時間短，但在小算例速度比隨機算子策略慢，分析這個過程，終點加速策略中收斂性最強的概率上山算子的運行次數相對較少，這說明概率上山算子對小算例的收斂速度提升的效果較為顯著，大算例時概率上山算子對速度的影響變差.當算例超過3 000對時，終點加速策略的運行時間優于隨機算子策略.

3.4 自適應策略

3.4.1 自適應策略中發散代數的影響

本節研究發散代數對該策略的影響,實驗參數為：步長為100，記憶長度為2，高閾值為10-4，低閾值為10-10，乘客車主對數量為1 000對.實驗結果如表6所示.表6記錄了發散代數、5組達到最優解95%的較優解的時間、占最優解價值的比率及其均值.

從實驗結果中可以發現，這個參數對運行速度有影響.以50代的平均運行時間為標準，其他代數運行時間約為50代平均運行時間的80%～140%(不考慮缺省值).從實驗結果還可以看出，當發散代數超過90代時開始出現發散現象，此時算法過程不再收斂.

3.4.2 自適應策略中記憶長度的影響

本節研究記憶長度對自適應策略的影響，本節其他參數為步長100，發散代數為20，高閾值為10-4，低閾值為10-10，發散代數為20，乘客車主對數量為1 000對.實驗結果如表7所示.

表7記錄了記憶長度、5組達到最優解95%的較優解的時間、占最優解價值的比率及其均值.

Table 6 Divergence Length for Adaptive Strategy Table表6 自適應策略發散代數表

Notes: DL represents divergence length.

Table 7 Memory Length for Adaptive Strategy Table表7 自適應策略記憶長度表

Notes: ML represents memory length.

實驗結果表明記憶長度變大會增漲算法的運行時間，記憶長度為9時的平均運行時間是長度為2時的143.35%.

3.4.3 自適應策略中閾值的影響

本節研究高低閾值對結果的影響，由于高低閾值之間存在約束，所以將其放在一起實驗.本節其他參數為步長100，記憶長度為2，發散代數20，乘客車主對數量為1 000對.實驗結果如表8所示.

表8記錄了記憶長度、5組達到最優解95%的較優解的時間、占最優解價值的比率及其均值.

Table 8 Threshold for Adaptive Strategy Table表8 自適應策略閾值表

Notes: HT represents negative base-10 logarithm of high threshold; LT represents negative base-10 logarithm of low threshold.

實驗結果表明：高低閾值能在一定程度內降低過程的消耗時間.以高閾值為10-2，低閾值為10-8為標況下，高閾值變化會使結果在81.95%～100%范圍浮動，而低閾值則處于79.01%～100%.它們的效果都不是特別顯著.

3.4.4 自適應策略在不同實驗規模下的效果

本節考察自適應策略在不同算例下的運行結果.實驗參數為：步長為100，高閾值為10-4，低閾值為10-10，發散代數為20，記憶長度為2.實驗結果見圖9和表9.表9記錄了乘客車主對數量、5組達到最優解95%的較優解的時間、占最優解價值的比率及其均值、最優算法時間.

分析實驗結果，自適應策略在1 000對以下，雖然劣于隨機算子策略，但此時運行時間較短，差距不超過3 s.自適應策略在1 000對算例以上運行時間開始顯著優于隨機算子策略和終點加速策略.在1 000對算例時，自適應策略的平均運行時間為隨機算子策略的77.67%，標準算法的38.44%.在3 000對算例時，自適應策略的平均運行時間為隨機算子策略的72.76%，終點加速策略的78.41%，標準算法的18.22%.

Fig.9 Adaptive strategy contrast graph圖9 自適應策略對照圖

Table 9 Adaptive Strategy in Different Data Size Table表9 自適應策略數據規模表

Notes: PN represents participant number; OART represents optimal algorithm running time.

Fig.10 Convergence trend of multiple strategy in iterations times圖10 各策略的迭代次數收斂趨勢

3.5 模式收斂趨勢及共享匹配結果

3種模式的收斂趨勢如圖10和圖11所示.表10展示了在不同的乘客司機對的數量之下不使用共享匹配的總行駛路程、使用共享匹配后的總行駛路程、共享匹配后總節約路程.圖12則展示了部分乘客與車主的匹配結果.

Fig.11 Convergence trend of multiple strategy in running time圖11 各策略的運行時間收斂趨勢

Table 10 Route Contrast Table
表10 路程對比表

ParticipantNumber∕pairTotal DistanceUnshared WayShared WaySavedDistance5069806435545100140341163923952002771921749597050066332487291760310001322689188240386

Fig.12 Matching result of partial drivers and riders圖12 部分車主乘客匹配效果圖

3.6 本文算法和一種基于連接的近似值方法的比較

本節對本文算法和一種較新的近似值方法[11]進行實驗以比較求解效率和質量.

本節選取的策略為自適應策略，參數為：步長為100，發散代數為50，高閾值為10-3，低閾值為10-6，記憶長度為2，迭代次數為10萬次.近似值方法的參數為：分區為10區，擬合率為1.05(保證該算法的求解質量達到最優解的95.24%以上).

需要指出的是，本文的問題模型與文獻[11]中的模型不同，因此刪去了其模型中車主的要求SRP值.此外，該近似方法可能發生退化，在發生退化時，其可獲得真實乘客車主二分圖的價值矩陣，并使用最優解算法來尋找最優解.

實驗結果如表11所示.表11記錄了乘客車主數量、自適應策略2個階段及總體的運行時間、自適應策略的解的SRP值、最優解SRP值、自適應策略的解占最優解的比率、近似值方法2個階段及總體的運行時間(不包括退化后使用最優算法的時間)、近似值方法是否退化.

Table 11 Comparison Between Adaptive Strategy and Approximate Algorithm for Join-based RS表11 自適應策略與基于連接的車輛共乘近似值方法比較表

Notes: PN represents participant number; Rate represents the ratio of current solution to optimal solution in percentage; BD represents whether approximate algorithm has degenerated.

從實驗結果中可以看出，本文方法的速度相較于近似值算法有較大提升，在10對算例下，自適應策略運行時間為近似值算法的33.91%，算例達到500對時，自適應策略運行時間僅為近似值算法的0.26%.

4 總結與展望

本文提出了一種基于單步交換操作解空間圖的解搜索算法.首先，提出了一種兼顧資源利用率和方案可行性的價值評估方法；然后對價值矩陣的生成方式作出了改進；接著提出了3種搜索算子，并根據3種搜索算子設計了3種搜索策略；最后通過實驗測試了各策略對其相應參數的敏感性，并與標準算法及一種較新的近似值方法作了比較.實驗研究表明，本文算法的各個策略都能給出接近最優解SRP 95%以上的高質量解，并且在大部分的算例中運行時間比標準算法和近似值方法有顯著的降低.

在下一階段的研究中，我們將考慮動態時間窗模式下的車輛共乘問題.動態時間窗模式下，車主和乘客的請求將被動態地加載，此時需考慮窗體的劃分方法與全局價值的最大化.車輛共乘問題各種模型始終存在一定差異性，下一階段研究將致力于針對動態車輛共乘問題提出一種可泛化的有效的模型和解決方法.