徐 毅 童詠昕 李 未

(軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室(北京航空航天大學(xué)) 北京 100191) (北京航空航天大學(xué)計(jì)算機(jī)學(xué)院 北京 100191)

拼車，也即“合乘”、“共乘”和“順風(fēng)車”，是指多位擁有不同起終點(diǎn)位置的乘客經(jīng)協(xié)商共同乘坐同一輛車并分擔(dān)費(fèi)用的共享出行模式.拼車因其社會(huì)和經(jīng)濟(jì)價(jià)值而得到了廣泛應(yīng)用，也逐漸由原先熟人間的小范圍共乘變?yōu)槿缃袷忻耖g的大規(guī)模拼車.當(dāng)下越來越多的共享出行平臺(tái)推出拼車服務(wù)，例如滴滴出行公司的拼車業(yè)務(wù)、Uber公司的UberPool業(yè)務(wù)和ExpressPool業(yè)務(wù)、Lyft公司的Lyft Line業(yè)務(wù)、Waze公司的Waze Carpool業(yè)務(wù)等[1-5].同時(shí)，拼車的參與規(guī)模也呈爆發(fā)式增長(zhǎng).據(jù)統(tǒng)計(jì)，2016年滴滴出行公司的拼車業(yè)務(wù)覆蓋全國(guó)超過300個(gè)城市，日均訂單量超過157萬.

較之拼車而言，另一種傳統(tǒng)的共享出行模式為出租車，俗稱打車，即乘客臨時(shí)雇傭汽車并按里程付費(fèi)的出行模式.在出租車模式中，每位司機(jī)在同一時(shí)間段內(nèi)最多服務(wù)于單一訂單.而在拼車模式中，每位司機(jī)在同一時(shí)間段內(nèi)可服務(wù)于多個(gè)行程間有重疊的訂單.正是二者服務(wù)模式的差異，導(dǎo)致其核心算法模型有著本質(zhì)區(qū)別.具體而言，打車模式聚焦于每個(gè)訂單與每位司機(jī)之間的匹配滿意度，因此其算法原型為二分圖匹配；而拼車模式更關(guān)心各訂單之間協(xié)作的滿意度，并通過合理的路線規(guī)劃來優(yōu)化所有訂單與司機(jī)間的滿意度，其本質(zhì)算法模型為撥號(hào)叫車問題(dial-a-ride problem, DARP)，即為1個(gè)司機(jī)規(guī)劃1條路線來完成由多個(gè)乘客發(fā)出的運(yùn)送請(qǐng)求從而最小化總行駛距離的問題[6].特別是，從問題的計(jì)算復(fù)雜性分析視角可見，適用于打車模式的二分圖匹配問題在多項(xiàng)式時(shí)間內(nèi)可求得最優(yōu)解，而DARP屬于NP-難問題[6].因此，求解拼車問題即使在小規(guī)模靜態(tài)場(chǎng)景中也具有相當(dāng)?shù)碾y度與挑戰(zhàn).

近年來，移動(dòng)互聯(lián)網(wǎng)與普適計(jì)算技術(shù)日益普及，給拼車問題帶來了數(shù)據(jù)量大、動(dòng)態(tài)性強(qiáng)、目標(biāo)多樣、應(yīng)用范圍廣的新特點(diǎn).在此背景下，拼車問題也逐漸演變?yōu)榇笠?guī)模拼車問題.例如在2017年，滴滴出行公司的拼車業(yè)務(wù)累計(jì)分享座位數(shù)達(dá)到10.5億個(gè)，涉及到的數(shù)據(jù)規(guī)模龐大.此外，在拼車需求高峰時(shí)段每秒就有可能產(chǎn)生上百個(gè)拼車訂單，平臺(tái)需要在秒級(jí)時(shí)間內(nèi)做出響應(yīng)，數(shù)據(jù)產(chǎn)生的動(dòng)態(tài)性強(qiáng).同時(shí)，大規(guī)模拼車問題中平臺(tái)、司機(jī)和乘客等各參與方都有各自的目標(biāo)：平臺(tái)期望更高的收益，司機(jī)期望更多的接單量，而乘客則期望更高效的出行時(shí)間，因此求解大規(guī)模拼車問題還需考慮目標(biāo)的多樣性.最后，拼車問題還具有廣泛的應(yīng)用，衍生出如送餐、最后一公里配送等一系列變種應(yīng)用.上述這些新挑戰(zhàn)導(dǎo)致原本針對(duì)小規(guī)模應(yīng)用的拼車算法失效，求解大規(guī)模拼車問題的難度上升，因而催生了大量針對(duì)大規(guī)模拼車問題的新理論、算法、優(yōu)化與實(shí)現(xiàn)的學(xué)術(shù)研究.同時(shí)，為實(shí)現(xiàn)產(chǎn)品級(jí)拼車應(yīng)用，激勵(lì)機(jī)制、隱私保護(hù)、人身安全保障等關(guān)于社會(huì)影響因素的實(shí)際問題也是大規(guī)模拼車問題的相關(guān)研究熱點(diǎn).

本文總結(jié)近年來大規(guī)模拼車算法的最新研究進(jìn)展，做出了3點(diǎn)貢獻(xiàn)：

1) 重點(diǎn)回顧了當(dāng)前大規(guī)模拼車平臺(tái)的核心算法問題——路線規(guī)劃問題，并從偏好角度、優(yōu)化目標(biāo)、業(yè)務(wù)場(chǎng)景、時(shí)間復(fù)雜性、近似理論分析等多個(gè)維度對(duì)相關(guān)算法研究進(jìn)行了系統(tǒng)性的分析和比較；

2) 對(duì)實(shí)際拼車應(yīng)用驅(qū)動(dòng)的一系列社會(huì)影響因素(如激勵(lì)機(jī)制、隱私保護(hù)和人身安全保障等)的研究進(jìn)展進(jìn)行了詳細(xì)的闡述和討論；

3) 結(jié)合現(xiàn)有研究的不足之處，展望了拼車技術(shù)的未來潛在研究方向，為相關(guān)科研人員和從業(yè)者提供了有價(jià)值的參考.

1 拼車問題概述

本節(jié)首先介紹拼車問題涉及的基本概念與定義，隨后介紹本綜述與現(xiàn)有相關(guān)綜述的區(qū)別，最后介紹大規(guī)模拼車平臺(tái)的通用工作流程.

1.1 問題定義介紹

首先介紹拼車問題涉及的3個(gè)基本概念，即司機(jī)、訂單與平臺(tái).

定義1.司機(jī).拼車問題中的1位司機(jī)用w表示，它包含司機(jī)的初始位置、汽車容量等屬性.1個(gè)由m位司機(jī)組成的集合表示為W={w1,w2,…,wm}.

定義2.訂單.拼車問題中的1個(gè)訂單用r表示.乘客向平臺(tái)提交拼車請(qǐng)求(也稱為發(fā)布請(qǐng)求)，平臺(tái)收到請(qǐng)求并生成1個(gè)完整的訂單.1個(gè)訂單包含的屬性有：請(qǐng)求的發(fā)布時(shí)間、乘客的起點(diǎn)(即上車地點(diǎn))、乘客的終點(diǎn)(即下車地點(diǎn))、截止時(shí)間與乘客數(shù)量.1個(gè)由n個(gè)訂單組成的集合表示為R={r1,r2,…,rn}.

在拼車問題中，如果1個(gè)訂單在發(fā)布后被司機(jī)接受，且在其截止時(shí)間之前司機(jī)將乘客送達(dá)其終點(diǎn)，則稱為司機(jī)完成了該訂單.司機(jī)w被指派的訂單用集合Rw表示.

定義3.平臺(tái).拼車問題中的平臺(tái)用P表示，其擁有一定數(shù)量的司機(jī)(來自司機(jī)集合W，同時(shí)收到一系列訂單(來自訂單集合R).平臺(tái)將訂單分配給司機(jī)，為司機(jī)規(guī)劃行駛路線，并最終通過司機(jī)完成的訂單獲取收益.

根據(jù)定義1～3，下文介紹拼車的核心問題，即路線規(guī)劃問題.

定義4.路線.給定司機(jī)w與其被指派的訂單集合Rw.司機(jī)w的路線Sw定義為由w的起始位置與訂單的起點(diǎn)或終點(diǎn)構(gòu)成的1個(gè)序列，即Sw={l0,l1,…,lk}.其中，l0是司機(jī)w的起始位置，l1,…,lk是集合Rw中某個(gè)訂單的起點(diǎn)或終點(diǎn).

在實(shí)際應(yīng)用和現(xiàn)有文獻(xiàn)中，一條可行的路線還需要滿足一定約束條件，這些約束條件通常包括：

1) 順序約束.在一條可行路線中，任意訂單的起點(diǎn)應(yīng)該出現(xiàn)在它的終點(diǎn)之前，即司機(jī)需要先行駛至起點(diǎn)接取乘客、再行駛至終點(diǎn)送達(dá)乘客.

2) 容量約束.在任意時(shí)刻，每位司機(jī)乘載的乘客總?cè)藬?shù)不得超過該輛汽車的容量.

3) 截止時(shí)間約束.每位乘客需要在其訂單的截止時(shí)間之前被送達(dá)至終點(diǎn).

4) 不可撤回約束.一旦平臺(tái)指派并通知某個(gè)司機(jī)完成某個(gè)訂單，則該指派決定不可撤回.

5) 繞路約束.在一條可行路線中，每位乘客的繞路距離不超過某個(gè)閾值.這里繞路距離等于乘客由于參與拼車而多繞行的距離.

基于定義1～4，一個(gè)通用的路線規(guī)劃問題見定義5.

定義5.路線規(guī)劃.在拼車問題中，給定司機(jī)集合W、訂單集合R和平臺(tái)P.路線規(guī)劃問題旨在為每位司機(jī)w∈W決定一條滿足某些約束條件的行駛路線Sw，并使得某個(gè)優(yōu)化目標(biāo)達(dá)到最優(yōu).

在現(xiàn)有研究中，不同的偏好角度往往決定了不同的優(yōu)化目標(biāo).例如，基于司機(jī)角度的優(yōu)化目標(biāo)包括最小化司機(jī)的行駛總距離、最小化司機(jī)的最大完工時(shí)間；基于乘客角度的優(yōu)化目標(biāo)包括最小化乘客的等待時(shí)間、最大化乘客的社會(huì)效用；基于平臺(tái)角度的優(yōu)化目標(biāo)包括最大化平臺(tái)的訂單完成數(shù)以及最大化平臺(tái)的總收入等.除這些優(yōu)化目標(biāo)外，文獻(xiàn)[7]還提出了1個(gè)靈活、泛化的目標(biāo)函數(shù).通過調(diào)節(jié)合適的參數(shù)，該目標(biāo)函數(shù)可以等價(jià)地轉(zhuǎn)換為不同偏好角度的優(yōu)化目標(biāo).第2節(jié)將對(duì)與路線規(guī)劃相關(guān)的文獻(xiàn)進(jìn)行具體地分析和總結(jié).

1.2 現(xiàn)存綜述區(qū)別

拼車問題的算法原型可追溯到撥號(hào)叫車問題.現(xiàn)存關(guān)于拼車算法的綜述可分為2類：撥號(hào)叫車問題的綜述和拼車技術(shù)綜述，下面將進(jìn)一步闡述本文與此2類現(xiàn)存工作區(qū)別.

1.2.1 與撥號(hào)叫車問題綜述的區(qū)別

撥號(hào)叫車問題是運(yùn)籌學(xué)研究中的一個(gè)經(jīng)典的算法理論問題，已有一些運(yùn)籌學(xué)領(lǐng)域研究對(duì)求解該問題的相關(guān)算法進(jìn)行了總結(jié)[6-12].其中，綜述性文獻(xiàn)[7-12]均發(fā)表于2013年之前，并沒有系統(tǒng)地討論近年來的拼車算法的相關(guān)文獻(xiàn).而近期的綜述性文獻(xiàn)[6]對(duì)基于拼車出行的撥號(hào)拼車問題進(jìn)行了系統(tǒng)性的總結(jié)，該文獻(xiàn)主要討論理論層面的拼車路線規(guī)劃問題，而沒有考慮在真實(shí)應(yīng)用場(chǎng)景中大規(guī)模拼車所面臨的實(shí)際問題，如路網(wǎng)結(jié)構(gòu)、時(shí)空索引設(shè)計(jì)等，同時(shí)還缺少對(duì)拼車出行中如激勵(lì)機(jī)制、隱私保護(hù)等其他社會(huì)影響因素的系統(tǒng)性討論.

1.2.2 與拼車技術(shù)綜述的區(qū)別

現(xiàn)存關(guān)于拼車技術(shù)的系統(tǒng)性文獻(xiàn)綜述十分有限，僅有文獻(xiàn)[13].與文獻(xiàn)[13]相比，本文的主要區(qū)別與創(chuàng)新之處在于3點(diǎn)：

1) 文獻(xiàn)[13]覆蓋的文章多發(fā)表于2015年之前，滴滴出行、Uber等平臺(tái)剛剛推出自己的拼車應(yīng)用，拼車發(fā)展尚在萌芽階段，其未能囊括近4年來飛速發(fā)展的拼車新技術(shù)；而本文則關(guān)注近年來大規(guī)模拼車所具有的數(shù)據(jù)量大、動(dòng)態(tài)性強(qiáng)、目標(biāo)多樣、應(yīng)用范圍廣等新特性，總結(jié)了近4年新的相關(guān)論文以及核心技術(shù)的改進(jìn)，更具有時(shí)效性與全面性.

2) 文獻(xiàn)[13]側(cè)重于介紹一般化的拼車概念，因此基于簡(jiǎn)單的司機(jī)乘客數(shù)量對(duì)拼車問題進(jìn)行了分類，在算法上也僅僅介紹了Filter and Refine這一種拼車框架；而本文更注重拼車算法的研究，根據(jù)平臺(tái)角度、司機(jī)角度和乘客角度下的不同優(yōu)化目標(biāo)對(duì)大量拼車算法的研究文獻(xiàn)進(jìn)行了更深層次的分類、算法分析與對(duì)比，更具有深度性.

3) 文獻(xiàn)[13]在介紹拼車的社會(huì)影響因素時(shí)內(nèi)容較為簡(jiǎn)單寬泛；而本文針對(duì)每個(gè)社會(huì)影響因素調(diào)研了更全面的相關(guān)工作，并進(jìn)行了細(xì)致的分類與對(duì)比，更具有系統(tǒng)性.

1.3 平臺(tái)工作流程

拼車服務(wù)中的用戶主要由司機(jī)和乘客組成，他們通過拼車平臺(tái)建立聯(lián)系，分別構(gòu)成這一雙邊市場(chǎng)的供給與需求.典型的大規(guī)模拼車平臺(tái)有Uber、滴滴出行、Lyft、Grab、Via與Waze CarPool等[1-2,5,14-16].

如圖 1所示，大規(guī)模拼車平臺(tái)(簡(jiǎn)稱“平臺(tái)”)包含兩大主要模塊，即路線規(guī)劃與社會(huì)影響因素的相關(guān)解決方案(包括激勵(lì)機(jī)制、隱私保護(hù)與人身安全保障3個(gè)子模塊)，在這些模塊作用下，平臺(tái)通過司機(jī)與乘客的手機(jī)客戶端對(duì)二者進(jìn)行管理和分配.具體的工作流程有3個(gè)：

1) 提交訂單.提交訂單階段指的是乘客發(fā)起請(qǐng)求到平臺(tái)接受該請(qǐng)求的過程.在這個(gè)階段中，乘客提出一個(gè)拼車請(qǐng)求.平臺(tái)分別調(diào)用隱私保護(hù)與激勵(lì)機(jī)制模塊，首先通過隱私保護(hù)機(jī)制保護(hù)乘客的敏感信息(如位置信息)，并通過激勵(lì)機(jī)制對(duì)該請(qǐng)求進(jìn)行定價(jià).隨后，平臺(tái)將價(jià)格等信息發(fā)送給乘客，待乘客確認(rèn)或拒絕.如果乘客拒絕該價(jià)格，平臺(tái)將取消該訂單.

2) 路線規(guī)劃.路線規(guī)劃階段指的是平臺(tái)為訂單中的乘客指派司機(jī)并為該司機(jī)提供行駛路線的過程.在這一階段中，平臺(tái)調(diào)用路線規(guī)劃模塊，通過部署的路線規(guī)劃算法對(duì)乘客提交的訂單進(jìn)行分配，即根據(jù)內(nèi)部的優(yōu)化目標(biāo)指派某位司機(jī)服務(wù)該訂單，并為該司機(jī)規(guī)劃路線.

3) 完成訂單.完成訂單階段指的是司機(jī)執(zhí)行接送乘客任務(wù)以及乘客被送達(dá)終點(diǎn)后的處理過程.在司機(jī)執(zhí)行接送任務(wù)的過程中，平臺(tái)調(diào)用人身安全保障模塊來保護(hù)乘客與司機(jī)的人身安全.在乘客被送達(dá)后，平臺(tái)需要調(diào)用激勵(lì)機(jī)制模塊決定乘客需向平臺(tái)支付相應(yīng)的費(fèi)用，并接受乘客對(duì)司機(jī)的服務(wù)評(píng)價(jià)，同時(shí)決定司機(jī)從中獲取的報(bào)酬.

Fig. 1 The workflow of ridesharing platform圖1 拼車平臺(tái)的工作流程

2 路線規(guī)劃

路線規(guī)劃是大規(guī)模拼車平臺(tái)工作流程中最為核心的問題.對(duì)平臺(tái)而言，路線規(guī)劃算法往往決定了司機(jī)的工作效率、乘客的出行體驗(yàn)和平臺(tái)的盈利情況等.本節(jié)根據(jù)偏好角度的不同對(duì)現(xiàn)有路線規(guī)劃的相關(guān)研究進(jìn)行分類，分別從司機(jī)角度(2.1節(jié))、乘客角度(2.2節(jié))和平臺(tái)角度(2.3節(jié))對(duì)現(xiàn)有文獻(xiàn)進(jìn)行闡述和分析，最后對(duì)這些文獻(xiàn)進(jìn)行了總結(jié)(2.4節(jié)).

2.1 基于司機(jī)角度的路線規(guī)劃

對(duì)司機(jī)而言，其通常希望以更短的距離服務(wù)指派的訂單，或在更短的時(shí)間內(nèi)完成被指派的訂單.因此，從司機(jī)的角度進(jìn)行路線規(guī)劃，常用的優(yōu)化目標(biāo)包括最小化司機(jī)行駛總距離和最小化司機(jī)最大完工時(shí)間.

2.1.1 最小化司機(jī)行駛總距離的路線規(guī)劃

最小化行駛距離是解決拼車中路線規(guī)劃問題的文獻(xiàn)中主要的優(yōu)化目標(biāo).這一類問題的基本模型即1.2節(jié)所述的撥號(hào)叫車問題.該問題為單個(gè)司機(jī)和多個(gè)訂單進(jìn)行路線規(guī)劃，從而在滿足一定約束的條件下最小化司機(jī)的行駛距離.根據(jù)業(yè)務(wù)場(chǎng)景的不同，這部分研究又可分為2類，即針對(duì)靜態(tài)場(chǎng)景的研究和針對(duì)動(dòng)態(tài)場(chǎng)景的研究.在靜態(tài)場(chǎng)景中，通常假設(shè)所有訂單的信息初始即已知；而在動(dòng)態(tài)場(chǎng)景中，訂單信息僅在發(fā)布時(shí)才能由平臺(tái)獲知.由于信息的不確定性，動(dòng)態(tài)場(chǎng)景中的路線規(guī)劃問題通常難于它在靜態(tài)場(chǎng)景下的對(duì)應(yīng)問題.

Fig. 2 An illustration of the insertion operation圖2 插隊(duì)操作的示意圖

此后，Gupta等人[20-21]針對(duì)拼車中最小化行駛距離的路線規(guī)劃問題，提出了基于k-森林問題的近似算法，該算法具有近似比保證.具體來說，k-森林問題旨在從n對(duì)起點(diǎn)和終點(diǎn)中選擇k對(duì)構(gòu)成1個(gè)連通子圖，并使得該子圖的連通花銷最少.文獻(xiàn)[20]所提出算法的基本思路是將k-森林問題中的k值設(shè)置成司機(jī)的容量大小，從而使用k-森林問題的近似算法每次從余下訂單中選出不超過k個(gè)訂單(即不超過容量限制).

近年來，更多的文獻(xiàn)關(guān)注拼車平臺(tái)中動(dòng)態(tài)場(chǎng)景(也稱為實(shí)時(shí)場(chǎng)景)下的路線規(guī)劃問題. 其中，這些文獻(xiàn)提出的算法主要可以分成2類：基于插隊(duì)的算法和基于匹配的算法.

為了在動(dòng)態(tài)場(chǎng)景下解決以最小化行駛距離為目標(biāo)的路線規(guī)劃問題，大多數(shù)文獻(xiàn)[22-25]基于插隊(duì)操作來設(shè)計(jì)算法.插隊(duì)操作最早由Jaw等人[26]提出，其基本思想如圖2所示.在執(zhí)行1次插隊(duì)操作之前，首先給定司機(jī)的當(dāng)前行駛路線和1個(gè)新發(fā)布的訂單，而插隊(duì)操作旨在將這個(gè)新訂單的起點(diǎn)和終點(diǎn)分別插入到原有路線中，從而獲得新的路線并使得司機(jī)的行駛距離盡可能短.對(duì)于這對(duì)起點(diǎn)與終點(diǎn)插入位置，插隊(duì)操作共有如圖2所示的3種情況：1)新訂單的起點(diǎn)和終點(diǎn)相鄰地添加至當(dāng)前路線的末尾(情況1)；2)新訂單的起點(diǎn)和終點(diǎn)相鄰地插入至當(dāng)前路線的開始位置或中間位置(情況2)；3)新訂單的起點(diǎn)和終點(diǎn)不相鄰地插入到當(dāng)前路線的中間位置(情況3).值得一提的是，插隊(duì)這一操作不僅適用于動(dòng)態(tài)場(chǎng)景，也經(jīng)常被應(yīng)用于靜態(tài)場(chǎng)景中.

Ma等人[24-25]將插隊(duì)操作應(yīng)用到面向路網(wǎng)的路線規(guī)劃問題中.他們實(shí)現(xiàn)了一個(gè)時(shí)間復(fù)雜度為O(n3)的插隊(duì)算法，其基本思想是分別枚舉新訂單中起點(diǎn)和終點(diǎn)的插入位置并檢查新路線是否滿足約束條件，在所有滿足約束條件的路線中選擇距離增量最短的一條作為新路線.為了解決多個(gè)司機(jī)、多個(gè)訂單的路線規(guī)劃問題，他們提出了T-Share框架.該框架能夠?qū)崟r(shí)地處理每個(gè)訂單，并依據(jù)截止時(shí)間等時(shí)空約束條件篩選可被分配的司機(jī)，從而通過插隊(duì)操作計(jì)算每個(gè)篩選后的司機(jī)為了服務(wù)新訂單所增加的行駛距離，最終指派行駛距離增加最少的司機(jī)來完成該訂單.為了加快算法的運(yùn)行時(shí)間，他們還采用了基于網(wǎng)格的空間索引以及雙向搜索算法來篩選司機(jī).實(shí)驗(yàn)證明：與不使用拼車算法的出行方式比較，他們提出的算法能夠在多完成25%訂單量的同時(shí)減少13%的行駛距離.

在T-Share框架的基礎(chǔ)上，Huang等人[23]提出了一種基于字典樹的數(shù)據(jù)結(jié)構(gòu)，即活動(dòng)樹(kinetic tree).在活動(dòng)樹中，每條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑都代表了對(duì)應(yīng)司機(jī)在當(dāng)前時(shí)刻下的一條可行路線，而司機(jī)總是按照總距離最短的路線行駛.每當(dāng)一個(gè)新訂單到來時(shí)，他們提出的算法通過在活動(dòng)樹上遞歸的方式計(jì)算新訂單插隊(duì)后增加的行駛距離，其中每次插隊(duì)操作需要O(n2)的時(shí)間復(fù)雜度.最后，該算法將保留所有滿足約束條件的可行路線并相應(yīng)地更新整棵活動(dòng)樹.由于可行路線的數(shù)量在最壞情況下會(huì)達(dá)到指數(shù)級(jí)，他們還進(jìn)一步提出了基于熱點(diǎn)聚類的活動(dòng)樹(hotspot-based kinetic tree).考慮到其良好的實(shí)驗(yàn)結(jié)果，該數(shù)據(jù)結(jié)構(gòu)被部分相關(guān)文獻(xiàn)[27-28]所采納和應(yīng)用.

Santi等人在文獻(xiàn)[29]中同樣采用了插隊(duì)算法來解決拼車的路線規(guī)劃問題.首先，他們嘗試將不同的訂單聚合成組.其次，將所有的組按照距離排序.然后，盡可能多地將每個(gè)組內(nèi)的訂單插入到當(dāng)前司機(jī)的路線中.特別地，他們采用一種基于批次(batch)的路線規(guī)劃方法，即每隔一段時(shí)間對(duì)當(dāng)前批次內(nèi)積攢的訂單獨(dú)立進(jìn)行路線規(guī)劃.

在文獻(xiàn)[23-25，29]中，插隊(duì)操作存在著時(shí)間復(fù)雜度較高的缺陷.為了解決這一缺陷，Tong等人在文獻(xiàn)[22]中首次提出了基于動(dòng)態(tài)規(guī)劃的插隊(duì)算法，將時(shí)間復(fù)雜度從平方復(fù)雜度降低為線性復(fù)雜度，并進(jìn)一步提出了基于線性時(shí)間插隊(duì)操作的通用框架，大幅度減少了在路網(wǎng)中進(jìn)行冗余的最短路徑查詢.通過在大規(guī)模路網(wǎng)上進(jìn)行真實(shí)數(shù)據(jù)的實(shí)驗(yàn)測(cè)試，該文獻(xiàn)證實(shí)了其所提出的算法pruneGreedyDP遠(yuǎn)遠(yuǎn)優(yōu)于文獻(xiàn)[23-24,29]所提出的算法.通常情況下，文獻(xiàn)[22]提出的算法可以提升優(yōu)化目標(biāo)多達(dá)12.8倍，同時(shí)其運(yùn)行時(shí)間還降低至4.83%.

除基于插隊(duì)操作的算法外，基于匹配模型的算法也在相關(guān)文獻(xiàn)中得到應(yīng)用[30-31].在文獻(xiàn)[30]中，作者假設(shè)每輛車的容量不超過2，并在這個(gè)前提下為每位司機(jī)規(guī)劃路線.作者首先從3維匹配問題進(jìn)行規(guī)約，證明了該特殊情況下的路線規(guī)劃問題依然屬于NP-難問題[32].文獻(xiàn)[30]進(jìn)一步提出了近似比為2.5的近似算法解決靜態(tài)場(chǎng)景下的路線規(guī)劃問題.該算法的基本思想是先枚舉每2位乘客拼單的所有情況，再構(gòu)建表示司機(jī)和枚舉路線間關(guān)系的二分圖，然后通過求解二分圖最小權(quán)和匹配的匈牙利算法找到近似解[33].

與之不同地，文獻(xiàn)[31]聚焦在動(dòng)態(tài)場(chǎng)景下的路線規(guī)劃算法，并采用了基于批次的分單方法.此外，該文獻(xiàn)假設(shè)同一批次內(nèi)的訂單不會(huì)被分配到同一輛車中，從而構(gòu)建能夠表示司機(jī)與該批次訂單關(guān)系的二分圖.最終，Ta等人[31]通過執(zhí)行二分圖上的連接操作完成對(duì)每位司機(jī)的路線規(guī)劃.

2.1.2 最小化司機(jī)最大完工時(shí)間的路線規(guī)劃

盡管大多數(shù)從司機(jī)角度優(yōu)化路線的文獻(xiàn)旨在減少行駛總距離，仍有少部分文獻(xiàn)[34-36]聚焦在最小化所有司機(jī)中的最大完工時(shí)間，即最小化所有司機(jī)完成最后一個(gè)訂單的時(shí)間.

Ascheuer等人[35]主要解決動(dòng)態(tài)場(chǎng)景下面向單個(gè)司機(jī)和多個(gè)訂單的基于最小化司機(jī)的最大完工時(shí)間的路線規(guī)劃問題.他們首先提出了2種解決框架：重新規(guī)劃框架(REPLAN)和暫時(shí)遺忘框架(IGNORE).重新規(guī)劃框架的核心思想是對(duì)于每個(gè)新到來的訂單，都實(shí)時(shí)地與當(dāng)前未完成的訂單一起重新執(zhí)行路線規(guī)劃算法.相應(yīng)地，暫時(shí)遺忘框架的核心思想是先由司機(jī)按照原有路線完成部分訂單后，再對(duì)積攢的訂單統(tǒng)一進(jìn)行路線規(guī)劃，最后由司機(jī)繼續(xù)完成這些被暫時(shí)“遺忘”的訂單.顯然，后者執(zhí)行的面向單個(gè)司機(jī)和多個(gè)訂單的路線規(guī)劃算法次數(shù)更少，因此其運(yùn)行時(shí)間通常更短.同時(shí)，他們還證明了2個(gè)框架在對(duì)手模型(adversarial model)下的競(jìng)爭(zhēng)比都是2.5ρ，這里ρ表示靜態(tài)場(chǎng)景下解決面向單個(gè)司機(jī)和多個(gè)訂單的最小化行駛距離的近似算法的近似比.最后，結(jié)合2種算法，他們提出了一種智能啟動(dòng)(SMARTSTAT)算法，該算法能夠自適應(yīng)地對(duì)積攢的訂單執(zhí)行面向單個(gè)司機(jī)和多個(gè)訂單的路線規(guī)劃算法，并將競(jìng)爭(zhēng)比提高到2ρ.

2.1.3 司機(jī)角度路線規(guī)劃小結(jié)

表1總結(jié)了基于司機(jī)角度進(jìn)行路線規(guī)劃的主要算法研究.

Table 1 The Summary of Algorithms on Route Planning from Drivers’ Perspective表1 基于司機(jī)角度的路線規(guī)劃算法總結(jié)

就算法的應(yīng)用場(chǎng)景而言，可以發(fā)現(xiàn)當(dāng)前研究趨勢(shì)正從靜態(tài)場(chǎng)景轉(zhuǎn)變?yōu)楦油ㄓ玫膭?dòng)態(tài)場(chǎng)景，且近期研究多針對(duì)大規(guī)模的拼車數(shù)據(jù)(訂單量最高可達(dá)到百萬級(jí)別)，這也反映了人們?nèi)粘３鲂兄袑?duì)拼車服務(wù)的需求和依賴[22].

就算法的運(yùn)行效率而言，通過比較算法時(shí)間復(fù)雜度可以發(fā)現(xiàn)：文獻(xiàn)[22]所提出的算法prune-GreedyDP具有最低的時(shí)間復(fù)雜度，并通過大規(guī)模的真實(shí)數(shù)據(jù)驗(yàn)證了算法的實(shí)際運(yùn)行效率.此外，這些算法往往需要通過大量的插隊(duì)操作來規(guī)劃路線，因此，如何高效地將插隊(duì)操作與時(shí)空索引結(jié)合，是未來進(jìn)一步提升算法運(yùn)行效率的潛在方法.

就算法的近似效果而言，通過比較算法近似比或競(jìng)爭(zhēng)比可以發(fā)現(xiàn)，現(xiàn)有研究?jī)H在單個(gè)司機(jī)的情況下具有近似效果的理論保證.當(dāng)問題變得更加復(fù)雜時(shí)(例如多個(gè)司機(jī)的情況)，暫無研究提出具有理論保證的近似算法.基于此，是否存在更通用問題場(chǎng)景下對(duì)數(shù)階乃至常數(shù)階近似比或競(jìng)爭(zhēng)比的算法仍是一個(gè)開放問題.

2.2 基于乘客角度的路線規(guī)劃

在對(duì)拼車請(qǐng)求進(jìn)行路線規(guī)劃時(shí)，乘客往往希望該路線盡量少繞路從而可以盡快到達(dá)終點(diǎn).此外，最新研究表明乘客還希望能夠與彼此間友好的乘客共享行程.因此，從乘客的角度進(jìn)行路線規(guī)劃，常用的優(yōu)化目標(biāo)通常包括最小化等待時(shí)間和最大化社會(huì)效用.

2.2.1 最小化乘客等待時(shí)間的路線規(guī)劃

在大規(guī)模拼車問題中，乘客在向平臺(tái)提出請(qǐng)求后，往往希望能夠盡快到達(dá)其終點(diǎn).從乘客角度進(jìn)行路線規(guī)劃，一個(gè)很自然的想法就是最小化乘客的等待時(shí)間.

Psaraftis[37]于1980年使用所有乘客中的最大等待時(shí)間衡量乘客的不滿意程度，即以最小化所有乘客中的最大等待時(shí)間為目標(biāo)來進(jìn)行路線規(guī)劃，進(jìn)一步證明了在拼車問題中基于該目標(biāo)的路線規(guī)劃問題屬于NP-難問題.因此，他們提出了一個(gè)指數(shù)時(shí)間復(fù)雜度的精確算法，可以解出小數(shù)據(jù)規(guī)模下(訂單數(shù)量通常不超過10)的最優(yōu)解解.為了解決更大規(guī)模訂單下的路線規(guī)劃問題，Jaw等人[26]采用了基于最小化乘客的最大等待時(shí)間的插隊(duì)操作，即以最小化乘客的最大等待時(shí)間作為插隊(duì)操作的優(yōu)化目標(biāo).其基本思想是枚舉每個(gè)訂單來嘗試插入到所有司機(jī)的已規(guī)劃路線中，并最終把訂單指派給使得最大等待時(shí)間增加最小的司機(jī).盡管該算法的時(shí)間復(fù)雜度從指數(shù)時(shí)間降低到了多項(xiàng)式時(shí)間，但卻依然只能快速地處理訂單總數(shù)不超過3 000規(guī)模的數(shù)據(jù).該算法低效的主要原因是其對(duì)插隊(duì)操作的實(shí)現(xiàn)需要3次方的時(shí)間復(fù)雜度，為了降低這一操作帶來的時(shí)間開銷，Xu等人[38]提出了基于動(dòng)態(tài)規(guī)劃的插隊(duì)算法.其核心思想是通過動(dòng)態(tài)規(guī)劃將查詢最優(yōu)插隊(duì)位置的操作轉(zhuǎn)化為查詢特定區(qū)間最小值的操作，從而采用動(dòng)態(tài)區(qū)間的查詢索引(如線段樹或樹狀數(shù)組等)將時(shí)間復(fù)雜度降低到線性時(shí)間復(fù)雜度.實(shí)驗(yàn)證明該方法可將插隊(duì)操作加快最高達(dá)998.1倍.Krumke等人[39]研究了在動(dòng)態(tài)場(chǎng)景下最小化乘客的最大等待時(shí)間的路線規(guī)劃問題，并證明任何確定性或隨機(jī)算法都不存在常數(shù)競(jìng)爭(zhēng)比.

Fig. 3 An illustration of the RTV-Graph圖3 RTV-圖的數(shù)據(jù)結(jié)構(gòu)示意圖

2.2.2 最大化乘客社會(huì)效用的路線規(guī)劃

社會(huì)效用(social utility)一直是出行平臺(tái)中路線規(guī)劃問題的常用目標(biāo)之一[43-48].為了提高乘客在大規(guī)模拼車中的出行體驗(yàn)，現(xiàn)有文獻(xiàn)也開始關(guān)注拼車服務(wù)中共享行程的乘客之間、司機(jī)與乘客之間的社交關(guān)系.例如，首先通過定義社會(huì)效用模型來表示乘客間是否適宜共享行程、是否具有相同偏好等社交關(guān)系，然后再根據(jù)社會(huì)效用模型進(jìn)行路線規(guī)劃.

Kameswaran等人[49]通過對(duì)Uber公司的司機(jī)及搭載的乘客進(jìn)行調(diào)研，發(fā)現(xiàn)了社交關(guān)系在拼車平臺(tái)中的重要性.具體地，文獻(xiàn)[49]發(fā)現(xiàn)乘客們往往希望能夠與性格相似的人共享行程，甚至希望在行駛過程中彼此可以通過交流打發(fā)時(shí)間.此外，還有一些乘客可以接受一些比較繞路的行駛路線，但前提條件是行駛途中可以經(jīng)過一些如風(fēng)景名勝等特定地點(diǎn).文獻(xiàn)[50-51]進(jìn)一步探究了大規(guī)模拼車問題中以最大化社會(huì)效用作為優(yōu)化目標(biāo)的路線規(guī)劃問題.其中，Cheng等人[50]在社會(huì)效用模型中既考慮了乘客間的社交網(wǎng)絡(luò)關(guān)系，還考慮了乘客與司機(jī)間的社交網(wǎng)絡(luò)關(guān)系.具體而言，乘客r和司機(jī)c之間的社會(huì)效用函數(shù)為

μ(r,c)=α×μv(r,c)+β×μr(r,c)+γ×μt(r,c),

其中，函數(shù)μv表示乘客r和司機(jī)c的社交因素指標(biāo)，函數(shù)μr表示乘客r和司機(jī)c所搭載的其他乘客間的社交因素指標(biāo)，函數(shù)μt表示乘客r對(duì)所規(guī)劃路線的滿意程度，而參數(shù)α,β,γ用來衡量三者之間的權(quán)重關(guān)系.文獻(xiàn)[50]進(jìn)一步提出了靜態(tài)場(chǎng)景中的以最大化社會(huì)效用為優(yōu)化目標(biāo)的路線規(guī)劃問題，并證明了該問題不存在任何具有常數(shù)近似比的算法.因此，文獻(xiàn)[50]采用基于插隊(duì)操作的啟發(fā)式算法解決該問題，并在2個(gè)大規(guī)模真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn).Fu等人[51]提出基于社會(huì)效用的Top-k路線查詢問題，即為每位乘客提供社會(huì)效用最大的k條候選路線，由乘客根據(jù)自己的偏好進(jìn)一步選擇.該文獻(xiàn)提出2種不同的過濾候選司機(jī)的算法，即基于邊的過濾算法和基于網(wǎng)格索引的過濾算法.

2.2.3 乘客角度路線規(guī)劃小結(jié)

表2總結(jié)了基于乘客角度進(jìn)行路線規(guī)劃的主要算法研究.

Table 2 The Summary of Algorithms on Route Planning from Passengers’ Perspective表2 基于乘客角度的路線規(guī)劃算法總結(jié)

就算法的應(yīng)用場(chǎng)景與優(yōu)化目標(biāo)而言，可以發(fā)現(xiàn)目前研究大多局限于靜態(tài)場(chǎng)景，而對(duì)動(dòng)態(tài)場(chǎng)景的探索略為欠缺.同時(shí)，傳統(tǒng)研究多聚焦于最小化乘客等待時(shí)間等簡(jiǎn)單量化目標(biāo)，而近2年的文獻(xiàn)[50-51]側(cè)重于優(yōu)化拼車過程中的用戶體驗(yàn)，如乘客和乘客間的社交關(guān)系以及乘客與司機(jī)間的社交關(guān)系等，由此可見人文關(guān)懷在拼車中愈發(fā)重要.如何有效度量并且高效計(jì)算社會(huì)效用成為了新的挑戰(zhàn).

就算法的運(yùn)行效率與近似效果而言，雖然早期研究提出了一些精確算法，但其只針對(duì)小規(guī)模數(shù)據(jù)而無法適用于當(dāng)前真實(shí)拼車平臺(tái)的大規(guī)模訂單需求.而目前適用于大規(guī)模場(chǎng)景的算法中，文獻(xiàn)[40]提出的算法具有最高的運(yùn)行效率，且是現(xiàn)有文獻(xiàn)中唯一對(duì)多個(gè)司機(jī)的情況具有理論保證的算法.但該理論保證要求訂單的時(shí)空分布滿足嚴(yán)格的假設(shè)條件，而這些假設(shè)可能并不符合實(shí)際應(yīng)用(如要求訂單的位置信息滿足均勻分布等).因此，如何在合理的假設(shè)前提下設(shè)計(jì)具有近似理論保證的高效算法仍具有很大挑戰(zhàn).

2.3 基于平臺(tái)角度的路線規(guī)劃

在進(jìn)行路線規(guī)劃時(shí)，拼車平臺(tái)關(guān)注的焦點(diǎn)往往是訂單完成數(shù)量以及平臺(tái)的總盈利.因此，從平臺(tái)的角度進(jìn)行路線規(guī)劃，常用的優(yōu)化目標(biāo)包括最大化平臺(tái)的訂單完成數(shù)和最大化平臺(tái)的總收入.

2.3.1 最大化平臺(tái)訂單完成數(shù)的路線規(guī)劃

拼車平臺(tái)往往從自身盈利的角度出發(fā)規(guī)劃合適的路線.由于受到時(shí)空約束的限制，實(shí)際平臺(tái)中用戶請(qǐng)求的拼車訂單無法保證全部完成，從而存在平臺(tái)拒單或者要求用戶等待分配的情況.因此，一個(gè)自然的優(yōu)化目標(biāo)是最大化平臺(tái)的訂單完成總數(shù)量，即在滿足約束條件的情況下為盡可能多的乘客提供服務(wù).

Kleiner等人[52]首先提出了一個(gè)以最大化平臺(tái)的訂單完成數(shù)為優(yōu)化目標(biāo)的智能動(dòng)態(tài)拼車系統(tǒng)DRS.該系統(tǒng)采用拍賣機(jī)制，即每個(gè)司機(jī)先對(duì)自己喜好的訂單進(jìn)行投標(biāo)，最終由平臺(tái)來決定每個(gè)訂單該如何指派，并為指派的司機(jī)制定行駛路線.文獻(xiàn)[52]證明了這一基于拍賣機(jī)制的拼車系統(tǒng)具有激勵(lì)相容(incentive compatible)的性質(zhì).在進(jìn)行路線規(guī)劃時(shí)，該系統(tǒng)先計(jì)算每位司機(jī)接送若干位乘客的行駛距離矩陣，然后利用3次方時(shí)間的匈牙利算法求解分配方案，從而再確定每位司機(jī)接送乘客的先后順序.Santos等人[53]額外考慮了乘客的花費(fèi)因素，即他們希望找到一條最優(yōu)路線，既可以最小化乘客花費(fèi)，又能夠最大化訂單完成數(shù)量.在為司機(jī)進(jìn)行路線規(guī)劃時(shí)，該文獻(xiàn)依然采用了基于插隊(duì)操作的局部搜索算法.

Cici等人[54]在其工作中證明了最大化訂單完成數(shù)量的問題實(shí)際等價(jià)于最小化所需司機(jī)數(shù)量的問題.Vazifeh等人[55]則進(jìn)一步提出了一個(gè)基于交通網(wǎng)絡(luò)的算法解決最小化用車數(shù)量這一等價(jià)問題.該問題旨在滿足時(shí)空約束的條件下完成所有的訂單，并最小化所需要的司機(jī)數(shù)量.大量基于真實(shí)數(shù)據(jù)的實(shí)驗(yàn)表明該算法僅使用70%的車輛即可完成全部的訂單.作者還前瞻性地認(rèn)為該算法也可以用于無人車的調(diào)度系統(tǒng)中.此外，現(xiàn)有文獻(xiàn)還考慮了一些真實(shí)系統(tǒng)中的環(huán)境因素.例如文獻(xiàn)[56]還考慮了在實(shí)際路網(wǎng)中具有不同類型的道路前提下如何設(shè)計(jì)路線規(guī)劃算法.

2.3.2 最大化平臺(tái)總收入的路線規(guī)劃

從平臺(tái)角度考慮，另外一個(gè)自然的優(yōu)化目標(biāo)是最大化平臺(tái)的總收入.在實(shí)際系統(tǒng)和現(xiàn)有文獻(xiàn)中，平臺(tái)的總收入往往被定義為所有乘客支付的訂單價(jià)格總和減去平臺(tái)支付給所有司機(jī)的報(bào)酬.

Asghari等人[57]首先分析了在動(dòng)態(tài)場(chǎng)景下，不存在具有常數(shù)競(jìng)爭(zhēng)比的確定性算法能夠近似地解決基于該目標(biāo)的路線規(guī)劃問題.隨后，他們提出了一種基于分支定界的框架APART，遞歸地嘗試為每個(gè)新來的訂單找到當(dāng)前最優(yōu)的司機(jī).實(shí)驗(yàn)結(jié)果證明，該算法獲得的平臺(tái)總收入顯著優(yōu)于基于活動(dòng)樹的算法[23]和基于最近鄰搜索的算法[58].

文獻(xiàn)[59-60]都采用了基于二分圖匹配的算法，其基本思路與文獻(xiàn)[29]的想法類似，即先嘗試把可共享的若干訂單(通常不超過容量限制)進(jìn)行聚合(也被稱作將訂單打包)，再一次性地把打包好的訂單分派給一位司機(jī).考慮到訂單打包這一環(huán)節(jié)往往需要枚舉遍歷所有的可能組合，并進(jìn)行大量的在線最短路徑查詢，該方法并不適用于高容量限制、大規(guī)模路網(wǎng)的場(chǎng)景.例如，文獻(xiàn)[59]假設(shè)汽車的容量限制不得超過3.

文獻(xiàn)[22]提出了一個(gè)統(tǒng)一的優(yōu)化目標(biāo)，該目標(biāo)既可以等價(jià)地轉(zhuǎn)化為最大化平臺(tái)的訂單完成數(shù)，也能夠等價(jià)地轉(zhuǎn)化為最大化平臺(tái)的總收入.他們進(jìn)一步分析了該問題的復(fù)雜性，證明該問題定義下任何確定性算法或隨機(jī)算法均不存在常數(shù)競(jìng)爭(zhēng)比.為了減少路網(wǎng)中的最短路徑查詢次數(shù)，該文獻(xiàn)提出了一種使用歐氏距離執(zhí)行預(yù)插隊(duì)操作的剪枝策略.最后，基于百萬級(jí)規(guī)模的真實(shí)數(shù)據(jù)的實(shí)驗(yàn)表明，該文獻(xiàn)所提出的算法pruneGreedyDP遠(yuǎn)遠(yuǎn)優(yōu)于基于二分圖匹配來進(jìn)行路線規(guī)劃的經(jīng)典算法[29].此外，因?yàn)榧糁Σ呗远?jié)約的最短路徑查詢次數(shù)多達(dá)579億次.

2.3.3 平臺(tái)角度路線規(guī)劃小結(jié)

表3總結(jié)了基于平臺(tái)角度進(jìn)行路線規(guī)劃的主要相關(guān)研究.

Table 3 The Summary of Algorithms on Route Planning from Platforms’ Perspective表3 基于平臺(tái)角度的路線規(guī)劃算法總結(jié)

就算法的運(yùn)行效率與近似效果而言，文獻(xiàn)[22]的時(shí)間復(fù)雜度在考慮各變量范圍的情況下仍優(yōu)于其他算法，是目前此類問題最高效的求解方案.該文獻(xiàn)同時(shí)也證明了在動(dòng)態(tài)場(chǎng)景中不存在具有常數(shù)競(jìng)爭(zhēng)比的確定性算法或隨機(jī)算法.因此，基于平臺(tái)角度的路線規(guī)劃的一個(gè)開放性問題是探索是否存在對(duì)數(shù)階近似比或競(jìng)爭(zhēng)比的算法.此外，除近似比或競(jìng)爭(zhēng)比外，遺憾(regret)也常被作為算法理論保證的衡量標(biāo)準(zhǔn)之一[61].在基于最大化平臺(tái)訂單完成數(shù)的優(yōu)化目標(biāo)中，遺憾可以用來表示最優(yōu)解的最大訂單完成數(shù)與近似算法能夠完成訂單數(shù)的差值.在基于最大化平臺(tái)總收入的優(yōu)化目標(biāo)中，遺憾則可以用來表示平臺(tái)的最高總收入與近似算法能夠獲得的實(shí)際收入之間的差值.差值越小，則意味著算法的效用更好.但是，現(xiàn)有文獻(xiàn)均以探究近似比或競(jìng)爭(zhēng)比為主.因此，另外一個(gè)開放性問題是現(xiàn)有算法或新算法是否可以在遺憾這一理論保證指標(biāo)上具有好的分析結(jié)果.

2.4 路線規(guī)劃算法總結(jié)

表1、表2和表3分別從司機(jī)、乘客和平臺(tái)角度對(duì)大規(guī)模拼車的路線規(guī)劃算法進(jìn)行了分析和對(duì)比.綜合這3個(gè)表格可見，現(xiàn)有研究往往僅針對(duì)司機(jī)、乘客或平臺(tái)的單一角度對(duì)路線進(jìn)行規(guī)劃.然而，作為一個(gè)典型的雙邊市場(chǎng)，拼車平臺(tái)需要同時(shí)兼顧司機(jī)和乘客的用戶體驗(yàn).此外，只有少量工作提出了具有理論保證的近似算法，且往往僅針對(duì)1個(gè)司機(jī)、多個(gè)訂單的場(chǎng)景.而對(duì)于多個(gè)司機(jī)和多個(gè)訂單的離線場(chǎng)景或在線場(chǎng)景，幾乎沒有任何文章提出具有理論保證的算法.最后，現(xiàn)有研究的另一個(gè)假設(shè)是其僅針對(duì)歐氏空間或者靜態(tài)路網(wǎng)設(shè)計(jì)路線規(guī)劃算法，而所述方法通常難適用于反映實(shí)時(shí)交通情況的復(fù)雜路網(wǎng)環(huán)境，因而在實(shí)際應(yīng)用場(chǎng)景中具有一定局限性.

此外，在真實(shí)平臺(tái)中使用路線規(guī)劃算法時(shí)，還需要考慮一些實(shí)際因素.例如乘客對(duì)起點(diǎn)和終點(diǎn)的選擇與實(shí)際的GPS位置存在一定誤差，因此平臺(tái)需要依賴大量的上車地點(diǎn)和下車地點(diǎn)候選集減小該誤差.而司機(jī)可能存在不熟悉行駛路線的情況，因此平臺(tái)應(yīng)該在保證優(yōu)化目標(biāo)的前提下優(yōu)先對(duì)熟悉路線的司機(jī)進(jìn)行指派和分單.

最后，現(xiàn)有研究還存在一些假設(shè)過強(qiáng)之處，例如：總假設(shè)乘客不會(huì)臨時(shí)取消訂單、司機(jī)從不拒絕平臺(tái)所指派的訂單等，然而實(shí)際拼車平臺(tái)(如滴滴出行等)常有違背這些假設(shè)的情況發(fā)生[1].針對(duì)第1種情況，當(dāng)乘客臨時(shí)取消訂單時(shí)，平臺(tái)將該乘客取消訂單的情況實(shí)時(shí)地通知給所指派司機(jī)，并從為司機(jī)規(guī)劃的路線中刪除該乘客的起點(diǎn)和終點(diǎn)，從而保證司機(jī)仍然能夠順利地接送后續(xù)乘客.此外，在訂單高峰期，司機(jī)可能僅愿意接受具有更高利潤(rùn)的訂單，而出現(xiàn)拒絕某些低利潤(rùn)拼車訂單的行為，但現(xiàn)有算法往往不適用于該情況.因此，如何在路線規(guī)劃問題中考慮挑單和拒單等行為也是未來的研究方向.

3 社會(huì)影響因素及相關(guān)解決方案

除了路線規(guī)劃這一核心，大規(guī)模拼車平臺(tái)的工作流程還涉及了諸多社會(huì)影響因素.其中，最主要的因素包括如何對(duì)司機(jī)和乘客的積極性進(jìn)行調(diào)動(dòng)，以及如何對(duì)他們的隱私和人身安全等進(jìn)行保護(hù).基于此，本節(jié)分別對(duì)激勵(lì)機(jī)制(3.1節(jié))、隱私保護(hù)(3.2節(jié))和人身安全保障(3.3節(jié))等社會(huì)影響因素進(jìn)行闡述、分析和總結(jié).

3.1 激勵(lì)機(jī)制

大規(guī)模拼車問題中的激勵(lì)機(jī)制指通過增加司機(jī)收入、降低乘客花費(fèi)等手段吸引他們參與拼車，從而擴(kuò)大拼車服務(wù)市場(chǎng)、提高拼車平臺(tái)收益的各種方法.按照是否直接使用價(jià)格進(jìn)行激勵(lì)，可以將廣泛研究和投入實(shí)際應(yīng)用的激勵(lì)機(jī)制分為基于定價(jià)的激勵(lì)機(jī)制和基于獎(jiǎng)勵(lì)的激勵(lì)機(jī)制2類.

3.1.1 基于定價(jià)的激勵(lì)機(jī)制

大規(guī)模拼車問題中，乘客向平臺(tái)支付費(fèi)用以獲取服務(wù)，司機(jī)通過接送乘客從平臺(tái)獲取報(bào)酬.基于定價(jià)的激勵(lì)機(jī)制指通過向乘客收取合理的費(fèi)用和向司機(jī)支付合理的報(bào)酬來激勵(lì)乘客和司機(jī)參與的激勵(lì)方式.根據(jù)價(jià)格是否實(shí)時(shí)調(diào)整，基于定價(jià)的激勵(lì)機(jī)制可進(jìn)一步分為2類：基于固定價(jià)格的激勵(lì)機(jī)制和基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制.

1) 基于固定價(jià)格的激勵(lì)機(jī)制

基于固定價(jià)格的激勵(lì)機(jī)制(俗稱“一口價(jià)”)指乘客所需支付的費(fèi)用和司機(jī)從每份訂單獲得的報(bào)酬均在訂單行程開始前確定，不因拼車過程中新乘客的加入、路線的變更等導(dǎo)致額外時(shí)間花費(fèi)的因素而實(shí)時(shí)調(diào)整.

文獻(xiàn)[62]使用雙邊拍賣模型(double auction model)對(duì)基于固定價(jià)格的激勵(lì)機(jī)制進(jìn)行建模，以此設(shè)計(jì)分單算法來匹配司機(jī)和任務(wù).該文獻(xiàn)首先以司機(jī)和乘客的預(yù)期價(jià)格為基礎(chǔ)，結(jié)合個(gè)人信用等因素，生成綜合分?jǐn)?shù).其次，迭代地將乘客和司機(jī)的綜合分?jǐn)?shù)分別按照降序和升序排列，并對(duì)司機(jī)和乘客進(jìn)行匹配.該文獻(xiàn)提出的機(jī)制具有真實(shí)可信(truthfulness)的性質(zhì)，即乘客和司機(jī)均愿意按照其真實(shí)的心里預(yù)期價(jià)格進(jìn)行報(bào)價(jià)，且能夠保證平臺(tái)收支平衡.實(shí)驗(yàn)結(jié)果表明，在該文獻(xiàn)所提出的定價(jià)方式下，成交訂單數(shù)較雙邊VCG拍賣模型有所增加，而總成交額僅略低于最優(yōu)定價(jià)模型下的總成交額.

文獻(xiàn)[63]同時(shí)考慮現(xiàn)有訂單和未來訂單的彈性需求來制定長(zhǎng)期的定價(jià)機(jī)制，并從長(zhǎng)遠(yuǎn)角度考慮增加社會(huì)福利.該文獻(xiàn)認(rèn)為拼車定價(jià)問題若忽略實(shí)時(shí)變動(dòng)的彈性打車需求，會(huì)產(chǎn)生福利預(yù)期過高和服務(wù)效率過低的問題.因此，作者將長(zhǎng)期定價(jià)的思想應(yīng)用到動(dòng)態(tài)拼車問題中，將拼車的定價(jià)問題建模為排隊(duì)理論中的多服務(wù)器排隊(duì)模型，從而研究以社會(huì)福利作為優(yōu)化目標(biāo)的定價(jià)問題.實(shí)驗(yàn)表明，在使用相同路線規(guī)劃算法的前提下，該文獻(xiàn)所設(shè)計(jì)的定價(jià)機(jī)制可以獲得更高的社會(huì)福利.

文獻(xiàn)[64]研究如何通過制定價(jià)格的方式使平臺(tái)收益最大化.具體來說，平臺(tái)在時(shí)刻t位于區(qū)域i的收益可形式化地表示為

Wolfson等人[65]研究了拼車過程中針對(duì)不同乘客進(jìn)行收費(fèi)的公平性問題.在使用拼車服務(wù)時(shí)，不同乘客間拼車會(huì)產(chǎn)生不同的費(fèi)用，乘客傾向于尋找使其花費(fèi)最小的乘客分享行程.文獻(xiàn)將其建模為一個(gè)圖上的匹配問題并提出GRF(guaranteed-ridesharing-fairness)定價(jià)機(jī)制.具體而言，首先計(jì)算全局最優(yōu)匹配和個(gè)體公平匹配2種方案，然后在實(shí)現(xiàn)全局最優(yōu)匹配方案的同時(shí)按照個(gè)體公平匹配方案的定價(jià)機(jī)制收取費(fèi)用，最后將全局最優(yōu)匹配方案的剩余利潤(rùn)平分給各個(gè)乘客進(jìn)行補(bǔ)貼.這種方式既保持了對(duì)社會(huì)福利的最大化，又能保證參與乘客的個(gè)體公平性.

2) 基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制

基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制指乘客所需支付的費(fèi)用和司機(jī)從每份訂單獲得的報(bào)酬均基于具體的行駛路線或時(shí)間花費(fèi)等因素并按照某種規(guī)則實(shí)時(shí)調(diào)整.

Ma等人[24]基于動(dòng)態(tài)場(chǎng)景下針對(duì)多個(gè)司機(jī)的路線規(guī)劃問題，提出了基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制.在該定價(jià)機(jī)制中，為了激勵(lì)更多司機(jī)和乘客參與，司機(jī)收取的單位距離費(fèi)用以一定比例高于非拼車模式(即正常打車模式)的價(jià)格.例如若正常打車模式中每公里費(fèi)用為p元，則司機(jī)在拼車模式下每公里將可以獲得p乘以(1+α)倍的報(bào)酬，這里α表示額外獲得報(bào)酬的系數(shù).相應(yīng)地，若司機(jī)正在服務(wù)d名乘客，則每個(gè)乘客在該公里的費(fèi)用為(1+α)pd元.然而，該基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制有可能導(dǎo)致乘客的實(shí)際支出高于正常打車模式的支出，降低乘客對(duì)拼車的興趣.

Ma等人在文獻(xiàn)[25]中擴(kuò)展了文獻(xiàn)[24]中的思想.該文獻(xiàn)首先提出為激勵(lì)司機(jī)和乘客參與拼車過程，基于定價(jià)的激勵(lì)機(jī)制應(yīng)具備的3個(gè)性質(zhì)：1)乘客使用拼車服務(wù)所付費(fèi)用應(yīng)小于其使用正常打車模式所付費(fèi)用；2)在拼車過程中受到繞路影響的乘客，其所需支付費(fèi)用應(yīng)獲得一定折扣；3)付給司機(jī)的報(bào)酬需要涵蓋司機(jī)為了接單行駛的總距離.為滿足這3條性質(zhì)，文獻(xiàn)[25]提出了以下基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制.對(duì)乘客而言，其所需支付的費(fèi)用由2部分組成：一部分為正常打車模式下的費(fèi)用減去平臺(tái)預(yù)設(shè)的一個(gè)常數(shù)f，這里f相當(dāng)于乘客使用拼車服務(wù)得到的優(yōu)惠；另一部分是司機(jī)為了接送新訂單繞路而導(dǎo)致的額外費(fèi)用.對(duì)司機(jī)而言，其所獲得的實(shí)際報(bào)酬為其服務(wù)的所有乘客支付的費(fèi)用之和.文獻(xiàn)[25]同時(shí)證明了該基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制符合其所提出的3點(diǎn)性質(zhì).

文獻(xiàn)[57,66-67]將拍賣理論應(yīng)用到基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制設(shè)計(jì).Asghari等人[57]研究了以最大化平臺(tái)收入為優(yōu)化目標(biāo)的定價(jià)問題.具體來說，每個(gè)司機(jī)具有一個(gè)私有的費(fèi)用衡量函數(shù)，表示其行進(jìn)一段距離所需要的花費(fèi).而每個(gè)乘客具有一個(gè)費(fèi)用折扣函數(shù)，表示因新訂單插隊(duì)導(dǎo)致的繞路距離與支付費(fèi)用折扣的映射關(guān)系.這一折扣函數(shù)保證乘客支付的費(fèi)用不會(huì)高于其使用正常打車模式的費(fèi)用，因而能夠激勵(lì)乘客使用拼車應(yīng)用.平臺(tái)最終的收益等于乘客支付的總費(fèi)用與平臺(tái)支付給司機(jī)的總報(bào)酬的差值.為解決該問題，文獻(xiàn)[57]提出了基于拍賣思想的定價(jià)模型.即乘客在平臺(tái)發(fā)布訂單后，附近司機(jī)分別估計(jì)其接受該訂單所需的報(bào)酬并作為報(bào)價(jià).平臺(tái)根據(jù)司機(jī)的報(bào)價(jià)將訂單分配給報(bào)價(jià)最低的司機(jī)完成.值得注意的是，文獻(xiàn)[57]的這種定價(jià)方式能夠保證乘客所付費(fèi)用低于正常打車模式的費(fèi)用，因而能夠激勵(lì)乘客參與拼車.

針對(duì)文獻(xiàn)[57]中司機(jī)在自主計(jì)算行駛費(fèi)用過程中可能匯報(bào)虛假價(jià)格的問題，Asghari等人進(jìn)一步在文獻(xiàn)[66]中指出，對(duì)于司機(jī)來說，拼車中基于定價(jià)的激勵(lì)機(jī)制應(yīng)滿足2個(gè)性質(zhì)：1)真實(shí)可信，即司機(jī)虛報(bào)價(jià)格所得到的收益應(yīng)不大于其如實(shí)報(bào)價(jià)所得到的收益，這能夠保證司機(jī)的報(bào)價(jià)都是真實(shí)的；2)個(gè)體理性(individual rationality)，即司機(jī)所獲得的收益應(yīng)不少于其行駛開銷，該條性質(zhì)保證司機(jī)愿意參與到拼車中.基于文獻(xiàn)[57]提出的問題定義和定價(jià)框架，文獻(xiàn)[66]引入拍賣理論中的第二價(jià)格密封拍賣，使得預(yù)估報(bào)酬最低的司機(jī)獲得訂單，但將次低的預(yù)估報(bào)酬付給司機(jī).該文獻(xiàn)證明上述基于定價(jià)的激勵(lì)機(jī)制滿足真實(shí)可信和個(gè)體理性的性質(zhì).在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)進(jìn)一步表明，文獻(xiàn)[66]提出的定價(jià)機(jī)制具有與文獻(xiàn)[57]幾乎相同的平臺(tái)收益.

文獻(xiàn)[67]在最大化平臺(tái)收益的目標(biāo)下，從乘客角度研究如何設(shè)計(jì)具有真實(shí)可信性質(zhì)的基于浮動(dòng)價(jià)格的機(jī)制.具體來說，文獻(xiàn)[67]提出了基于貪心和基于訂單排序的訂單分配算法，并通過尋找臨界費(fèi)用(critical payment)的方式確定向乘客收取的每公里價(jià)格，并證明了其定價(jià)機(jī)制對(duì)于乘客來說具有真實(shí)可信的性質(zhì)，即能夠使得乘客匯報(bào)真實(shí)的對(duì)每公里價(jià)格的預(yù)期.實(shí)驗(yàn)表明，該文獻(xiàn)提出的算法運(yùn)行效率較好，而基于訂單排序的算法能夠獲得更高的平臺(tái)收益.

文獻(xiàn)[68]研究以社會(huì)福利最大化為優(yōu)化目標(biāo)的基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制設(shè)計(jì)問題，其具體優(yōu)化目標(biāo)等價(jià)于最小化拼車總花費(fèi)(所有司機(jī)報(bào)酬之和)與所有訂單最短距離之和的比值.平臺(tái)首先估計(jì)乘客所提交訂單的費(fèi)用上界，并對(duì)接受該估計(jì)的乘客訂單進(jìn)行分配.對(duì)于被分配的訂單，其單位距離的價(jià)格等于司機(jī)已支付報(bào)酬與已分配訂單最短距離之和的比值.對(duì)應(yīng)地，乘客所需付的費(fèi)用為單位價(jià)格與其行進(jìn)距離的乘積.該文獻(xiàn)進(jìn)一步證明了其所提出的定價(jià)模型具有真實(shí)可信的特點(diǎn)，實(shí)驗(yàn)表明其提出的定價(jià)模型較其他模型具有更高的社會(huì)福利.

3.1.2 基于獎(jiǎng)勵(lì)的激勵(lì)機(jī)制

基于獎(jiǎng)勵(lì)的激勵(lì)機(jī)制指通過積分、補(bǔ)貼、紅包等方式對(duì)司機(jī)或乘客進(jìn)行激勵(lì).根據(jù)獎(jiǎng)勵(lì)對(duì)象的不同，基于獎(jiǎng)勵(lì)的激勵(lì)機(jī)制可分為面向司機(jī)的獎(jiǎng)勵(lì)方法和面向乘客的獎(jiǎng)勵(lì)方法.盡管現(xiàn)有文獻(xiàn)對(duì)基于獎(jiǎng)勵(lì)的激勵(lì)機(jī)制研究較少，但該種制度已被廣泛應(yīng)用于滴滴出行、Uber等主流拼車平臺(tái)[1-2].

1) 面向司機(jī)的獎(jiǎng)勵(lì)方法

面向司機(jī)的獎(jiǎng)勵(lì)方法指平臺(tái)使用獎(jiǎng)勵(lì)的方式激勵(lì)司機(jī)參與并提供更好的服務(wù)，其主要包括司機(jī)評(píng)分和組隊(duì)競(jìng)賽2種方式.

司機(jī)評(píng)分指拼車平臺(tái)根據(jù)多種因素對(duì)司機(jī)進(jìn)行綜合評(píng)分，并根據(jù)評(píng)分決定是否優(yōu)先為司機(jī)分配訂單.司機(jī)評(píng)分機(jī)制被許多拼車平臺(tái)采用，例如滴滴出行公司的“服務(wù)分”就是一種司機(jī)評(píng)分機(jī)制：乘客在訂單完成后對(duì)司機(jī)的服務(wù)進(jìn)行打分，而司機(jī)的“服務(wù)分”則在路線規(guī)劃階段提供給乘客[1-5].由于評(píng)分的高低會(huì)影響到司機(jī)是否被優(yōu)先分配訂單，這種機(jī)制能夠有效激勵(lì)司機(jī)提供良好的服務(wù).

游戲化的組隊(duì)競(jìng)賽是一種新穎的面向司機(jī)的獎(jiǎng)勵(lì)方法.例如在滴滴出行的組隊(duì)競(jìng)賽中，司機(jī)以小組(6人左右)為單位參與到平臺(tái)設(shè)置的競(jìng)賽活動(dòng)中，平臺(tái)考察小組的活躍時(shí)長(zhǎng)、接單次數(shù)等指標(biāo)，并對(duì)排名靠前的小組進(jìn)行獎(jiǎng)勵(lì)[1].這些獎(jiǎng)勵(lì)既包括物質(zhì)獎(jiǎng)勵(lì)，也包括諸如服務(wù)分等其他獎(jiǎng)勵(lì).組隊(duì)競(jìng)賽一方面能夠以競(jìng)爭(zhēng)的方式調(diào)動(dòng)司機(jī)的積極性，從而使他們更有動(dòng)力參與到拼車服務(wù)中；另一方面，小組內(nèi)部各成員之間可以方便地進(jìn)行交流溝通，從而能在一定程度上緩解司機(jī)的工作壓力并使他們產(chǎn)生對(duì)小組以及平臺(tái)的歸屬感.滴滴平臺(tái)于2018年多次推出組隊(duì)競(jìng)賽的活動(dòng)，已經(jīng)覆蓋全國(guó)超過100個(gè)城市，結(jié)果顯示司機(jī)的工作時(shí)長(zhǎng)、接單數(shù)量都有所增加.

2) 面向乘客的獎(jiǎng)勵(lì)方法

面向乘客的獎(jiǎng)勵(lì)方法指平臺(tái)給予乘客權(quán)益上的保障和價(jià)格上的優(yōu)惠，從而激勵(lì)他們使用拼車服務(wù),其中包括積分政策、會(huì)員制度和紅包優(yōu)惠等激勵(lì)方法.

積分政策指平臺(tái)根據(jù)乘客打車的花費(fèi)按照一定比例返還積分.當(dāng)乘客的積分累計(jì)到一定數(shù)額時(shí)，可以通過平臺(tái)的積分商城兌換商品或優(yōu)惠券等.積分制度可以在一定程度上吸引乘客使用拼車服務(wù)，也能夠幫助平臺(tái)在同行競(jìng)爭(zhēng)中可以獲得一定優(yōu)勢(shì).

會(huì)員制度指平臺(tái)根據(jù)乘客使用拼車服務(wù)的次數(shù)設(shè)置乘客的會(huì)員等級(jí)，并向不同等級(jí)的會(huì)員提供不同程度的權(quán)益.例如，高等級(jí)的滴滴出行會(huì)員可以享受優(yōu)先派車與免費(fèi)升級(jí)為優(yōu)享車等權(quán)益[1].會(huì)員制度能夠激勵(lì)乘客對(duì)同一平臺(tái)的長(zhǎng)期使用，從而防止乘客向其他同類平臺(tái)的流失.

紅包優(yōu)惠指拼車平臺(tái)不定期地給乘客發(fā)放打折券或紅包，從而使乘客以低價(jià)享受到拼車服務(wù).以滴滴出行為例，該平臺(tái)周期性地向乘客發(fā)放打折券，以此激勵(lì)乘客使用拼車應(yīng)用[1].對(duì)于乘客而言，價(jià)格上的優(yōu)惠能夠直接激勵(lì)他們使用拼車應(yīng)用.此外，在每次訂單結(jié)算后，平臺(tái)也會(huì)向乘客隨機(jī)發(fā)放紅包，當(dāng)紅包累計(jì)到一定金額后可以一次性抵扣車費(fèi).

上述面向乘客的激勵(lì)方法已經(jīng)在實(shí)際平臺(tái)中得到了廣泛應(yīng)用，但仍舊缺乏進(jìn)一步的理論研究.

3.1.3 激勵(lì)機(jī)制小結(jié)

表4列舉了本部分涉及的各類激勵(lì)機(jī)制.可以看出，大部分研究集中在基于定價(jià)的激勵(lì)機(jī)制.其中，基于固定價(jià)格的激勵(lì)機(jī)制具有2個(gè)優(yōu)點(diǎn)：1)乘客在行程開始前獲知價(jià)格并決定是否接受，不必承擔(dān)行駛路線變化等導(dǎo)致的額外花銷，減少了乘客利益糾紛的可能性；2)司機(jī)報(bào)酬不受行車路線影響，激勵(lì)司機(jī)以最短行程和最快速度完成訂單，能一定程度提高司機(jī)完成訂單的效率.反之，基于浮動(dòng)價(jià)格的激勵(lì)機(jī)制的2個(gè)特點(diǎn)則使其更適合動(dòng)態(tài)的拼車環(huán)境：1)乘客所需支付的費(fèi)用和司機(jī)從每份訂單獲得的報(bào)酬均根據(jù)行駛路線或時(shí)間花費(fèi)等情況實(shí)時(shí)調(diào)整，能夠避免路線調(diào)整或突發(fā)意外等因素導(dǎo)致的收費(fèi)不合理情況；2)該類機(jī)制能夠保證司機(jī)所獲得的報(bào)酬不低于實(shí)際花銷，從而激勵(lì)司機(jī)參與拼車.盡管現(xiàn)有文獻(xiàn)分別基于不同的優(yōu)化目標(biāo)提出了不同的固定價(jià)格或浮動(dòng)價(jià)格的定價(jià)機(jī)制，但現(xiàn)有文獻(xiàn)往往僅針對(duì)這些定價(jià)方式的短期收益進(jìn)行了實(shí)驗(yàn)比較.而在實(shí)際平臺(tái)中，機(jī)制的穩(wěn)定性也常常是一項(xiàng)重要的評(píng)估指標(biāo)，系統(tǒng)地分析和評(píng)估現(xiàn)有定價(jià)機(jī)制是否可以達(dá)到穩(wěn)定的長(zhǎng)期收益可能成為未來潛在的研究方向.

Table 4 The Summary of Algorithms on the Incentive Mechanisms in Large-scale Ridesharing表4 面向大規(guī)模拼車的激勵(lì)機(jī)制算法總結(jié)

此外，分別從司機(jī)和乘客角度介紹了實(shí)際應(yīng)用中基于獎(jiǎng)勵(lì)的激勵(lì)機(jī)制.這些機(jī)制對(duì)于激勵(lì)司機(jī)參與拼車服務(wù)和激勵(lì)乘客使用拼車服務(wù)具有良好的效果.然而，學(xué)術(shù)界對(duì)這些機(jī)制的量化研究還有所欠缺，這也成為未來潛在的研究方向之一.

3.2 隱私保護(hù)

在大規(guī)模拼車應(yīng)用中，用戶的隱私信息一方面包括乘客訂單的起終點(diǎn)位置、司機(jī)的行駛軌跡等時(shí)空敏感信息，另一方面也包括乘客的住址和聯(lián)系方式等個(gè)人信息.拼車平臺(tái)需要在保護(hù)這些隱私的基礎(chǔ)上進(jìn)行路線規(guī)劃等操作.因此，從隱私保護(hù)方法的角度對(duì)基于加密技術(shù)、差分隱私和區(qū)塊鏈的隱私保護(hù)技術(shù)的研究成果進(jìn)行闡述.

3.2.1 基于加密技術(shù)的隱私保護(hù)方法

基于加密技術(shù)的隱私保護(hù)方法通過加密技術(shù)對(duì)用戶的隱私信息進(jìn)行加密，而平臺(tái)則使用加密后的時(shí)空信息進(jìn)行路線的規(guī)劃.現(xiàn)有研究主要基于同態(tài)加密技術(shù)(homomorphic encryption, HE).同態(tài)加密具有高可塑性(易于修改和擴(kuò)展特性)、無需解密即可進(jìn)行加乘運(yùn)算等優(yōu)勢(shì).

文獻(xiàn)[69]提出了ORide(oblivious ride)機(jī)制以保護(hù)拼車服務(wù)中乘客與司機(jī)的位置信息，并在訂單的分配過程中考慮最小化司機(jī)行駛總距離.該機(jī)制基于部分同態(tài)加密技術(shù)(somewhat homomorphic encryption, SHE)，且不依賴可信的第三方服務(wù)器(trusted third server).具體流程為：司機(jī)和乘客的位置坐標(biāo)經(jīng)過加密后上傳到拼車平臺(tái).之后，拼車平臺(tái)通過加密后的數(shù)據(jù)進(jìn)行計(jì)算并將候選司機(jī)發(fā)送給乘客的客戶端.然后，由乘客選擇合適的司機(jī)進(jìn)行訂單的分配并將結(jié)果返回給拼車平臺(tái).最后，乘客與司機(jī)通過私密頻道交換各自的真實(shí)時(shí)空信息來保證隱私安全.文獻(xiàn)[69]將基于同態(tài)加密技術(shù)的密文作為操作載體進(jìn)行司機(jī)的篩選，通過對(duì)密文打包的方式降低計(jì)算開銷.實(shí)驗(yàn)結(jié)果進(jìn)一步顯示，隱私保護(hù)機(jī)制在各種參數(shù)下均能取得較好的匹配結(jié)果.

與文獻(xiàn)[69]類似，文獻(xiàn)[70]中提出的SRide動(dòng)態(tài)拼車系統(tǒng)也采用部分同態(tài)加密技術(shù)保護(hù)乘客和司機(jī)的位置信息.在不使用可信第三方服務(wù)器的前提下，文獻(xiàn)[70]將加密后用戶的時(shí)空信息映射到與時(shí)間相對(duì)應(yīng)的時(shí)間戳和與位置相對(duì)應(yīng)的空間網(wǎng)格內(nèi)，并通過映射后的時(shí)空信息過濾候選司機(jī)，減少待匹配司機(jī)的數(shù)量，減少對(duì)加密信息的操作所帶來的計(jì)算開銷.最后，該系統(tǒng)在路線規(guī)劃階段，計(jì)算乘客與司機(jī)的預(yù)期接車地點(diǎn)的相似性，并以最大化相似性為指標(biāo)完成訂單分配.實(shí)驗(yàn)表明，SRide完成匹配任務(wù)的時(shí)間分別為5 s和9 s，運(yùn)行時(shí)間相比于文獻(xiàn)[69]大大減少.

文獻(xiàn)[71]采用替換加密和換位加密等經(jīng)典加密方法完成保護(hù)乘客位置信息前提下對(duì)拼車訂單的分配，其基本思想是在訂單分配過程中考慮密文間的相似度.具體地，拼車平臺(tái)將乘客和司機(jī)加密后的信息轉(zhuǎn)換為詞向量，通過向量之間的相同位數(shù)來衡量信息的相似程度，通過依次比較乘客與司機(jī)之間的時(shí)間向量相似性和空間向量相似性來完成訂單的分配.最后，文獻(xiàn)[71]分別在真實(shí)數(shù)據(jù)與合成數(shù)據(jù)上進(jìn)行了實(shí)驗(yàn)驗(yàn)證，結(jié)果表明如果允許司機(jī)進(jìn)行跨區(qū)域接單，訂單完成數(shù)量將大幅度增加.

3.2.2 基于差分隱私的隱私保護(hù)方法

除基于加密技術(shù)的隱私保護(hù)方法外，文獻(xiàn)[72-73]與實(shí)際平臺(tái)(如Uber等)采用基于差分隱私(differential privacy)的隱私保護(hù)方法[58,74-75].基本思想是通過對(duì)原有數(shù)據(jù)添加噪聲保證司機(jī)與乘客的時(shí)空敏感信息不被泄露，然后基于添加噪聲后的數(shù)據(jù)進(jìn)行路線規(guī)劃的計(jì)算.

Tong等人[72]采用了差分隱私技術(shù)保護(hù)乘客的位置信息，同時(shí)最小化司機(jī)的行駛距離.具體地，平臺(tái)根據(jù)位置信息將司機(jī)分為不同集合，然后通過分析對(duì)偶變量(dual variable)對(duì)乘客與司機(jī)集合進(jìn)行匹配.然后，在配對(duì)的司機(jī)集合與乘客集合內(nèi)部進(jìn)行匹配得到最終的匹配結(jié)果.Tong等人[72]同時(shí)引入一種聯(lián)合差分隱私優(yōu)化過程(jointly differential privacy optimization process)，在進(jìn)行集合匹配過程中用以保護(hù)乘客與司機(jī)的個(gè)人隱私.實(shí)驗(yàn)結(jié)果顯示，Tong等人[72]將提出的JDP-Ride算法與不涉及隱私保護(hù)的基線算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明提出的JDP-Ride算法損失更小、實(shí)驗(yàn)結(jié)果更穩(wěn)定.

此外，Andrés等人[76]提出了專門針對(duì)空間位置信息的差分隱私方法：地理信息不可辨別性理論(geo-indistinguishability theorem, Geo-I)，以專門保護(hù)個(gè)人位置信息.具體來說，給定原始點(diǎn)集合X和噪聲點(diǎn)集合Z，該理論要求對(duì)于任意的2個(gè)原始點(diǎn)x,x′∈X和噪聲點(diǎn)z∈Z，所提出的隱私保護(hù)方法K需滿足：

K(x)(z)≤eε×d(x,x′)K(x′)(z),

其中，K(x)(z)為原始點(diǎn)x映射為噪聲點(diǎn)z的概率.該理論已被廣泛應(yīng)用于保護(hù)時(shí)空敏感的位置信息[77-78].文獻(xiàn)[73]研究滿足地理信息不可辨別性約束下最小化乘客平均等待時(shí)間的問題.首先提出了一種基線算法，對(duì)乘客的位置信息加入拉普拉斯噪聲使其滿足ε-差分隱私，然后在此基礎(chǔ)上使用匈牙利算法對(duì)乘客與司機(jī)進(jìn)行一次分配.針對(duì)該基線算法對(duì)車輛利用率低的問題，提出對(duì)未滿座的車輛迭代地執(zhí)行多輪匹配，將仍有空座位的車輛與未分派的新訂單進(jìn)行匹配，從而使得可以完成訂單的車輛增加、乘客的等待時(shí)間減少.

3.2.3 基于區(qū)塊鏈的隱私保護(hù)機(jī)制

區(qū)塊鏈技術(shù)起源于比特幣，本質(zhì)上是一種去中心化(不依賴額外的第三方管理機(jī)構(gòu))的、開放性的(除交易各方私有信息被加密外，區(qū)塊鏈數(shù)據(jù)對(duì)所有人開放)和匿名的(信息傳遞可以匿名進(jìn)行)分布式數(shù)據(jù)庫(kù)與計(jì)算范式，近年來受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注[79-82].文獻(xiàn)[80]使用區(qū)塊鏈中的私有鏈(private blockchain)達(dá)到隱私保護(hù)的目的.采用基于區(qū)塊鏈的車霧計(jì)算技術(shù)(vehicular fog computing)，并提出了一個(gè)高效的隱私保護(hù)拼車系統(tǒng)FICA，可同時(shí)保護(hù)乘客與司機(jī)的位置信息和軌跡信息.車霧計(jì)算使用一種叫做RSU(road side unit)的分布式計(jì)算單元處理用戶的數(shù)據(jù).在訂單完成后，用戶需要將交易記錄上傳平臺(tái)用以后續(xù)審核，而這些記錄可被用來還原乘客與司機(jī)的個(gè)人信息從而導(dǎo)致隱私泄露.為了方便管理的同時(shí)保護(hù)隱私安全，F(xiàn)ICA使用RSU建立交易記錄的私有鏈，在該私有鏈中僅支持擁有相應(yīng)權(quán)限的用戶執(zhí)行寫操作，用以保證數(shù)據(jù)的可審核性與私密性.文獻(xiàn)[80]的實(shí)驗(yàn)結(jié)果顯示在乘客和司機(jī)數(shù)量為1 000時(shí)FICA的匹配時(shí)間不超過14 s，且優(yōu)于文獻(xiàn)[69]提出的ORide系統(tǒng).

3.2.4 隱私保護(hù)小結(jié)

表5總結(jié)了大規(guī)模拼車應(yīng)用中隱私保護(hù)的相關(guān)文獻(xiàn).由表5中可以看出，大部分研究工作著力于在靜態(tài)場(chǎng)景、保護(hù)隱私的前提下，指派合適的司機(jī)并規(guī)劃合理的路線；少部分工作考慮了更具普適性的動(dòng)態(tài)場(chǎng)景.

Table 5 The Summary of Algorithms on the Privacy Protection in Large-Scale Ridesharing表5 面向大規(guī)模拼車的隱私保護(hù)算法總結(jié)

3.3 人身安全保障

近年來，拼車平臺(tái)涉及人身安全的惡性事件頻發(fā)，引起了社會(huì)的廣泛關(guān)注.如何在大規(guī)模拼車應(yīng)用中保護(hù)乘客與司機(jī)的人身安全也成為一個(gè)不可避免的問題.現(xiàn)有研究通常從路線規(guī)劃、用戶管理等角度來考慮這一問題.

3.3.1 基于路線規(guī)劃的人身安全保障

基于路線規(guī)劃的人身安全保障旨在為司機(jī)和乘客選擇安全的拼車對(duì)象和拼車路線.

文獻(xiàn)[83]通過選擇安全的拼車對(duì)象來保障乘客的人身安全.現(xiàn)有研究表明：出于安全考慮，人們更愿意和有直接或間接朋友關(guān)系的人一起拼車[84].據(jù)此，Wang等人[83]提出了一個(gè)考慮社交網(wǎng)絡(luò)的拼車匹配算法.然而，將拼車服務(wù)僅限制在好友之間可能導(dǎo)致拼車匹配成功概率的降低和繞路開銷的增加.為了解決這一問題，Wang等人[83]對(duì)比了基于3種不同社交關(guān)系限制條件的算法效果，即僅可與有直接社交關(guān)系的人(例如朋友關(guān)系)一起拼車、可與有直接社交關(guān)系或間接社交關(guān)系(例如朋友的朋友)的人一起拼車和可與任意乘客一起拼車.實(shí)驗(yàn)結(jié)果表明，具有特定空間分布的社交網(wǎng)絡(luò)下，限制拼車僅發(fā)生在朋友之間所帶來的額外繞路開銷并不顯著，且將存在良好社交關(guān)系的乘客優(yōu)先匹配可以大幅提高朋友拼車率.

文獻(xiàn)[85]通過選擇安全的拼車路線來保障雙方的人身安全，其依據(jù)是拼車過程中惡性事件往往發(fā)生在存在安全隱患的路段，或由司機(jī)擅自更改行車路線導(dǎo)致.文獻(xiàn)[85]將乘客的上車、下車的地點(diǎn)固定為某一特定集合，并通過在這些地點(diǎn)加裝監(jiān)控來保障乘客和司機(jī)的安全.這種固定站點(diǎn)接送的方式同時(shí)還能夠大幅度緩解交通擁堵.文章表明其所提出的方法能夠平均減少31.5%的行駛距離.

3.3.2 基于用戶管理的人身安全保障

基于用戶管理的人身安全保障旨在通過建立合理的用戶管理機(jī)制保障人身安全.

聲譽(yù)管理機(jī)制是一種應(yīng)用廣泛的用戶管理機(jī)制.文獻(xiàn)[86]認(rèn)為，乘客和司機(jī)的聲譽(yù)對(duì)拼車平臺(tái)而言至少有2方面的積極作用：1)良好的聲譽(yù)可以幫助建立司機(jī)與乘客間的信任感；2)聲譽(yù)可以促使乘客和司機(jī)為他們的行為負(fù)責(zé)，而惡意用戶會(huì)因?yàn)檩^低的聲譽(yù)值被辨別出來，并且受到懲罰.文獻(xiàn)[87]提出一個(gè)分布式的聲譽(yù)管理協(xié)議，根據(jù)與某一個(gè)用戶(乘客或司機(jī))接觸過的其他用戶的評(píng)價(jià)來為該用戶計(jì)算一個(gè)全局的聲譽(yù)值，并且確保這個(gè)協(xié)議能夠讓理性的用戶們主動(dòng)遵守從而做到互利共贏.當(dāng)一個(gè)用戶決定是否要與另一個(gè)用戶拼車的時(shí)候，可以同時(shí)考慮根據(jù)他自身以往的接觸經(jīng)歷計(jì)算出對(duì)方的局部聲譽(yù)值和綜合所有用戶的評(píng)價(jià)計(jì)算出全局聲譽(yù)值，取二者中的較低者作為參考.這一規(guī)則能夠避免參與者有選擇地對(duì)待某些用戶.如果對(duì)方的聲譽(yù)值高于該用戶可接受的最低聲譽(yù)值，則該用戶可以信任對(duì)方并同意拼車.

此外，這一聲譽(yù)管理系統(tǒng)還可以如3.1節(jié)所述作為激勵(lì)機(jī)制發(fā)揮作用，即通過對(duì)聲譽(yù)的管理促進(jìn)用戶遵守規(guī)章制度、減少違規(guī)操作.實(shí)驗(yàn)表明，良好的聲譽(yù)能夠讓用戶更容易地獲得更好的拼車體驗(yàn).具體來說，在聲譽(yù)管理系統(tǒng)的激勵(lì)下，用戶更容易找到拼車對(duì)象，或能夠以更短的行走距離前往上車地點(diǎn).

工業(yè)界還使用一些其他的用戶管理機(jī)制保障司機(jī)與乘客的人身安全.例如，滴滴出行要求平臺(tái)的司機(jī)必須經(jīng)過三證(身份證、駕駛證和車輛行駛證)驗(yàn)真的審核；通過對(duì)司機(jī)進(jìn)行背景審查來構(gòu)建司機(jī)畫像從而降低暴力犯罪、酒后駕駛等違法行為的可能性(如圖4所示)；利用人臉識(shí)別技術(shù)核實(shí)實(shí)際駕駛員身份，嚴(yán)防冒用他人身份注冊(cè)、私換駕駛員接單等行為；設(shè)置緊急聯(lián)系人以便在危急時(shí)刻及時(shí)求助等[1-2,88].上述措施都是從加強(qiáng)對(duì)司機(jī)管理的角度保障乘客的人身安全.此外針對(duì)司機(jī)的人身安全保障，滴滴出行能夠?qū)λ緳C(jī)的危險(xiǎn)駕駛行為進(jìn)行檢測(cè)和實(shí)時(shí)預(yù)警，同時(shí)對(duì)于司機(jī)的異常停留等不當(dāng)行為進(jìn)行人工干預(yù)與檢測(cè)，從而抑制危險(xiǎn)狀況的升級(jí)，以達(dá)到保障司機(jī)的人身安全的目的[1,3].

3.3.3 人身安全保障小結(jié)

表6總結(jié)了大規(guī)模拼車應(yīng)用中人身安全保障的相關(guān)文獻(xiàn).可以看出，工業(yè)界已經(jīng)采取了諸如用戶管理等保障人身安全的措施并起到了良好的效果，但對(duì)相關(guān)機(jī)制的量化分析和理論研究還較為缺乏.

Fig. 4 An illustration of driver’s profile圖4 司機(jī)畫像舉例

ReferenceSolutionProtecting UsersProtecting DriversScenarioObjectiveRef[83]Restrictions on Users√√StaticMinimize Total DistanceRef[85]Fixed Pick-up and Drop-off Locations√×DynamicMaximize the Coverage of DriversRef[87]Reputation Management√√DynamicMaximize Number of Completed Orders

4 未來研究方向

目前大規(guī)模拼車作為一個(gè)研究熱點(diǎn)，仍有很多問題值得學(xué)者們深入研究.本節(jié)簡(jiǎn)述其中4類潛在的研究方向，供研究者們參考.

1) 有理論保證的路線規(guī)劃算法

現(xiàn)存研究通常采用啟發(fā)式算法解決多位司機(jī)、多個(gè)訂單的路線規(guī)劃問題，但尚缺乏針對(duì)該問題全局性能近似優(yōu)化的理論分析.此外，現(xiàn)有研究?jī)H從司機(jī)、乘客和平臺(tái)的單方面考慮如何進(jìn)行路線規(guī)劃，這導(dǎo)致了所規(guī)劃的路線難以同時(shí)對(duì)三者達(dá)到性能的優(yōu)化.因此，現(xiàn)存的主要挑戰(zhàn)是如何設(shè)計(jì)具有近似理論保障的路線規(guī)劃算法，能夠計(jì)算一條折中路線從而實(shí)現(xiàn)多目標(biāo)優(yōu)化.此外，現(xiàn)有研究的路線規(guī)劃算法往往僅針對(duì)于歐氏空間或者靜態(tài)路網(wǎng)，而不能解決復(fù)雜路網(wǎng)環(huán)境下所存在如堵車等實(shí)際因素.因此，如何將具有理論保障的路線規(guī)劃算法擴(kuò)展到復(fù)雜路網(wǎng)環(huán)境也具有一定挑戰(zhàn).

2) 混合普通打車的定價(jià)機(jī)制

盡管現(xiàn)有的拼車激勵(lì)機(jī)制研究對(duì)多種定價(jià)方式進(jìn)行了探索，但是這些研究假設(shè)乘客的出行方式僅拼車一種，而忽視了實(shí)際場(chǎng)景：在實(shí)際打車平臺(tái)中，拼車模式往往與普通打車模式同時(shí)存在，即乘客可同時(shí)選擇2類出行方式.因此同時(shí)考慮拼車與普通打車供需情況的定價(jià)策略顯得更為合理.當(dāng)供大于求時(shí)，平臺(tái)能夠僅通過普通打車來滿足乘客的出行需求，此時(shí)若仍通過折扣的方式激勵(lì)用戶參與拼車，反而削弱了平臺(tái)的收入.當(dāng)供小于求時(shí)，平臺(tái)由于車輛短缺難以通過普通打車來滿足乘客的出行需求，此時(shí)適當(dāng)增加對(duì)拼車模式的激勵(lì)可以滿足更多需求從而增加平臺(tái)收入.因此，一個(gè)潛在的研究方向是混合拼車與普通打車供的定價(jià)機(jī)制設(shè)計(jì).

3) 動(dòng)態(tài)場(chǎng)景下的健全保障措施

拼車過程中的隱私保護(hù)及安全保障是近年來社會(huì)普遍關(guān)注的熱點(diǎn)問題，然而相關(guān)文獻(xiàn)在這方面研究不足.一方面，現(xiàn)存研究往往針對(duì)靜態(tài)場(chǎng)景下如何保障用戶的隱私，而忽略了實(shí)際應(yīng)用中更為普遍的動(dòng)態(tài)場(chǎng)景(即在線情況).因此，一個(gè)核心問題是在動(dòng)態(tài)場(chǎng)景下，如何設(shè)計(jì)有效的算法保護(hù)用戶的隱私、可行的機(jī)制保證用戶的安全.特別地，現(xiàn)有關(guān)于拼車過程中人身安全問題的研究多為調(diào)研、案例研究性質(zhì)的工作，缺乏在實(shí)際應(yīng)用中從技術(shù)層面提出具體的措施來解決該類問題.由于隱私與安全問題與用戶的切身利益息息相關(guān)，因此具有較大的研究意義.

4) 基于交互仿真的拼車模擬環(huán)境

為了驗(yàn)證拼車應(yīng)用的路線規(guī)劃、激勵(lì)機(jī)制與隱私保護(hù)等算法問題，一個(gè)高性能的模擬環(huán)境必不可少.盡管現(xiàn)有研究已經(jīng)提出了一些拼車的模擬器，但是它們的核心功能往往是提供司機(jī)和乘客的時(shí)空信息、分析統(tǒng)計(jì)算法性能等，而不具備與仿真算法的交互式驗(yàn)證[89-92].例如，為了驗(yàn)證激勵(lì)機(jī)制的定價(jià)策略是否合理，模擬環(huán)境應(yīng)該能夠模擬乘客的心理預(yù)期和決策行為，即用戶是否接受給定的價(jià)格.而現(xiàn)有模擬器往往不具備上述類似的功能.因此，為了更好地開展大規(guī)模拼車算法的相關(guān)研究，一個(gè)潛在的問題是如何設(shè)計(jì)一個(gè)基于交互式仿真驗(yàn)證的模擬環(huán)境.

5 結(jié)束語

本文介紹了共享出行中一類重要的應(yīng)用——拼車，并針對(duì)大規(guī)模拼車算法的研究進(jìn)展進(jìn)行綜述.文章首先介紹了拼車問題的基本概念和工作流程，隨后對(duì)大規(guī)模拼車算法的核心問題——路線規(guī)劃進(jìn)行系統(tǒng)地討論與分析，進(jìn)一步對(duì)大規(guī)模拼車應(yīng)用驅(qū)動(dòng)的社會(huì)影響因素進(jìn)行分類闡述.總的來說，大規(guī)模拼車問題在具有理論保證的路線規(guī)劃算法、混合定價(jià)機(jī)制、動(dòng)態(tài)場(chǎng)景保障措施和仿真拼車模擬環(huán)境等方向還具有潛在的研究?jī)r(jià)值.作為共享出行的一個(gè)重要應(yīng)用形式，大規(guī)模拼車問題也為學(xué)術(shù)界提供了新穎的問題背景和研究動(dòng)機(jī)，正在受到廣泛關(guān)注，仍是大數(shù)據(jù)應(yīng)用領(lǐng)域當(dāng)前的研究熱點(diǎn)之一.希望本文能夠?yàn)榇笠?guī)模拼車算法研究領(lǐng)域的從業(yè)者們提供參考與幫助.