關(guān)于網(wǎng)約車(chē)訂單分配策略的綜述*

鄭小紅，龍 軍，蔡志平

(國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073)

1 引言

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

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

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

實(shí)現(xiàn)訂單分配策略，最初有廣播算法和貪婪算法(如先到先服務(wù)[22])。后來(lái)，隨著傳感設(shè)備、計(jì)算機(jī)存儲(chǔ)能力和計(jì)算能力不斷提升，數(shù)據(jù)收集、數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)利用更加方便，且伴隨著計(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é)簡(jiǎn)述了系統(tǒng)從乘客發(fā)起乘車(chē)請(qǐng)求到請(qǐng)求被響應(yīng)的完整流程。第3節(jié)按不同派單模式詳細(xì)地介紹了不同的訂單分配策略，并描述了實(shí)現(xiàn)方法。第4節(jié)全面地列舉了訂單分配策略的評(píng)估指標(biāo)。最后一節(jié)對(duì)全文進(jìn)行總結(jié)。

2 請(qǐng)求處理及派單過(guò)程

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

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

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

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

3 訂單分配策略

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

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

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

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

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

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

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

(1)

(2)

(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)

(5)

(6)

(7)

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

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

(8)

(9)

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

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

(10)

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

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

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

Table 1 Comparision of different dispatch systems

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

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

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

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

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

4.1 乘客指標(biāo)

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

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

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

Waittotal=Waitmatching+Waittravel

(11)

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

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

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

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

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

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

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

Nij=αsi-β(si+sij)

(12)

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

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

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

(13)

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

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

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

5 結(jié)束語(yǔ)

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