馬瑞民，姚立飛

(1.廣州大學(xué) 管理學(xué)院，廣東 廣州 510006; 2.廣東財(cái)經(jīng)大學(xué) 地理與旅游學(xué)院，廣東 廣州 510320)

0 引言

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

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

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

1 問題描述

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

一些學(xué)者已經(jīng)構(gòu)建了相關(guān)的順風(fēng)車匹配系統(tǒng)最優(yōu)化模型[2]：

(1)

(2)

(3)

(4)

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

(5)

上述模型旨在實(shí)現(xiàn)系統(tǒng)最優(yōu)化的目標(biāo)，即系統(tǒng)中所有車輛的總行駛距離最小化或系統(tǒng)中所有車輛總行駛時(shí)間最小化，但并未考慮匹配雙方的成本分配，在系統(tǒng)最優(yōu)模型的方案中有可能出現(xiàn)司機(jī)的匹配出行的成本還高于單獨(dú)出行的成本的情況。從參與者個(gè)體角度來看，系統(tǒng)最優(yōu)化模型給出的方案對參與者來說并不是最佳選擇的選擇。

2 順風(fēng)車出行穩(wěn)定匹配模型

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

2.1 模型假設(shè)

A1：一個(gè)司機(jī)只能載一個(gè)乘客，一個(gè)乘客也只能搭乘一個(gè)司機(jī)的車。

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

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

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

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

2.2 參與者偏好序

(1)參與者效用函數(shù)構(gòu)建

在本研究中共享出行參與者的成本分為兩個(gè)部分：距離成本和時(shí)間機(jī)會(huì)成本。

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

(6)

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

(7)

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

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

(8)

(2)參與者效用值排序

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

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

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

(9)

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

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

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

(10)

式中fso是考慮參與者之間成本分配后的系統(tǒng)最優(yōu)值，模型(10)能夠保證參與者之間成本分配后個(gè)人成本節(jié)省是非負(fù)的，即保證了出行成本會(huì)有減少，但是并不能解決前文所提到的穩(wěn)定匹配。

2.3 穩(wěn)定優(yōu)化模型

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

(11)

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

3 模型求解

3.1 可行域空間縮減方法

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

3.1.1偏好列表相關(guān)理論

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

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

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

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

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

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

定理1假設(shè)γ和γ′表示偏好結(jié)構(gòu)，且滿足γ′±Iγ。令μ和μ′表示相對應(yīng)的穩(wěn)定匹配，Mμ(Mμ′)表示偏好μ于μ′(偏好μ′于μ)的司機(jī)的集合，同樣的道理，令Wμ(Wμ′)表示偏好μ于μ′ (偏好μ′于μ)的乘客的集合。那么，μ′和μ與Mμ′和Wμ之間是一種雙射關(guān)系。

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

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

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

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

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

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

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

3.1.2 Delete算子構(gòu)建

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

(1)Delete算子

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

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

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

3.1.3算法流程

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

第2個(gè)階段是對第1階段得到的偏好列表進(jìn)行精簡，最終輸出精簡的偏好列表。

3.2 模型處理

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

(12)

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

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

4 算例分析

順風(fēng)車的匹配成功與否往往與參與到順風(fēng)車平臺的人數(shù)有關(guān)，故將研究城區(qū)繁華區(qū)域的順風(fēng)車匹配，由于實(shí)際的數(shù)據(jù)難以獲得，這里將采用合理的數(shù)據(jù)模擬方法來產(chǎn)生相應(yīng)的出行供給與出行需求。

4.1 參數(shù)設(shè)置

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

系統(tǒng)中參與者的時(shí)間窗口的產(chǎn)生方法如下：為了提高順風(fēng)車的參與率，主要研究上班高峰期的出行。根據(jù)已有研究可知，出行者早上平均最晚出發(fā)時(shí)間為7:30 am，假設(shè)最晚出發(fā)時(shí)間是以7:30 am 為均值，標(biāo)準(zhǔn)差為45 min的一個(gè)正態(tài)分布。將均值轉(zhuǎn)化為分鐘，則早上7:30可以記為450 min，即本研究的出行者最晚出發(fā)時(shí)間ldp是以450為均衡，45為標(biāo)準(zhǔn)差的一個(gè)正態(tài)分布，那么參與者p的最晚到達(dá)時(shí)間lap=ldp+tp，其中tp表示參與者p直接開車從起點(diǎn)到終點(diǎn)的時(shí)間。

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

FTp=ldp-edp=lap-eap。

(13)

假設(shè)彈性時(shí)間也是服從正態(tài)分布的，均值為一個(gè)給定的值FTmin，標(biāo)準(zhǔn)差為4 min，那么根據(jù)式(13)可以求得edp=ldp-FTp，eap=lap-FTp。

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

4.2 評價(jià)指標(biāo)

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

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

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

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

(4) 司機(jī)平均繞路比率(Dt)：司機(jī)平均繞路比率定義為司機(jī)因?yàn)閰⑴c順風(fēng)車出行需要的額外行駛距離除以該司機(jī)單獨(dú)出行的行駛距離，再對所有成功匹配的司機(jī)求取平均值。Dt的表達(dá)式如下：

為了衡量本研究構(gòu)建的穩(wěn)定匹配模型以及提出的Delete算子的穩(wěn)定性，本節(jié)進(jìn)一步構(gòu)建了如下指標(biāo)來進(jìn)行衡量模型的效果。

(5) Price of Anarchy (POA)：根據(jù)前文定義，POA定義為穩(wěn)定距離總節(jié)省偏離系統(tǒng)最優(yōu)距離總節(jié)省的比例。POA表達(dá)式如下：

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

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

4.3 結(jié)果分析

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

將Suc，Sav，Sipr，Dt，POA5個(gè)指標(biāo)對平臺中潛在參與者數(shù)量和匹配區(qū)域中聚集中心對順風(fēng)車匹配結(jié)果的影響進(jìn)行對比分析。如圖4所示，參與者數(shù)量變化區(qū)間為400～2 400，參與者彈性時(shí)間的均值為FT=30 min，彈性時(shí)間服從正態(tài)分布，標(biāo)準(zhǔn)差為4 min，平臺向成功匹配的匹配對收取的費(fèi)用比例η=10%，這里并不考慮參與者的時(shí)間機(jī)會(huì)成本，即ω=0，區(qū)域內(nèi)所有司機(jī)單位行駛距離成本α為2元/km。

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

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

(2) 時(shí)間機(jī)會(huì)成本、聚集中心對匹配的影響

下面將對參與者時(shí)間機(jī)會(huì)成本和匹配區(qū)域中聚集中心對順風(fēng)車匹配結(jié)果的影響進(jìn)行對比分析。其中參與者時(shí)間機(jī)會(huì)成本系數(shù)從0～0.9變化。參與者彈性時(shí)間的均值為FT=30 min，彈性時(shí)間服從正態(tài)分布，標(biāo)準(zhǔn)差為4 min，平臺向成功匹配的匹配對收取的費(fèi)用比例η=10%，區(qū)域內(nèi)參與者人數(shù)為1 400，其中司機(jī)700，乘客700，區(qū)域內(nèi)所有司機(jī)單位行駛距離成本α為2元/km。

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

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

(3) 算法效率

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

圖5 各程序運(yùn)行時(shí)間對比Fig.5 Comparison of running time of each program

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

5 結(jié)論

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