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

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

(廣東工業大學計算機學院，廣東 廣州 510006)

1 引言

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

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

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

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

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

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

2 系統模型

在共乘匹配模型中存在著乘客和司機2種角色，共乘平臺負責兩者之間的匹配。如圖1所示，首先乘客向共乘平臺發送請求，請求內容包括起點、終點和請求所包含的乘客數等必要信息。此外，車輛向共乘平臺發送自己當前所處的位置和收費信息。最后共乘平臺根據雙方提供的相關信息進行匹配。令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分別表示該請求的起點、請求的終點、請求所包含乘客數和請求可接受的繞路比例。令vj=(oj,aj),vj∈V表示第j輛車，1≤j≤n,其中oj和aj分別表示該車的當前位置和可提供的座位數。本文涉及的其它符號及其含義如表1所示。

Figure 1 System model圖1 系統模型

表1 符號及含義

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

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

3 司機與乘客的主從博弈

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

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

3.1 乘客屬性

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

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

(5)

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

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

(6)

(7)

(8)

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

(9)

其中α1和α2分別表示時間效用和費用效用的權重。

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

3.2 司機屬性

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

pmin≤pj≤pmax,1≤j≤n

(10)

(11)

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

3.3 求解目標

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

(12)

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

(13)

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

OBJ: maxJ(G)

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

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

4 算法

4.1 請求劃分

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

算法1請求劃分算法CR

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

輸出：聚類結果M。

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

2:repeat

3: 計算各向量ci∈C到當前已有聚類中心之間的最短距離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(ci)，如式(14)所示:

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

(14)

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

(15)

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

4.2 定價與匹配

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

(16)

其中,λ表示平均每個聚類內的請求數。

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

(17)

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

原來這屆的社長要改選時，一共有七位大三的學長符合選舉資格，但沒有一位想當社長，最后只好用猜拳決定，猜輸的當社長。

(18)

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

(19)

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

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

(20)

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

(21)

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

(22)

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

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

(23)

以上兩個階段會持續迭代進行，直到同一聚類內不同群組有相同的群組效用，此時的定價標準與車輛請求匹配關系為最終結果。

算法DPMA具體細節如算法2所示。

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

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

輸出：匹配結果Z。

1: 車輛初始化收費標準；

2:flag=1；

3:whileflagdo

4:Stage1:Pricing

6:forvj∈Vkdo

7: 更新車輛收費標準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: 根據式(12)計算群組效用Uj；

17:endfor

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

19:flag=0；

20:endif

21:endwhile

22:returnZ

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

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

Figure 2 Relationship between cluster and group圖2 聚類與群組的關系

定理1執行算法DPMA后，公平指數會收斂至1。

證明根據算法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′為乘客可接受價格的取值上限，μ為價格更新速度，兩者皆為常數。令q=(M′-μ)/M′，則q大于0且小于1，因此每輪迭代后u1與u2之差Δu可以視為一個公比為q的等比數列，如式(28)所示:

Δu′=q·Δu,0

(28)

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

□

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

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

□

5 實驗與結果分析

5.1 實驗設置

5.1.1 數據集與實驗環境

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

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

5.1.2 對比算法

基于現有的研究方法，本文設計了兩個對比算法，具體如下：

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

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

5.1.3 實驗參數與對比指標

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

Table 2 Parameters and their values in experiment 1表2 實驗1中參數及其設置

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

Table 3 Parameters and their values in experiment 2表3 實驗2中參數及其設置

5.2 實驗結果及分析

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

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

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

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

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

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

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

6 結束語

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