朱麗華，龍海俠

(1.安陽工學(xué)院 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，河南 安陽 455000；2.海南師范大學(xué) 信息科學(xué)技術(shù)學(xué)院，海南 ?？?571158)

0 引 言

隨著社會(huì)經(jīng)濟(jì)的發(fā)展和人們工作節(jié)奏步伐的加快，實(shí)時(shí)共享乘車(俗稱拼車)正在迅速改變?nèi)藗兠刻焐舷掳嗤祷蚱渌顒?dòng)的交通出行方式。實(shí)時(shí)共享乘車最早起源于少數(shù)西方發(fā)達(dá)國家，然后迅速引進(jìn)到國內(nèi)。如美國著名的優(yōu)步(Uber)和來福車(Lyft)，以及國內(nèi)的滴滴、首約汽車和曹操出行等網(wǎng)約車公司。這種網(wǎng)約車公司的一個(gè)明顯特征是要建立一個(gè)用戶社區(qū)(或稱共同體)，其中上下班往返的人(或稱通勤者)可以對(duì)駕駛員/乘客進(jìn)行評(píng)分，然后利用這些信息自動(dòng)形成彼此了解/信任的通勤者群體，以降低相關(guān)的交通成本。本文將這個(gè)問題稱為社會(huì)共享乘車(social sharing by car，SSC)問題。

本文將SSC問題轉(zhuǎn)換為一個(gè)圖約束聯(lián)盟形成(graph constraint coalition formation，GCCF)問題，其中的通勤者(即乘客和司機(jī))組成聯(lián)盟(即加入一輛車)，以滿足由社交網(wǎng)絡(luò)施加的約束(即用戶更愿意與他們的朋友一起加入一輛車)。具體來說，根據(jù)關(guān)于GCCF的相關(guān)文獻(xiàn)[1,2]，只有當(dāng)參與這個(gè)聯(lián)盟的通勤者構(gòu)成社交網(wǎng)絡(luò)的一個(gè)連通子圖時(shí)，認(rèn)為一個(gè)聯(lián)盟是可行的。

近年來，有一些文獻(xiàn)針對(duì)SSC問題和GCCF問題進(jìn)行研究；文獻(xiàn)[3]將網(wǎng)約拼車匹配與路徑優(yōu)化問題考慮為靜態(tài)車輛路徑問題，構(gòu)建了網(wǎng)約拼車匹配與路徑優(yōu)化模型；文獻(xiàn)[4]提出了一種基于數(shù)據(jù)挖掘的城市上下班拼車線路優(yōu)化擬合的方法；文獻(xiàn)[5]研究了與拼車相關(guān)方面的計(jì)算，提出了一種模型來評(píng)價(jià)拼車計(jì)劃；文獻(xiàn)[6]分析了網(wǎng)約車服務(wù)流程及服務(wù)問題，并運(yùn)用服務(wù)藍(lán)圖描繪網(wǎng)絡(luò)約租車的全服務(wù)流程，而未就網(wǎng)約車服務(wù)建立一個(gè)定量化的數(shù)學(xué)模型；文獻(xiàn)[7]提出了一種出租車綜合推薦系統(tǒng)，設(shè)計(jì)了拼車情況下的費(fèi)用分?jǐn)倷C(jī)制和拼車決策，達(dá)到使出租車司機(jī)利潤提高和乘客的乘車費(fèi)用降低的目標(biāo)；與聯(lián)盟形成相關(guān)的優(yōu)化問題(即聯(lián)盟結(jié)構(gòu)生成)多年來也一直受研究人員所關(guān)注[8-10]，這些研究提供了一些最優(yōu)解技術(shù)且能夠提供質(zhì)量保證的近似算法。但都不考慮限制可行聯(lián)盟的圖約束，因此，不能應(yīng)用于GCCF問題；文獻(xiàn)[11]提出了一種稱為雙層蟻群優(yōu)化的隨機(jī)算法來處理面向任務(wù)的聯(lián)盟結(jié)構(gòu)問題；文獻(xiàn)[12]提出了各種聯(lián)盟結(jié)構(gòu)生成算法，以保證找到一個(gè)最優(yōu)的聯(lián)盟結(jié)構(gòu)，并提出了基于協(xié)同聯(lián)盟群的動(dòng)態(tài)規(guī)劃(synergy coalition group-based dynamic programming，SCGDP)算法，以保證一個(gè)最優(yōu)聯(lián)盟結(jié)構(gòu)和一個(gè)最小核心穩(wěn)定收益向量。但SCGDP算法要執(zhí)行必要的搜索操作，以保證在給定的特征函數(shù)博弈中找到聯(lián)盟，且這種方法效率的一個(gè)關(guān)鍵要素是尋找一個(gè)有效和高效的定界函數(shù)(也稱限界函數(shù)或邊界函數(shù)，即成長函數(shù)的上界)來剪枝搜索空間的重要部分的可能性。對(duì)于特定的特征函數(shù)來說，這樣的定界函數(shù)很容易得到，可以分解為單調(diào)和反單調(diào)函數(shù)之和(m+a)。但SSC問題不具有這樣的特性，因此本文針對(duì)文獻(xiàn)[12]中提出的BBA算法進(jìn)行擴(kuò)展后作為本文SSC問題的求解技術(shù)，以便為大規(guī)模系統(tǒng)(例如多達(dá)2000個(gè)代理)提供解決方案。

本文首先提出了SSC優(yōu)化問題的GCCF的定量化形式，然后將一個(gè)社會(huì)共享乘車問題轉(zhuǎn)化為一個(gè)受社交網(wǎng)絡(luò)約束的圖約束聯(lián)盟形成問題，從而建立起一個(gè)社會(huì)共享乘車問題模型，通過分析得到該問題模型的最佳聯(lián)盟結(jié)構(gòu)以及最優(yōu)路徑的計(jì)算，進(jìn)而采用一種改進(jìn)的分支定界方法來求解這個(gè)社會(huì)共享乘車問題，從而使得該系統(tǒng)的社會(huì)福利最大化。實(shí)驗(yàn)結(jié)果表明，本文的算法模型不僅可以改善社會(huì)福利，降低整個(gè)系統(tǒng)的成本，還能夠?yàn)橹械纫?guī)模的系統(tǒng)快速高效地獲得最優(yōu)解且為大規(guī)模的系統(tǒng)獲得質(zhì)量保證的近似解。

1 GCCF問題及其求解

1.1 GCCF問題

聯(lián)盟博弈或特征函數(shù)博弈由一組有限的玩家A和一個(gè)特征函數(shù)v：2A→R構(gòu)成，特征函數(shù)將每個(gè)聯(lián)盟C∈2A映射為它的值，這個(gè)值描述一組玩家通過形成一個(gè)聯(lián)盟可以獲得多少共同的收益；一個(gè)聯(lián)盟結(jié)構(gòu)(coalition structure，CS)是將一組代理劃分為不相交的聯(lián)盟，全部聯(lián)盟結(jié)構(gòu)的集合為∏(A)。一個(gè)聯(lián)盟結(jié)構(gòu)CS的價(jià)值確定為其構(gòu)成聯(lián)盟的價(jià)值之和，即

(1)

聯(lián)盟形成問題(或聯(lián)盟結(jié)構(gòu)生成問題)以聯(lián)盟博弈作為輸入，目標(biāo)是確定最有價(jià)值的聯(lián)盟結(jié)構(gòu)CS*，即

(2)

現(xiàn)在，給定一個(gè)圖G=(A,E)，其中E?A×A是代理之間的邊集，表示它們之間的關(guān)系，文獻(xiàn)[1]認(rèn)為，如果由一個(gè)聯(lián)盟C所導(dǎo)出的G的子圖中的全部成員都是連通的，就說一個(gè)聯(lián)盟C是可行的，也就是說，如果對(duì)于來自a,b∈C的每一對(duì)玩家，在G中有一條不離開C就連接它們的路徑。給定一個(gè)圖G，可行的聯(lián)盟集合為

FC(G)={C?A|C在G上導(dǎo)出的子圖是連通的}

(3)

因此，圖約束聯(lián)盟形成博弈就是一個(gè)與圖G一起的聯(lián)盟博弈，如果C∈FC(G)，則聯(lián)盟C就認(rèn)為是可行的。在GCCF博弈中，如果每個(gè)聯(lián)盟都是可行的，則聯(lián)盟結(jié)構(gòu)CS就認(rèn)為是可行的，即

CS(G)={CS∈∏(A)|CS?FC(G)}

(4)

因此，一個(gè)GCCF問題的目標(biāo)就是識(shí)別CS*，即最有價(jià)值的聯(lián)盟結(jié)構(gòu)

(5)

在定義了GCCF問題的基礎(chǔ)上，下面給出求解GCCF問題的算法。

1.2 GCCF問題的求解

BBA是基于圖G上的邊收縮的概念，它表示與其事件頂點(diǎn)相關(guān)聯(lián)的聯(lián)盟的合并。這種操作可用于生成整個(gè)搜索空間CS(G)并將其組織為一個(gè)根樹TG，根樹TG可以以多項(xiàng)式存儲(chǔ)需求遍歷，以找到最優(yōu)解。每個(gè)可行的聯(lián)盟結(jié)構(gòu)CS∈CS(G)僅用2色圖GC表示一次，即每個(gè)TG節(jié)點(diǎn)一次，其中GC的節(jié)點(diǎn)代表CS的聯(lián)盟，且邊被標(biāo)記為灰色(這種邊仍然可以收縮)或黑色(意味之前的邊收縮已經(jīng)完成)，而且其端點(diǎn)不能在算法的以下階段中處于相同的聯(lián)盟中。圖1(a)所示為一個(gè)2-色圖的示例，圖1(b)為收縮后的結(jié)構(gòu)，其中邊({A},{B})為黑色，因此，在算法的任何后續(xù)步驟中，都不可能收縮它。這個(gè)標(biāo)記確保每個(gè)可行的聯(lián)盟結(jié)構(gòu)用TG表示而沒有任何冗余。具體來說，給定一個(gè)表示可行的聯(lián)盟結(jié)構(gòu)CS的節(jié)點(diǎn)TG，對(duì)其子節(jié)點(diǎn)在相應(yīng)的2-色圖GC中收縮每個(gè)灰色節(jié)點(diǎn)進(jìn)行評(píng)估，將根在CS的TG的子樹稱為ST(CS)。

圖1 灰色邊收縮示例

下面將一個(gè)SSC問題建模為一個(gè)GCCF問題并進(jìn)行求解。

2 SSC問題的建模及其求解

2.1 SSC問題模型

本節(jié)來定義SSC問題模型?？紤]一組乘客R={r1,…,rR}，其中R>0為總的乘客數(shù)，非空司機(jī)(駕駛員)集合D?R，D包括擁有一輛私家車的乘客，也把D稱為代理。每個(gè)司機(jī)ri∈D都可以在他的車?yán)锝蛹{s(ri)個(gè)乘客(包括他自己在內(nèi))，其中函數(shù)s:R→N0給出每個(gè)車的座位數(shù)。如果ri?D，則s(ri)=0。給定一組乘客C?R，如果下列約束成立，則稱C是有效的。

約束1:|C|>1??ri∈C:s(ri)≥|C|，即對(duì)于全部乘客來說，至少有一個(gè)乘客有一輛有足夠座位的汽車。

注意，這種約束允許一個(gè)乘客ri?D可以是“單獨(dú)的”，即如果可供使用的座位總數(shù)少于系統(tǒng)中的乘客總數(shù)，則這樣的乘客可能需要使用付費(fèi)的公共交通工具，支付車票的費(fèi)用為k({ri})。定義函數(shù)k:R0→R-給出這種成本，其中R0={{ri}|ri∈R-D}是除司機(jī)外的全部“單獨(dú)的”集合，因?yàn)榧僭O(shè)這樣的乘客總是更愿意使用公共交通工具。

現(xiàn)今，在幾個(gè)拼車在線服務(wù)(例如滴滴、Lyft和Uber)中，通勤者可以聲明他是否是司機(jī)或乘客，因此這兩個(gè)集合是不相交的，而且一個(gè)有效的乘客集合C最多包含一個(gè)司機(jī)。因此，下列附加約束必須成立：

約束2:|C∩D|≤1，即每輛汽車的司機(jī)數(shù)目最多可為一人。

注意，盡管約束2是可選的，但它適用于目前的實(shí)際情況。盡管如此，由于本文的方法支持更一般的模型，所以也可以應(yīng)用于這種約束不成立的情況。

考慮SSC問題發(fā)生中的地理環(huán)境的地圖，用一個(gè)連通圖M=(P,Q)來表示，其中P是地圖的地理位置點(diǎn)的集合，Q是這些點(diǎn)之間的邊的集合(每條邊與一個(gè)正的權(quán)值關(guān)聯(lián))。在下文中，我們假設(shè)通過n個(gè)點(diǎn)的一條路徑表示為一個(gè)元組P∈Pn，Pi表示在這樣的一個(gè)元組中的第i個(gè)點(diǎn)。

根據(jù)文獻(xiàn)[5]，將有效乘客集合C的總成本v(C)定義為

(6)

式中：PC是C的最優(yōu)路徑，且t：Pn→R-，c：Pn→R-和f：Pn→R-為負(fù)的成本函數(shù)(由于本文考慮的是一個(gè)最大化問題，故將成本表示為負(fù)值，也可以表示為正值)，分別表示駛過一條給定路徑的時(shí)間成本、認(rèn)知成本(根據(jù)文獻(xiàn)[5]，這個(gè)成本代表了司機(jī)在行駛途中所遭受的疲勞)和燃油成本。將這3個(gè)成本函數(shù)的總和表示為cost(·)。注意，如果C∩D=?，則約束1規(guī)定，C由沒有汽車的單個(gè)乘客構(gòu)成，因此其成本用k(·)表示。此外，PC定義如下

(7)

如前所述，共享乘車的一個(gè)關(guān)鍵方面是社交網(wǎng)絡(luò)G的存在，它限制了群體的形成。因此，SSC模型既考慮了關(guān)于可行聯(lián)盟的定義，又將有效的座位集合定義為不違背約束1且其成員在G上導(dǎo)出一個(gè)連通子圖的集合。這樣，就把SSC問題轉(zhuǎn)化為了一個(gè)GCCF問題，因?yàn)槊總€(gè)有效的乘客集合確實(shí)是一個(gè)聯(lián)盟，而且v(·)給出了其聯(lián)盟值。因此，CS*表示系統(tǒng)的最佳聯(lián)盟結(jié)構(gòu)，這種結(jié)構(gòu)使得該系統(tǒng)的社會(huì)福利最大化(即總成本最小化)。然而，式(7)中的最優(yōu)路徑PC的計(jì)算是一個(gè)較難的問題，下節(jié)將闡明如何對(duì)成本函數(shù)進(jìn)行合理假設(shè)來降低這種復(fù)雜性，從而使這種計(jì)算變得容易處理。

2.2 路徑的計(jì)算

式(7)的計(jì)算復(fù)雜性來自于對(duì)成本函數(shù)t(·)、c(·)和f(·)的假設(shè)的缺失。然而，在許多城市道路中，汽車駛過一條路徑(線路)的成本依賴于路徑本身的長度，更長的路徑通常會(huì)導(dǎo)致更高的成本。因此，假設(shè)t(·)、c(·)和f(·)為反單調(diào)函數(shù)，即假設(shè)兩條路徑Pi和Pj，如果Pi的長度大于Pj的長度，則t(Pi)

命題1 如果t(·)、c(·)和f(·)是反單調(diào)函數(shù)，則對(duì)于乘客集合C的最優(yōu)路徑PC就是最短路徑Pi∈VP(C)。

證明：因?yàn)閠(·)、c(·)和f(·)是反單調(diào)函數(shù)，則t(·)+c(·)+f(·)也是反單調(diào)函數(shù)，故命題顯然成立。

給定一條路徑P∈Pn，則把函數(shù)best:Pn→Pm定義為

(8)

式中：函數(shù)sp(·)給出了兩點(diǎn)之間的最短路徑，⊕表示元組的級(jí)聯(lián)，m表示所有這些級(jí)聯(lián)產(chǎn)生的點(diǎn)的數(shù)目。如果sp(·)采用Dijkstra算法實(shí)現(xiàn)，則函數(shù)best(·)可以在O((n-1)·(|Q|+(|P|log|P|)))計(jì)算完成。此外，如果M是一個(gè)歐幾里德圖，則sp(·)可以采用A*算法在O((n-1)·|Q|)內(nèi)計(jì)算完成。

命題2 給定點(diǎn)的一個(gè)元組T，則best(T)是按順序通過這些點(diǎn)的最短路徑。

證明：用反證法。假設(shè)存在一條路徑P′按順序通過T的全部點(diǎn)，且P′比best(T)短，這樣，T中必然存在兩個(gè)連續(xù)點(diǎn)，即pi和pj，使得P′的從pi到pj的子路徑比best(T)的從pi到pj的子路徑短，這顯然是矛盾的，因?yàn)樗`背了best(T)的定義。

最后，給定乘客集合C，我們將VT(C)定義為元組的集合，該集合包含且僅包含其乘客的全部起點(diǎn)和目的地點(diǎn)(沒有重復(fù))，并且滿足約束3和約束4。在此基礎(chǔ)上，提出以下定理：

定理1給出了一種有效的算法來計(jì)算一組乘客的最優(yōu)路徑，假設(shè)成本函數(shù)是反單調(diào)的。其搜索空間是VT(C)，其大小明顯小于式(7)的VP(C)，即|C|、|VT(C)|對(duì)于合理規(guī)模的乘客群體來說是可控的。實(shí)際上，對(duì)于|C|=5(即平均一輛汽車的座位數(shù))，它僅為2520。

在下一節(jié)，我們將詳細(xì)討論如何將CFSS算法應(yīng)用于解決上述定義的問題。

2.3 SSC問題的求解

為了求解SSC問題，必須將原始的BBA算法進(jìn)行改進(jìn)，以滿足2.1中引入的附加約束。具體來說，為了保證約束1和約束2成立，必須避免形成無效的乘客集合聯(lián)盟。這可以通過避免綠色邊的收縮來實(shí)現(xiàn)，因?yàn)榫G色邊的收縮將導(dǎo)致違背這些約束。因此，這樣的邊必須用紅色標(biāo)記，即使沒有訪問相應(yīng)的子樹。事實(shí)上，這相當(dāng)于遍歷這樣的搜索空間并丟棄它們可能包含的任何可能解，因?yàn)檫@樣的解將違背上述約束之一。

提高BBA效率的關(guān)鍵是采用分支和定界搜索策略來剪枝搜索空間的有效部分。文獻(xiàn)[12]針對(duì)一類特殊的特征函數(shù)即m+a函數(shù)提出了一種通用的定界技術(shù)。但式(6)定義的特征函數(shù)不是一個(gè)m+a函數(shù)，因?yàn)樗蕾囉赑C，特別是依賴于乘客的起點(diǎn)和目的地點(diǎn)的實(shí)際位置。作為一個(gè)示例，圖2所示為3個(gè)乘客的起點(diǎn)和目的地點(diǎn)，即R={r1,r2,r3}，其中只有r1擁有一輛自己的汽車，即D={r1}。為簡化起見，假設(shè)v(C)等于PC的長度，且k({r2})=k({r3})=-1。

圖2 3個(gè)乘客的起點(diǎn)和目的地點(diǎn)

下面提出可以在本文的共享乘車場景中使用的替代定界技術(shù)。

2.3.1 定界計(jì)算

在搜索樹中，給定一個(gè)可行的聯(lián)盟結(jié)構(gòu)CS，現(xiàn)在來給出如何計(jì)算由ST(CS)中的特征函數(shù)所假定的值的上界M(CS)，即M(CS)≥V(CSi)?CSi∈ST(CS)。這個(gè)值可用于避免訪問ST(CS)，如果M(CS)不大于當(dāng)前的最好解。

首先，提出一種方法來計(jì)算在約束2成立情況下的M(CS)。在這些情況下，不可能合并兩個(gè)包含司機(jī)的聯(lián)盟，因?yàn)橹挥胁粨碛衅嚨膯蝹€(gè)乘客才允許加入到現(xiàn)有的組。注意，如果考慮反單調(diào)的成本函數(shù)，則增加一個(gè)乘客到一輛車只會(huì)帶來更大的成本，因此，全部車輛(即所有包含司機(jī)的聯(lián)盟)的成本之和僅在增加乘客之后才能增加，更一般地，如果cost(·)是一個(gè)反單調(diào)函數(shù)且約束2成立，則

M(CS)=∑C∈Rd(CS)v(C)

(9)

式中：Rd(CS)={C∈CS|C∩D≠?}。

(10)

現(xiàn)在可以提出以下命題：

命題3 如果cost(·)是一個(gè)反單調(diào)函數(shù)，則

(11)

證明：這個(gè)證明可以從三角形不等式的旅行商問題即TSP問題(traveling salesman problem，TSP)的界的證明中得到[13,14]。

上述結(jié)果能夠確定ST(CS)中的所有聯(lián)盟結(jié)構(gòu)的界V(·)，也可以用來計(jì)算具有質(zhì)量保證的近似解。

2.3.2 近似解

上一節(jié)描述的定界技術(shù)允許對(duì)搜索空間的有效部分進(jìn)行剪枝，從而為中等規(guī)模的系統(tǒng)(如多達(dá)100個(gè)代理)提供最優(yōu)解。然而，實(shí)際的應(yīng)用可能涉及數(shù)千個(gè)代理的共同體，且遵循實(shí)時(shí)拼車的概念，因此系統(tǒng)應(yīng)該能夠在短時(shí)間內(nèi)提供解決方案，即對(duì)于實(shí)際應(yīng)用來說，必須考慮近似解。上一節(jié)討論的定界技術(shù)可以用來實(shí)現(xiàn)近似的SSC問題。具體而言，就是在一段時(shí)間ts后，停止搜索過程，并計(jì)算搜索樹的全部葉子結(jié)構(gòu)的界M(CS)，這些值中的最大值就是在ts中找到的近似解的一個(gè)容許界。

3 實(shí)驗(yàn)結(jié)果

為了對(duì)本文所提出算法的有效性進(jìn)行驗(yàn)證，軟件上采用C++語言并結(jié)合Matlab7.0，硬件在Pentium IV 2.0 GHz(512 M內(nèi)存)的PC機(jī)和Windows XP操作系統(tǒng)環(huán)境下完成。

3.1 算法性能評(píng)價(jià)目標(biāo)及數(shù)據(jù)集

評(píng)價(jià)算法性能的主要目標(biāo)有：①采用本文提出的共享乘車算法的社會(huì)福利改善；②從運(yùn)行時(shí)間和可擴(kuò)展性方面評(píng)價(jià)本文提出的最優(yōu)算法性能；③本文算法擴(kuò)展到大量代理(即多達(dá)2000 個(gè)代理)時(shí)所能提供的近似性能和保證。

實(shí)驗(yàn)采用真實(shí)的數(shù)據(jù)集，包括空間數(shù)據(jù)和社會(huì)數(shù)據(jù)。具體而言，采用的地圖M=(P,Q)是北京城市的真實(shí)寫照，其中|P|=8330個(gè)點(diǎn)，|Q|=13290條邊，相當(dāng)于每10 m一個(gè)點(diǎn)的平均分辨率。這個(gè)地圖是從微軟提供的地球生命(GeoLife)[15]數(shù)據(jù)集得到的，它包括17 621個(gè)軌跡，總距離約為120萬km，由具有多種采樣率的不同GPS記錄器和GPS電話記錄得到。在實(shí)驗(yàn)中，還將這個(gè)軌跡池用來對(duì)隨機(jī)路徑進(jìn)行采樣，以用于提供乘客的起點(diǎn)和目的地點(diǎn)；此外，在每個(gè)實(shí)驗(yàn)中，圖G是Twitter社交圖大爬行的子圖，之所以采用Twitter數(shù)據(jù)集，是因?yàn)樗敲赓M(fèi)提供的，不受隱私限制(不像Facebook)。具體而言，G是通過一個(gè)標(biāo)準(zhǔn)算法[16]從一個(gè)較大的圖中提取一個(gè)子圖得到，即從整個(gè)圖的一個(gè)隨機(jī)節(jié)點(diǎn)開始遍歷，然后將每個(gè)節(jié)點(diǎn)和對(duì)應(yīng)的弧添加到G中，直至得到所需的節(jié)點(diǎn)數(shù)為止。

一方面，由于司機(jī)是少數(shù)，且在城市環(huán)境中很少存在疲勞駕駛，故其認(rèn)知成本可以不加考慮；另一方面，由于全部拼車乘客的時(shí)間都是預(yù)先計(jì)劃好的，且整個(gè)時(shí)間的長短決定了路徑的長短，從而直接影響汽車的燃料費(fèi)用，故在實(shí)驗(yàn)中，為簡化起見，采用一個(gè)僅慮燃料費(fèi)用的成本模型，即

(12)

全部實(shí)驗(yàn)都在考慮約束2(即司機(jī)總是開車)上進(jìn)行，因?yàn)檫@樣可以模擬現(xiàn)實(shí)中的在線服務(wù)，例如滴滴打車、Lyft和Uber；每個(gè)實(shí)驗(yàn)在20個(gè)隨機(jī)情形下重復(fù)進(jìn)行。

3.2 社會(huì)福利的改善

社會(huì)福利的改善是基于每個(gè)乘客采用各自的交通工具(即不拼車)方案相比時(shí)社會(huì)福利的改善(即整個(gè)系統(tǒng)的成本減少)，這可以表明在采用本文的拼車算法時(shí)，整個(gè)用戶社區(qū)(共同體)可以獲得的收益。具體來說，將社會(huì)福利改善定義為

100·|[V(CS*)-V(R0)]/V(R0)|

(13)

式中：V(CS*)為采用本文拼車算法時(shí)獲得最優(yōu)解時(shí)的成本，V(R0)為每個(gè)乘客采用各自的交通工具(即不拼車)方案時(shí)的成本。福利改善的程度受系統(tǒng)中司機(jī)所占百分比(即代理|D|)的影響，因?yàn)檫@決定了可供使用的座位數(shù)量，以及在不需要采用公共交通工具的情況下，可以共享汽車的乘客數(shù)量。圖3所示為得到的實(shí)驗(yàn)結(jié)果。從圖3可見，一方面，隨著更多司機(jī)的出現(xiàn)，一個(gè)乘客更有可能加入一輛其路徑更接近他/她的車，所以社會(huì)福利的改善會(huì)隨之而增加。如當(dāng)總的乘客只有10%擁有車(即司機(jī)百分比|D|=10%)時(shí)，平均成本減少是23.5%，當(dāng)有半數(shù)的乘客擁有汽車(即司機(jī)百分比|D|=50%)時(shí)，平均成本減少達(dá)到36.3%；另一方面，如果大多數(shù)乘客擁有自己的汽車，如司機(jī)百分比超過80%時(shí)，那么共享拼車就不是很有效了，這時(shí)社會(huì)福利的改善反而減少，因?yàn)闆]有車的乘客數(shù)量大大減少，他們可以從與有車的司機(jī)共享他們的通勤中獲益。

圖3 社會(huì)福利的改善

為了進(jìn)一步表明本文算法的有效性，將它與文獻(xiàn)[12]的算法和一個(gè)典型的貪婪算法相比較。盡管文獻(xiàn)[12]考慮了協(xié)同圖上的聯(lián)盟結(jié)構(gòu)生成和分支定界，但這種算法必須要尋找一個(gè)有效和高效的定界函數(shù)來剪枝搜索空間的重要部分。對(duì)于特定的特征函數(shù)來說，這樣的定界函數(shù)很容易得到，而SSC問題不具有這樣的特性；在貪婪算法中，每個(gè)司機(jī)都選擇它的下一站作為它的當(dāng)前乘客的目的地點(diǎn)和剩余乘客的起點(diǎn)之間的最近點(diǎn)。這個(gè)選擇考慮了社交網(wǎng)絡(luò)的制約，避免了不可行聯(lián)盟的形成。3種算法的結(jié)果如圖3所示，可見，無論司機(jī)百分比|D|處于較低還是較高時(shí)，本文算法獲得的社會(huì)福利的改善始終高于文獻(xiàn)[12]的算法和貪婪算法。特別是當(dāng)大多數(shù)乘客擁有自己的車時(shí)，文獻(xiàn)[12]的算法和貪婪算法得到的解的成本比本文的算法要高，所以社會(huì)福利的改善下降更多。只有很少的乘客不擁有自己的車的情況下，文獻(xiàn)[12]的算法和貪婪算法表現(xiàn)稍好，因?yàn)樗赡軙?huì)在考慮最優(yōu)的聯(lián)盟之前將一名乘客分配給一個(gè)次優(yōu)的聯(lián)盟。

3.3 最優(yōu)算法的運(yùn)行時(shí)間和可擴(kuò)展性

圖4所示為當(dāng)代理數(shù)量|D|從30增加到100時(shí)采用本文算法和文獻(xiàn)[12]算法計(jì)算最優(yōu)解所需要的運(yùn)行時(shí)間。在3種情形下對(duì)算法進(jìn)行了測(cè)試，即在低(|D|=10%)、中(|D|=50%)和高(|D|=80%)的司機(jī)百分比下。從圖4可以看到，該參數(shù)對(duì)兩種算法的性能都有明顯影響。事實(shí)上，搜索空間的大小取決于可用的座位數(shù)量(即搜索空間在可用的座位數(shù)量百分比較低時(shí)減小)，以及沒有自己的汽車而能夠從共享他們的通勤中受益的乘客人數(shù)(即搜索空間當(dāng)大多數(shù)代理擁有自己的汽車時(shí)減小)，這與3.2得到的社會(huì)福利改善的結(jié)果是一致的。由于在任何情況下，本文算法都可以在合理的時(shí)間內(nèi)解決有100個(gè)代理的系統(tǒng)，如在|D|=50%的情況下最多大約2 h，這個(gè)運(yùn)行時(shí)間適用于一天前或一周前請(qǐng)求的服務(wù)(例如滴滴和Lyft)。且由于本文的定界技術(shù)允許剪枝搜索空間的有效部分，所以本文算法的性能不但是合理的，而且相比于文獻(xiàn)[12]的算法，在獲得最優(yōu)解時(shí)所需要的運(yùn)行時(shí)間始終小于文獻(xiàn)[12]的算法。

圖4 計(jì)算最優(yōu)解所需的運(yùn)行時(shí)間

3.4 近似性能

圖5所示為當(dāng)本文方法用于求解|R|∈{500,1000,2000}的大型系統(tǒng)時(shí)得到的近似比(即上界值與近似解的比值)。具體來說，當(dāng)采用2.3節(jié)描述的近似技術(shù)時(shí)，在ts=100s后停止搜索樹的遍歷。實(shí)驗(yàn)結(jié)果表明，對(duì)于|R|=500和|D|=80%來說，所得到的上界僅比在限定時(shí)間內(nèi)得到的解高6.7%，而當(dāng)|R|=2000和|D|=50%時(shí)，其最大值為41%，即在最壞的情況下，得到的近似比為1.41，因此這個(gè)解至少為最優(yōu)解的71%。

圖5 解的近似比

4 結(jié)束語

本文對(duì)社會(huì)共享乘車(俗稱拼車)問題進(jìn)行了研究，首先將其建模為一個(gè)GCCF問題，并針對(duì)GCCF擴(kuò)展了一種BBA算法來求解這個(gè)問題。實(shí)證評(píng)價(jià)表明，本文的拼車算法不僅可以改善社會(huì)福利，降低整個(gè)系統(tǒng)的成本，而且還可以計(jì)算出具有良好質(zhì)量保證(即在最壞情況下近似比為1.41)的大型系統(tǒng)(即多達(dá)2000 個(gè)代理)的解，因此適合于實(shí)際應(yīng)用。

未來的研究將著眼于擴(kuò)展本文的算法模型，包括采用交通信息、乘客時(shí)間約束以及多跳拼車[17]的更復(fù)雜的線路情形。