沈弼龍 趙 穎 黃 艷 鄭緯民

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

大數(shù)據(jù)背景下動態(tài)共乘的研究進(jìn)展

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

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

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

共乘;動態(tài)共乘;大數(shù)據(jù);優(yōu)化算法;城市計(jì)算

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

1 共乘問題概述

1.1 共乘發(fā)展歷史

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

1.2 共乘發(fā)展現(xiàn)狀

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

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

Fig. 1 Dynamic ride sharing system framework圖1 動態(tài)共乘系統(tǒng)框架示意圖

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

2 動態(tài)共乘問題定義

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

2.1 動態(tài)共乘系統(tǒng)概覽

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

2.2 動態(tài)共乘基本概念

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

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

Fig. 2 Request time window圖2 服務(wù)請求時(shí)間窗口示意圖

將給定路網(wǎng)G上，當(dāng)前時(shí)刻所有行程請求的集合記為TR.

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

將給定路網(wǎng)G上，當(dāng)前時(shí)刻所有車輛的集合記為C=Car.

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

定義5. 動態(tài)共乘問題.給定路網(wǎng)G上的車輛集合C和服務(wù)請求集合TR，將不同的服務(wù)請求分配到不同車輛并進(jìn)行行程安排，使車輛在滿足動態(tài)共乘約束的條件下，達(dá)成一定的優(yōu)化目標(biāo).

在后面的2.3節(jié)和2.4節(jié)中將分別介紹動態(tài)共乘需滿足的約束條件和優(yōu)化目標(biāo).

2.3 動態(tài)共乘約束條件分析

定義6. 有效分配.給定車輛Car與一個(gè)單獨(dú)的服務(wù)請求tr，當(dāng)他們的匹配滿足共乘約束時(shí)，稱該匹配為有效分配.

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

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

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

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

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

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

請求的乘客數(shù)小于或等于車上空位數(shù)：

(1)

乘客可在規(guī)定時(shí)間窗口內(nèi)完成請求:

?tri∈Car.TRrec,

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

(2)

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

(3)

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

Table1 Constraint Conditions of Dynamic Ride Sharing

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

2.4 動態(tài)共乘優(yōu)化目標(biāo)

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

2.4.1 降低車輛行程開銷

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

2.4.2 提高共乘匹配成功率

當(dāng)處理n輛車、m個(gè)服務(wù)請求時(shí)，還有一個(gè)總體目標(biāo)：匹配成功率.

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

綜上，動態(tài)共乘主要有總體開銷最小化、響應(yīng)時(shí)間最小化、匹配成功率最大化等優(yōu)化目標(biāo)：

總體開銷最小化,即：

(4)

匹配成功率最大化,即：

(5)

近年來，動態(tài)共乘的研究工作的優(yōu)化目標(biāo)也不盡相同，總結(jié)起來如表2所示.

Table2 Optimization Goal of Dynamic Ride Sharing

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

3 動態(tài)共乘問題分類

動態(tài)共乘問題按共乘的完成方式與車上乘客的數(shù)量可分為單車輛單乘客、單車輛多乘客、多車輛單乘客、多車輛多乘客4種[41].不同類型的共乘模型適用于不同的應(yīng)用場景，采用的優(yōu)化方法也不同，本節(jié)對動態(tài)共乘的不同分類進(jìn)行介紹.其中，單車輛多乘客模型最為典型，是本文的重點(diǎn).

3.1 單車輛單乘客動態(tài)共乘

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

3.2 單車輛多乘客動態(tài)共乘

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

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

3.3 多車輛單乘客動態(tài)共乘

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

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

3.4 多車輛多乘客動態(tài)共乘

多車輛多乘客模型可以看成是多車輛單乘客動態(tài)共乘模型的進(jìn)一步擴(kuò)展，即利用多個(gè)車輛進(jìn)行多個(gè)乘客的輸送.對這種模型擴(kuò)展，還可以松弛車輛行駛中的司機(jī)身份限制，即在行程中可切換司機(jī)，在某段路上原來充當(dāng)乘客的人可以充當(dāng)駕駛員駕駛車輛.這種模型可以應(yīng)用于租賃汽車中，如可隨時(shí)租賃使用的ZipCar[42]，車輛的租用者可以通過智能規(guī)劃、角色互換實(shí)現(xiàn)出行成本的最優(yōu)化.

4 動態(tài)共乘優(yōu)化主要方法

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

4.1 動態(tài)共乘優(yōu)化問題的復(fù)雜性

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

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

4.2 動態(tài)共乘優(yōu)化問題實(shí)時(shí)性需求

定義11. 響應(yīng)時(shí)間.Timecomp=tri.tget-tri.treq，其中，tri.treq表示服務(wù)請求發(fā)起時(shí)間，tri.tget表示系統(tǒng)判斷新請求能否被成功匹配的時(shí)間.降低響應(yīng)時(shí)間以滿足動態(tài)共乘的實(shí)時(shí)性需求，是決定大數(shù)據(jù)背景下動態(tài)共乘應(yīng)用效果的關(guān)鍵技術(shù)之一.

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

4.3 動態(tài)共乘優(yōu)化的Filter and Refine框架

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

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

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

4.4 Filter主要方法

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

4.4.1 預(yù)先計(jì)算可行解的優(yōu)化方法

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

4.4.2 建立動態(tài)空間索引優(yōu)化方法

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

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

4.4.3 基于請求分組預(yù)處理及并行優(yōu)化方法

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

FEC(tri,trj)=

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

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

FEC(tr1,tr2)=

FEC(tr1,tr3)=

AC({tr1,tr2,tr3})=

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

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

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

4.5 Refine主要方法

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

4.5.1 簡化計(jì)算模型的優(yōu)化方法

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

4.5.2 利用新型樹結(jié)構(gòu)的優(yōu)化方法

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

Fig. 10 Kinetic Tree for trip schedules[37].圖10 利用Kinetic Tree方法優(yōu)化行程規(guī)劃示意圖[37]

4.5.3 利用啟發(fā)式算法的優(yōu)化方法

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

5 動態(tài)共乘人文影響

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

5.1 信用體系

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

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

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

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

5.2 價(jià)格機(jī)制

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

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

5.3 信息交互與隱私問題

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

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

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

6 共乘問題展望

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

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

[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)(張小曳, 孫俊英, 王亞強(qiáng), 等. 我國霧-霾成因及其治理的思考[J]. 科學(xué)通報(bào),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)(楊杰, 李小平, 陳湉. 基于增量時(shí)空軌跡大數(shù)據(jù)的群體挖掘方法[J]. 計(jì)算機(jī)研究與發(fā)展, 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) (湯黎明, 劉其華. 鄰里合乘——社區(qū)拼車常態(tài)化的探索[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)(邵增珍, 王洪國, 劉弘, 等. 多車輛合乘問題的兩階段聚類啟發(fā)式優(yōu)化算法[J]. 計(jì)算機(jī)研究與發(fā)展,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