基于圖約束聯(lián)盟形成的社會共享乘車問題

朱麗華，龍海俠

(1.安陽工學院 計算機科學與信息工程學院，河南 安陽 455000；2.海南師范大學 信息科學技術學院，海南 海口 571158)

0 引 言

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

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

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

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

1 GCCF問題及其求解

1.1 GCCF問題

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

(1)

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

(2)

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

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

(3)

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

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

(4)

因此，一個GCCF問題的目標就是識別CS*，即最有價值的聯(lián)盟結構

(5)

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

1.2 GCCF問題的求解

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

圖1 灰色邊收縮示例

下面將一個SSC問題建模為一個GCCF問題并進行求解。

2 SSC問題的建模及其求解

2.1 SSC問題模型

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

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

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

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

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

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

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

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

(6)

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

(7)

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

2.2 路徑的計算

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

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

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

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

(8)

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

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

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

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

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

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

2.3 SSC問題的求解

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

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

圖2 3個乘客的起點和目的地點

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

2.3.1 定界計算

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

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

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

(9)

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

(10)

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

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

(11)

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

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

2.3.2 近似解

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

3 實驗結果

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

3.1 算法性能評價目標及數(shù)據(jù)集

評價算法性能的主要目標有：①采用本文提出的共享乘車算法的社會福利改善；②從運行時間和可擴展性方面評價本文提出的最優(yōu)算法性能；③本文算法擴展到大量代理(即多達2000 個代理)時所能提供的近似性能和保證。

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

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

(12)

全部實驗都在考慮約束2(即司機總是開車)上進行，因為這樣可以模擬現(xiàn)實中的在線服務，例如滴滴打車、Lyft和Uber；每個實驗在20個隨機情形下重復進行。

3.2 社會福利的改善

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

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

(13)

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

圖3 社會福利的改善

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

3.3 最優(yōu)算法的運行時間和可擴展性

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

圖4 計算最優(yōu)解所需的運行時間

3.4 近似性能

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

圖5 解的近似比

4 結束語

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

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