大數據背景下動態共乘的研究進展

沈弼龍 趙 穎 黃 艷 鄭緯民

1(清華大學計算機科學與技術系 北京 100084)2 (北德克薩斯州大學計算機科學與工程系 美國德克薩斯州登頓市 311277)(shenbilong@gmail.com)

大數據背景下動態共乘的研究進展

沈弼龍1趙 穎1黃 艷2鄭緯民1

1(清華大學計算機科學與技術系 北京 100084)2(北德克薩斯州大學計算機科學與工程系 美國德克薩斯州登頓市 311277)(shenbilong@gmail.com)

共乘也被稱為“合乘”、“拼車”、“順風車”，通過有效整合運力資源減少路上行駛車輛數量，對緩解交通擁堵、降低出行費用、減輕環境污染都有重要意義.大數據背景下實時更新的車輛位置信息數據、城市交通數據、社交網絡數據，為智能出行特別是共乘帶來了全新的發展機遇.在車輛行駛中對乘客請求進行實時匹配的動態共乘，是大數據背景下智能出行發展趨勢的代表.在統一歸納了解決動態共乘實時性的Filter and Refine框架基礎上，介紹了動態共乘的各種類型；針對大數據背景下動態共乘問題遇到的問題，對Filter步驟中預先計算可行解、建立動態空間索引、基于請求分組預處理及并行優化方法，Refine步驟中簡化計算模型、采用新型數據結構、利用啟發式算法等優化方法進行了詳細介紹；然后對大數據背景下保證動態共乘系統的價格機制、信用體系和人機接口等相關技術進行了分析；最后，總結展望了大數據背景下動態共乘中亟待解決的關鍵問題和未來的研究方向，以期為創造低碳生活、綠色出行，解決環境污染有所啟示.

共乘;動態共乘;大數據;優化算法;城市計算

隨著經濟發展、人民生活水平提高，私家車的普及率也越來越高，給生活帶來了方便，但車輛數量的增加也帶來了交通擁堵、出行費用上漲、環境污染等一系列問題.根據中國社會科學院數據顯示，2012年北京因交通擁堵每天增加社會成本4 000萬元，每年經濟損失達146億元；同時機動車尾氣也是霧霾[1]的主要成因之一.共乘出行中駕駛員把車輛上空余的位置提供給乘客，也被稱為“拼車”、“汽車共享”、“順風車”或“搭便車”.這種出行方式提高了交通資源的利用率，既降低了出行成本，又緩解了交通擁堵、霧霾、噪音等環境污染問題[2-4].據研究在美國只需4%的司機選擇共乘，就可以解決美國68個主要城市次年車輛增長造成的擁堵問題[5].早期共乘以上下班通勤和長途旅行為主，甚至傳統的公交車、地鐵在某種程度上都可以看成更為廣義的共乘系統.共乘方式按出發后行程是否可變，分為靜態共乘和動態共乘2種.靜態共乘需在車輛出發前規劃好行程，出行之后不能改變行程，這種共乘方式靈活性較差，沒有發揮資源最大潛力，對共乘服務的大規模發展有一定限制.隨著網絡基礎設施的不斷完善，智能手機等移動終端的廣泛應用及GPS、北斗等定位技術的發展，為實時動態共乘發展提供了數據服務基礎.動態共乘允許司機在車輛行駛中與乘客匹配，使得共乘匹配更為靈活、方便，但同時帶來了計算復雜度、匹配成功率、價格機制、信用機制等一系列問題.本文的貢獻主要在于：1)對動態共乘問題進行了統一框架的定義；2)多維度介紹了共乘問題分類；3)對動態共乘問題中遇到的實時性等挑戰和解決方案進行了分析總結；4)對影響共乘問題的價格機制、信用體系和人機接口的技術因素進行了分析和總結；5)通過對當前動態共乘問題及典型應用研究分析，指出了動態共乘面臨的主要問題和未來發展趨勢.

1 共乘問題概述

1.1 共乘發展歷史

共乘源自于熟人之間的自發行為，這種行為可以直接減少用戶出行成本.以北美為例[6-7]，共乘發展主要經歷了5個階段：1)1942年共乘以汽車俱樂部的形式出現，主要是為了解決二戰期間的資源短缺問題，在這一階段處于共乘萌芽階段，主要依靠簡單的公告牌來完成；2)在20世紀60 年代到70年代之間，在這階段出現了工人自發和政府組織的共乘行為，如美國在一些高速公路上修建專門的共乘車道[8](high-occupancy vehicle lane， HOV)，規定只有上座2人以上的車才可以駛入，同時Slugging[9]形式的長途拼車也出現了，共乘的人員范圍進一步擴大；3)從20世紀80年代開始，以解決環境污染和交通擁堵為目標，運輸管理協會等組織出現，基于電話叫車服務的共乘業務開始發展；4)從1999年到2004年，圍繞解決擁堵問題，共乘服務商開始大力發展參與共乘的人數，基于互聯網的在線共乘業務和專門的出行服務511[10]也在此階段出現，智能共乘開始興起；5)從2004年到現在，隨著智能手機等移動終端的普及，GPS、北斗等定位技術的發展，海量的移動終端與車輛位置信息可以方便被獲取，基于移動終端的共乘平臺開始涌現，共乘進入了全新以技術為驅動的時代，靈活的實時動態共乘相關研究與原型系統開始出現.新的技術為共乘解決氣候變暖、降低石油進口和解決交通擁堵等問題提供了更有力的保證.歐洲國家[11-12]和日本、新加坡等國也都開始了共乘的嘗試.

1.2 共乘發展現狀

隨著定位技術、移動網絡的發展和智能終端的普及，終端設備、即時通信、城市交通、社交網絡每天都在產生海量數據，而且這些數據量也在隨著時間迅速增長，以江蘇省為例，其交通軌跡數據已高達500多億條、100多TB，每日新增數據量7 000萬條、150多GB[13].以海量個人的實時出行數據、交通信息數據、社交媒體數據等為代表的大數據背景為智能交通系統發展帶來了新的機遇[14].共乘這種出行方式出現已久，但由于過去信息傳播能力與手段的限制，很長一段時間僅限于具有親密關系的人群，沒有大規模發展.而在大數據背景下，實時地理位置感知、海量數據處理等技術的成熟為共乘的大規模發展提供了平臺支撐，基于終端設備的出行方式被人們逐步接受為共乘的大規模發展提供了用戶支撐，共乘出行迎來了全新的發展機遇.

近年來智能共乘平臺逐步普及發展.國外已涌現出Avego[15]，mitfahrgelegenheit[16]，zimride[17]，Carpooling[18]，Blablacar[19]等共乘平臺，Uber[20]，Lyft[21]用車平臺也推出拼車服務.國內的共乘業務相對起步較晚，在杭州、北京、武漢等城市，相繼出現了民間自發組織的共乘，如武漢的鄰里合乘[22]項目，北京2008年因奧運期間限行而自發組織的拼車等.近年隨著滴滴[23]、神州專車[24]等智能終端叫車業務的發展，國內用戶對通過智能終端叫車的出行方式也已經接受.共乘業務服務商也如雨后春筍般涌現，已有51用車[25]、嘀嗒拼車[26]、滴滴順風車[23]等數十個拼車平臺，并在上下班通勤中得到了大量應用.

Fig. 1 Dynamic ride sharing system framework圖1 動態共乘系統框架示意圖

從現有共乘應用形式上看，車主與乘客都是在行程出發之前完成匹配，匹配后按預先規劃路線行駛.這種共乘對資源的利用率有一定的局限性，車輛如果出發之前沒有完成乘客匹配，在行程出發后即使有可匹配的乘客也無法對其請求進行響應，實載率提高有限，在應用上存在一定局限性，沒有充分發掘交通大數據的潛力.為進一步提高共乘資源利用率，近年研究學者提出了動態共乘的概念[27]，并有大量研究工作，在提高匹配度[28-31]、降低行程開銷[4,28-29,32-38]、減少用戶請求響應時間[4,29-30,32,34-40]等方面展開了研究，其中許多研究基于真實出行數據集進行了測試仿真.例如黃艷[37]，鄭宇[4]，Agatz[28]等人分別利用了上海市17 000臺出租車行程軌跡數據[37]、北京市33 000臺出租車軌跡數據、亞特蘭大市的真實出行模型進行了共乘出行的模擬.實驗模擬表明，動態共乘能有效降低車輛空車率，提高實載率，為節省出行成本、降低碳排放、緩解交通擁堵提供了有效的解決方案，是未來智能出行的發展方向之一.

2 動態共乘問題定義

共乘問題可看成優化問題，即對路上行駛的n輛車、m個服務請求，規劃出車輛與服務請求的匹配關系及行車路線，使得到滿足的服務請求數最多.共乘按車輛出發后可否進行匹配，分為靜態共乘和動態共乘2類.靜態共乘，司機和乘客需在行程開始前，完成滿足乘客和路程約束條件的匹配，出發后不能更改行程；動態共乘，司機在行程開始之后，仍可在滿足乘客和路程約束的情況下，與乘客進行實時動態匹配.靜態共乘可以看成是動態共乘在某一時刻收到所有請求的特殊情況.動態共乘依賴網絡、智能終端、精準定位技術，采用動態匹配算法，車輛可在行駛中接受新的乘客請求，進行實時動態共乘匹配，使運力資源得到了最大化的利用.動態共乘帶來了匹配方法、路線規劃、法律規范、出行安全、個人隱私等問題，本文中主要對大數據背景下動態共乘中的匹配方法與路線規劃問題及促進動態共乘的相關技術進行討論.

2.1 動態共乘系統概覽

如圖1所示，一個典型的動態共乘請求處理流程可以表示為：1)乘客將行程請求及相應約束條件發送到服務器；2)服務器根據乘客提供的行程請求及相應約束，將乘客與能提供相應服務的車輛進行匹配；3)對符合乘客要求的車輛，將匹配結果發送給相應司機，若匹配失敗直接通知乘客請求失敗；4)司機根據收到的用戶請求結合自身情況進行服務確認；5)服務器將匹配好的服務信息通知給乘客；6)司機按新的行程安排將乘客載上車并送到指定地點.

2.2 動態共乘基本概念

定義1. 路網.路網為集合G=V,E,W.其中，V為節點集合，表示路網中不同的位置點；E為路網中各邊(u,v)∈E,(u,v∈V)的集合；每條邊都有自己的權值，記為W(u,v)，代表通過邊(u,v)的開銷，開銷用時間或距離表示.給定行駛速度下，距離和時間開銷度量可相互轉換.

定義2. 服務請求.給定G=V,E,W，服務請求tr=o,d,pn,tow,tdw,ε.其中，請求的起點o∈V；終點d∈V；pn為本次請求的乘客人數；tow為上車時間窗口，tow=to.s,to.e，to.s為上車的最早時間，to.e為上車的最晚時間；tdw為下車時間窗口，tdw=td.s,td.e，td.s為下車最早時間，td.e為下車最晚時間，如圖2所示；服務約束ε用來表示最大容許的繞路開銷，為(1+ε)×dist(o,d)，其中dist(o,d)表示為點o與點d之間的距離.定義車輛實際到達tr.o的時間為tr.tvo，將乘客送達tr.o的時間定義為tr.tvd.

Fig. 2 Request time window圖2 服務請求時間窗口示意圖

將給定路網G上，當前時刻所有行程請求的集合記為TR.

定義3. 車輛.Car=id,t,loc,schedule,TRrec,ncap,nemp.其中，id表示車輛唯一編碼；t表示時間戳；loc表示車輛在時刻t的位置；schedule表示車輛時刻t已有安排；TRrec表示當前車上已有乘客請求集合，TRrec=tr1,tr2,tr3,…；ncap表示車輛總容量；nemp表示車上當前空閑容量.

將給定路網G上，當前時刻所有車輛的集合記為C=Car.

定義4. 行程安排.給定路網G，行程安排是某一時刻車輛Car對其將要完成上客點、落客點的時序安排，schedule=v0,v1,…,vk這段行程可以表示為一個頂點序列(v0,v1,…,vk)，其中(vi,vi+1)為集合E中的邊，v0表示行程安排時車輛的位置點.

定義5. 動態共乘問題.給定路網G上的車輛集合C和服務請求集合TR，將不同的服務請求分配到不同車輛并進行行程安排，使車輛在滿足動態共乘約束的條件下，達成一定的優化目標.

在后面的2.3節和2.4節中將分別介紹動態共乘需滿足的約束條件和優化目標.

2.3 動態共乘約束條件分析

定義6. 有效分配.給定車輛Car與一個單獨的服務請求tr，當他們的匹配滿足共乘約束時，稱該匹配為有效分配.

定義7. 請求完成.一個單獨的服務請求tr被分配到車輛Car,在滿足共乘約束的條件下，該車將乘客由tr.o送至tr.d處，則稱請求tr被Car完成.

動態共乘主要有時間、距離、價格及個人喜好等約束條件.時間約束有服務時間窗口、到達時間點和額外增加時間等；距離約束條件有整體行程距離、個人繞路距離等；價格約束有成本開銷、最低成交價格等；個人喜好約束有個人性別、行為習慣、駕駛經驗等.個人喜好約束屬人文范疇，不在本文研究范圍內.時間和距離如前所述在給定行駛速度下，可以互相轉換；價格可通過定價策略基于行程和時間獲得，因此本文主要以路網開銷W(u,v)及距離作為分析基礎.

定義8. 行程開銷.對于一個車輛Car的行程安排，完成schedule=v0,v1,…,vk中各點的行程，這段行程的總開銷定義為

Fig. 3 Detour cost圖3 繞路開銷示意圖

如圖3所示，新增乘客而給原來行程帶來的繞路開銷比:

在本文中，對某臺車輛Car和某個乘客請求tri，定義動態共乘有效分配的約束條件如下：

請求的乘客數小于或等于車上空位數：

(1)

乘客可在規定時間窗口內完成請求:

?tri∈Car.TRrec,

tri.to.s≤tri.tvp≤tri.to.e,

(2)

對每個請求，乘客繞路開銷比小于最大容忍值：

(3)

近年來，不同動態共乘研究中的約束條件如表1所示:

Table1 Constraint Conditions of Dynamic Ride Sharing

Notes: “√” means concerned; “×” means unconcerned.

2.4 動態共乘優化目標

傳統靜態共乘中，車輛出發前完成車輛與乘客的匹配，車輛出發后行程不再變化，對匹配算法耗時敏感性不高；而動態共乘中，由于新增的行程請求會對已有的行程安排產生影響，進而可能影響到車上已有乘客的行程體驗，在進行新的請求匹配時，不僅要考慮到新的共乘請求是否滿足約束，還需考慮新增乘客對已接受請求乘客的影響.動態共乘的優化目標主要有：1)降低車輛總行程開銷；2)提高共乘匹配成功率.在不同的應用場景和研究中優化目標各不相同.

2.4.1 降低車輛行程開銷

Fig. 4 Rescheduling with a new request[37]圖4 收到行程請求需處理的新的規劃[37]

2.4.2 提高共乘匹配成功率

當處理n輛車、m個服務請求時，還有一個總體目標：匹配成功率.

動態共乘中乘客請求的匹配效果也是大數據背景下共乘能否可持續發展的重要因素，如乘客的請求不能被有效匹配，會使用戶體驗下降，而多次匹配失敗很可能造成用戶流失，匹配成功率可以從宏觀尺度上反映匹配效果.實時動態共乘可近似看成貪婪匹配問題.乘客發出行程需求后，希望在一定的時間內得到服務響應.利用匹配算法，在某個時刻會產生乘客和車輛在這一時刻的最優匹配安排，并將用戶請求分配到指定車輛，但隨著新的請求加入后，之前“最優安排”的匹配在之后的時刻可能已非最優.然而對實時的請求處理，這種方法從技術角度容易實現，也容易被乘客和司機所接受，因此對動態共乘的匹配一般都認為是到某一時間點所能達到的最優匹配.

綜上，動態共乘主要有總體開銷最小化、響應時間最小化、匹配成功率最大化等優化目標：

總體開銷最小化,即：

(4)

匹配成功率最大化,即：

(5)

近年來，動態共乘的研究工作的優化目標也不盡相同，總結起來如表2所示.

Table2 Optimization Goal of Dynamic Ride Sharing

Notes: “√” means concerned; “×” means unconcerned.

3 動態共乘問題分類

動態共乘問題按共乘的完成方式與車上乘客的數量可分為單車輛單乘客、單車輛多乘客、多車輛單乘客、多車輛多乘客4種[41].不同類型的共乘模型適用于不同的應用場景，采用的優化方法也不同，本節對動態共乘的不同分類進行介紹.其中，單車輛多乘客模型最為典型，是本文的重點.

3.1 單車輛單乘客動態共乘

單車輛單乘客動態共乘模型是動態共乘模型中的基礎模型，在這種模型中每臺車輛只允許與一名乘客進行共乘匹配，匹配過程中車輛Car=id,t,loc,schedule,TRrec,ncap,nemp,TRrec僅有車輛已完成乘客匹配和無乘客2種狀態.在這種模型中，默認將ncap=1，當nemp=0時，車輛不再接受新的請求.不需要考慮新發出請求的乘客與已經在車上乘客原請求的沖突，只需要考慮乘客與司機的匹配.在單乘客模型中，司機會繞路去搭載乘客，因此會考慮繞路所帶來的開銷，Agatz等人[28]研究的優化方法中，以最小化總體行程及每個人的花費為目標，約束條件為總的繞路距離小于司機與乘客各自未進行共乘開銷的總和.作者基于2008年Atlanta的地鐵出行數據進行了動態共乘的出行模擬，并通過優化方法取代了簡單貪心算法，改進了共乘匹配效果.而Kleiner等人[29]的研究中，通過計算司機繞路的最小成本，在滿足最小成本的基礎上，乘客通過價格競拍的方式與車輛進行匹配.單車輛單乘客動態共乘模型是動態共乘算法的基本模型，比較容易實施，匹配復雜度低；但因為一般車輛都有多個座位(ncap>1)可提供，這種共乘模型沒有充分發掘運輸潛力，所以很多研究都在單車單乘客模型的基礎上進行了擴展.

3.2 單車輛多乘客動態共乘

在單乘客動態共乘模型的基礎上，單車輛多乘客動態共乘模型中車輛Car=id,t,loc,schedule,TRrec,ncap,nemp，只要Car滿足車輛上仍有空閑座位，即nemptn，而每個節點的到達時間在加入新乘客之前是滿足乘客約束的，而如第2節所述，對新的用戶請求，需對已有schedule中的位置點和新乘客的位置點進行規劃，判斷是否能得到符合所有乘客約束的路線規劃，以確定新的乘客請求能否接受.

Fig. 5 Insertion in single driver multiple passengers圖5 單車輛多乘客共乘插入行程示意圖

3.3 多車輛單乘客動態共乘

在實際應用中，松弛完成某一乘客行程請求的車輛數量，由原來的一臺車輛完成某一乘客的輸送變為可由多臺車輛協作完成對某乘客的輸送，得到單乘客多車輛模型[40].如圖6所示，某時刻Car1,Car2已分別與tr1,tr2匹配，行程請求tr3出現，在單車輛模型中，無論tr3與Car1還是Car2匹配，都會產生較大繞路開銷.而在多車輛單乘客模型中，首先由Car1將tr3帶到指定的換乘點Pt，由Car2完成余下的行程，則可以較小繞路開銷完成匹配.這種模型更為靈活，提高了用戶的匹配成功率，使資源利用潛力進一步被發掘.

Fig. 6 A composite route offered as a transport solution[40]圖6 多車輛單乘客組合路線示意圖[40]

3.4 多車輛多乘客動態共乘

多車輛多乘客模型可以看成是多車輛單乘客動態共乘模型的進一步擴展，即利用多個車輛進行多個乘客的輸送.對這種模型擴展，還可以松弛車輛行駛中的司機身份限制，即在行程中可切換司機，在某段路上原來充當乘客的人可以充當駕駛員駕駛車輛.這種模型可以應用于租賃汽車中，如可隨時租賃使用的ZipCar[42]，車輛的租用者可以通過智能規劃、角色互換實現出行成本的最優化.

4 動態共乘優化主要方法

如2.3節和2.4節所述，動態共乘匹配算法需要在滿足時間窗口、繞路等約束條件下對總體開銷、響應時間、匹配成功率進行優化.對動態共乘而言，需要解決共乘匹配時間開銷大與動態共乘應用的實時性需求之間的矛盾，解決這種矛盾的經典方法是利用Filter and Refine框架.本節首先介紹了大數據背景下動態共乘優化問題，隨后圍繞Filter and Refine 框架對動態共乘優化方法進行詳細闡述.

4.1 動態共乘優化問題的復雜性

動態共乘的實時處理是其大數據背景下廣泛應用的挑戰之一.以司機的角度，新的請求到來時，司機可能已經接受了一些乘客行程請求，并在接受新的行程請求時已對這些行程請求安排了行駛路線.對一個新的請求，車輛需要重新進行路線安排以判斷其是否能接受新的請求.如2.4.1節所述情景，車輛行駛至點P時，已經接受tr1,tr2,tr3用戶請求，并完成乘客tr2的輸送，如圖4所示，對應tr2乘客已經在車上，已經到達tr1.o但尚未到達tr1.d，對應tr2的乘客已經完成輸送，而tr3還未上車，需要行駛經過tr3.o，tr3.d，對應于tr4，需行駛至tr4.o，tr4.d.如圖7所示，確定車輛能否接受新行程請求tr4需在P對節點tr1.d,tr3.o,tr3.d,tr4.o,tr4.d進行路線規劃，判斷能否找到同時滿足：①車上空位約束Car.nemp；②時間窗口tr1.tow,tr3.tow,tr3.tdw,tr4.tow,tr4.tdw約束；③每名乘客的行程繞路約束δdet(tr1.o,tr1.d),δdet(tr3.o,tr3.d),δdet(tr4.o,tr4.d)路線規劃schedule=v0,v1,…,vk.該規劃過程可看成圖搜索問題，是拓展的旅行商問題，已被證明為NPC[4,37]問題.

Fig. 7 Possible schedules with a new request圖7 行程規劃示意圖

4.2 動態共乘優化問題實時性需求

定義11. 響應時間.Timecomp=tri.tget-tri.treq，其中，tri.treq表示服務請求發起時間，tri.tget表示系統判斷新請求能否被成功匹配的時間.降低響應時間以滿足動態共乘的實時性需求，是決定大數據背景下動態共乘應用效果的關鍵技術之一.

如4.1節所述，車輛接受到新的請求后，需在P點對tr1.d,tr3.o,tr3.d,tr4.o,tr4.d進行規劃，以期在滿足約束條件下得到最優化的schedule=v0,v1,…,vk.動態共乘的實際應用中，車輛在路網上移動，如果不能在有效的時間內對用戶請求進行相應匹配，則無法滿足動態共乘匹配的實時性要求.因此需設計專門的優化算法來滿足動態共乘的實時性需求.減少用戶請求響應時間是動態共乘大規模應用需解決的關鍵技術，后文將主要圍繞動態共乘實時性的有關研究進行展開.

4.3 動態共乘優化的Filter and Refine框架

近年來對大數據背景下動態共乘的研究中，解決實時性問題主要采取Filter and Refine框架[43].基本思想是：首先利用某些過濾條件將不能完成匹配的車輛或乘客從車輛集合C和乘客請求集合TR中剔除，僅保留可能符合條件的車輛或乘客請求，或通過聚合分組等方法縮小問題解空間；然后在較小的解空間中對車輛和乘客進行匹配.即：

Step1. Filter.給定G=V,E,W、服務請求集合TR=tr、車輛集合C=Car，對tri∈TR，將C中無法滿足匹配約束的車輛進行過濾，得到CFiltered=Car,|CFiltered|≤|C|；對Cari∈C，將TR中無法滿足的行程請求進行過濾，得到TRFiltered=tr,|TRFiltered|≤|TR|；通過聚合等方法將TR聚合成小數量的請求組，得到TRGrouped=tr,|TRGrouped|≤|TR|.

Step2. Refine.將Filter步驟獲得的候選車輛集合CFiltered中的車輛，與乘客請求集合TRFiltered進行匹配，tr滿足上下車時間窗口tow,tdw和繞路開銷δdet等約束的基礎上，得到行程開銷最小的乘客-車輛匹配對.

4.4 Filter主要方法

Filter步驟中，目標是通過剪枝與過濾降低Refine中的候選解規模.動態共乘，乘客發出請求后，需要對在路網上行駛的車輛進行匹配檢索，針對移動目標快速索引問題，雖然已有一些動態空間索引技術[44-45]，但這些算法不是專門為動態共乘設計的.如R-tree結構，因為多目標的位置不斷變換，會引起葉子節點的不斷更新，帶來額外開銷.Filter步驟主要有預先計算可行解、建立動態空間索引、利用價格開銷過濾和基于分組預處理聚類等方法.

4.4.1 預先計算可行解的優化方法

如前所述，在電話叫車服務中的靜態共乘服務，匹配在車輛出發前進行，對實時性要求不高，基于離線操作可得到較好的優化效果.然而對于動態共乘，因不斷有新請求到來，需進行實時規劃，靜態匹配的方法已經不能滿足實時性需求.Coslovich等人[35]提出2階段插入算法改進系統的實時性：第1階段，利用乘客請求的時間間隙進行預先計算，得出當前路線中車輛可有效響應的路線安排，在這一步計算中，對n個可停靠的站點，根據搜索可得到的有效路線數量由少變多設計了2種算法，復雜度分別為O(n3)與O(n4).實際應用時，首先采用搜索到路線少、復雜度為O(n3)的可選路線搜索方法，在時間充裕的情況下調用搜索到可選路線多、復雜度為O(n4)的方法.第2階段，當動態的請求發生時，通過第1階段的預先計算的可行解，對新的行程請求進行判斷，并引進局部松弛時間和全局松弛時間對新的請求進行加速，在這個階段插入的時間復雜度為O(n).這種優化方法面向傳統的電話叫車服務，適用于中小規模的動態共乘問題.

4.4.2 建立動態空間索引優化方法

車輛在路網上行駛，快速檢索出可能符合約束條件的候選車輛，縮小規劃與匹配的候選車輛數，可有效降低共乘系統響應時間.鄭宇等人[4]針對出租車共乘提出了基于區塊的動態空間索引方法.如圖8利用空間索引方法優化匹配示意圖[4]所示，這種方法預先把空間分成小的區塊，并根據區塊內部的路網分布，如圖8(a)所示，將單元區塊用路網上靠近區塊中心的點來表示，計算基于路網的區塊距離，生成區塊距離矩陣，如圖8(b)所示，每個區塊記錄了時間近鄰區塊索引、空間近鄰區塊索引、區塊內將會到達出租車的索引，其中，時間近鄰區塊索引和空間近鄰區塊索引按時間與空間的遞增排序，出租車索引按到達時間排序，如圖8(c)所示.用戶發出乘車請求tr=o,d,pn,tow,tdw,ε后，分別從請求的起點tr.o和終點tr.d所在方格gridi和gridj按照距離由近到遠的方式在空間近鄰索引中拓展搜索區塊，得到近鄰區塊中的出租車作為候選車輛，完成候選車輛的第1步過濾,如圖8(d)所示.

Fig. 8 A spatio-temporal index to quickly retrieve candidate taxi[4]圖8 利用空間索引方法優化匹配示意圖[4]

4.4.3 基于請求分組預處理及并行優化方法

大數據背景下的大規模共乘問題中，動態的行程可以看成是流數據的分組問題[46]，即把具有相近距離起點、終點的請求進行分組，降低Refine步驟的解空間.Gidofalvi等人[30]針對大規模行程請求，實現了基于SDSQ流數據管理系統的行程分組(trip grouping, TG)并行化算法，在TG算法中用額外開銷FEC(fractional extra cost)來衡量不同請求行程間的關系，給定2個請求tri與trj：

FEC(tri,trj)=

某一請求tri對已經聚合請求集合s的平攤開銷定義為AC(amortized cost)：

通過計算行程之間的FEC以及行程請求和行程請求組的AC，TG算法實現了對請求進行分組.如圖9所示，對請求tr1,tr2,tr3：

FEC(tr1,tr2)=

FEC(tr1,tr3)=

AC({tr1,tr2,tr3})=

m個請求未做并行化處理的算法復雜度為O(m3).實現并行計算時，不同的任務劃分方法對并行計算效果影響較大，該文分別測試了基于靜態點的4分法SPQ(static point quad partitioning) 、基于中位數的靜態多維劃分方法(static KD partitioning， SKD)、自適應的基于點的4分法 (adaptive point quad partitioning， APQ)、自適應多維劃分方法(adaptive KD partitioning， AKD)四種數據流的劃分方法，通過實驗得出自適應多維劃分方法具有最好的劃分效果，在16個核的機器上進行并行計算時，較串行算法獲得了10倍以上的加速比，為請求分組及利用并行計算的方法進行共乘數據處理都提供了一定借鑒.

Fig. 9 Illustration of fractional extra cost(FEC) and amortized cost(AC) calculations w.r.t request tr2[30]圖9 額外開銷(FEC)與平攤開銷(AC)計算示意圖[30]

基于分布式系統對移動物體進行檢索的研究近年也取得了相關進展，于自強等人[47]設計了動態條帶索引(dynamic strip index， DSI)的索引結構，與基于方格的區塊劃分不同，動態條帶索引采用條帶劃分的方法對移動物體進行索引，保證了數據的分布式處理效果，同時作者基于DSI設計了分布式移動物體的K近鄰檢索算法(distributedk-NN search， DKNN)，并在Apache S4上進行了實現，獲得了較好的可擴展性與查詢速度，為利用分布式系統的方法來提高移動物體索引效率提供了一定借鑒.

4.5 Refine主要方法

如4.4節所述，在經過Filter步驟處理后，需匹配的車輛集合C與行程請求集合TR空間已經縮小.Refine步驟，需要對Filter步驟中獲得的候選車輛集合和新的請求集合進行匹配.能否將新的請求與車輛進行匹配，取決于新請求和車輛上已有的TRrec進行路線規劃后能否找到滿足約束的可行解.如4.1節所述對車輛路線的規劃是一個NPC問題，如果利用精確算法，解決匹配問題的時間會隨著問題規模的增大而呈現指數級的增長.在路徑規劃的研究中，比較典型的有分支定界法[48]、整形規劃法[49]、遺傳算法和蟻群算法等方法，但這些方法主要解決的問題是離線匹配，遠不能滿足實時動態需求.因此針對動態共乘，需專門地優化算法來加快行程規劃速度.現有動態共乘Refine步驟主要優化手段有簡化計算模型、引進專有數據結構、采用啟發式方法等.

4.5.1 簡化計算模型的優化方法

為滿足實時性，T-share[4]在利用調度算法檢測候選出租車是否符合要求時，采取了簡化問題模型方法，即對新的請求不重新規劃路線，僅在原行程安排中插入新請求，將規劃問題精簡為插入判斷問題，同時引入了距離矩陣和松弛時間，利用距離三角不等式來對新插入行程的合法性進行判斷，對有n個點的行程，將算法復雜度由O(n!)降為O(n2).這種方法提高了動態共乘系統的實時性，但因為簡化了問題，會對解的最優性造成損失.

4.5.2 利用新型樹結構的優化方法

黃艷等人[37]提出了基于活動樹(Kinetic Tree)數據結構的優化方法.一般的分支定界法對新請求的判斷未利用原來的計算結果，從而產生了重復計算，導致運算時間增加.作者為了避免了重復運算，設計了活動樹.如圖10所示，活動樹中保存了當前所有可行規劃，根節點到葉子節點的次序表示規劃路徑.新的乘客請求到來時，如果采用圖搜索的方法，每一步都需對多點圖進行搜索，無法利用之前的計算結果，算法復雜度與節點處呈幾何級數增長.而通過活動樹保存當前最優的路徑安排和所有的有效安排schedule=v0,v1,…,vk，在收到新的請求時，只需基于保存在活動樹中的有效路線對新請求tr.o,tr.d進行插入有效判斷即可.如圖10所示，令si表示行程tri請求的起點tri.o，令ei表示行程tri請求的終點tri.d.收到第1個請求生成如圖10(a)所示活動樹.當第2個乘客請求到達時，第1個乘客已經上車.此時利用10(a)所示活動樹對乘客2的起、終點有效性進行判斷，假設乘客1先下車再接乘客2路線不滿足約束，得到先送乘客2到終點和先送乘客1到終點這2個可能路線，其中最優路線為(l,s2,e1,e2)，而符合約束的可行路線(l,s2,e2,e1)也被記錄，生成如圖10(b)所示活動樹.在車輛向乘客2起點行駛途中，收到乘客3請求，此時需要判斷先接乘客2還是乘客3，假設此時有5條可滿足約束的路線，其中最優路線為(l,s2,s3,e2,e3,e1)，得到如圖10(c)所示活動樹.乘客2上車后，收到乘客4請求，此時圖10(c)中r3右子樹已無效，假設此時有2種路線滿足共乘約束，則得到如圖10(d)所示活動樹.同時作者針對路線中節點過多造成空間搜索開銷過大的問題，提出了基于熱點的優化方法，將距離小于閾值θ的點聚合為一個hotspot節點，使得插入位置判斷次數減少，進一步縮小解空間，降低系統運算量，提高響應速度.作者利用上海實際出行數據進行了實驗仿真與性能測試，實驗表明與整形規劃方法相比，活動樹方法獲得了1個數量級以上的加速比.

Fig. 10 Kinetic Tree for trip schedules[37].圖10 利用Kinetic Tree方法優化行程規劃示意圖[37]

4.5.3 利用啟發式算法的優化方法

對應于路線的規劃問題，遺傳算法、蟻群算法、禁忌搜索算法、模擬退火方法、粒子群優化等啟發式優化方法也被采用.Herbawi等人[50]比較了蟻群算法和遺傳算法在動態共乘中的性能，并基于帶有時間窗口的多乘客多車輛動態共乘問題，提出了遺傳算法的解決方案[51].在多乘客多車輛動態共乘問題中，優化目標為車輛行程時間最短、車輛行駛距離最短、乘客等待時間最短以及最大化的匹配效果.利用遺傳算法進行行程安排時，每一個車輛的行程被記錄到列表中schedule=v0,v1,…,vk，同時未被滿足的乘客請求也被記錄到一個不滿足列表中.遺傳算法初始化時，首先將車輛的起終點插入到車輛的行程安排中，而后隨機選擇路線安排插入已有路線中，作為遺傳的父代.在生成可行解后，選取可行路線并對其中的路線通過交換來生成后代，作為單點交叉算子，該文對路線中的路徑點提出了5種變異操作.Santos等人[52]提出了面向出租車的動態共乘優化問題框架和啟發式算法，在該框架中以乘客和車主的總成本最小為優化目標，以插入行程給原車輛帶來額外的時間開銷作為貪心函數，并采取了本地搜索優化的方法優化匹配效率，該文的作者對數百個真實請求數據進行了動態共乘匹配模擬，得到了秒級的響應時間.

5 動態共乘人文影響

動態共乘將運力資源進行了整合優化，這種資源整合過程，除了匹配與路線規劃計算本身，司機與乘客的社會行為因素也是共乘系統需考慮的因素.本節對影響乘客體驗的信用體系、價格機制和用戶信息交互等人文因素在共乘方面所進行的研究進行闡述.

5.1 信用體系

共乘形成于熟人之間，而后隨著通信與交互手段逐步發展[11-12]，這種行為本身離不開人們之間的信任關系.Chaube等人[53]對大學校園共乘系統研究表明，共乘參與者之間的信任關系直接影響共乘參與度，陌生人之間有7%的人接受共乘，在熟人之間有98%接受共乘，而與熟人的朋友的共乘也會有69%被接受.因此，Cici等人[54]通過分析用戶電話呼叫記錄，發掘共乘潛力.FaceBook，Twitter、微博、微信等社交應用把興趣愛好、背景相同的人形成了一種天然的聚合.利用社交網絡信息進行用戶愛好分析，增加用戶的參與度已經被應用在實現系統中.ZimRide，Avego和Carticipate等系統已經開始利用SNS進行用戶的連接，而Uber也在推出熟人共乘補貼等服務，培養用戶共乘習慣.為增加用戶認同感，Blablacar等共乘系統甚至把司機的聊天水平作為評價體系的一部分.但大數據背景下的動態共乘中，司機與乘客的關系并不僅限于熟人，因此在共乘系統中，需要一個完善的信用體系，規避可能出現的信用風險，提高司機服務質量和乘客的參與熱情，使共乘系統長期、穩定、健康發展.

通過信用體系來保證用戶長期參與性也是很多C2C和O2O系統中需要解決的問題[55-56].我們認為，共乘系統中信用體系需考慮信用可查、信用可評、信用公平、失信處罰等因素[56].在建立信任的過程中，歷史交易積累產生的信任感是最直接有效的.很多共乘系統采取了第三方支付+信用評價的方式，將用戶反饋與第三方支付系統相結合促進交易經驗分享，保證交易資金安全，約束乘客和司機的行為，產生良性循環，使共乘系統更好地為乘客和司機服務.

第三方支付[57]中錢款不直接在司機與乘客間流動，采用第三方信用擔保的方式，保證支付安全，如Paypal、支付寶等.第三方支付的典型流程如下：在完成乘客和司機匹配后，乘客將預付費放到第三方支付托管機構；在乘客按預先約定好的方案完成行程后，對司機服務進行評價，在確定完成服務后，第三方平臺將費用轉給司機，從而完成整個共乘的支付.為保證支付安全和信用體系的構建，對第三方托管平臺不僅要求其進行資金托管，更要求其具有權威、獨立的評價能力，能對用戶產生足夠的約束力.當前Avego、Zebigo、Goloco、51用車、嘀嗒拼車、天天拼車等系統采用的都是這種支付方式.

用戶反饋機制的構建，往往采用不同維度的互評體系，共乘完成后由乘客和司機互相評價.我們認為動態共乘信用評價體系需滿足3項需求：①保證司機與乘客歷史信用的可查詢性，司機和乘客可以在匹配前對共乘人員進行了解；②建立完善的失信處罰機制，如某個乘客在確定匹配后多次單方面退出行程，那么在下次匹配的過程中，將對其匹配的優先級做一定的懲罰，甚至取消其共乘匹配資格；③保證信用評價的公平性，充分考慮影響服務質量的因素的多元性.如某車輛已載有1名乘客，司機與第2名乘客達成了一個新的共乘請求后，第3名的共乘請求到達，司機也接受了第3名乘客的請求，在司機接第2名乘客上車時，由于第2名乘客沒有按時到達指定地點，造成了之后對第3名乘客的服務延遲.如果只是簡單的評分，必然會影響司機信用評級的公平性.因此針對共乘出行模式本身的特點，制定專有的信用評價體系對共乘系統廣泛推廣有重要作用.

5.2 價格機制

Fig. 11 Total cost for a ride sharing with detour[29]圖11 共乘成本開銷示意圖[29]

Kamar等人[58]提出了一個基于VCG(Vickrey-Clarke-Groves)[59]機制的定價策略，利用該機制保證定價的激勵相容等特性，同時該文作者測試了不同策略對計算效率、預算平衡、激勵相容、匹配成功率的影響.Cheng等人[60]提出了解決生活中最后1公里到達的共乘方案，考慮了動態和需求響應機制來安排非專用商業車隊(出租車或多乘客小客車)共乘，提出了基于征求意愿支付率(willing payment rate)和意愿補償率(compensation rate)的競拍機制，并基于現實和模擬數據測試了在2種競拍機制下不同參數對共乘的影響.Zhao等人[61]提出了一個基于市場調節的共乘系統，在這個系統中通勤者通過他們提出的出行約束來進行匹配，比如可用的座位數、開銷，為增加匹配度，通勤者可充當司機或乘客的角色.在之前的策略中，VCG策略可能會導致系統需要補貼才能正常運轉，產生赤字.固定價格的方法不能滿足激勵相容，作者提出了一個帶有雙邊底價的VCG機制，具有激勵相容的特性，并使底價在一定范圍內赤字得以控制.

5.3 信息交互與隱私問題

移動設備及可穿戴設備的普及，為有效解決系統與人的快速交互提供新的途徑，有效的人機接口對共乘體驗起著重要作用.面向共乘的人機交互主要解決以下4個問題[62]：1)有效信息獲取；2)隱私保護；3)易用性；4)智能化信息處理.

隨著智能手機的應用，共乘平臺由基于PC的桌面網頁瀏覽向智能終端遷移.用戶通過移動端提交行程的起點、終點及相關約束，較以往更為快捷.共乘系統因優化目標不同，需要用戶提交信息也有所差別：如Noah系統[32]是以關心用戶本人的乘客感受為目標，乘客在進行共乘匹配時，提交當前地點、目的地、等待時間和繞路約束；T-Share系統[4]中用戶提交上車地點、下車地點及上車和下車的時間窗口.這2種系統都有效獲取了用戶需求，及時將位置及行程信息提交給系統與車輛進行匹配.在進行匹配定位時，為直觀地顯示司機與乘客的位置，共乘平臺通過調用現有的Google Map、Bing Map、百度地圖、高德地圖等第三方地圖服務商的接口，實現更直觀有效的交互.隨著語音識別和文本分析技術的不斷發展，交互手段越來越人性化[63]，語音、人臉識別等交互手段被廣泛采用.在實際應用中，語義上下文反映了用戶的當前應用場景，基于語義場景為用戶提供更智能服務的研究[64]也逐步展開.

隨著人機交互、社交網絡、城市計算和上下文感知技術的發展，場景感知、用戶肖像技術在帶來精準智能服務的同時也帶來了個人信息安全問題.如地址信息會直接表現出生活空間、興趣地點等個人信息，而乘客在共乘時也會考慮個人隱私泄露的問題，在信息有效交互的基礎上保證乘客和司機的個人隱私也是共乘需要面對和解決的問題，這方面的研究也逐步展開，主流媒體和學術界對個人隱私和安全的關注越發凸顯.近年來保護用戶隱私的信息交互方法被提出[65]，如共乘系統在匹配成功之前不會泄露用戶和司機的地址位置信息，以其他形式進行有效的可視化顯示，只有在匹配成功后才告知相關位置，減少用戶的隱私泄露程度.

6 共乘問題展望

現在對動態共乘的研究大都還沒有考慮到當前實際交通情況對共乘的影響，基于社交網絡挖掘共乘潛力的研究也處在初級階段.我們相信動態共乘技術將向4個方面發展：1)通過對社交網絡進行研究，吸引更多的人參與到共乘中來，形成良性循環；2)利用歷史交通數據和當前交通情況等多元信息的路況預測技術；3)優化復雜路況情況下智能匹配技術；4)依靠環境感知等技術，為乘客提供更為智能易用的共乘服務.

共乘隨著參與者數量的增加會產生良性循環，當參與人數達到一個保證服務的“臨界點”后，參與司機和乘客的數量將會出現穩定的自增長.當前，共乘還主要局限于長途和上下班通勤，形式以靜態共乘為主，隨著參與用戶數量的增加與動態共乘技術的發展，動態共乘將會在未來得到廣泛應用.而共乘技術也同樣適用于物流中的請求處理與規劃.有關研究表明，一臺自動駕駛汽車可以代替當下10輛私家車[66]，無人駕駛技術已日趨完善，其與動態共乘匹配技術結合，將會更有效地解決城市中的交通擁堵問題.共乘技術帶來的不僅是交通狀況的改進、自然環境的改善、出行成本的降低，更是全新的智能生活方式.

[1]Zhang Xiaoye, Sun Junying, Wang Yaqiang, et al.Factors contributing to haze and fog in China[J]. Chinese Science Bulletin, 2013, 58(13): 1178-1187 (in Chinese)(張小曳, 孫俊英, 王亞強, 等. 我國霧-霾成因及其治理的思考[J]. 科學通報,2013, 58(13): 1178-1187)

[2]Firnkorn J, Muller M. What will be the environmental effects of new free-floating car-sharing systems? The case of car2go in ulm[J]. Ecological Economics, 2011, 70(8): 1519-1528

[3]d’Orey P M, Fernandes R, Ferreira M. Reducing the environmental impact of taxi operation: The taxi-sharing use case[C]Proc of the 12th IEEE Int Conf on Its Telecommunications (ITST-2012).Piscataway, NJ: IEEE, 2012: 313-317

[4]Ma shuo, Zheng Yu, Wolfson O. T-share: A large-scale dynamic taxi ridesharing service[C]Proc of the 29th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2013: 410-421

[5]Dillenburg J F, Wolfson O, Nelson P C. The intelligent travel assistant[C]Proc of the 5th IEEE Int Conf on Intelligent Transportation Systems(ICITS).Piscataway, NJ: IEEE, 2002: 691-696

[6]Chan N D, Shaheen S A. Ridesharing in north america: Past, present, and future[J]. Transport Reviews, 2012, 32(1): 93-112

[7]Badoe D A, Miller E J. Transportation-land-use interaction: Empirical findings in North America, and their implications for modeling[J]. Transportation Research Part D: Transport and Environment, 2000, 5(4): 235-263

[8]Konishi H, Mun S I. Carpooling and congestion pricing: HOV and HOT lanes[J]. Regional Science and Urban Economics, 2010, 40(4): 173-186

[9]Ma Shuo, Wolfson O. Analysis and evaluation of the slugging form of ridesharing[C]Proc of the 21st ACM SIGSPATIAL Int Conf on Advances in Geographic Information Systems. New York: ACM, 2013: 64-73

[10]Metropolitan Transportation Commission. 511.ORG[OL]. [2015-07-01]. http:www.511.org

[11]Shaheen S, Cohen A. Growth in worldwide carsharing: An international comparison[J]. Journal of the Transportation Research Board, 2007, 1992(10): 81-89

[12]Shaheen S A, Cohen A P. Carsharing and personal behicle services: Worldwide market developments and emerging trends[J]. International Journal of Sustainable Transportation, 2012, 7(1): 5-34

[13]Yang Jie, Li Xiaoping, Chen Tian. A group mining method for incremental spatio-temporal trajectory big data[J]. Journal of Computer Research and Development, 2014, 51(Suppl2): 76-85 (in Chinese)(楊杰, 李小平, 陳湉. 基于增量時空軌跡大數據的群體挖掘方法[J]. 計算機研究與發展, 2014, 51(增刊2): 76-85)

[14]Zhang Junping, Wang Feiyue, Wang Kunfeng, et al. Data-driven intelligent transportation systems: A survey[J]. IEEE Trans on Intelligent Transportation Systems, 2011, 12(4): 1624-1639

[15]Carma Technology Corporation. carmacarpool[OL]. [2015-07-01]. https:carmacarpool.com

[16]Comuto. mitfahrgelegenheit[OL]. [2015-07-01]. http:www.mitfahrgelegenheit.de

[18]Carpooling. Carpooling[OL]. [2015-07-01]. https:www.carpooling.com

[19]BlaBlaCar Technology Corporation. Blablacar[OL]. [2015-07-01]. https:www.blablacar.com

[20]Uber Technologies Inc. Uber[OL]. [2015-07-01]. https:www.uber.com

[21]Lyft, Inc. Lyft[OL]. [2015-07-01]. https:www.lyft.com

[22]Tang Liming, Liu Qihua. Neighborhood carpool practice: A case study on community carpool[J]. Urban Transport of China, 2010, 8(6): 29-33 (in Chinese) (湯黎明, 劉其華. 鄰里合乘——社區拼車常態化的探索[J]. 城市交通, 2010, 8(6): 29-33)

[23]Beijing Xiaoju Technology Co, Ltd. 滴滴[OL]. [2015-07-01]. http:www.xiaojukeji.com

[24]China Auto Rental Holdings Inc. 神州專車 [OL]. [2015-07-01].http:zhuanche.zuche.com

[25]Beijing Shuailai Century Technology Co, Ltd. 51用車[OL]. [2015-07-01].http:www.51yche.com

[26]Beijing Changxing Information Technology Co, Ltd. 嘀嗒[OL]. [2015-07-01].http:www.didapinche.comhome

[27]Halll R W, Qureshe A. dynamic ride-sharing: Theory and practice[J]. Journal of Transportation Engineering, 1997, 123(4): 308-315

[28]Agatz N A H, Erera A L, Savelsbergh M W P, et al. Dynamic ride-sharing: A simulation study in metro Atlanta[J]. Transportation Research Part B-Methodological, 2011, 45(9): 1450-1464

[29]Kleiner A, Nebel B, Ziparo V A, et al. A mechanism for dynamic ride sharing based on parallel auctions[C]Proc of the 22nd Int Joint Conf on Artificial Intelligence (IJCAI). San Francisco: Morgan Kaufmann, 2011: 266-272

[30]Gidofalvi G, Pedersen T B, Risch T, et al. Highly scalable trip grouping for large-scale collective transportation systems[C]Proc of the 11th Int Conf on Extending Database Technology: Advances in Fatabase Technology. New York: ACM, 2008: 678-689

[31]Shao Zengzhen, Wang Hongguo, Liu Hong, et al. Heuristic optimization algorithms of multi-carpooling problem based on two-stage clustering[J]. Journal of Computer Research and Development, 2013, 50(11): 2325-2335 (in Chinese)(邵增珍, 王洪國, 劉弘, 等. 多車輛合乘問題的兩階段聚類啟發式優化算法[J]. 計算機研究與發展,2013, 50(11): 2325-2335)

[32]Tian C, Huang Yan, Liu Zhi, et al. Noah: A dynamic ridesharing system[C]Proc of the 2013 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2013: 985-988

[33]Shemshadi A, Sheng Q Z, Zhang W E. A decremental search approach for large scale dynamic ridesharing[C]Proc of Web Information Systems Engineering-WISE 2014. Berlin: Springer, 2014: 202-217

[34]d’Orey P M, Fernandes R, Ferreira M, et al. Empirical evaluation of a dynamic and distributed taxi-sharing system[C]Proc of the 15th IEEE Int Conf on Intelligent Transportation Systems (ITSC 2012). Piscataway, NJ: IEEE, 2012: 140-146

[35]Coslovich L, Pesenti R, Ukovich W. A two-phase insertion technique of customers for a dynamic dial-a-ride problem[J]. European Journal of Operational Research, 2006, 175(3): 1605-1615

[36]Attanasio A, Cordeau J F, Ghiani G, et al. Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem[J]. Parallel Computing, 2004, 30(3): 377-387

[37]Huang Yan, Bastani F, Jin Ruoming, et al. Large scale real-time ridesharing with service guarantee on road networks[C]Proc of the 40th Int Conf on Very Large Data Bases. New York: VLDB Endowment, 2014: 2017-2028

[38]Armant V, Brown K N. Minimizing the driving distance in ride sharing systems[C]Proc of the 26th IEEE Int Conf on Tools with Artificial Intelligence (ICTAI 2014).Piscataway, NJ: IEEE, 2014: 568-575

[39]Li Baoxiang, Krushinsky D, Reijers H A, et al. The share-a-ride problem: People and parcels sharing taxis[J]. European Journal of Operational Research, 2014, 238(1): 31-40

[40]Xing Xin, Warden T, Nicolai T, et al. SMIZE: A spontaneous ride-sharing system for individual urban transit[C]Proc of the 7th German Conf on Multiagent System Technologies (MATES). Berlin: Springer, 2009: 165-176

[41]Agatz N, Erera A, Savelsbergh M, et al. Optimization for dynamic ride-sharing: A review[J]. European Journal of Operational Research, 2012, 223(2): 295-303

[42]Bardhi F, Eckhardt G M. Access-based consumption: The case of car sharing[J]. Journal of Consumer Research, 2012, 39(4): 881-898

[43]Shen Bilong, Huang Yan, Zhao Ying. Dynamic ridesharing[J]. SIGSPATIAL Special, 2015, 7(3): 3-11

[44]Mokbel M F, Xiong X, Aref W G. Sina: Scalable incremental processing of continuous queries in spatio-temporal databases[C]Proc of the 2004 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2004: 623-634

[45]Tao Yufei, Papadias D, Sun Jimeng. The TPR*-tree: An optimized spatio-temporal access method for predictive queries[C]Proc of the 29th Int Conf on Very Large Data Bases. Trondheim, Norway: VLDB Endowment, 2003: 790-801

[46]Zeitler E, Risch T. Massive scale-out of expensive continuous queries[C]Proc of the 37th Int Conf on Very Large Data Bases. Trondheim, Norway: VLDB Endowment, 2011: 1181-1188

[47]Yu Ziqiang, Liu Yang, Yu Xiaohui, et al. Scalable distributed processing ofKnearest neighbor queries over moving objects[J]. IEEE Trans on Knowledge and Data Engineering, 2015, 27(5): 1383-1396

[48]Cordeau J F. A branch-and-cut algorithm for the dial-a-ride problem[J]. Operations Research, 2006, 54(3): 573-586

[49]Kalantari B, Hill A V, Arora S R. An algorithm for the traveling salesman problem with pickup and delivery customers[J]. European Journal of Operational Research, 1985, 22(3): 377-386

[50]Herbawi W, Weber M. Ant colony vs genetic multiobjective route planning in dynamic multi-hop ridesharing[C]Proc of the 23rd IEEE Int Conf on Tools with Artificial Intelligence (ICTAI). Piscataway, NJ: IEEE, 2011: 282-288

[51]Herbawi W, Weber M. The ridematching problem with time windows in dynamic ridesharing: A model and a genetic algorithm[C]Proc of IEEE World Congress on Computa-tional Intelligence( WCCI 2012). Piscataway, NJ: IEEE, 2012: 1-8

[52]Santos D O, Xavier E C. Dynamic taxi and ridesharing: A framework and heuristics for the optimization problem[C]Proc of the 23rd Int Joint Conf on Artificial Intelligence(IJCAI). San Francisco: Morgan Kaufmann, 2013: 2885-2891

[53]Chaube V, Kavanaugh A L, Perez-Quinones M A. Leveraging social networks to embed trust in rideshare programs[C]Proc of the 43rd Hawaii Int Conf on System Sciences (HICSS). Piscataway, NJ: IEEE, 2010: 1-8

[54]Cici B, Markopoulou A, Frías-Martínez E, et al. Quantifying the potential of ride-sharing using call description records[C]Proc of the 14th Workshop on Mobile Computing Systems and Applications. New York: ACM, 2013: 17

[55]Artz D, Gil Y. A survey of trust in computer science and the semantic Web[J]. Web Semantics: Science, Services and Agents on the World Wide Web, 2007, 5(2): 58-71

[56]Yu Han, Shen Zhiqi, Miao Chunyan, et al. A survey of trust and reputation management systems in wireless communications[J]. Proceedings of the IEEE, 2010, 98(10): 1755-1772

[57]Witkowski J, Seuken S, Parkes D C. Incentive-compatible escrow mechanisms[C]Proc of the 25th AAAI Conf on Artificial Intelligence. Menlo Park: AAAI, 2011: 751-757

[58]Kamar E, Horvitz E. Collaboration and shared plans in the open world: Studies of ridesharing[C]Proc of the 21st Int Joint Conf on Artificial Intelligence (IJCAI).San Francisco: Morgan Kaufmann, 2009: 187-194

[59]Makowski L, Ostroy J M. Vickrey-Clarke-Groves mechanisms and perfect competition[J]. Journal of Economic Theory, 1987, 42(2): 244-261

[60]Cheng S F, Nguyen D T, Lau H C. Mechanisms for arranging ride sharing and fare splitting for last-mile travel demands[C]Proc of the 2014 Int Conf on Autonomous Agents and Multi-Agent Systems. New York: ACM, 2014: 1505-1506

[61]Zhao Dengji, Zhang Dongmo, Gerding E H, et al. Incentives in ridesharing with deficit control[C]Proc of the 2014 Int Conf on Autonomous Agents and Multi-Agent Systems. New York: ACM, 2014: 1021-1028

[62]Rayle L, Shaheen S, Chan N, et al. App-based, on-demand ride services: Comparing taxi and ridesourcing trips and user characteristics in San Francisco[R]. Berkeley: University of California Transportation Center, 2014: 1-19

[63]Ozenc F K, Cranor L F, Morris J H. Adapt-a-ride: Understanding the dynamics of commuting preferences through an experience design framework[C]Proc of the 2011 Conf on Designing Pleasurable Products and Interfaces. New York: ACM, 2011: 61

[64]Mirisaee S H, Brereton M, Roe P. Bridging the representation and interaction challenges of mobile context-aware computing: Designing agile ridesharing[C]Proc of the 23rd Australian Computer-Human Interaction Conf. New York: ACM, 2011: 221-224

[65]Radke K, Brereton M, Mirisaee S, et al. Tensions in developing a secure collective information practice-the case of agile ridesharing[C]Proc of the 13th Int Conf on Human-Computer Interaction (INTERACT 2011). Berlin: Springer, 2011: 524-532

[66]Fagnant D J. The future of fully automated vehicles: Opportunities for vehicle-and ride-sharing, with cost and emissions savings[D]. Austin: The University of Texas at Austin, 2014

Shen Bilong, born in 1984. PhD candidate. Student member of CCF. His main research interests include spatio-temporal data mining, urban computing, and machine learning.

Zhao Ying, born in 1977. PhD. Member of CCF. Her main research interests include data mining, machine learning.

Huang Yan, born in 1974. PhD supervisor. Her main research interests include spatio-temporal databases and mining, geo-stream data processing, smart transportation, and location-based social networks.

Zheng Weimin, born in 1946. PhD supervisor. Fellow member of CCF. His main research interests include grid and cluster computing, high performance storage system and big data analysis.

Survey on Dynamic Ride Sharing in Big Data Era

Shen Bilong1, Zhao Ying1, Huang Yan2, and Zheng Weimin1

1(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084)2(ComputerScienceandEngineeringDepartment,UniversityofNorthTexas,Denton,TX,USA311277)

The availability of multi-source data in big data era can potentially lead to a revolution in ride sharing, which has been widely studied in academia as a means of reducing the number of cars, congestion, and pollution by sharing empty seats, and is lack of popularity in practice due to the inflexibility of off-line booking, limited resources and so on. In big data era, dynamic ride sharing, powered by mobile computation, location based service, and social networks, emerges and gains popularities recently for providing real-time and flexible ride sharing services through real-time travel planning systems. These systems raise research opportunities as well as challenges, including how to process real-time location data and traffic data, to match ride requests and cars in real time, and to provide fair, secure, and low-priced services to gain more participants. This paper defines the problem of dynamic ride sharing formally and discusses its variants and recent developments. The framework of filter and refine to solve the real-time challenges of matching requests and cars is then discussed. In particular, in the filter step, we introduce the method of pre-computing, spatio-temporal index, grouping, and parallelizing. In the refine step, we introduce the method of lazy calculation strategy, new index tree structure, and evolutionary computation. We also discuss the techniques related to social factors such as pricing strategies, credit system, human-computer interaction, and security in big data era. Finally, this paper ends with a panoramic summary and a discussion on possible future research directions.

ride sharing; dynamic ride sharing; big data; optimization algorithm; urban computing

2015-08-10；

2016-05-09

TP391