鄭小紅，龍 軍，蔡志平

(國防科技大學(xué)計算機(jī)學(xué)院,湖南 長沙 410073)

1 引言

網(wǎng)約車(出租車)是我們?nèi)粘Ｉ钪胁豢扇鄙俚墓渤鲂薪煌üぞ咧?，給人們出行帶來便利的同時也在源源不斷地產(chǎn)生大量數(shù)據(jù)，通過對海量數(shù)據(jù)的挖掘能幫助緩解交通壓力，提升城市治理效果。在城市計算領(lǐng)域[1,2]，存在大量基于網(wǎng)約車(出租車)歷史數(shù)據(jù)的研究，比如時間預(yù)估[3 - 5]、城市異常[6,7]、人流預(yù)測[8,9]、路線規(guī)劃[10,11]和網(wǎng)約車訂單分配[12]。

在路邊招手打車是最傳統(tǒng)的打車方式，在這種方式下，司機(jī)需要具備豐富的個人經(jīng)驗尋找乘客，不僅浪費(fèi)時間和資源，還容易導(dǎo)致嚴(yán)重的供需不平衡。隨著全球定位系統(tǒng)和手機(jī)的發(fā)展，新加坡出租車公司推出電話約車的打車方式[13]，這種方式在一定程度上減少了乘客等待時間，提高了車輛的利用率。如今，伴隨著互聯(lián)網(wǎng)技術(shù)和智能手機(jī)的全面普及，利用手機(jī)通過互聯(lián)網(wǎng)打車的方式逐漸流行，“網(wǎng)約車”開始出現(xiàn)在大眾的視野里，越來越多的出行公司應(yīng)運(yùn)而生，如滴滴出行、Uber和Lyft等。電話約車、網(wǎng)絡(luò)平臺打車等打車方式的出現(xiàn)，雖然方便了乘客和司機(jī)，卻給出行平臺(出租車公司)帶來一個難題——如何更好地匹配乘客請求和司機(jī)需求？

研究網(wǎng)約車訂單分配策略，有助于緩解交通壓力，使人們的出行更加方便，提高司機(jī)的收入，減少車輛的空載時間和距離，減少資源浪費(fèi)，保護(hù)環(huán)境。它的研究經(jīng)歷了很長時間，大多數(shù)的網(wǎng)約車訂單分配策略主要基于在搶單模式和系統(tǒng)派單模式。其中搶單模式由出行平臺按照某種策略將一個乘客請求訂單發(fā)送給多名空載司機(jī)，司機(jī)憑手速搶單，這種模式下的主要分配策略有基于距離的訂單分配[13]和最大化訂單成功率的訂單分配[12]。系統(tǒng)派單模式則由出行平臺根據(jù)一定的策略將乘客請求與空載司機(jī)配對，由司機(jī)執(zhí)行匹配結(jié)果，目前主要的策略有基于乘客最短等待時間的訂單分配[14]、最小化全局乘客等待時間的訂單分配[15,16]、最大化司機(jī)收益的訂單分配[17,18]、模糊組合規(guī)則(Fuzzy Combination Rule)[19]和供需平衡策略(Demand-supply Balancing Strategy)[20]等。根據(jù)不同的受益對象，訂單分配策略又可以分為從乘客角度考慮的訂單分配策略、從司機(jī)角度考慮的訂單分配策略、融合乘客角度與司機(jī)角度的訂單分配策略以及從出行系統(tǒng)考慮的訂單分配策略[21]。

實現(xiàn)訂單分配策略，最初有廣播算法和貪婪算法(如先到先服務(wù)[22])。后來，隨著傳感設(shè)備、計算機(jī)存儲能力和計算能力不斷提升，數(shù)據(jù)收集、數(shù)據(jù)存儲、數(shù)據(jù)利用更加方便，且伴隨著計算機(jī)技術(shù)和大數(shù)據(jù)技術(shù)的發(fā)展，人們逐漸使用海量歷史數(shù)據(jù)學(xué)習(xí)潛在的有用信息和輔助訂單分配，其中主要的方法有深度神經(jīng)網(wǎng)絡(luò)[23]、強(qiáng)化學(xué)習(xí)[24]以及遷移學(xué)習(xí)[25,26]等。

文章的組織結(jié)構(gòu)如下：第2節(jié)簡述了系統(tǒng)從乘客發(fā)起乘車請求到請求被響應(yīng)的完整流程。第3節(jié)按不同派單模式詳細(xì)地介紹了不同的訂單分配策略，并描述了實現(xiàn)方法。第4節(jié)全面地列舉了訂單分配策略的評估指標(biāo)。最后一節(jié)對全文進(jìn)行總結(jié)。

2 請求處理及派單過程

圖1描述了從乘客發(fā)起打車請求到司機(jī)響應(yīng)平臺派單的完整流程，乘客通過手機(jī)打車軟件App(Application)輸入乘車起點(diǎn)和終點(diǎn)，向出行平臺發(fā)送打車請求。出行平臺獲取到乘客請求后，按照一定的規(guī)則匹配乘客請求與空載車輛。隨后，平臺將完成匹配的乘客信息和司機(jī)信息分別發(fā)送到彼此的打車軟件中，司機(jī)響應(yīng)平臺派單結(jié)果。在這個過程中，出行平臺系統(tǒng)全天24小時不間斷地實時收集網(wǎng)約車的信息(GPS、是否載客等)和乘客請求。

Figure 1 Process of online ride- hailing services圖1 網(wǎng)絡(luò)打車流程

在電話約車時代早期，乘客請求量少，系統(tǒng)中心通常采用集中分配方式。但是，隨著網(wǎng)絡(luò)打車需求逐漸增加，這種分配方式會延長乘客等待時間，降低車輛利用率。為了解決系統(tǒng)分配效率低的問題，分布式方式逐漸被使用[15]。通常，出行平臺將城市劃分為多個邏輯區(qū)域[17,22]，針對每一個區(qū)域產(chǎn)生的訂單獨(dú)立分配，為了縮短乘客等待時間，在一個分配周期會同時分配多個請求[12,15,17]，從而達(dá)到全局最優(yōu)的效果。

一般情況下，在分配系統(tǒng)服務(wù)器端存在一個乘客請求隊列，當(dāng)系統(tǒng)收到乘客請求時，將請求訂單加入隊列，與此同時，系統(tǒng)從隊列中獲取乘客請求進(jìn)行匹配。對于空載車輛信息，沒有固定的存儲方式，在調(diào)研的文獻(xiàn)中，有按空閑時間降序排列的隊列方式[22]，有按車輛進(jìn)入某一區(qū)域的時間先后順序排隊的隊列方式[16]。

3 訂單分配策略

搶單模式和系統(tǒng)派單模式最主要的區(qū)別在于司機(jī)是否可以參與訂單決策過程，或者在系統(tǒng)將訂單分派給司機(jī)后，司機(jī)之間是否還需要進(jìn)一步競爭訂單，如果仍然需要競爭則為搶單模式，否則為系統(tǒng)派單模式。在不同模式下，訂單分配結(jié)果的執(zhí)行方式不同，本節(jié)按照搶單模式和系統(tǒng)派單模式分別介紹網(wǎng)約車的訂單分配策略。

3.1 搶單模式下的訂單分配策略

在搶單模式的派單規(guī)則中，分配的乘客請求訂單與空載司機(jī)一般是一對多的形式，即一個請求訂單分派給多名空載司機(jī)，訂單在多個司機(jī)間被競爭，最終僅由一名司機(jī)獲得訂單的執(zhí)行權(quán)。本文根據(jù)分派策略中采用的關(guān)鍵參數(shù)將搶單模式下的訂單分配策略歸納為基于距離的訂單分配和基于歷史數(shù)據(jù)的訂單分配。

(1)基于距離的訂單分配。

2003年，新加坡出租車公司推出電話約車時，設(shè)計了一個分配系統(tǒng)AVLDS(Automatic Vehicle Location and Dispatch System)，它采用了基于距離的訂單分配方式[13]，即當(dāng)系統(tǒng)接收到乘客打車請求時，通過無線數(shù)據(jù)通信方式將乘客請求廣播給距離乘客10 km以內(nèi)的出租車，司機(jī)通過安裝在車上的按鈕響應(yīng)系統(tǒng)接單，如果請求在一定時間內(nèi)沒有司機(jī)響應(yīng)，系統(tǒng)將重新搜索最近的車輛再次派單。

(2)基于歷史數(shù)據(jù)的訂單分配。

網(wǎng)約車(出租車)產(chǎn)生的歷史訂單數(shù)據(jù)中蘊(yùn)含著豐富的潛在信息，滴滴出行在2017年根據(jù)歷史訂單數(shù)據(jù)學(xué)得司機(jī)接受訂單的可能性，將訂單分配給最有可能接受該訂單的空載司機(jī)，目的是盡可能提高訂單被完成的概率(成功率)[12]。比如,在一次訂單分配周期中，假設(shè)有N個訂單請求，M輛空載車輛，分配結(jié)果矩陣形如式(1)所示[7]：

(1)

(2)

(3)

3.2 系統(tǒng)派單模式下的訂單分配策略

由于在搶單模式下，司機(jī)的自主選擇權(quán)力更大，在決策的過程中，他們自身的偏好往往占據(jù)主導(dǎo)地位，一些目的地較為偏僻或者擁堵的訂單可能長時間沒有司機(jī)響應(yīng)，因而會大大地降低乘客滿意度。目前在市場上和研究中，系統(tǒng)派單模式逐漸成為主流。

(1)從乘客角度考慮的訂單分配策略。

從乘客角度考慮的訂單分配策略，包括基于最短接車時間的訂單分配[14]和最優(yōu)化全局乘客等待時間的訂單分配[15,16]。

通常，乘客滿意度與等待時間相關(guān)聯(lián)，等待時間越長，乘客滿意度越低。Lee等[14]認(rèn)為采用最短接車距離的訂單分配策略(即分派距離乘客最近的車輛前往接車)，乘客的等待時間不一定最短。如圖2所示，乘客與車輛在道路的兩端，雖然距離最近，但車輛需要在一個可掉頭的地方轉(zhuǎn)向去接乘客，如果存在另一輛距離遠(yuǎn)但能最快到達(dá)乘客起點(diǎn)位置的車輛，從乘客滿意度考慮，它將是更好的分派結(jié)果。因此，他在2004年提出了一個基于最短接車時間的訂單分派系統(tǒng)，結(jié)合派單時的交通情況，分派能最快到達(dá)乘客起點(diǎn)的車輛前往接客，這不僅縮短了乘客等待時間，同時也提高了車輛的利用率。

Figure 2 Driver pick-up passenger圖2 司機(jī)接客

隨著網(wǎng)絡(luò)打車越來越流行，出行平臺每秒鐘需要處理成百上千條乘客請求訂單，若按隊列順序逐一分配乘客請求，一方面系統(tǒng)需要具備更快的處理能力，另一方面乘客等待時間、司機(jī)接車距離等并沒有達(dá)到全局最優(yōu)。因此，2007年Seow等[15,16]從全局考慮，設(shè)計了一個分布式分配系統(tǒng)NTuCab(N-Taxi Group Collaborative)，并提出最小化全局乘客等待時間的訂單分配策略。如圖3所示(圖中‘s’代表時間單位秒)，乘客P1先發(fā)起請求，此時有C1、C2 2輛空車可用，按照最短乘客等待時間分配，將C1分配給P1，當(dāng)P2發(fā)起請求時，系統(tǒng)將剩下的空車C2分配給P2，則P1、P2總的等待時間為220 s。根據(jù)Seow提出的策略，要使總的乘客等待時間最短，則應(yīng)該將C1分配給P2，C2分配給P1，此時P1、P2總的等待時間為200 s，整體等待時間減少了20 s。

Figure 3 Order dispatch based on the shortest pickup time圖3 基于最短接車時間的訂單分配

(2)從司機(jī)角度考慮的訂單分配策略。

出行平臺作為中間橋梁，它的服務(wù)對象既有乘客也有司機(jī)，因此對于訂單分配策略的研究，出行平臺除了需要考慮乘客的滿意度，也需要兼顧司機(jī)的體驗感。為了避免出現(xiàn)司機(jī)長時間沒有乘客、空載距離長等現(xiàn)象，Alshamsi等[22]從司機(jī)的角度出發(fā)，提出了基于司機(jī)最長空閑時間的訂單分配、結(jié)合接車距離和空載時間的訂單分配[28]以及最大化司機(jī)收益的訂單分配[17,18]。

2009年，Alshamsi等[22]將空閑時間最長的出租車設(shè)置為優(yōu)先分派對象，目的是平衡司機(jī)利益。他將城市按照人口密度、道路結(jié)構(gòu)等要素劃分成多個邏輯區(qū)域，對每個區(qū)域建立一個請求隊列和空車隊列，在一個區(qū)域中當(dāng)有人發(fā)起打車請求時，系統(tǒng)搜索乘客所在區(qū)域內(nèi)的空載車輛，由空閑時間最長的司機(jī)獲得當(dāng)前分配的乘客請求訂單，如果當(dāng)前區(qū)域內(nèi)沒有空載車輛，1 min后系統(tǒng)搜索鄰近區(qū)域中時間最長的空載車輛進(jìn)行分配，如果1 min內(nèi)當(dāng)前區(qū)域和附近區(qū)域一直沒有可分配的車輛，則訂單將被系統(tǒng)取消。該系統(tǒng)第1次使用了多智能體[29]自組織技術(shù)[30]。

2017年，Kusuma[28]在Alshamsi等[22]的基礎(chǔ)上，綜合考慮司機(jī)接車距離和司機(jī)空閑時間，提出了3種不同的分配方案。系統(tǒng)按照乘客請求隊列中的順序，以先到先服務(wù)的原則，依次從乘客請求隊列中取出乘客訂單，按如下方案匹配請求訂單和空載車輛，分別是：①賦予司機(jī)空閑時間和接車距離一定權(quán)重，將訂單分配給權(quán)重和最大的司機(jī)。②將訂單廣播給一定圓形范圍內(nèi)的司機(jī)，選擇廣播域內(nèi)空閑時間最長的司機(jī)。如果有多名空閑時間一樣的司機(jī)，將訂單分配給距離最近的司機(jī)。③將空閑時間和接車距離按一定范圍劃分成相同大小的類別，不同類別分別賦予不同的分?jǐn)?shù)，其中，空閑時間長的類別分?jǐn)?shù)高，接車距離短的類別分?jǐn)?shù)高，將2個分?jǐn)?shù)相加，總分?jǐn)?shù)最高的司機(jī)獲得訂單。

除了接車時間和空閑時間，另一個最直接影響司機(jī)滿意度的是司機(jī)收益，滴滴出行在2018年提出了一種基于馬爾可夫決策過程MDP(Markov Decision Process) 的智能派單方法[17]，目的是整體提高司機(jī)的收入。它主要將訂單分配建模成為一個序列決策問題[31,32]，在線下利用強(qiáng)化學(xué)習(xí)從歷史數(shù)據(jù)中學(xué)得行為-狀態(tài)價值函數(shù)，在線上使用該函數(shù)計算當(dāng)前狀態(tài)下司機(jī)選擇訂單的收益，最后利用KM(Kuhn-Munkres)算法[33]求解二部圖[34,35]的最優(yōu)匹配，從而在全局上使司機(jī)收益最大。在這個策略中，滴滴出行將搶單模式轉(zhuǎn)變?yōu)橄到y(tǒng)派單模式，使訂單完成率提高了10%[17]。2019年，滴滴出行又提出了一個新的基于深度強(qiáng)化學(xué)習(xí)與半馬爾可夫決策過程的智能派單系統(tǒng)[18]，它在之前研究[17,36]的基礎(chǔ)上，同時將時間與空間作為長期優(yōu)化目標(biāo)，并利用深度神經(jīng)網(wǎng)絡(luò)進(jìn)行更準(zhǔn)確的價值估計。此外，對于數(shù)據(jù)量稀疏的城市，作者還提出了一種基于漸進(jìn)式網(wǎng)絡(luò)(Progressive Network)[37]的多城市遷移學(xué)習(xí)框架，利用其它城市豐富的數(shù)據(jù)量幫助其進(jìn)行價值估計。

(3) 融合乘客角度與司機(jī)角度的訂單分配策略。

融合乘客角度與司機(jī)角度的訂單分派策略，指系統(tǒng)在訂單分派過程中同時考慮了乘客與司機(jī)的利益，目前，這類策略主要包括模糊組合規(guī)則[19]和供需平衡策略[20]。

分派系統(tǒng)解決了司機(jī)與乘客之間信息不對稱的問題，使得空閑車輛得以有效利用，使乘客需求能被盡快滿足。Shrivastava等[19]認(rèn)為分派時不僅要考慮乘客的等待時間，還需要均衡司機(jī)之間獲得分派的機(jī)會，并在最近車輛規(guī)則(Nearest Vehicle Rule)和最少使用車輛規(guī)則(Least Utilized Vehicle Rule)的基礎(chǔ)上，提出一種模糊組合規(guī)則，即將乘客訂單分配給距離乘客較近且利用率較低的車輛，Shrivastava利用函數(shù)μnearness(·)、μutilization(·)分別將車輛與乘客的距離、車輛利用值映射到[0，1]，最后采用組合規(guī)則函數(shù)μ(·)求得分派結(jié)果。

(4)

(5)

(6)

(7)

其中，x表示車輛與乘客之間的距離，l代表車輛利用值(即l=utilization(k),k∈T)，T為待分配的車輛集合，N為待分配的車輛總數(shù)，j表示最終分派的車輛，max(·)和min(·)分別代表最大值函數(shù)和最小值函數(shù)，a、b、c、d是常量，且由系統(tǒng)設(shè)置。

當(dāng)出現(xiàn)供需不平衡時，尤其在需求量遠(yuǎn)大于供應(yīng)量的情況下，采用最近空閑車輛的規(guī)則，對司機(jī)而言，其接車時間并非最短。因此，Maciejewski等[20]在2016年提出了一種供需平衡策略，即當(dāng)前有空閑車輛時，系統(tǒng)按照先到先服務(wù)原則獲取乘客隊列中的第1個請求，分派給與它距離最近的空閑車輛k*,k*的計算公式如式(8)所示[20]。當(dāng)前沒有空閑車輛時，一旦有車輛完成送客任務(wù)后，它將被分派給距離它最近的乘客i*,i*的計算公式如式(9)所示[20]。

(8)

(9)

(4)從出行系統(tǒng)考慮的訂單分配策略。

出租車公司的主要收益來自出租車司機(jī)向公司上繳的固定租車費(fèi)用，而出行平臺主要從一次完整的行程訂單中按比例抽取一定的費(fèi)用[38]，因此使用平臺打車的人越多、司機(jī)完成的訂單量越多，它獲取的利益越大。對出行平臺而言，除了考慮司機(jī)和乘客的感受，同時也需要考慮自身利益。2016年，Gao等[21]根據(jù)乘客等待時間和司機(jī)純利潤，定義了系統(tǒng)的效用函數(shù)(如式(10)所示)，在司機(jī)對個人凈利潤和乘客對網(wǎng)約車特殊要求的限制條件下，提出最大化整個系統(tǒng)收益。他同樣將分配問題轉(zhuǎn)化為帶權(quán)二部圖的匹配問題，并提出了一種基于KM算法的新的解決方案。

(10)

3.3 分派系統(tǒng)對比

為了對比訂單分配策略之間的區(qū)別，本文將上述訂單分配策略對應(yīng)的分派系統(tǒng)匯總于表1，并對比了他們的分派模式、優(yōu)化目標(biāo)和評估指標(biāo)等。從表1我們可以知道，大多數(shù)的訂單分配策略研究主要基于系統(tǒng)派單模式，由于系統(tǒng)派單減少了司機(jī)參與決策的過程，因此司機(jī)只需執(zhí)行系統(tǒng)派單結(jié)果，同時也更專注于服務(wù)乘客；另一方面，系統(tǒng)派單還能緩解供需不平衡問題，避免司機(jī)拒載等現(xiàn)象。在優(yōu)化目標(biāo)方面，多數(shù)文獻(xiàn)主要從乘客角度或者司機(jī)角度考慮優(yōu)化，對乘客而言，優(yōu)化最多的是乘客等待時間，因為乘客等待時間與乘客的滿意度相關(guān)，等待時間越長，乘客滿意度越低；對于司機(jī)，空閑時間和收益是主要優(yōu)化對象，因為這2個因素直接關(guān)系到司機(jī)收入。在衡量指標(biāo)方面，多數(shù)分派系統(tǒng)主要評估等待時間(包含分配時間和接車時間)、司機(jī)總收益、訂單被服務(wù)比例這3個指標(biāo)，這是因為它們分別與乘客、司機(jī)、出行平臺緊密相關(guān)，最能集中體現(xiàn)三方各自的利益。

在表1中，除了系統(tǒng)AVLDS、NTuCab，其他系統(tǒng)都以文獻(xiàn)第1位作者的姓或公司的名字代表。乘客請求訂單如果是逐一分配，則系統(tǒng)一次分配一個訂單，否則系統(tǒng)在一個分配周期內(nèi)同時分配多個訂單。此外，表中‘-’表示沒有的意思，評估對象中出現(xiàn)的所有評估參數(shù)都在本文第4節(jié)作了詳細(xì)分類和解釋。

Table 1 Comparision of different dispatch systems

3.4 其他相關(guān)研究

共享乘車的訂單分配[39 - 41]與網(wǎng)約車訂單分配是最相近的研究。共享乘車方式一定程度上滿足了更多人的需求，減少了乘客等待時間，增加了司機(jī)收入和車輛利用率。尤其在乘車需求量很大的時候，即市場供不應(yīng)求時，更多的人會選擇共享乘車。而且從節(jié)能環(huán)保的角度看，共享乘車是一種綠色的出行方式。但是，共享乘車方式普遍存在司機(jī)繞路接客、司機(jī)繞路送客等現(xiàn)象，很容易影響司機(jī)服務(wù)乘客的質(zhì)量。另一方面，共享乘車對訂單分配提出了更高要求，系統(tǒng)需要考慮更多的限制條件，比如乘客人數(shù)、乘客對性別的要求等。

匹配問題是與訂單分配策略很相近的另一個研究方向。為了匹配乘客與司機(jī)，文獻(xiàn)[42]分別將待分配乘客和司機(jī)作為二部圖的2個頂點(diǎn)集，乘客與司機(jī)之間的距離作為邊權(quán)值，直接利用匈牙利算法及其改進(jìn)算法求解二部圖的完美匹配，通過引入虛擬乘客或司機(jī)解決乘客和司機(jī)數(shù)量不對等問題。Zheng等[38]將司乘匹配問題轉(zhuǎn)化為穩(wěn)定婚姻問題SMP(Stable Marriage Problem)，并提出一種穩(wěn)定婚姻方法分派出租車。除此之外，在很多網(wǎng)約車訂單分配系統(tǒng)中[17,18,21]，在一個分配周期里，為了達(dá)到全局最優(yōu)的效果，通常將訂單分配問題轉(zhuǎn)化為帶權(quán)二部圖的最優(yōu)匹配問題，并利用KM算法或者改進(jìn)的KM算法求解。將訂單分配問題轉(zhuǎn)化為帶權(quán)二部圖的最優(yōu)匹配問題，關(guān)鍵點(diǎn)在于如何求得二部圖的權(quán)值。

4 訂單分配策略評估指標(biāo)

實驗中，通常需要記錄實驗結(jié)果并用它們驗證實驗猜想和衡量實驗好壞。本節(jié)根據(jù)派單過程中的參與對象，將訂單分配評估指標(biāo)歸納為乘客指標(biāo)、司機(jī)指標(biāo)和出行平臺指標(biāo)。

4.1 乘客指標(biāo)

乘客指標(biāo)，主要從乘客角度衡量網(wǎng)約車訂單分派系統(tǒng)的優(yōu)缺點(diǎn)，它可以間接地衡量乘客對分配結(jié)果的滿意程度。本節(jié)根據(jù)調(diào)查文獻(xiàn)中不同乘客指標(biāo)出現(xiàn)的頻率，將乘客指標(biāo)分為常用指標(biāo)和其它指標(biāo)。

(1)常用指標(biāo)。

等待時間，指乘客發(fā)起打車請求到乘客上車這段時間，它包括等待系統(tǒng)分配時間(從乘客發(fā)起打車請求到系統(tǒng)完成分配的時間)和等待司機(jī)接車時間(從司機(jī)接到系統(tǒng)派單任務(wù)到司機(jī)抵達(dá)乘客起點(diǎn)的時間)，這三者之間的關(guān)系如式(11)[42]所示，其中，Waittotal、Waitmatching、Waittravel分別代表乘客等待時間、等待系統(tǒng)分配訂單時間以及等待司機(jī)接車時間。無論是等待系統(tǒng)分配時間還是等待司機(jī)接車時間，時間越長，乘客滿意度越低，最終甚至取消請求訂單。除此之外，系統(tǒng)分配時間越長，表示系統(tǒng)分配效率越低。

Waittotal=Waitmatching+Waittravel

(11)

乘客取消訂單數(shù)，表示分派系統(tǒng)在真實環(huán)境中運(yùn)行時，由乘客主動取消打車請求的訂單數(shù)量，同乘客等待時間一樣，它包括乘客在系統(tǒng)派單階段取消訂單的數(shù)量和在系統(tǒng)分配派單任務(wù)后取消訂單的數(shù)量。造成乘客取消訂單的原因有很多，比如乘客更改行程、系統(tǒng)派單時間長和司機(jī)接車時間長等。

(2)其它指標(biāo)。

在大多數(shù)的訂單分派系統(tǒng)[12,14,15,22]采用常用的乘客評估指標(biāo)，但也有文獻(xiàn)提出新的衡量指標(biāo)，比如在文獻(xiàn)[38]中，作者用乘客和司機(jī)之間的最短路徑距離表示乘客的不滿意程度，當(dāng)距離越大時，表示乘客越不滿意。

4.2 司機(jī)指標(biāo)

司機(jī)指標(biāo)，主要從司機(jī)角度衡量訂單分配策略的好壞，同乘客指標(biāo)一樣，本節(jié)將司機(jī)指標(biāo)總結(jié)為常用指標(biāo)和其它指標(biāo)。

(1)常用指標(biāo)。

對司機(jī)而言，收入是最直接的利益，它可以用來衡量司機(jī)對派單系統(tǒng)的滿意程度。一般情況下，司機(jī)收益直接在運(yùn)行系統(tǒng)中統(tǒng)計，但Gao[21]等提出了一種計算單個司機(jī)純利潤的公式(如式(12)所示[21])，其中Nij表示將司機(jī)j安排給乘客i的純利潤，α和β分別代表每公里乘坐出租車的費(fèi)用和司機(jī)支出的費(fèi)用，si表示乘客的行程總長，而sij表示司機(jī)j到乘客i的距離。最后求和所有司機(jī)的純利潤并將它作為衡量系統(tǒng)的指標(biāo)之一。另外，文獻(xiàn)[17]認(rèn)為司機(jī)收益與司機(jī)載客行駛距離有關(guān)，他在實驗過程中統(tǒng)計了所有已完成訂單的距離之和，并把它作為司機(jī)總收益和評估指標(biāo)之一。

Nij=αsi-β(si+sij)

(12)

空載時間(距離)，指司機(jī)在沒有載客任務(wù)情況下行駛的總時間(距離)，它不僅能反映分配算法的效率[42]，也在一定程度上反映了車輛的利用率，空載時間(距離)越長，車輛利用率越低。此外，空載行駛不僅浪費(fèi)司機(jī)時間，而且消耗油量，增加司機(jī)的支出。如果訂單策略分配合理，司機(jī)空載時間得到有效利用，能促使更多乘客需求被滿足。

完成(取消)訂單數(shù)，指司機(jī)在評估時間范圍內(nèi)完成(取消)訂單的總數(shù)，它間接地表明分配系統(tǒng)的效率和司機(jī)對派單結(jié)果的滿意度，司機(jī)完成訂單的數(shù)量越多，表明分配效果越好。此外，造成司機(jī)取消分配訂單的原因有很多，比如司機(jī)個人原因、司機(jī)距離分配的乘客太遠(yuǎn)、乘客的目的地太偏僻等。響應(yīng)訂單數(shù)，指司機(jī)在評估時間范圍內(nèi)響應(yīng)系統(tǒng)派單的總數(shù)，響應(yīng)訂單數(shù)不等于完成訂單數(shù)，因為司機(jī)響應(yīng)系統(tǒng)派單僅表示司機(jī)接受系統(tǒng)分配的派單任務(wù)，在這之后如果乘客取消了訂單分配，則司機(jī)并不能完成這個訂單請求。對完成訂單數(shù)、取消訂單數(shù)、響應(yīng)訂單數(shù)求平均即為完成訂單比例(成功率[12]、完單率[18])、取消訂單比例、響應(yīng)訂單比例(應(yīng)答率[17,18])。

(2)其它指標(biāo)。

(13)

4.3 出行平臺指標(biāo)

對出行平臺而言，乘客和司機(jī)的滿意程度除了用乘客指標(biāo)和司機(jī)指標(biāo)衡量外，另一個最直觀的評價是乘客在手機(jī)應(yīng)用上對每一次行程的評分。但通常情況下，只有一小部分乘客會在完成一次行程后主動參與評分活動，同時在實際情況中，存在司機(jī)為了高分而主動邀請乘客給予好評的現(xiàn)象，因此乘客評分并不能完全客觀地反映出乘客的真實感受。

同司機(jī)收益指標(biāo)一樣，出行平臺的收益也可以直接從運(yùn)行系統(tǒng)中統(tǒng)計。由于出行平臺將從每一個行程訂單中按比例抽取一定的費(fèi)用作為報酬，所以司機(jī)完成訂單的數(shù)量也能間接地反映出行平臺的收益。除此之外，文獻(xiàn)[21]定義了系統(tǒng)效用值函數(shù)(如式(10)所示)，并將它作為衡量分配系統(tǒng)的指標(biāo)之一。

5 結(jié)束語

從路邊招手打車，到出行平臺智能派單，出租車打車方式的變化促進(jìn)了網(wǎng)約車訂單分配策略的進(jìn)步，使越來越多的乘客需求得到滿足，縮短了乘客等待時間，逐漸地提高了司機(jī)的收益。本文第一次全面地總結(jié)了從手機(jī)約車到網(wǎng)絡(luò)打車方式中的訂單分配策略以及相應(yīng)的評估指標(biāo)，我們發(fā)現(xiàn)，目前的策略通常只考慮了乘客、司機(jī)和出行平臺三方中的某一方或兩方的利益，出行平臺作為提供服務(wù)的第三方，如果只滿足乘客或者司機(jī)的利益，都將會降低另一方的使用感和滿意度。因此，我們下一步的研究工作將圍繞如何平衡司機(jī)和乘客之間利益的同時使總的訂單完成量最大展開，從而在乘客、司機(jī)和出行平臺之間形成三贏的局面。