面向公平保障的共乘定價與匹配算法*

林彥佳,武繼剛,吳嘉鑫,陳 龍

(廣東工業(yè)大學(xué)計算機學(xué)院，廣東 廣州 510006)

1 引言

共乘是一種將具有相似行程和相近出行時間的多名乘客聚集到同一車輛中完成服務(wù)的出行方式。在一般的共乘場景中，參與人員包括司機和乘客。同時諸如滴滴和Uber等共乘平臺充當(dāng)著中介，負責(zé)對雙方進行匹配。通過參與共乘，乘客能以更少的費用出行，而司機通過同時為多名乘客提供服務(wù)獲得更多的收入。與非共乘相比，共乘可以緩解交通擁堵，減少能源消耗并節(jié)省差旅支出[1,2]。根據(jù)共乘車輛的屬性，可以將共乘分為2大類：基于私家車的共乘[3 - 5]和基于出租車的共乘[6 - 8]。在基于私家車的共乘中，車主為有相似行程的乘客提供服務(wù)以賺取額外的收入。在基于出租車的共乘中，多名乘客一同出行以分攤出行費用。由于出租車有較高的靈活性，因此本文的研究重點為基于出租車的共乘。在基于私家車的共乘中，提供共乘接載服務(wù)的司機有自身明確的起點和終點，因此其在提供共乘服務(wù)時行駛線路相對固定。而在基于出租車的共乘中，車輛前往的目的地隨著共乘請求的加入而變化，因此具有更高的不確定性。

由于共乘的諸多優(yōu)點，共乘的問題已經(jīng)得到了廣泛的研究。在現(xiàn)實應(yīng)用場景中共乘請求存在離線和在線2種類型，文獻[9]提出了一種根據(jù)歷史數(shù)據(jù)挖掘潛在乘客的方法，以達到服務(wù)更多乘客的目的。文獻[10,11]指出基于聚合點的共乘能在保證服務(wù)質(zhì)量的同時服務(wù)更多的請求和保護乘客隱私，提高共乘的效率。文獻[12,13]綜合考慮了時間和空間約束，分別為乘客提供多個可選的車輛并由此制定共乘費用策略。文獻[14,15]分別提出了基于拍賣和雙向拍賣的共乘匹配機制。文獻[16]提出了一種基于二分圖的匹配方法，以降低問題的整體計算復(fù)雜度。文獻[17]將共乘匹配問題轉(zhuǎn)化為最小化所有參與者的出行成本問題，以實現(xiàn)共乘中的高效匹配。另外，隨著移動技術(shù)的發(fā)展，社交關(guān)系等因素也成為影響共乘服務(wù)質(zhì)量的因素之一，文獻[18]在共乘的匹配過程中結(jié)合了社交網(wǎng)絡(luò)中用戶之間的關(guān)系,以達到提高共乘服務(wù)質(zhì)量的目的。

盡管現(xiàn)有研究已從多個方面對共乘進行了探索，但它們都沒有考慮到現(xiàn)實應(yīng)用中存在的收費標(biāo)準(zhǔn)不統(tǒng)一和惡意價格競爭的問題。例如，有些司機為了提升競爭力和接送更多乘客而壓低價格；在共乘請求的高峰期，空閑司機少乘客請求多，部分司機因處于相對有利位置而哄抬價格，這都會導(dǎo)致正常的市場競爭秩序被破壞。此外，現(xiàn)有的共乘研究也沒有充分考慮共乘請求地理位置的相似性，現(xiàn)有的大多數(shù)研究對共乘請求采用逐個處理的方法，即當(dāng)收到乘客發(fā)送的共乘請求后，共乘平臺會逐個匹配，而忽略了有些請求可能存在起點和終點高度相似的情況。共乘匹配結(jié)果是由共乘平臺根據(jù)當(dāng)前司機與乘客的數(shù)目及其所處的位置等信息決定的，同一時刻的不同乘客的匹配結(jié)果在等待時間、單位距離所需支付的費用和繞路距離等不一定相同，因此乘客所得服務(wù)的質(zhì)量也可能存在較大差異。為減小共乘匹配中乘客所得服務(wù)質(zhì)量的差異性，本文同時考慮乘客支付費用、車輛座位數(shù)和繞路距離約束，對共乘的公平問題進行了深入研究。本文主要貢獻總結(jié)如下：

(1)結(jié)合乘客支付費用、車輛座位數(shù)和繞路距離約束，提出最大化共乘匹配結(jié)果公平性方案，并將共乘中的定價與匹配過程建模為一個兩階段的主從博弈，其中司機為領(lǐng)導(dǎo)者，乘客為跟隨者，同時引入Raj Jain’s公平指數(shù)作為評估標(biāo)準(zhǔn)來衡量共乘匹配結(jié)果。

(2)基于乘客的位置屬性，設(shè)計了請求劃分算法，以縮小匹配范圍，提高匹配效率。為解決本文提出的最大化匹配結(jié)果公平性的問題，設(shè)計了一個基于兩階段主從博弈的定價與匹配算法DPMA(Distributed Pricing and Matching Algorithm)，并分析了其收斂性。在DPMA中，司機與乘客依次做出博弈決策,以保證最大化匹配結(jié)果的公平性。

(3)在真實出租車數(shù)據(jù)集上進行了實驗，驗證了DPMA的收斂性。實驗結(jié)果表明，本文DPMA在公平指數(shù)上分別比現(xiàn)有Rank算法和BA (Bilateral Arrangement)算法高出34.03%和24.42%，其中本文算法在該指標(biāo)上接近于1，即所設(shè)計機制可以有效避免惡意價格競爭。

2 系統(tǒng)模型

在共乘匹配模型中存在著乘客和司機2種角色，共乘平臺負責(zé)兩者之間的匹配。如圖1所示，首先乘客向共乘平臺發(fā)送請求，請求內(nèi)容包括起點、終點和請求所包含的乘客數(shù)等必要信息。此外，車輛向共乘平臺發(fā)送自己當(dāng)前所處的位置和收費信息。最后共乘平臺根據(jù)雙方提供的相關(guān)信息進行匹配。令R={r1,r2,…,rm}表示共乘請求的集合，V={v1,v2,…,vn}表示車輛的集合，即共乘場景中存在m個請求和n輛車。令ri=(oi,di,si,δi),ri∈R表示第i個共乘請求，1≤i≤m,其中oi、di、si和δi分別表示該請求的起點、請求的終點、請求所包含乘客數(shù)和請求可接受的繞路比例。令vj=(oj,aj),vj∈V表示第j輛車，1≤j≤n,其中oj和aj分別表示該車的當(dāng)前位置和可提供的座位數(shù)。本文涉及的其它符號及其含義如表1所示。

Figure 1 System model圖1 系統(tǒng)模型

表1 符號及含義

在共乘系統(tǒng)中，乘客和司機有各自的屬性，因此在共乘匹配過程中需要滿足一些約束。

(1) 費用約束：令ω*表示在非共乘場景下每位乘客需向司機支付的單位距離費用，ωj為共乘場景下車輛vj向每位乘客收取的單位距離費用。由于共乘會給乘客帶來一定的繞路和等待時間，因此共乘場景下的收費比非共乘時的低，兩者的比值pj如式(1)所示:

(1)

其中,pj越小，乘客在共乘場景下所需支付的費用相較于非共乘場景下越少，pmax為共乘平臺設(shè)定的pj取值上限。

(2) 座位約束：由于每輛車的座位數(shù)是有限的，因此共乘請求所包含的乘客數(shù)應(yīng)不大于車輛可提供的座位數(shù)。令zij表示請求ri和車輛vj之間的匹配關(guān)系，如果由車輛vj接送請求ri中的乘客，則zij=1，否則zij=0。對于每個請求ri，滿足如式(2)所示的約束:

(2)

即每個請求最多只能分配到一輛車上。對于任意車輛vj，滿足如式(3)所示約束:

(3)

即每輛車同時接送的乘客數(shù)不超過其總座位數(shù)。

(3) 繞路約束：車輛必須滿足車上乘客的繞路距離約束。令Gj表示車輛vj當(dāng)前正在服務(wù)的共乘請求集合，則接載新請求r*=(o*,d*,s*,δ*)中的乘客需滿足如式(4)所示約束:

(4)

其中，li表示請求ri的起點到終點的距離，Δl*表示請求r*加入后車輛vj所增加的繞路距離。式(4)表示，只有當(dāng)新的共乘請求加入所帶來的繞路距離Δl*不大于該車輛當(dāng)前正在服務(wù)的所有請求所能接受的繞路距離，該請求才會被車輛接受。

3 司機與乘客的主從博弈

在共乘匹配開始之前，各司機同時向共乘平臺發(fā)送價格信息，這可能導(dǎo)致一些特殊情況的發(fā)生。例如，部分司機為了吸引更多的乘客而將價格定得很低，即惡意競價，導(dǎo)致司機之間的合理競爭被破壞。另外，當(dāng)司機處在一個相對有利的位置時，即當(dāng)空閑司機少乘客請求多時，可能存在司機哄抬價格的現(xiàn)象。在這樣的情況下，有些乘客雖然參與了共乘，卻仍需支付相對較高的費用，同時還需花費時間等待和繞路，這些乘客的利益將會受到損害。若將乘客在共乘中的所得服務(wù)(如與共乘伙伴的社交關(guān)系、支付費用、等待時間和繞路距離等)量化為統(tǒng)一可對比的指標(biāo)，則各乘客所得服務(wù)質(zhì)量可能存在較大差異。

主從博弈，即一個存在領(lǐng)導(dǎo)者和跟隨者的博弈。在該博弈中，領(lǐng)導(dǎo)者在博弈中優(yōu)先做出決策，跟隨者在領(lǐng)導(dǎo)者之后做出博弈決策。由于主從博弈能很好地反映多參與者之間的博弈關(guān)系，因此它被應(yīng)用于許多研究場景，例如無線網(wǎng)絡(luò)[19]、移動邊緣計算[20]和無人機[21]等。在共乘匹配中司機為服務(wù)提供方，乘客為被服務(wù)方，因此可將雙方的匹配過程視為一個以司機為領(lǐng)導(dǎo)者、乘客為跟隨者的主從博弈。由于司機和乘客分別需要根據(jù)已有條件做出決策，因此該博弈可分為兩階段。在第一階段，司機收到來自乘客的共乘請求，隨后根據(jù)請求做出價格的調(diào)整；在第二階段，乘客會收到關(guān)于不同車輛的信息，包括車輛的當(dāng)前位置和收取費用等，然后根據(jù)已有信息選擇目標(biāo)車輛。

3.1 乘客屬性

與文獻[18]類似，本文根據(jù)效用值來評估共乘，并使用多屬性效用模型[15,22]來具體地表示共乘匹配中的效用。設(shè)F(xk)表示第k個屬性對應(yīng)的效用值,其計算如式(5)所示:

F(xk)=1-xk/Mk，1≤k≤K

(5)

其中,Mk為xk的最大取值，即隨著xk的增大，其對應(yīng)的效用值會降低。xk為第k個屬性的取值； 一般各權(quán)重取值相同[10]。隨著共乘技術(shù)的發(fā)展，費用已不再是乘客考慮的唯一因素。由于乘客發(fā)送共乘請求與司機為乘客提供服務(wù)之間存在時間間隔，即存在等待時間，等待時間的長短會影響共乘體驗質(zhì)量，因此本文效用值屬性包含等待時間屬性和出行費用屬性。

乘客發(fā)送完共乘請求之后，需要在起點處等待接送車輛，這一過程的等待時間包含兩個部分：一部分為共乘平臺響應(yīng)延遲，即乘客發(fā)送共乘請求與共乘平臺向乘客發(fā)送匹配結(jié)果之間的時間差；另一部分為車輛接送延遲，即司機從其當(dāng)前位置到乘客起點所需的時間。因此，請求ri等待車輛vj的時間eij如式(6)所示:

(6)

(7)

(8)

綜上，請求ri的效用值ui如式(9)所示:

(9)

其中α1和α2分別表示時間效用和費用效用的權(quán)重。

由于不同車輛當(dāng)前所處的位置和收取的費用不同，對同一乘客而言，與不同的車輛匹配后其對應(yīng)的效用值也不同。同時，乘客的選擇之間也存在相互影響的關(guān)系。例如當(dāng)大多數(shù)乘客選擇收費相對較低的車輛后，如果有新乘客做出同樣的選擇，那么其等待時間和繞路距離將會增加，其他司機可能也無法在共乘中獲取利益。

3.2 司機屬性

為了保證司機的利益，在設(shè)定pj取值上限的同時需要為其設(shè)定一個下限，即式(1)可重寫為式(10):

pmin≤pj≤pmax,1≤j≤n

(10)

(11)

其中,ωj為共乘場景下車輛vj向每位乘客收取的單位距離費用，li表示請求ri的起點到終點的距離。

3.3 求解目標(biāo)

若將車輛vj服務(wù)的各個共乘請求視為一個整體，并定義其為群組Gj，同時令G為各群組組成的集合。對于群組Gj，令其中各個請求效用值的平均值為該群組的效用Uj，則Uj可表示如式(12)所示：

(12)

由于Raj Jain’s公平指數(shù)能很好地衡量多方之間的公平性，因此它已被廣泛應(yīng)用于5G[24]、無人機[25]和電力市場[26]等領(lǐng)域。根據(jù)Raj Jain’s公平指數(shù)的定義，共乘的公平指數(shù)J(G)如式(13)所示:

(13)

其中,共有n個群組，即存在n輛車和n組對應(yīng)的乘客，Uj表示第j個群組的群組效用。由Raj Jain’s公平指數(shù)的定義可知，J值越大，共乘匹配結(jié)果的公平性越高。因此，面向公平保障的共乘匹配問題可表示為:

OBJ: maxJ(G)

s.t.(2),(3),(4),(6),(9),(10),(12)

其中,J(G)表示共乘的公平指數(shù)；式(2)表示每個請求最多只能與一輛車匹配；式(3)表示車輛同時接送的乘客不得超過其總座位數(shù)；式(4)表示車輛必須滿足乘客的最大繞路距離約束；式(6)表示乘客等待時間為共乘平臺響應(yīng)延遲和車輛接送延遲之和；式(9)表示請求效用值為時間效用與費用效用的加權(quán)和；式(10)為乘客的共乘費用約束；式(12)表示群組效用為同一群組內(nèi)請求效用的平均值。

4 算法

4.1 請求劃分

在共乘匹配開始之前，乘客需提交關(guān)于請求的信息，包括請求的起點位置、終點位置和乘客數(shù)。根據(jù)請求起點和終點的經(jīng)緯度信息，可用一個向量ci=(si.lat,si.lon,di.lat,di.lon),ci∈C來表示請求ri的位置屬性，其中si.lat,si.lon,di.lat和di.lon分別表示請求ri起點的緯度、起點的經(jīng)度、終點的緯度和終點的經(jīng)度，C代表請求的位置向量的集合。由于有些共乘請求有相近的起點和終點，因此將這些請求分配到同一輛車能減少繞路距離和等待時間，即將有相似向量的請求聚類到一起處理能提高共乘匹配效率。由于共乘平臺服務(wù)范圍較廣，并不是任意的兩個請求都能屬于同一個聚類，為了更合理地劃分請求，本文基于K-means++[27]設(shè)計了一個請求劃分算法CR(Clustering for Requests)，具體細節(jié)如算法1所示。

算法1請求劃分算法CR

輸入：請求的位置向量集合C，聚類數(shù)目K。

輸出：聚類結(jié)果M。

1:隨機選擇一個請求作為初始聚類中心q1；

2:repeat

3: 計算各向量ci∈C到當(dāng)前已有聚類中心之間的最短距離D(ci)；

4: 計算各向量ci選為聚類中心的概率P(ci)；

5: 按照輪盤法選擇下一個聚類中心；

6:until選出K個聚類中心;

7:repeat

8:forci∈Cdo

9: 計算到聚類中心的距離dis(ci,qk),?qk∈Q；

10: 更新ci所屬聚類Mi；

11:endfor

12:fork=1 toK

13: 計算新的聚類中心位置Qk；

14:endfor

15:until聚類中心位置不再改變;

16:returnM

請求劃分算法包含兩個部分，分別為聚類中心初始化階段(第1～6行)和聚類階段(第7～15行)。令Q表示聚類中心的集合，在初始化階段，首先隨機選擇一個請求的位置向量作為初始聚類中心；隨后計算各個向量到當(dāng)前已有聚類中心的最短距離D(ci)，如式(14)所示:

D(ci)=min{dis(ci,qk)},?qk∈Q

(14)

其中dis(ci,qk)表示向量ci到中心qk的歐氏距離。隨后計算各個請求被選為聚類中心的概率，對任意請求的位置向量ci∈C，其成為下一聚類中心的概率如式(15)所示:

(15)

當(dāng)完成各向量成為聚類中心概率的計算后，按照輪盤法選擇出下一個聚類中心。重復(fù)以上步驟直到選出K個聚類中心。在聚類階段，持續(xù)計算請求的位置向量到各聚類中心的距離并將請求劃分到最近的聚類中心所屬的類中，同時更新聚類中心的位置，直到新的聚類中心的位置不再改變。算法1的輸入為請求的位置向量的集合C和聚類數(shù)目K，輸出聚類結(jié)果M為各共乘請求所屬聚類，其中|M|=K，即輸出的聚類數(shù)目與K相等。

4.2 定價與匹配

當(dāng)執(zhí)行完算法1之后，所有的請求被劃分為K個類，隨后共乘平臺將尋找每個聚類內(nèi)乘客位置附近的車輛來參與共乘。請求總數(shù)目|R|與聚類數(shù)目K之間的關(guān)系如式(16)所示：

(16)

其中,λ表示平均每個聚類內(nèi)的請求數(shù)。

令Rk為第k個聚類中請求的集合，Vk為附近可匹配的車輛集合，則Rk與Vk的關(guān)系如式(17)和式(18)所示:

(17)

|Vk|≤|Rk|,1≤k≤K

原來這屆的社長要改選時，一共有七位大三的學(xué)長符合選舉資格，但沒有一位想當(dāng)社長，最后只好用猜拳決定，猜輸?shù)漠?dāng)社長。

(18)

具體地，式(17)表示乘客總數(shù)不多于車輛總座位數(shù)。若乘客總數(shù)多于車輛總座位數(shù)，則無論請求與車輛如何匹配，都將存在部分乘客無法被接載。這使得部分共乘請求雖然參與了共乘匹配，但其中的乘客又無法得到接載服務(wù)，導(dǎo)致該請求一直處于等待被響應(yīng)的狀態(tài)。式(18)表示參與共乘匹配車輛總數(shù)不多于請求總數(shù)。若車輛總數(shù)多于請求總數(shù)，則無論雙方如何匹配，總是存在部分車輛匹配失敗。這使得部分車輛雖然參與了共乘匹配，但又無法提供接載服務(wù)，導(dǎo)致該車輛一直處于等待被響應(yīng)的狀態(tài)。請求集合Rk與車輛集合Vk數(shù)目的比值ρk如式(19)所示:

(19)

即在請求數(shù)目|Rk|不變的前提下，車輛數(shù)目|Vk|越大，其對應(yīng)的比值ρk越小。

為了保證共乘中的公平性，本文設(shè)計了一個基于兩階段主從博弈的分布式定價與匹配算法DPMA來解決共乘的定價與匹配問題。

(20)

對任意vj∈Vk，如果其群組效用大于平均效用，即群組內(nèi)請求有一個相對較高的效用值，則車輛vj的價格調(diào)整策略如式(21)所示:

(21)

其中,pmax為pj取值的上限，μ為價格更新速度。對任意vj∈Vk，如果其群組效用小于平均效用，即群組內(nèi)請求有一個相對較低的效用值，則車輛vj的價格調(diào)整策略如式(22)所示:

(22)

其中,pmin為pj取值的下限。

在第二階段，即乘客與司機匹配階段，乘客根據(jù)司機價格的調(diào)整而改變所選的目標(biāo)車輛。首先驗證所有共乘請求ri∈Rk能否在滿足共乘費用、座位數(shù)和繞路距離約束的前提下與車輛vj∈Vk匹配，如果可行，則計算對應(yīng)的效用值，否則其對應(yīng)的效用值為0；隨后根據(jù)效用值由大到小對車輛排序，最終選定效用值最大的車輛v*作為共乘請求ri的目標(biāo)車輛，如式(23)所示:

(23)

以上兩個階段會持續(xù)迭代進行，直到同一聚類內(nèi)不同群組有相同的群組效用，此時的定價標(biāo)準(zhǔn)與車輛請求匹配關(guān)系為最終結(jié)果。

算法DPMA具體細節(jié)如算法2所示。

算法2分布式定價與匹配算法DPMA

輸入：共乘請求集合Rk，車輛集合Vk。

輸出：匹配結(jié)果Z。

1: 車輛初始化收費標(biāo)準(zhǔn)；

2:flag=1；

3:whileflagdo

4:Stage1:Pricing

6:forvj∈Vkdo

7: 更新車輛收費標(biāo)準(zhǔn)pj；

8:endfor

9:Stage2:Matching

10:forri∈Rkdo

11: 計算不同車輛下的效用值u(ri,vj),?vj∈Vk；

12: 更新zij,?j∈[1,|Vk|]；

13: 更新v*行駛路徑；

14:endfor

15:forvj∈Vkdo

16: 根據(jù)式(12)計算群組效用Uj；

17:endfor

18:ifUj==Uj′,?vj∈Vk,vj′∈Vk,j≠j′then

19:flag=0；

20:endif

21:endwhile

22:returnZ

由于任意兩個包含請求和車輛的元組并無交集，因此算法2可分布式執(zhí)行。

聚類與群組的關(guān)系如圖2所示，當(dāng)執(zhí)行完算法1之后，有相似位置向量的請求會被劃分到同一個聚類中，隨后對于同一聚類內(nèi)的共乘請求，算法2將分配到同一輛車的乘客視為一個群組。

Figure 2 Relationship between cluster and group圖2 聚類與群組的關(guān)系

定理1執(zhí)行算法DPMA后，公平指數(shù)會收斂至1。

證明根據(jù)算法DPMA第3～21行迭代過程中群組效用的變化，可將請求群組劃分為兩類，即效用增加的群組和效用減少的群組。將效用值增加的群組視為一個單一乘客，u1和u′1分別表示迭代前和迭代后的效用值，同時將效用值減少的群組視為一個單一乘客，u2和u′2分別表示迭代前和迭代后的效用值，其計算如式(24)～式(26)所示:

(24)

(25)

u′1-u′2=(1-t)(u1-u2)

(26)

其中，t=μ/M′。因此,以上公式可以進一步表示為式(27)：

(27)

其中,M′為乘客可接受價格的取值上限，μ為價格更新速度，兩者皆為常數(shù)。令q=(M′-μ)/M′，則q大于0且小于1，因此每輪迭代后u1與u2之差Δu可以視為一個公比為q的等比數(shù)列，如式(28)所示:

Δu′=q·Δu,0

(28)

其中,q為一輪迭代前后效用值之差的比值。由于0

□

定理2假設(shè)在同一時間間隙內(nèi)，請求的數(shù)目為m，車輛的數(shù)目為n，則算法DPMA的時間復(fù)雜度為O(mnlogn)。

證明算法DPMA包括兩個階段。第一階段主體部分由一個for循環(huán)構(gòu)成，循環(huán)的次數(shù)為車輛數(shù)目n，因此第一階段的時間復(fù)雜度為O(n)。第二階段每個請求需計算對應(yīng)每輛車的效用值，并根據(jù)效用值對車輛排序，即存在兩個嵌套的for循環(huán)及一個快速排序，其中排序操作位于外層循環(huán)之內(nèi)，與內(nèi)層循環(huán)同級，外層循環(huán)的次數(shù)為請求數(shù)目m，內(nèi)層循環(huán)的次數(shù)為車輛數(shù)目n，快速排序所包含元素個數(shù)為車輛數(shù)目n，因此第二階段的時間復(fù)雜度為O(m·(n+nlogn))=O(mnlogn)。由定理1的結(jié)論可知，算法DPMA第3～21行所需循環(huán)次數(shù)為常數(shù)，因此算法DPMA的時間復(fù)雜度為O(n)+O(mnlogn)=O(mnlogn)。

□

5 實驗與結(jié)果分析

5.1 實驗設(shè)置

5.1.1 數(shù)據(jù)集與實驗環(huán)境

實驗所用數(shù)據(jù)集為New York Green Taxi Trip Records[28]，該數(shù)據(jù)集包含2016年1月1日至1月31日紐約市綠色出租車接載乘客的信息，其中每條記錄包括乘客的上下車時間、起點經(jīng)緯度、終點經(jīng)緯度、乘客數(shù)目、車輛行駛距離和乘客支付費用等。本文實驗對該數(shù)據(jù)集進行預(yù)處理提取乘客信息，包括乘客的上下車時間、起點經(jīng)緯度、終點經(jīng)緯度和乘客數(shù)目。

本實驗使用Python語言，在搭載Windows 10操作系統(tǒng)、內(nèi)存為8 GB、處理器為Intel Core i7-6700 @ 3.40 GHz的計算機上執(zhí)行。為減小實驗誤差和避免實驗結(jié)果的偶然性，所有實驗結(jié)果均為20次實驗的平均值。

5.1.2 對比算法

基于現(xiàn)有的研究方法，本文設(shè)計了兩個對比算法，具體如下：

(1) BA[18]：BA算法為雙向匹配算法。在正式匹配之前，首先各共乘請求ri,?ri∈R根據(jù)自身起點位置和各車輛當(dāng)前所處位置，選擇距離自己最近的車輛v*作為目標(biāo)車輛；隨后從各車輛vj,?vj∈V角度出發(fā)，判斷車輛v*能否在滿足車上已有乘客和請求ri的費用約束、繞路距離約束和自身座位數(shù)約束下接送該乘客，如果各約束都能滿足，則由v*負責(zé)接送請求ri中的乘客，否則請求ri需等待下一次匹配。為了優(yōu)先服務(wù)更早發(fā)送共乘請求的乘客，本文設(shè)計的算法刪除了文獻[18]中的“替換”(即如果加入新乘客ri并替換車上已有乘客r*能提高整體效用，則用ri替換r*)步驟。

(2) Rank[14]：Rank算法分為兩個階段，分別是共乘請求打包階段和共乘請求分發(fā)階段。在共乘請求打包階段，每個請求ri會先選擇距離最近的車輛v′，并選擇一個包含請求自身且共乘比例(即共乘距離與車輛行駛總距離的比值)最大的請求集合packi作為目標(biāo)共乘伙伴，其中packi?R,ri∈packi,|packi|≤a′。在共乘請求分發(fā)階段，首先根據(jù)共乘比例的數(shù)值對各packi由大到小排序，隨后根據(jù)排序結(jié)果將頭元素pack*取出，將乘客集合pack*分配到其對應(yīng)車輛v*，并將pack*從排序列表中刪除，同時刪除列表中與pack*或車輛v*沖突的元素。隨后重復(fù)取出列表的頭元素，將其分配到對應(yīng)車輛，直到列表為空。文獻[14]為基于拍賣的匹配算法，其對各packi的排序依據(jù)為乘客可接受支付費用的最大值與實際支付費用之差。由于本文模型中只設(shè)定司機收費的上下限，對乘客不設(shè)定可接受費用的范圍，因此本文設(shè)計的算法將排序依據(jù)修改為各packi中乘客共乘距離與實際行駛距離的比值。

5.1.3 實驗參數(shù)與對比指標(biāo)

實驗1本實驗在小規(guī)模范圍內(nèi)驗證算法DPMA的收斂性。其中共乘請求集合為R={r1,r2,…,r6}，車輛集合為V={v1,v2}。實驗對比車輛v1與車輛v2收費變化及其對應(yīng)群組效用的變化，同時對比不同的車輛價格更新速度μ和效用函數(shù)中α1∶α2的比值對算法DPMA公平指數(shù)收斂性的影響。實驗參數(shù)設(shè)置如表2所示，其中黑體值為實驗?zāi)J參數(shù)值。為消除實驗環(huán)境及其他因素對實驗結(jié)果的影響，實驗1假設(shè)乘客所需的等待時長與車上已有乘客數(shù)目為線性關(guān)系。

Table 2 Parameters and their values in experiment 1表2 實驗1中參數(shù)及其設(shè)置

實驗2該實驗在大規(guī)模數(shù)據(jù)下針對多組不同的參數(shù)設(shè)置對DPMA、BA和Rank的實驗結(jié)果做對比。對比內(nèi)容包括改變請求的總數(shù)、平均每個聚類所包含的請求數(shù)、車輛的座位數(shù)和請求與車輛的數(shù)目比值，以及在不同參數(shù)設(shè)置下三個算法的Raj Jain’s公平指數(shù)變化和司機的收益率變化。其中司機的收益率為司機的實際收入與非共乘情況下收入的比值。實驗參數(shù)設(shè)置如表3所示，黑體值為實驗?zāi)J參數(shù)值。

Table 3 Parameters and their values in experiment 2表3 實驗2中參數(shù)及其設(shè)置

5.2 實驗結(jié)果及分析

由表2可知，初始時車輛1比車輛2收費低，并且離乘客群體更近，因此其對應(yīng)群組內(nèi)請求的效用值較高。而車輛2收費較高，并且離乘客群體較遠，因此其對應(yīng)群組內(nèi)請求的效用值較低。為了提高共乘的公平性，各車輛需要對價格進行調(diào)整，隨后重新進行車輛與請求的匹配。圖3展示了實驗1的實驗結(jié)果，包括迭代過程中相比非共乘車輛單位距離收費、群組效用和公平指數(shù)的變化。如圖3a和圖3b所示，經(jīng)過多輪迭代后各車輛的收費趨于穩(wěn)定，同時，兩輛車對應(yīng)的群組效用也趨于相同。圖3c實驗結(jié)果顯示，在不同的價格更新速度下，公平指數(shù)的收斂速度并不相同，價格更新速度越快，公平指數(shù)收斂得也越快。圖3d實驗結(jié)果顯示，在α1與α2的比值分別為1∶1.5，1∶1和1∶0.5的實驗中，公平指數(shù)都能以較快的速度收斂。但是，當(dāng)比值為1∶0.25時，公平指數(shù)收斂較慢，這是因為乘客支付費用占較低的權(quán)重導(dǎo)致群組效用的更新變慢，因此群組效用之差變化幅度較小。對于能較快收斂的情況，乘客支付費用所占比重越高，收斂速度越快，這是因為價格的更新與群組效用之差呈線性相關(guān)，更大的權(quán)重能更快縮小群組效用的差距，公平指數(shù)也因此收斂更快。由圖3c和圖3d實驗結(jié)果可以看出，DPMA算法能夠收斂，不同的參數(shù)設(shè)置下公平指數(shù)接近于1，即本文所設(shè)計的機制可以避免惡意價格競爭。

Figure 3 Convergence verification of DPMA圖3 算法DPMA收斂性驗證

圖4為DPMA、BA和Rank三種算法在公平指數(shù)上的對比。如圖4a和圖4b所示，在不同的乘客總數(shù)和車輛座位數(shù)下，DPMA算法和BA算法在公平指數(shù)上基本保持穩(wěn)定，前者公平指數(shù)保持在99.50%以上，后者公平指數(shù)保持在75.40%左右。而Rank算法則呈下跌趨勢，這是因為Rank算法采用打包多個請求并由單個車輛接送的匹配方式，容易出現(xiàn)部分車輛有較高的上座率而其他車輛上座率較低甚至為零的現(xiàn)象，導(dǎo)致匹配結(jié)果的公平性降低。由圖4c實驗結(jié)果可知，當(dāng)單個聚類內(nèi)乘客數(shù)目變化時，DPMA算法和Rank算法的公平指數(shù)基本保持穩(wěn)定；而BA算法則有明顯的下降趨勢，這是因為當(dāng)乘客數(shù)目增多時，乘客對目標(biāo)車輛的選擇存在更多差異，各群組效用之間的差異較大，導(dǎo)致公平指數(shù)降低。當(dāng)平均聚類大小從6增長到14時，BA算法在公平指數(shù)上下跌約12.00%。圖4d對比了三個算法在不同的請求與車輛數(shù)目比值下的公平指數(shù)變化。隨著比值的上升，公平指數(shù)都呈上升趨勢，這是因為在乘客數(shù)目不變的情況下，車輛總數(shù)的減少導(dǎo)致乘客可選擇車輛減少，乘客之間選擇的差異會減少，因此公平指數(shù)會呈上升趨勢。由實驗結(jié)果折線圖可知，本文提出的DPMA算法在公平指數(shù)上接近于1。

Figure 4 Fairness index under different parameter settings圖4 不同參數(shù)設(shè)置下的公平指數(shù)變化

圖5為DPMA、BA和Rank三種算法在司機收益率上的對比。如圖5a和圖5b所示，隨著乘客數(shù)目和請求車輛比值的增長，三個算法的司機收入都呈上漲的趨勢，這是因為當(dāng)共乘場景中存在更多的共乘請求時，司機有機會同時接送更多具有相似起點和終點的乘客，其中DPMA算法和Rank算法下的收益率分別比BA算法下的高出11.47%和11.77%。由圖5c可知,在不同的聚類大小下，司機的收益率在三個算法里均存在小幅度波動，其中DPMA算法和Rank算法分別保持在1.38和1.36左右，BA算法則呈現(xiàn)下降趨勢，但程度較小。這是因為在請求與車輛比值不變的前提下，車輛平均能同時接送的乘客數(shù)也為定值，因此司機收入不會有較大的波動。如圖5d所示，隨著車輛座位數(shù)的增長，司機的收入也保持增長，這是因為車輛有了更多的空間去接送更多乘客，然而由于車上乘客有繞路距離的約束，司機只能在保證已有乘客的約束能夠滿足的前提下才能為更多乘客提供服務(wù)，因此司機的收入不會隨著座位數(shù)的增長而無限上漲，而是最終趨于穩(wěn)定。

Figure 5 Surplus rate of drivers under different parameter settings圖5 不同參數(shù)設(shè)置下的司機收益率變化

結(jié)合圖4與圖5可知，本文提出的DPMA算法與Rank算法在司機收益率上基本相近，與BA算法相比則高出11.39%。在公平指數(shù)上,本文提出的DPMA算法分別比Rank算法和BA算法高出34.03%和24.42%，且基本保持在99.50%以上。

6 結(jié)束語

本文研究了共乘場景中的公平性問題，綜合考慮了乘車費用、車輛容量、等待時間和繞路距離等因素，提出了最大化匹配結(jié)果公平性的問題，并將共乘中的定價與匹配問題建模為一個面向公平保障的兩階段主從博弈。采用多屬性效用模型表示乘客效用值，并引入Raj Jain’s公平指數(shù)來衡量匹配結(jié)果的公平性。為縮小共乘匹配范圍，本文設(shè)計了一個基于K-means++的請求劃分算法。為保證共乘的公平性，設(shè)計了一個基于兩階段主從博弈的定價與匹配算法，并從理論上證明了其收斂性。在真實出租車數(shù)據(jù)集上與現(xiàn)有算法進行對比，實驗結(jié)果表明本文所提出的算法在公平指數(shù)上分別比Rank算法和BA算法高出34.03%和24.42%，公平指數(shù)接近于1。