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

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

1 引言

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

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

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

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

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

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

2 系統(tǒng)模型

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

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

表1 符號(hào)及含義

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

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

(1)

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

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

(2)

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

(3)

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

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

(4)

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

3 司機(jī)與乘客的主從博弈

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

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

3.1 乘客屬性

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

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

(5)

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

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

(6)

(7)

(8)

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

(9)

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

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

3.2 司機(jī)屬性

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

pmin≤pj≤pmax,1≤j≤n

(10)

(11)

其中,ωj為共乘場(chǎng)景下車輛vj向每位乘客收取的單位距離費(fèi)用，li表示請(qǐng)求ri的起點(diǎn)到終點(diǎn)的距離。

3.3 求解目標(biāo)

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

(12)

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

(13)

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

OBJ: maxJ(G)

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

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

4 算法

4.1 請(qǐng)求劃分

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

算法1請(qǐng)求劃分算法CR

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

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

1:隨機(jī)選擇一個(gè)請(qǐng)求作為初始聚類中心q1；

2:repeat

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

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

5: 按照輪盤(pán)法選擇下一個(gè)聚類中心；

6:until選出K個(gè)聚類中心;

7:repeat

8:forci∈Cdo

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

10: 更新ci所屬聚類Mi；

11:endfor

12:fork=1 toK

13: 計(jì)算新的聚類中心位置Qk；

14:endfor

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

16:returnM

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

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

(14)

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

(15)

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

4.2 定價(jià)與匹配

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

(16)

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

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

(17)

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

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

(18)

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

(19)

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

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

(20)

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

(21)

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

(22)

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

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

(23)

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

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

算法2分布式定價(jià)與匹配算法DPMA

輸入：共乘請(qǐng)求集合Rk，車輛集合Vk。

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

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

2:flag=1；

3:whileflagdo

4:Stage1:Pricing

6:forvj∈Vkdo

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

8:endfor

9:Stage2:Matching

10:forri∈Rkdo

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

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

13: 更新v*行駛路徑；

14:endfor

15:forvj∈Vkdo

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

17:endfor

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

19:flag=0；

20:endif

21:endwhile

22:returnZ

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

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

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

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

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

(24)

(25)

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

(26)

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

(27)

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

Δu′=q·Δu,0

(28)

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

□

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

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

□

5 實(shí)驗(yàn)與結(jié)果分析

5.1 實(shí)驗(yàn)設(shè)置

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

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

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

5.1.2 對(duì)比算法

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

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

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

5.1.3 實(shí)驗(yàn)參數(shù)與對(duì)比指標(biāo)

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果及分析

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

Figure 3 Convergence verification of DPMA圖3 算法DPMA收斂性驗(yàn)證

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

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

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

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

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

6 結(jié)束語(yǔ)

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