基于雙邊理論的順風車穩定匹配優化

馬瑞民，姚立飛

(1.廣州大學 管理學院，廣東 廣州 510006; 2.廣東財經大學 地理與旅游學院，廣東 廣州 510320)

0 引言

私人小汽車保有量持續增加，座位占用率卻一直很低下。截至2019年底，我國私人汽車擁有量達2.32億輛，其中載客汽車1.89億輛，但從平均保有量來講相比美國等發達國家仍然較低，這意味著我國私人汽車保量很有可能將會持續增加。但是，目前私人小汽車出行的座位占用率仍然很低。據調查北京市在上下班高峰期80%的私家車上都只有一個人[1]，整個交通網絡中的私人汽車座位的使用率極低。由此可見，如果能夠充分挖掘這部分交通網絡中尚未使用交通運輸能力，將對整個交通系統產生巨大的作用，而這也正是順風車的興起的契機。

移動互聯平臺、智能手機及GPS等技術的普及為順風車提供了新的機遇，目前已經有很多平臺提供順風車出行服務，如美國的UberX和Lyft，歐洲的BlaBlaCar以及國內的滴滴出行和嘀嗒出行等等。順風車出行是一種靈活的交通方式，平臺中司機和乘客給出出發時間及起止點，有平臺自動對其進行匹配并具有固定的費用計算規則，一旦匹配成功平臺將對司乘雙方告知信息。順風車出行與傳統的出租車出行是不同的，順風車出行不以盈利為目的，旨在司乘雙方的出行費用節省，且順風車出行中司乘雙方都是平臺的顧客，雙方都可根據其偏好自主選擇一起出行。司機與乘客之間的匹配是順風車出行中的一個關鍵問題。大多數研究將問題表述為具有不同系統優化目標的集中分配問題，如最小化總運行距離[2-4]、最小化總運行時間[5]、最大化系統匹配數量[6-7]等，且系統最優化匹配求解方法也是多種多樣，有精確算法[8-9]、遺傳算法[10]、貪婪算法[11]以及蜂群算法[12]等。但系統最優并不一定是參與者個人的最佳選擇，在順風車出行平臺中參與者是獨立的、利己的個體，如果他們相信存在更好的匹配，他們將拒絕平臺給出的匹配方案，接著去尋找更好的匹配對象或直接轉向其他的出行平臺，即平臺給出的匹配方案并不穩定。

穩定匹配的一個基本問題是眾所周知的穩定婚姻問題(Stable Marriage Problem, SMP)，它是由Gale和Shapley在1962年的開創性論文中首次提出的[13]。針對SMP提出了一種延遲接受算法(DA)，該算法可以為任何穩定的婚姻問題找到至少一個穩定的匹配解。然后，越來越多的SMP變體被提出[14]。在本研究中，往往存在參與者中的某一方因時間窗約束不接受方案或因成本分配不接受方案，而這些參與者是不會出現在偏好列表中的，即在順風車匹配問題中偏好列表是不完全的。此外，參與者在不同的匹配中可能獲得相同的利益，并不嚴格地偏好其中一種匹配。綜上，本研究將從參與者個體角度出發，引入穩定性概念，構建司乘雙方穩定匹配模型，并提出相對應的啟發式算法提高模型求解速度。

1 問題描述

圖1 司機i與乘客j之間的拼車出行Fig.1 Carpooling between driver i and passengers j

一些學者已經構建了相關的順風車匹配系統最優化模型[2]：

(1)

(2)

(3)

(4)

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

(5)

上述模型旨在實現系統最優化的目標，即系統中所有車輛的總行駛距離最小化或系統中所有車輛總行駛時間最小化，但并未考慮匹配雙方的成本分配，在系統最優模型的方案中有可能出現司機的匹配出行的成本還高于單獨出行的成本的情況。從參與者個體角度來看，系統最優化模型給出的方案對參與者來說并不是最佳選擇的選擇。

2 順風車出行穩定匹配模型

首先建立穩定匹配問題的線性規劃模型，并尋找出一個最優的穩定匹配解，記為fsta。對于平臺而言，獲利來源于匹配成功之后的距離節省s，假設平臺從每一對成功匹配都得到一個固定比例的利潤，令平臺獲利比例為η。

2.1 模型假設

A1：一個司機只能載一個乘客，一個乘客也只能搭乘一個司機的車。

A2：乘客與司機的出行成本完全取決于車輛的行駛距離。

A3：如果參與者沒有找到合適的匹配對象，將獨自開車出行。

A4：參與者對成本理性，所有可行的匹配都是對參與者有成本節省的。

A5：參與者知道所有潛在匹配對象的信息。

2.2 參與者偏好序

(1)參與者效用函數構建

在本研究中共享出行參與者的成本分為兩個部分：距離成本和時間機會成本。

ui(i,j)=α·sij+Pay(i,j)-wti,

(6)

uj(i,j)=α·dj-Pay(i,j)-wtj，

(7)

式中α表示單位距離的成本；Pay(i,j)為乘客j向司機i支付的車費。而Pay(i,j)的確定必須考慮參與者之間的具體成本分配方式，不同的分配方式Pay(i,j)是不一樣的。

目前關于單司機單乘客匹配模型中成本分配機制主要分為4種：(1) Geisberger等(2009) 提出平均分配司機與乘客合乘段的成本[15]；(2)Kleiner等(2011)提出平均分配總的行駛距離[16]；(3)Wang等(2013)提出平均分配可行匹配的成本節省[17]；(4)Agtaz等(2011)按原始距離比例進行參與者之間的成本分配[2]。采用原始距離比例進行參與者之間的成本分配，則有：

(8)

(2)參與者效用值排序

由于參與者是理性的，即拼車出行成本必須小于自己駕駛出行的成本，令自己出行的效用值u(p,p)=0，即若參與者沒有因為參與到共享出行平臺而有所改變或獲得利益，參與者將自己出行。

所有參與者最終有兩種匹配結果，第1種是存在可行的匹配對象并且匹配成功，此時效用值ui(i,j)>0&uj(i,j)>0,?k∈I,l∈J；第2種是有可接受的匹配對象但是沒有匹配成功或者沒有接受的匹配對象，此時效用值不大于0，即-(ui(i,j)>0&uj(i,j)>0),?k∈I,l∈J，這一類匹配對象將會直接從該參與者的偏好序中刪除。那么此時視為參與者與自己進行匹配。下面將參與者的偏好序定義為：

π(p)=([1l], [2k],…, [np],p),p∈P。

(9)

π(p)是根據參與者p的效用值進行排序得到的一個偏好序列，下面以具體例子具體說明偏好序中各個符號的意義。例如用π(j)=([1l],[2k],…,[ni],j)為乘客j的偏好序，那么[1l]為司機l∈I處在乘客j偏好序的首位，即對乘客j來說，司機l就是其最佳選擇；其中元素[ni]表示潛在的可接受的匹配對象處在列表π(j)的第n個位置，n也表示可行的匹配對象的數量。在偏好序的最后一個位置是參與者自己，表示如果參與者沒有找到可行的匹配對象，那么他將獨自開車出行或繼續留在平臺上等待匹配，直到他發布的出行信息過期(超出預計的出發時間)。令j?ij′表示司機i嚴格偏好乘客j于j′，同理，i?ji′表示司機j嚴格偏好乘客i于i′。如果司機i與乘客j之間的偏好關系滿足i?jj，那么對乘客j來說司機i是一個潛在的匹配對象，同理，j?ii表示乘客j是司機i的潛在接匹配對象。如果司機i與乘客j之間的偏好關系滿足i?jj且j?ii，那么(i,j)是一個可行的匹配對。

由上述分析我們可以對偏好序中的參與者分為兩類，第1類是存在可行的匹配對象并且匹配成功，這一類的司機與乘客分別記為I(j)∈I和J(i)∈J；第2類是有可接受的匹配對象但是沒有匹配成功或者沒有接受的匹配對象，這一類分別的匹配對象就是參與者自己，記為{i}和{j}。令M=I(j)∪{j}表示乘客j,j∈J的策略空間，令W=J(i)∪{i}表示司機i,i∈I的策略空間。令ψ表示可行匹配對(i,j)的集合，其中i∈M，j∈W。

從上述分析中可以知道，對于任何一個匹配對(i,j)∈ψ(其中i∈M，j∈W)都是可行的，也就是說(i,j)滿足了對應的時間窗口約束，同時考慮了司乘雙方的成本分配問題，(i,j)也能滿足匹配后的出行成本小于或等于匹配前的出行成本的成本約束。于是，可以將系統優化模型式(1)～(5)轉化為：

(10)

式中fso是考慮參與者之間成本分配后的系統最優值，模型(10)能夠保證參與者之間成本分配后個人成本節省是非負的，即保證了出行成本會有減少，但是并不能解決前文所提到的穩定匹配。

2.3 穩定優化模型

對于參與者來說，系統可能會存在一些無差異偏好序列，即對著某個參與者來說，存在多個匹配對象的偏好一樣。如此一來，這個參與者將有一個不嚴格偏好序，為了解決這個問題，Vate和Roth等提出的線性規劃方法對該問題進行求解。穩定匹配模型如下[18-19]:

(11)

對于小規模的匹配問題求解穩定最優解時，可以采用CPLEX進行求解，但是存在以下兩個問題：(1) 本研究要處理的是順風車共享出行參與者之間的匹配，涉及的參與者數量會比較大，而且要求匹配迅速及時。(2) Vate和Roth的優化模型中，仍然以系統最優化為目標，并沒有考慮參與者個人的滿意程度。因此，要將Vate和Roth等提出的線性規劃方法應用到現實，就只能考慮將該線性規劃模型的可行域空間盡可能地縮小，這正是本研究研究的重點問題。

3 模型求解

3.1 可行域空間縮減方法

當參與者的數量較小時，可以對模型(11)直接進行最優解求解，但是本研究需要處理的是共享出行平臺較大批量的司機與乘客的出行匹配，需要短時間進行大批量的匹配，如果不能對模型的可行域進一步地縮減，很難滿足現實中的需求。

3.1.1偏好列表相關理論

定義1[19]:一對一的司機乘客匹配可以定義為從參與者全集到參與者全集的一種單射關系，μ:M∪W→M∪W，對任意的i∈M和j∈W，滿足以下關系：

(1)μ(i)=j當且僅當μ(j)=i，此時i和j是匹配對，記為(i,j)；

(2)如果μ(i)?M，則μ(i)=i，此時i是沒有匹配上的，記為(i,i)；

(3)如果μ(j)?W，則μ(j)=j，此時j是沒有匹配上的，記為(j,j)。

其中，根據μ確定的所有匹配對的集合稱為匹配方案μ。

定義2: 一對一雙邊匹配μ:M∪W→M∪W，對任意的i∈I和j∈J，如果i和j滿足i?jμ(j)且j?iμ(i)，則稱(i,j)是匹配方案μ的一個阻礙對。

定理1假設γ和γ′表示偏好結構，且滿足γ′±Iγ。令μ和μ′表示相對應的穩定匹配，Mμ(Mμ′)表示偏好μ于μ′(偏好μ′于μ)的司機的集合，同樣的道理，令Wμ(Wμ′)表示偏好μ于μ′ (偏好μ′于μ)的乘客的集合。那么，μ′和μ與Mμ′和Wμ之間是一種雙射關系。

另一方面，假設j∈Wμ，同樣的，有μ(j)?jμ′(j)?jj，因此μ(j)∈M。令μ(j)=i，因為μ,μ′是穩定匹配，那么在μ,μ′中是不會存在阻礙對(i,j)的，即μ(i)?iμ′(i)是不成立的。因此i∈Mμ′，μ(Wμ)?Mμ′

由于μ′和μ都是單射，且Mμ′和Wμ都是有限集，則可以得出，μ′和μ與Mμ′和Wμ之間是一種雙射關系。證畢。

定理2 假設μ是任意的一個穩定匹配，S(μ)為與司機成功匹配的乘客的集合，n(μ)為與司機成功匹配的乘客的數量。則有，在所有的穩定匹配中，成功匹配的乘客的集合S(μ)和數量n(μ)都是一致的。

證明：采用反證法證明。假設偏好結構滿足γ′=γ，司機i在穩定匹配μ′中是成功匹配的，但是不在匹配μ中。則有i∈Mμ′，根據定理1可知，μ(Wμ)?Mμ′，即Wμ通過μ與Mμ′形成一種映射關系，那么司機i也必然在穩定匹配μ中，這與假設矛盾，因此命題成立。證畢。

推論1：假設μ是通過GS算法司機-optimal求解的穩定匹配方案，(i,j)是μ中的一個匹配對，且j的偏好序列可以表示為：π(j)=([1]，…，[i],[i]+1，…，[k],[nj],j)，那么將位置[i]+1到位置[nj]+1之間的偏好信息從乘客j的偏好序中刪除對匹配方案沒有影響。同理，假設μ′通過GS算法乘客-optimal求解的穩定匹配方案，類似地對司機列表進行刪減，對整個匹配方案沒有影響。

證明：采用反證法證明。先證明通過司機-optimal的GS算法對乘客列表進行刪減對匹配方案沒有影響。令μ是通過GS算法司機-optimal求解的穩定匹配方案，(i,j)是μ中的一個匹配對，假設對乘客j的偏好序進行刪減對匹配方案有影響，通過定理1和定理2，可以知道所有匹配中，在方案μ中匹配成功的個體，在其他穩定匹配方案中必然會匹配成功。那么說明在至少存在另一個穩定匹配方案μ′，使得(k,j)和(i,l)同時成立。因為在乘客j的偏好序中司機k的位置是在司機i后面的，則有i?jk，而由于是通過GS算法實現的司機-optimal的匹配方案，那么u?iu′，即j?il，由此定義3可知，(i,j)將會是匹配方案μ′的一個阻礙對，這與假設矛盾。因此命題成立。

同理，通過乘客-optimal的GS算法對司機列表進行刪減也不會對匹配方案產生影響。證畢。

3.1.2 Delete算子構建

將DA算法應用到順風車司機與乘客的匹配模型中，司機-Optimal延遲接受算法(DODA)得到的匹配方案對司機來說是最優的，但是對乘客來說卻是最差的一種匹配方案。反之，乘客-Optimal延遲接受算法(RODA)的流程，得到的匹配方案對乘客來說是最優的。

(1)Delete算子

DA算法是Delete算子的核心組成組成部分，利用Delete算子可以對匹配雙方的偏好列表有效地進行精簡，記經過Delete算子精簡之后的偏好序為π(p)gs。用一個列表來匯集所有司機的偏好序，這里稱這個列表為司機偏好列表，記為pl(d)，pl(d)=[π(1);π(2);…;π(i);…;π(m)],i∈I。同理記乘客的偏好列表為pl(r)，則有pl(r)=[π(1);π(2);…;π(j);…;π(n)],j∈J。偏好序的精簡過程如圖2所示。第1步，使用MODA算法后發現d3與r5成功匹配，那么根據推論1可知，將乘客r5偏好序中位于d3位置之后的元素(即排序在5以后的元素)刪除，對匹配結果沒有影響。因為乘客r5偏好序中位于d3位置之后的元素都已經刪除，這意味著乘客r5與d3位置之后的司機都不可能進行匹配，反之，司機d2和d6也不可能與乘客r5進行匹配，即可以將r5從司機d2和d6的偏好序中刪除。依此類推對所有乘客和司機的偏好序進行初次精簡。第2步，使用WODA算法對司機偏好序進行精簡，如圖2所示，此時(r4,d3)是WODA算法求解的穩定匹配方案中的一個匹配對，根據推論1可知，對司機d3偏好序中位于r4位置之后的元素進行刪除，對匹配結果沒有影響。與第一步精簡方法同理，r4位置之后的元素r8,r7,r6的偏好序中也可以進一步將d3刪除。

圖2 Delete算子對偏好序精簡過程Fig.2 Process of reduction of preference order by Delete operator

通過上述的兩步基于GS算法的Delete算子，形成一個精簡的乘客偏好列表，這里記為pl(r)gs=[π(1)gs,π(2)gs,…,π(j)gs,…,π(n)gs],j∈J；類似地，記精簡之后司機偏好列表為pl(d)gs=[π(1)gs,π(2)gs,…,π(i)gs,…,π(m)gs],i∈I。令Mgs和Wgs分別表示通過Delete算子對司機和乘客的潛在可接受匹配對象進行刪減之后的可行域。

3.1.3算法流程

第1階段的主要目的是求得司機與乘客集匹配雙方的偏好列表。根據式(2)判斷司機i與乘客j之間是否滿足時間窗口約束，如果滿足時間窗口約束，則根據式(6)和(7)分別計算ui(i,j)和uj(i,j)，如果u(i,j)<0那么就是意味著，盡管匹配對(i,j)滿足時間窗口約束，但是司機/乘客并不能通過匹配獲得出行成本節省，這種匹配是不穩定的，只要某一方不能獲得出行成本的節省，即匹配不可行的，此時令ui(i,j)=uj(i,j)=-K，K為一個足夠大的正數。在求得所有司機與乘客的效用后，進一步對司機與乘客的效用值進行排序，這里采用最簡單的冒泡法進行排序，最終輸出司機與乘客雙方的偏好列表，該偏好列表是按照效用值的大小從大到小依次排列的兩個序列。

第2個階段是對第1階段得到的偏好列表進行精簡，最終輸出精簡的偏好列表。

3.2 模型處理

對參與者偏好列表進行精簡之后，模型(11)轉化為：

(12)

定理3 模型(12)必然存在最優解[20]。

證明：本研究中參與者有兩種配方式，一是與可行的潛在匹配對象進行匹配或參與者與自己匹配，那么集合Mgs和Wgs的大小都會遠小于參與者的總數，即小于m+n。那么模型(12)為含有不超過m+n個變量的規劃模型，故其最多具有2(m+n)2個可行解，即模型的可行解為有限多個。根據GS算法可知，本研究考慮的雙邊匹配問題必然存在穩定匹配解，即模型(12)至少存在一個可行解。因此模型(12)必然存在最優解。

4 算例分析

順風車的匹配成功與否往往與參與到順風車平臺的人數有關，故將研究城區繁華區域的順風車匹配，由于實際的數據難以獲得，這里將采用合理的數據模擬方法來產生相應的出行供給與出行需求。

4.1 參數設置

假設城區繁華區域是一個長和寬都是20 km的一個正方形區域，且所有出行車輛在該區域內的平均行駛速度都為30 km/h，其中，乘客上下車的服務時間忽略不計，為了研究參與者的出行模式的影響，本研究將從研究兩種不同的參與者起點與終點的分布入手：一種是所有的參與者的起止點都均勻隨機地分布在區域內，另一種是參與者的起止點主要均勻隨機地分布在2個中心。在后一種分布中，司機乘客的起點和終點分別位于兩個不同的中心內，中心是一個圓形區域，半徑為r。

系統中參與者的時間窗口的產生方法如下：為了提高順風車的參與率，主要研究上班高峰期的出行。根據已有研究可知，出行者早上平均最晚出發時間為7:30 am，假設最晚出發時間是以7:30 am 為均值，標準差為45 min的一個正態分布。將均值轉化為分鐘，則早上7:30可以記為450 min，即本研究的出行者最晚出發時間ldp是以450為均衡，45為標準差的一個正態分布，那么參與者p的最晚到達時間lap=ldp+tp，其中tp表示參與者p直接開車從起點到終點的時間。

彈性時間(Flexible Time)：是指除去參與者從起點出發到終點的行駛時間外，可用的冗余時間。標記為FTp。

FTp=ldp-edp=lap-eap。

(13)

假設彈性時間也是服從正態分布的，均值為一個給定的值FTmin，標準差為4 min，那么根據式(13)可以求得edp=ldp-FTp，eap=lap-FTp。

為了計算簡便，本研究假設車輛行駛單位距離的成本為固定的一個值α，α會隨燃油價格的變化而變化，每天不同的時間段α的取值也會發生變化，如在滴滴順風車服務中，夜間單位行駛距離的收費明顯比白天高出很多，交通高峰期的收費也比非交通高峰期高，但是本研究是一種靜態的順風車匹配方案，故在某一個確定的時段，這里的α的取值也將會是一個固定的值。假設順風車匹配平臺將會向每一個成功匹配的匹配對(i,j)收取一定的費用φij，根據上文分析已知，平臺收取的費用與匹配對的距離節省成正比，且比例記為η，為了計算方便，令η是一個固定值。此外，關于司機與乘客的時間機會成本wtp，本研究假設時間機會成本的系數ω已知，系數ω與參與者的工資水平成正相關，假設參與者p的工資為w元/年，假設每天工作時間是8 h，那么系數ω關系式可以表示為：ωp=w/(12×30×8×60)。為了便于計算，本研究假設所有參與者對時間機會成本的敏感程度是一致的，以北京年平均工資為例計算時間機會成本系數，根據國家統計年鑒，北京市2019年平均年工資為111 390元，那么ω≈0.645。

4.2 評價指標

(1) 匹配成功率(Suc)：匹配成功率定義為成功匹配上的參與者出行量除以參與者發布的總的出行需求量。假設穩定匹配模型求解的結果中，成功匹配的匹配對的數量為Ns，在平臺中發布出行需求的司機數量為Nd，在平臺中發布出行需求的乘客數量為Nr，那么匹配成功率為：

Suc=2Ns/(Nd+Nr)×100%。

(2)總行駛距離節省比率(Sav)：總行駛距離節省比率定義為通過穩定匹配模型求解得到的系統總距離節省除以所有發布出行需求的司機與乘客直接從起點開車往終點的所有行駛距離之和，可以用公式表示為：

(3) 參與者個人出行平均節省比率(Si)：參與者個人出行平均節省定義為參與者出行的個人距離節省除以其獨自出行的行駛距離，再對所有成功匹配的參與者求平均值。根據不同的成本分配方式，Si的表達公式是不一樣的，本研究主要討論按比例分配方式。假設參與者按比例分配距離節省，那么Si的公式表達為：

(4) 司機平均繞路比率(Dt)：司機平均繞路比率定義為司機因為參與順風車出行需要的額外行駛距離除以該司機單獨出行的行駛距離，再對所有成功匹配的司機求取平均值。Dt的表達式如下：

為了衡量本研究構建的穩定匹配模型以及提出的Delete算子的穩定性，本節進一步構建了如下指標來進行衡量模型的效果。

(5) Price of Anarchy (POA)：根據前文定義，POA定義為穩定距離總節省偏離系統最優距離總節省的比例。POA表達式如下：

POA=(fso-fsta)/fso×100%。

(6) 程序運行時間：本研究可以分為3種：直接求解系統最優值f已經對應的匹配方案的運行時間，記為RT；求解考慮參與者之間成本分配的系統最優值fso的運行時間，記為RTso；利用Delete算子對參與者偏好列表精簡之后，求解穩定匹配值及對應的匹配方案的運行時間，記為RTsta。

4.3 結果分析

(1) 參與者數量、聚集中心對匹配的影響

將Suc，Sav，Sipr，Dt，POA5個指標對平臺中潛在參與者數量和匹配區域中聚集中心對順風車匹配結果的影響進行對比分析。如圖4所示，參與者數量變化區間為400～2 400，參與者彈性時間的均值為FT=30 min，彈性時間服從正態分布，標準差為4 min，平臺向成功匹配的匹配對收取的費用比例η=10%，這里并不考慮參與者的時間機會成本，即ω=0，區域內所有司機單位行駛距離成本α為2元/km。

圖3(a)是參與者數量與穩定匹配率關系的對比圖，從圖中可以看到，有交通中心時的穩定匹配率遠遠高于沒有交通中心時，當服務區內參與者數量僅為400時，有交通中心的順風車穩定匹配率就已經達到了91.3%，此時，無交通中心的順風車穩定匹配率僅僅為62.6%；而當服務區內參與者數量上升至2 400時，有交通中心的順風車穩定匹配率達到了95%，無交通中心的順風車匹配率僅為78%。圖3(b) 是參與者數量與穩定匹配總距離節省比率關系的對比圖，從圖中可以看到，有交通中心時的距離節省比率也是遠遠高于沒有交通中心時，從35.1%上升到39.9%，無交通中心的穩定匹配總距離節省比率隨著參與者數量的變化從18.3%變動到27.2%。圖3(c) 是參與者數量與穩定匹配個人平均出行距離節省比率關系的對比圖，與圖3(a)和圖3(b)中的曲線有著類似的規律，隨著參與者人數的不斷增加，Sipr曲線不斷上升，且有兩個交通中心的個人平均距離節省比率遠高于沒有交通中心。圖3(d) 是參與者數量與司機平均繞路比率關系的對比圖，從圖中可以看出，隨著參與者數量的不斷增加，司機的平均繞路比率不斷下降，且有交通中心時司機的繞路比率是遠低于沒有交通中心時。當參與者人數上升至2 400時，在有兩個交通中心的情況下，司機的繞路比率僅僅為16.1%，而此時，在沒有交通中心的情況下，高比率為24.2%。此外需要指出的是，盡管在有兩個交通中心的情況下，順風車匹配的指標Suc,Sav,Sipr,Dt都展示出更好的指標值并一直保持著良好的穩定性能。Gap指標，也就是POA值，一直維持在6.4%到7.4%之間。由此可見，隨著參與者人數的增加，本研究提出的穩定優化模型及算法都展示了良好，得到的穩定匹配解非常接近系統最優解。

圖3 參與者數量、聚集中心對順風車匹配的影響Fig.3 Influence of number of participants and gathering center on ridesharing matching

(2) 時間機會成本、聚集中心對匹配的影響

下面將對參與者時間機會成本和匹配區域中聚集中心對順風車匹配結果的影響進行對比分析。其中參與者時間機會成本系數從0～0.9變化。參與者彈性時間的均值為FT=30 min，彈性時間服從正態分布，標準差為4 min，平臺向成功匹配的匹配對收取的費用比例η=10%，區域內參與者人數為1 400，其中司機700，乘客700，區域內所有司機單位行駛距離成本α為2元/km。

圖4 (a)是參與者時間機會成本系數與穩定匹配率關系的對比圖，從圖中可以看到，無論服務區內有無聚集中心，穩定匹配率總是隨著參與者時間機會成本系數的變大而不斷下降，不同的是有兩個聚集中心的情況下，穩定匹配率處于較高的狀態。當參與者的時間機會成本系數增大到0.9時，匹配率依然高達77.6%，而此時沒有聚集中心時的穩定匹配率僅僅為48.6%，匹配率較低。圖4(b) 是參與者時間機會成本與穩定匹配總距離節省比率關系的對比圖，與圖(a)中的曲線有著類似的規律，隨著參與者時間機會成本系數的不斷增大，Sav曲線不斷下降。圖4 (c) 是參與者時間機會成本與穩定匹配個人平均出行距離節省比率關系的對比圖，從圖中可以發現，Sipr曲線不但沒有隨著時間機會成本系數的增加而下降，反而一直保持比較穩定的比率，并呈現略微的上升趨勢，原因在于出行者對時間的敏感程度高，往往不接受需要花太多時間的匹配，即拒絕繞路距離較長的匹配，接受的大都是繞路時間短，且成本節省比率大的匹配，因而會使個人出行的平均距離節省比率呈現上升趨勢。而這一點與圖4(d) 中參與者時間機會成本與司機平均繞路比率關系是相呼應的，從圖中可以看出，隨著參與者時間機會成本系數的不斷增加，司機的平均繞路比率是不斷下降的。圖4(e) 是參與者時間機會成本與穩定匹配POA值關系的對比圖，如圖所示，隨著時間機會成本系數的增大，穩定匹配解與系統最優解之間的差距越來越大，原因如前所述，出行者時間敏感度高時，出行者很有可能會拒絕一些耗時而有距離節省的匹配，導致穩定匹配解與最優解之間的差距越來越大。但是需要指出的，對時間很敏感的人群參與到順風車出行當中的比率相對較小。

圖4 彈性時間、聚集中心對順風車匹配的影響Fig.4 Influence of elastic time and gathering center on ridesharing matching

(3) 算法效率

這里將對3種不同的求解方式的程序運行時間進行對比：第1種，假設參與者之間按原始出行距離的比例分配出行成本，可以保證得到的匹配方案中所有的成功匹配的司乘雙方都有成本節省，對應模型為式(10)，記對應的程序運行時間為RTso；第2種，為系統穩定匹配模型(11)對應的程序運行時間RTsta2，此時參與者的偏好列表并未進行精簡；第3種，利用Delete算子對參與者偏好列表精簡之后模型(12)，求解穩定匹配值及對應的匹配方案的運行時間，記為RTsta1。

圖5 各程序運行時間對比Fig.5 Comparison of running time of each program

對RTsta1，RTsta2，RTso的比較可見圖5，如圖中所示，隨著參與者規模的不斷增大，RTsta1，RTsta2，RTso的值都有著明顯的增加，在參與者規模小于1 400 時，求解模型(10)的程序運行時間RTso、求解沒有精簡偏好列表的模型(11)對應的程序運行時間RTsta2和使用精簡列表的模型(12)的程序運行時間RTsta1差距很小，尤其是在小規模問題時，往往出現RTsta2

5 結論

本研究構建了順風車穩定匹配優化模型，并從參與者數量、參與者彈性時間、參與者時間機會成本、區域內有沒有聚集中心和算法效率等5個方面對本研究提出的算法進行分析，其中衡量指標包含匹配率Suc、總距離節省比率Sav、參與者個人出行距離節省比率Sipr、司機繞路比率Dt以及穩定優化解和系統最優解之間的POA值。通過全面的試驗和結果分析發現：(1) 無論服務區內有無聚集中心，隨著參與者數量的增加，匹配率Suc、總距離節省比率Sav和參與者個人出行距離節省比率Sipr都不斷上升，但服務區內有兩個交通聚集中心時，Suc，Sav和Sipr都分別高于沒有交通中心時，而隨著參與者數量的增加，司機繞路比率Dt不斷下降；(2) 無論服務區內有無交通聚集中心，隨著參與者時間機會成本系數的增加，匹配率Suc、總距離節省比率Sav和司機繞路比率Dt是不斷下降的，而隨著參與者時間機會成本系數的增加，POA值不斷增加的；(3) 隨著參與者彈性時間的增加，對于服務區內無交通中心的情況，隨著參與者數量的增加，匹配率Suc、總距離節省比率Sav和參與者個人出行距離節省比率Sipr都不斷上升，司機繞路比率Dt是不斷下降的；(4) 通過比較系統最優化模型、考慮參與者成本的系統優化模型和穩定匹配優化模型求解時間，發現本研究提出的偏好列表精簡算法非常有效，能夠有效地降低求解穩定匹配解的時間，使得本研究提出的穩定匹配優化模型能夠應用到大型的順風車匹配問題中。總而言之，本研究提出算法能夠快速有效地解決單司機單乘客穩定匹配問題。