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

郭羽含 張 宇 沈?qū)W利 于俊宇

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

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

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

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

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

本研究的主要貢獻(xiàn)有3個方面：

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

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

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

1 問題建模

1.1 問題形式化

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

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

設(shè)有車主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表示車主或乘客的所在節(jié)點，a表示車主或乘客的目標(biāo)節(jié)點，p表示節(jié)點，μ表示車主的利潤率.式(6)約束了圖的邊必定是非負(fù)邊.式(7)(8)為起點終點互斥性約束，一個車主或乘客的起點和終點應(yīng)是不同的.式(9)表示車輛的繞行距離及約束，其中CDL表示車主的繞行距離，μ為車主載乘客行駛每公里的收益與車主行駛每公里的花費之比率，式(9)能夠約束車主的共享過程處于收益狀態(tài)之內(nèi).

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

2.1 算法理論基礎(chǔ)

本問題的解可表達(dá)為

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)，簡稱離散排列問題.當(dāng)集合DT中的元素數(shù)量等于解向量S的維度nsolution時，稱該問題為簡單離散排列向量解問題(simple discrete permutation vector solution problem, SDPVSP)，否則稱為拓展的離散排解向量解問題(extend discrete permutation vector solution problem, EDPVSP)，以下首先討論SDPVSP的求解方法，然后再論述在EDPVSP下對該求解方法的拓展.

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

(13)

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

(14)

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

2) 對于DT元素數(shù)量小于向量維度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元素可被重復(fù)使用；式(17)表明null元素的自身不可交換性，null元素不可與其他位置的null交換.

解空間圖的解節(jié)點數(shù)量增多時，解空間圖的結(jié)構(gòu)會變得異常復(fù)雜，因而搜索高質(zhì)量解也變得尤為困難.本文基于SDPVSP和單步交換操作解空間圖(SSEOSSG)，提出一種多策略解空間圖搜索算法，簡稱解空間圖搜索算法.該算法能夠?qū)饪臻g圖進(jìn)行快速且高效的搜索.

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

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

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

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

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

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

輸出：價值矩陣V.

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

② fordinD

③ forrinR

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

/*r所在節(jié)點至目的節(jié)點的最短路徑*/

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

/*d所在節(jié)點至r所在節(jié)點的最短路徑*/

⑥D(zhuǎn)is3=shortest_path(dst(r),dst(d));

/*r目的節(jié)點至d目的節(jié)點的最短路徑*/

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

/*根據(jù)Dis1,Dis2,Dis3求出d和r的SRP*/

⑧ end for

⑨ end for

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

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

2) 檢索元操作.檢索所在節(jié)點至目標(biāo)節(jié)點的最短路徑.

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

算法2.改進(jìn)的價值矩陣生成算法.

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

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

輸出：價值矩陣V.

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

② ifm

③ fordinD

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

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

/*所有節(jié)點至d目標(biāo)節(jié)點的最短路徑*/

⑥ forrinR

/*r所在節(jié)點至目的節(jié)點的最短路徑*/

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

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

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

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

/*根據(jù)Dis1,Dis2,Dis3求出d和r的SRP*/

/*所有節(jié)點至r所在節(jié)點的最短路徑*/

/*r目標(biāo)節(jié)點至所有節(jié)點的最短路徑*/

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

2.3 大值優(yōu)先算法生成初始解

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

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

算法3.大值優(yōu)先算法.

輸入：價值矩陣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則結(jié)束*/

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

⑥ forlocationinnew_row/*對排序列進(jìn)行遍歷*/

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

⑧X[location]=1;

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

⑩ end if

2.4 迭代算子

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

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

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

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

數(shù)學(xué)公式描述為

選擇

?xij,xkl:

(18)

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

(19)

(20)

i≠k,j≠l.

(21)

執(zhí)行:

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

(22)

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

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

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

數(shù)學(xué)公式描述為

選擇

?xij,xkl:

(23)

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

(24)

(25)

i≠k,j≠l,

(26)

vil≥vij.

(27)

如果

vil+vkj≥vij+vkl

(28)

執(zhí)行:

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

(29)

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

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

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

數(shù)學(xué)公式描述為

選擇

?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)

執(zhí)行:

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

(37)

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

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

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

2.5 搜索策略

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

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

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

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

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

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

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

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

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

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

Fig.3 Adaptive strategy flowchart圖3 自適應(yīng)策略流程圖

3 實驗與分析

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

Fig.4 Visualization of path network original data圖4 路網(wǎng)源數(shù)據(jù)可視化

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

3.1 價值矩陣生成時間對比

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

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

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

3.2 隨機算子策略

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

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

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

Table 3 Random Operator Strategy Data Size Table表3 隨機算子策略數(shù)據(jù)規(guī)模表

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

3.3 終點加速策略

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

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

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

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

Notes: CL represents charging length.

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

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

Table 5 End-charging Strategy in Different Data Size Table表5 終點加速策略數(shù)據(jù)規(guī)模表

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

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

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

3.4 自適應(yīng)策略

3.4.1 自適應(yīng)策略中發(fā)散代數(shù)的影響

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

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

3.4.2 自適應(yīng)策略中記憶長度的影響

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

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

Table 6 Divergence Length for Adaptive Strategy Table表6 自適應(yīng)策略發(fā)散代數(shù)表

Notes: DL represents divergence length.

Table 7 Memory Length for Adaptive Strategy Table表7 自適應(yīng)策略記憶長度表

Notes: ML represents memory length.

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

3.4.3 自適應(yīng)策略中閾值的影響

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

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

Table 8 Threshold for Adaptive Strategy Table表8 自適應(yīng)策略閾值表

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

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

3.4.4 自適應(yīng)策略在不同實驗規(guī)模下的效果

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

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

Fig.9 Adaptive strategy contrast graph圖9 自適應(yīng)策略對照圖

Table 9 Adaptive Strategy in Different Data Size Table表9 自適應(yīng)策略數(shù)據(jù)規(guī)模表

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

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

3.5 模式收斂趨勢及共享匹配結(jié)果

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

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 本文算法和一種基于連接的近似值方法的比較

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

本節(jié)選取的策略為自適應(yīng)策略，參數(shù)為：步長為100，發(fā)散代數(shù)為50，高閾值為10-3，低閾值為10-6，記憶長度為2，迭代次數(shù)為10萬次.近似值方法的參數(shù)為：分區(qū)為10區(qū)，擬合率為1.05(保證該算法的求解質(zhì)量達(dá)到最優(yōu)解的95.24%以上).

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

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

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

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

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

4 總結(jié)與展望

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

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