基于候客點(diǎn)規(guī)劃的空閑出租車路線推薦算法

陳冬梅，卜霄菲，黃 河，杜 揚(yáng)，高國舉，孫玉娥

（1.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006；2.沈陽師范大學(xué) 軟件學(xué)院，沈陽 110034；3.蘇州大學(xué) 軌道交通學(xué)院，江蘇 蘇州 215137）

0 概述

隨著定位技術(shù)和4G/5G 技術(shù)的發(fā)展，裝備全球定位系統(tǒng)（Global Position System，GPS）設(shè)備的出租車越來越多［1-3］。通過對該類設(shè)備采集得到的海量軌跡數(shù)據(jù)進(jìn)行挖掘分析，可以在改善出租車服務(wù)質(zhì)量方面提供更好的數(shù)據(jù)支撐，令出租車服務(wù)更加舒適、快捷，使出租車成為更多乘客的出行選擇［4］。然而，在面臨日益增長的乘客需求和出租車供給不平衡的矛盾時(shí)，如何為空閑司機(jī)規(guī)劃路線，以最短時(shí)間和最短距離接載到乘客，成為學(xué)術(shù)界關(guān)注的熱點(diǎn)問題［5-7］。

傳統(tǒng)的空閑出租車路線推薦主要有2 種方式：載客點(diǎn)推薦［8-10］和載客路線推薦［5-7］。載客點(diǎn)推薦一般是通過對歷史軌跡數(shù)據(jù)的上下車事件進(jìn)行聚類從而發(fā)現(xiàn)乘客需求較多的載客點(diǎn)，當(dāng)司機(jī)發(fā)出請求時(shí)，可以推薦司機(jī)前往最近的接載點(diǎn)。例如文獻(xiàn)［8］通過歷史軌跡數(shù)據(jù)檢測停車點(diǎn)，從而并向空閑司機(jī)推薦這些停車點(diǎn)以最快的時(shí)間接載到乘客。文獻(xiàn)［9］通過將底層道路網(wǎng)絡(luò)聚類成多個(gè)路段集群，根據(jù)每個(gè)集群的特征評估其尋客潛力并進(jìn)行推薦。然而，該類方法忽略了前往這些載客熱點(diǎn)的路線并不唯一的問題，在沒有經(jīng)驗(yàn)知識的情況下，司機(jī)如何選擇效益最高的路線是一個(gè)難以解決的問題。

為解決接載點(diǎn)推薦存在的問題，近幾年的研究工作主要集中在為空閑司機(jī)推薦接載路線，原因是相比較只推薦接載點(diǎn)而言，直接推薦完整的路徑可以為無經(jīng)驗(yàn)的司機(jī)減少閑逛距離，從而減少空閑時(shí)的花費(fèi)成本。其中，文獻(xiàn)［5］提出路段的凈利潤函數(shù)，向司機(jī)推薦潛在利潤最大的路線。文獻(xiàn)［6］在文獻(xiàn)［5］的工作基礎(chǔ)上提出了一個(gè)基于蒙特卡洛搜索樹思想的路線推薦方法，實(shí)現(xiàn)了動態(tài)的接載概率。文獻(xiàn)［7］提出自適應(yīng)最短預(yù)期閑逛路線的推薦方法，能夠根據(jù)位置的容量和接載概率推薦路線。

目前存在的路線推薦方法主要是為空閑司機(jī)推薦一條完整的駕駛路線，直到司機(jī)接載到乘客或者遇到終點(diǎn)路段才停止推薦。但該方式忽略了真實(shí)路網(wǎng)環(huán)境下某些路段的可等待因素。例如餐飲服務(wù)集中地區(qū)、大型商場周圍、地鐵公交車站附近以及學(xué)校周邊的可停車路段，這些路段都會在特定的時(shí)間段（如車站到達(dá)、地鐵換乘、上課放學(xué)等時(shí)段）出現(xiàn)大量乘車需求。當(dāng)司機(jī)在某時(shí)段經(jīng)過這些路段時(shí)，傳統(tǒng)方法依然會繼續(xù)推薦行駛路線，卻沒有預(yù)判到該路段未來某段時(shí)間的乘車需求對司機(jī)決策的影響。例如當(dāng)司機(jī)經(jīng)過地鐵站附近的路段時(shí)，如果該地鐵站在未來1 min 剛好到站則會出現(xiàn)大量換乘乘客，此時(shí)司機(jī)選擇停車等待可能會更快接到乘客。相反，如果司機(jī)選擇繼續(xù)行駛，則會導(dǎo)致空閑出租車的閑逛距離過長，工作收益降低。相比較傳統(tǒng)的路線推薦方法而言，考慮路段等待因素不僅可以幫助司機(jī)更快地接載到乘客，而且可以幫助司機(jī)降低因閑逛產(chǎn)生的油費(fèi)損耗，從而進(jìn)一步減少能源消耗以及廢氣排放造成的空氣污染［11-12］。此外，通過考慮路段的可等待因素還可以幫助乘客減少因換乘產(chǎn)生的等待時(shí)間，在提高搭載雙方工作效率的同時(shí)，進(jìn)一步緩解交通擁堵的壓力，對提高城市的流動性具有重要意義［13-14］。

本文針對當(dāng)前路線推薦方法存在忽略路段可等待因素的問題，提出一種基于候客點(diǎn)規(guī)劃的空閑出租車路線推薦機(jī)制。通過分析出租車行駛過程產(chǎn)生的軌跡數(shù)據(jù)，將軌跡點(diǎn)和真實(shí)路段建立聯(lián)系。同時(shí)，處理出租車行走路段的歷史搭載信息，從而構(gòu)建接載概率預(yù)測模型?；谝延袛?shù)據(jù)，以推薦花費(fèi)成本更小的路線策略為準(zhǔn)則，提出一種考慮等待時(shí)間的路線推薦算法，并在真實(shí)的出租車軌跡數(shù)據(jù)集上驗(yàn)證該算法的有效性。

1 相關(guān)工作

目前關(guān)于出租車路線推薦方法主要有2 種：向出租車司機(jī)推薦接載熱點(diǎn)及向出租車司機(jī)推薦完整路線。

針對第1 種推薦方式，YUAN 等［13-14］通過學(xué)習(xí)乘客的移動模式和司機(jī)接載行為的知識，建立概率模型進(jìn)行停車點(diǎn)的推薦，使司機(jī)能以最短的時(shí)間接載到乘客。WANG 等［9］提出一 種基于排序的ELM 模型，該模型可以根據(jù)道路集群的拾取頻率來評估所有道路集群的尋客潛力并向出租車司機(jī)推薦具有最高尋客潛力的Top-k 道路集群。VERMA 等［15］基 于強(qiáng)化學(xué)習(xí)方法，利用蒙特卡抽樣建模經(jīng)驗(yàn)司機(jī)的行為，并通過司機(jī)的行為偏好捕捉乘客的需求變化，為閑逛司機(jī)推薦長期利益最大化的區(qū)域。CHEN 等［16］提出利用空閑狀態(tài)計(jì)算接載點(diǎn)的利潤并結(jié)合DBSCAN 聚類算法提取高利潤的乘客區(qū)域推薦給空閑司機(jī)。LI 等［17］基于司機(jī)目的點(diǎn)偏好這一因素提出基于目地點(diǎn)概率最大化的推薦算法PROMISE，為空閑司機(jī)推薦滿足目的區(qū)域的一系列接載點(diǎn)。LI 等［18］提出一種改進(jìn)的ARIMA 方法，預(yù)測熱點(diǎn)區(qū)域乘客移動的時(shí)空區(qū)域，從而挖掘出乘客的移動模式。HWANG 等［19］通過建立ON-OFF 模型獲取乘客下車位置和下一位乘客上車位置之間的關(guān)系，并估計(jì)出推薦點(diǎn)的期望利益。然而，這些推薦方法基本都是基于位置點(diǎn)的推薦而非實(shí)際的完整路線，而這對司機(jī)在找到乘客之前如何減少閑逛時(shí)間十分重要。

針對第2 種推薦方式，向出租車司機(jī)推薦完整路線，QU 等［5］提出一種Cost-Effective 的路線推薦系統(tǒng)，該系統(tǒng)首先提出一個(gè)凈利潤函數(shù)（乘客收益-出租車花費(fèi)）來評估每個(gè)路段的潛在收益?；谶f歸樹的思想生成尋找乘客的候選路徑，并利用凈利潤函數(shù)計(jì)算每個(gè)候選路徑的收益，并將收益最大的路徑推薦給空閑出租車司機(jī)。GARG 等［6］提出一個(gè)基于蒙特卡羅搜索樹的尋客策略，目的是令空閑司機(jī)與預(yù)期乘客之間的閑逛距離最小化。JI 等［11］將最小化空閑時(shí)間作為學(xué)習(xí)目標(biāo)，提出一個(gè)自適應(yīng)的深度強(qiáng)化學(xué)習(xí)策略，并進(jìn)行路線推薦。該工作通過深度網(wǎng)絡(luò)融合多個(gè)實(shí)時(shí)的內(nèi)外部特征，并為每個(gè)候選路徑學(xué)習(xí)一個(gè)評價(jià)分?jǐn)?shù)。同時(shí)，利用強(qiáng)化學(xué)習(xí)策略進(jìn)行學(xué)習(xí)，實(shí)時(shí)捕捉候選路徑的推薦分?jǐn)?shù)，并將分?jǐn)?shù)最高的路線推薦給空閑司機(jī)。QU 等［7］提出一個(gè)出租車收益的路線推薦方法即自適應(yīng)最短預(yù)期閑逛路線（ASER）。該方法通過設(shè)計(jì)概率網(wǎng)格發(fā)現(xiàn)潛在的接載位置和動態(tài)的接載概率，然后利用卡爾曼濾波方法預(yù)測每個(gè)網(wǎng)格的接載概率和容量，并在大數(shù)據(jù)應(yīng)用平臺下開發(fā)新的數(shù)據(jù)結(jié)構(gòu)框架以提高推薦效率。LUO 與LV 等［20-21］基于接載乘客的概率和容量問題，也提出一種出租車路線推薦方法，為一組司機(jī)推薦最優(yōu)的路線，目的是最小化平均閑逛駕駛距離。RONG 等［22-23］基于馬爾科夫決策模型為出租車司機(jī)推薦長期利潤最大化的路線。盡管當(dāng)前存在的空閑出租車路線推薦工作已經(jīng)解決了一些問題，但是這些方法均忽略了真實(shí)路網(wǎng)環(huán)境下某些路段的可等待因素，使推薦的路線因載客概率較低、行駛距離較長而花費(fèi)成本變高。

2 模型構(gòu)建

2.1 符號說明

定義1（節(jié)點(diǎn)）節(jié)點(diǎn)是指某2 個(gè)路段相交的點(diǎn)，可以表示為s=(id，lat，lon)，其中：id 是該節(jié)點(diǎn)的唯一標(biāo)識符；lat 和lon 分別表示該節(jié)點(diǎn)所在的經(jīng)緯度信息。

定義2（路段）1 條完整的路徑可以被多個(gè)節(jié)點(diǎn)s分割成多個(gè)路段序列r，其中每個(gè)路段均由2 個(gè)節(jié)點(diǎn)確定，即r=(sstart，send)。如果該路段不是終點(diǎn)路段，則與其相連的其他路段稱為它的鄰居路段，可以表示為

定義3（路線）路線R由一系列相連的路段組成，可以表示為R={r1→r2→…→rn}，滿足對于?i，1≤i≤n，，且該路 線的起點(diǎn) 為R_start=，該路線的終點(diǎn)為R_end=

定義4（路網(wǎng)）1 個(gè)路網(wǎng)可以表示為有向圖G(V，E，D)，其中：V表示所有節(jié)點(diǎn)的集合{s1，s2，…，sn；E={ri→j|si(idi，lati，loni)，sj(idj，latj，lonj)∈V} }表 示所有有向路段的集合；D表示為每個(gè)路段物理距離長度的集合，可由Haversine 式（1）計(jì)算得出：

其中：φ是節(jié)點(diǎn)s的緯度；λ是節(jié)點(diǎn)s的經(jīng)度；RRadius為地球半徑（6 371 km）。

定義5（軌跡）軌跡是按時(shí)間序列排序的一系列GPS 采樣點(diǎn)組成的集合，可以表示為Tr={p1→p2→…→pn}，其中每個(gè)采樣點(diǎn)表示為pi={lat，lon，time，empty，speed}記錄著采樣點(diǎn)的位置信息、時(shí)間戳、載客狀態(tài)、速度等信息。對于出租車的載客狀態(tài)可以由式（2）表示：

從出租車的軌跡數(shù)據(jù)中進(jìn)一步挖掘出租車是否處于停車狀態(tài)，并通過該狀態(tài)標(biāo)識可停車路段。對于2 個(gè)連續(xù)的GPS 采樣點(diǎn)pi和pi+1，利用Haversine 公式計(jì)算這2 個(gè)采樣點(diǎn)之間的距離與時(shí)間間隔，當(dāng)距離小于預(yù)先定義的距離閾值且時(shí)間間隔大于采集間隔時(shí)，認(rèn)為此時(shí)出租車的狀態(tài)為停車狀態(tài)，意味著司機(jī)經(jīng)過該路段時(shí)可以選擇停留。值得注意的是，本文定義的停車路段是司機(jī)在該路段等待有需求的乘客。在現(xiàn)實(shí)生活中，這類場景多數(shù)會出現(xiàn)在周圍有車站、商場附近、居民區(qū)等的路段。

定義6（時(shí)變的接載概率）由于不同道路環(huán)境、不同天氣以及不同時(shí)段等因素的影響，對于某一路段的乘客需求在不斷變化，因此對于任意的某一路段r在時(shí)間間隔[τ1，τ2]內(nèi)的搭載概率為：

2.2 問題描述

定義7當(dāng)出租車司機(jī)放下乘客處于空閑狀態(tài)時(shí)，可以發(fā)出尋客請求。根據(jù)空閑司機(jī)發(fā)出請求的路段r1和請求時(shí)間t，為空閑出租車司機(jī)推薦1 個(gè)效益最大化的接載路線R*={r1，r2，…，rL}，使得空閑司機(jī)選擇這條行駛路徑接載到乘客時(shí)的閑逛距離、閑逛時(shí)間和花費(fèi)成本最小，其中L表示選擇路徑的長度。

由于司機(jī)的花費(fèi)成本涉及到司機(jī)在接載到乘客之前所行駛的距離和所花費(fèi)的時(shí)間，因此對于每個(gè)路段的潛在花費(fèi)成本可以根據(jù)式（4）得出：

其中：p(ri，[τ1，τ2])表示在該路段接載到乘客的概率；Frent是出租車司機(jī)租賃出租車的費(fèi)用；Fgas是出租車行駛d(r)距離所花費(fèi)的汽油費(fèi)；tp(r)是出租車穿過該路段所花費(fèi)的時(shí)間；tw(r)是出租車停留在該路段所花費(fèi)的時(shí)間；t=tw+tp是出租車司機(jī)在該路段上花費(fèi)的總時(shí)間。

對于每個(gè)路段的潛在收益可根據(jù)式（5）得出：

因此對于每個(gè)路段的凈收益可由式（6）計(jì)算得出：

由該公式可以看出影響司機(jī)收益的重要因素是在閑逛時(shí)所花費(fèi)的時(shí)間和距離。因此，如果想要提高司機(jī)的收益，需要不斷減小司機(jī)在閑逛時(shí)所花費(fèi)的成本，即Minimise(Cost(r，t))。

基于以上定義，對于任意推薦路線R={r1，r2，r3，…，rL}可以計(jì)算其花費(fèi)成本函數(shù)為：

式（7）表示對于推薦的路徑R來說，當(dāng)出租車司機(jī)在路段rL接到乘客時(shí)，所花費(fèi)的成本最小。

以往的推薦算法是推薦一個(gè)連續(xù)駕駛路線，只考慮經(jīng)過路段的當(dāng)前接載概率，若經(jīng)過該路段沒有接載到乘客，則會繼續(xù)推薦路線，導(dǎo)致閑逛距離變長，花費(fèi)成本變高。而本文算法考慮了路段的可等待因素。當(dāng)出租車司機(jī)經(jīng)過靠近地鐵站、車站、學(xué)校等地方的路段時(shí)，能夠預(yù)判未來某個(gè)時(shí)刻可能發(fā)生的事件，比如由于地鐵到站而出現(xiàn)大量換乘乘客。本文算法推薦的具體步驟如下：1）根據(jù)歷史GPS 軌跡信息為每個(gè)路段統(tǒng)計(jì)出最長等待時(shí)間；2）設(shè)定司機(jī)在某路段等待的時(shí)間閾值是3 min，單位時(shí)間間隔是1 min；3）當(dāng)空閑司機(jī)在r1路段發(fā)出請求時(shí)，對于r1的鄰居路段{r2，r3，r4}以及等候間隔有2 種方案選擇。這2 種方案具體如下：

方案1在請求路段等待1～3 min，接到乘客；

方案2在請求路段等待1～3 min 后，選擇前往下一個(gè)路段。

對于某個(gè)司機(jī)在某一路段的選擇可由式（8）表示：

其表達(dá)含義是選擇最小花費(fèi)的行駛路段以及等待時(shí)間時(shí)的方案。因此，對于所有行駛時(shí)間小于Tmin，駕駛路段不超過L的候選路徑R={R1，R2，…，Rn}，本文的目標(biāo)是選擇1 個(gè)花費(fèi)成本最小的候選路徑R*，滿足：

3 算法設(shè)計(jì)

如圖1 所示，基于候客點(diǎn)規(guī)劃的空閑出租車路線推薦方法主要分為3 個(gè)步驟：1）進(jìn)行數(shù)據(jù)預(yù)處理，利用最短路徑匹配算法將GPS 軌跡匹配到真實(shí)的路網(wǎng)環(huán)境中，并依據(jù)連續(xù)2 個(gè)GPS 點(diǎn)之間的距離和時(shí)間屬性識別可停車路段，將停車時(shí)間超過5 min 的路段標(biāo)記出來；2）根據(jù)每個(gè)路段發(fā)生接載事件的特征，利用改進(jìn)的多層感知機(jī)有效地預(yù)測不同天、不同時(shí)段以及不同天氣情況下的接載概率；3）根據(jù)每個(gè)路段的接載概率，設(shè)計(jì)考慮等待時(shí)間的最小成本優(yōu)化路徑算法，從而進(jìn)行有效的路線推薦，實(shí)現(xiàn)效益最大化。

圖1 出租車路線推薦框架Fig.1 Framework of taxi route recommendation

3.1 路段匹配算法

在實(shí)際的數(shù)據(jù)采集過程中，由于設(shè)備的精度誤差、路網(wǎng)障礙物、信號強(qiáng)弱因素的影響，GPS 設(shè)備采集到的軌跡點(diǎn)往往散落在道路周圍而無法匹配到具體的路段上。本文首要解決的問題是為軌跡數(shù)據(jù)匹配具體的路段，并根據(jù)狀態(tài)位的表示為每個(gè)路段統(tǒng)計(jì)載客次數(shù)和空載次數(shù)，具體的算法描述及操作過程如下：

算法1路段匹配

結(jié)合實(shí)例（如圖2）對路段匹配算法1 進(jìn)行分析。對于待處理軌跡點(diǎn)p2，首先根據(jù)路網(wǎng)數(shù)據(jù)為其劃分1 個(gè)緩沖區(qū)buffe，如圖2（a）所示。該緩沖區(qū)由當(dāng)前點(diǎn)p2為中心點(diǎn)，radius 作為半徑進(jìn)行劃分。接著找到與該緩沖區(qū)相交的所有路段作為p2的候選路段candiSeg（算法1 第5 行）。然后對候選路段candiSeg進(jìn)行判斷：情況1，如果候選路段為空則返回null，匹配失?。磺闆r2，如果只包含一個(gè)候選路段則直接返回該路段作為匹配路段（如算法1 第6～9 行所示）；情況3，如果存在多個(gè)候選路段，如圖2（a）所示，candiSeg={r1，r2，r3}，則繼續(xù)進(jìn)行判斷。遍歷所有候選路段candiSeg，通過最短距離函數(shù)finddis 計(jì)算出與p2點(diǎn)距離最近的所有路段NearSeg 并判斷：情況1，若只包含1 個(gè)最近路段則直接返回該路段作為匹配路段（如算法1 第10～14 行所示）；情況2，若存在多個(gè)最近路段，如圖2（b）所示，nearSeg=｛r1，r2｝，則繼續(xù)利用最小角度函數(shù)findangle 計(jì)算與行駛方向夾角最小的路段作為匹配路段（如算法1 第15～17 行所示），如圖2（c）所示。最后，返回最佳匹配路段Machsegment=r1，如圖2（d）所示。

圖2 道路匹配實(shí)例Fig.2 Example of road matching

3.2 基于歷史數(shù)據(jù)的接載概率預(yù)測

在路線推薦問題中，有效預(yù)測不同路段的接載概率非常重要。由于不同位置、不同時(shí)段、不同天氣等因素的影響，潛在的接載概率不斷發(fā)生變化。以不同地區(qū)為例，圖3 分別表示了上海市虹橋機(jī)場和上海市南京步行街在不同時(shí)刻發(fā)生接載事件的情況，從圖3（a）可以看出，在上午04：00—08：00 時(shí)，有較多乘客選擇前往機(jī)場，并在機(jī)場下車。同一時(shí)段也可以發(fā)現(xiàn)，從機(jī)場選擇搭載出租車出行的需求比較少，導(dǎo)致在該時(shí)段有大量出租車空閑。因此，即使是機(jī)場這樣的接載熱點(diǎn)，此時(shí)的接載概率也非常低。而在晚上20：00 以后情況則剛好相反，該時(shí)段內(nèi)大量乘客到達(dá)機(jī)場并選擇前往市區(qū)，接載概率變高，可以將該地區(qū)推薦給空閑司機(jī)。

圖3 不同地區(qū)不同時(shí)段接載需求變化Fig.3 Changes in pick-up demand over time in different regions

如圖3（b）所示，對于商業(yè)區(qū)來說，供需不平衡主要發(fā)生在08：00—12：00，此時(shí)前往該地區(qū)的乘客較多，離開的人數(shù)比較少，可以看出在白天前往商業(yè)區(qū)的需求比較大，而晚上情況相反，更多的乘客選擇從步行街離開，并前往不同的地方。因此，為有效學(xué)習(xí)這些因素對接載概率的影響，本文構(gòu)建了一種基于多指標(biāo)輸入的多層感知機(jī)模型（Multi-Layer Perceptron Model，MLP）進(jìn)行接載概率的預(yù)測。

針對接載概率預(yù)測問題，大多數(shù)研究認(rèn)為接載概率的變化往往與時(shí)間序列呈現(xiàn)緊密的關(guān)系，并利用傳統(tǒng)的多層感知機(jī)方法，將單一的時(shí)間序列作為輸入數(shù)據(jù)，設(shè)計(jì)滯后步長并進(jìn)行接載概率的預(yù)測。然而通過前文的實(shí)例分析可以發(fā)現(xiàn)，影響路段接載概率的因素十分復(fù)雜（比如天氣、高平峰時(shí)段等）。這些復(fù)雜的因素與路段的接載概率呈現(xiàn)非線性相關(guān)，僅通過自身的時(shí)間序列進(jìn)行建模無法捕捉到真正的變化規(guī)律。因此，為提高預(yù)測精度，本文將提取多個(gè)相關(guān)因素如日期屬性、天氣、高平峰時(shí)段、時(shí)間間隔、接載數(shù)量和空載數(shù)量作為模型的輸入，然后通過建立一個(gè)實(shí)時(shí)的接載概率預(yù)測模型，進(jìn)行預(yù)測與分析。

為合理預(yù)測不同路段的接載概率，本文首先對空閑出租車在路段的行駛條件做出相應(yīng)的假設(shè)。假設(shè)1：空閑出租車在巡航路段均為單向行駛，不會存在倒車；假設(shè)2：空閑出租車不會在同一路段震蕩行駛（走走停停）。基于上述假設(shè)條件，本文對所選取的因素進(jìn)行量化處理。比如：日期屬性（1 代表工作日、2 代表周末、0 代表國家法定節(jié)假日）；天氣（-1代表雨天、1 代表晴天、0 代表多云）；高平峰（07：00—10：00 用1 表示、17：00—20：00 用2表示、其余時(shí)段用0 表示）；時(shí)間間隔（以1min 為間隔劃分工作時(shí)間段05：00—23：00 共1 140 個(gè)間隔）、接載數(shù)量（每個(gè)間隔內(nèi)載客次數(shù)）、空載數(shù)量（每個(gè)間隔內(nèi)空載次數(shù)）。將量化后的特征作為模型的輸入，模型的輸出即為預(yù)測不同路段的接載概率。對于感知機(jī)模型來說，不同的神經(jīng)元個(gè)數(shù)以及不同的激活函數(shù)影響著訓(xùn)練模型的復(fù)雜程度。本文選取上海市淮海中路這一路段，提取出該路段在30 天內(nèi)發(fā)生接載事件的特征數(shù)據(jù)，并以其80%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，剩余20%作為測試數(shù)據(jù)。經(jīng)過多次訓(xùn)練發(fā)現(xiàn)，當(dāng)訓(xùn)練的網(wǎng)絡(luò)層數(shù)選擇3 層，神經(jīng)元的個(gè)數(shù)選擇256，激活函數(shù)選擇ReLU 時(shí)效果最佳。該模型的預(yù)測結(jié)果如圖4 所示，從圖中可以看出預(yù)測值和真實(shí)值的分布較為一致，驗(yàn)證了預(yù)測模型的穩(wěn)定性。

圖4 預(yù)測結(jié)果對比Fig.4 Comparison of forecast results

為進(jìn)一步驗(yàn)證基于多指標(biāo)輸入的多層感知機(jī)模型的性能，本文利用只考慮時(shí)間序列的感知機(jī)模型作為對比，并使用MAE、MAPE、R2作為指標(biāo)對預(yù)測效果進(jìn)行評估，結(jié)果如表1 所示。由表1 可知，改進(jìn)后的多層感知機(jī)在MAE、MAPE、R2指標(biāo)上分別提高了0.5%、13%和16%。

表1 預(yù)測精度Table 1 Prediction accuracy

3.3 考慮等待時(shí)間的路線推薦算法

在3.1 節(jié)、3.2 節(jié)中對路段數(shù)據(jù)的處理使每個(gè)路段不僅包含了節(jié)點(diǎn)的經(jīng)緯度信息，還包含了歷史的接載情況、穿行該路段的距離以及時(shí)間。依據(jù)這些信息可以利用式（4）和式（8）計(jì)算出每個(gè)路段的花費(fèi)成本，然后根據(jù)推薦算法推薦效益最好的路線。

算法2考慮等待時(shí)間的路線推薦

算法2 描述了考慮等待時(shí)間的最小成本推薦方法的偽代碼。該算法首先從空閑司機(jī)的請求中獲取司機(jī)所在的當(dāng)前路段r和當(dāng)前時(shí)間t，并根據(jù)所在路段位置和時(shí)間信息得到一系列的鄰居路段c_rneighbor和當(dāng)前路段的接載概率p（如算法2 第1～5 行所示）。然后，基于圖搜索算法中的廣度優(yōu)先搜索算法策略對當(dāng)前路段的每個(gè)選擇（等待時(shí)間間隔，路段選擇），并計(jì)算其潛在的花費(fèi)成本（如算法2 第6 行所示），選擇花費(fèi)成本最小的方案（等待間隔，路段）作為當(dāng)前的選擇（如算法2 第7～12 行所示）。該過程被不斷重復(fù)直到推薦的路段長度超過L或者推薦的搜索總時(shí)間超過T時(shí)，則停止推薦并得出最小成本的推薦路線。

為解釋、驗(yàn)證本文提出的算法，下面將通過一個(gè)具體實(shí)例進(jìn)行說明。如圖5 所示，假設(shè)每個(gè)路段的行駛時(shí)間為30 s，路段的等待間隔為2 min，行駛距離為120 m，其單位時(shí)間的租賃費(fèi)為0.1，汽油費(fèi)為0.01。當(dāng)司機(jī)在r4路段在上午08：15 發(fā)出尋客請求時(shí)，由于直接穿行r4和r5路段的花費(fèi)最小，因此直接到達(dá)s6節(jié)點(diǎn)時(shí)間為上午08：16。此時(shí)對于傳統(tǒng)推薦算法而言，如果在r5路段未接到乘客，則會繼續(xù)選擇下一個(gè)行駛路段。假設(shè)選擇的行駛路段為r3，此時(shí)的花費(fèi)成本為4.2。而根據(jù)式（8）可知，本文推薦的算法在該路段節(jié)點(diǎn)選擇等待2 min 接載到乘客所花費(fèi)的成本最小，為1.2。原因是該路段在上午08：18時(shí)刻會有公交車到站，出現(xiàn)大量換乘乘客，乘客需求增加，導(dǎo)致該路段的接載概率提高，使得空閑司機(jī)更容易接載到乘客。

圖5 考慮等待時(shí)間的路線推薦案例Fig.5 Route recommendation case considering waiting time

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)及實(shí)驗(yàn)環(huán)境

出租車數(shù)據(jù)：本文所采用的實(shí)驗(yàn)數(shù)據(jù)來自上海10 694 名出租車司機(jī)在2015 年4 月1 日—2015 年4 月30 日生成的軌跡數(shù)據(jù)，其中每條數(shù)據(jù)的采集頻率是10 s，采集內(nèi)容包含司機(jī)編號、位置、時(shí)間、速度、狀態(tài)等，詳細(xì)信息如表2 所示。

表2 上海市出租車GPS 軌跡數(shù)據(jù)示例Table 2 Example of GPS trajectories data taxis in Shanghai

從OpenStreetMap 中獲取上海市真實(shí)道路網(wǎng)絡(luò)的所有信息，其中包含465 735 個(gè)節(jié)點(diǎn)和197 758 個(gè)路段，并且在處理數(shù)據(jù)的過程中為每個(gè)路段標(biāo)記其穿行時(shí)間、穿行距離和歷史接載數(shù)據(jù)。

本文實(shí)驗(yàn)采用的性能評估和分析代碼是用python語言編寫，并在Intel?CoreTMi5-8250 CPU@1.60 GHz，8 GB內(nèi)存64 位Windows10 系統(tǒng)上運(yùn)行。

4.2 對比算法

為評估本文所提算法，采用以下4 種算法作為對比，進(jìn)一步驗(yàn)證該算法的有效性。

1）MNP 算法。為空閑司機(jī)推薦完整路線，通過凈利潤函數(shù)計(jì)算每個(gè)路段的潛在效益，并分別利用暴力法和遞歸策略篩選出最佳的推薦路線［5］。

2）InExperience 算法。利用歷史軌跡數(shù)據(jù)計(jì)算每個(gè)司機(jī)的歷史收入，把收入最低的前10%的司機(jī)作為無經(jīng)驗(yàn)司機(jī)，并選擇其空閑時(shí)所行駛的路線作為對比。

3）Random 算法。采用隨機(jī)方式為每種決策編號，并通過隨機(jī)函數(shù)選擇路線。

4）WTR 算法。本文提出的基于候客點(diǎn)規(guī)劃的空閑出租車路線推薦算法。

4.3 對比指標(biāo)

本文選擇提升性能比rimprove作為實(shí)驗(yàn)的性能指標(biāo)，其含義為相比較其他算法所提升的百分比。當(dāng)獲得一個(gè)司機(jī)請求時(shí)，從不同算法推薦路線所需要的花費(fèi)成本、閑逛時(shí)間和閑逛距離3 個(gè)方面進(jìn)行性能驗(yàn)證，計(jì)算式如式（10）～式（12）所示：

式（10）表示本文推薦的算法WTR 與對比算法相比，在花費(fèi)成本這一指標(biāo)上所改善的性能百分比。式（11）表示本文推薦的WTR 算法相比較對比算法，在閑逛時(shí)間這一指標(biāo)上所改善的性能百分比。式（12）表示本文推薦的WTR 算法相比較對比算法，在閑逛距離這一指標(biāo)上所改善的性能百分比。

4.4 實(shí)驗(yàn)結(jié)果

本文首先在上海市淮海中路附近（經(jīng)度121.457 0°至121.486 8°，緯度31.219 8°至31.230 9°）隨機(jī)生成規(guī)模大小分別為10 個(gè)、100 個(gè)、1 000 個(gè)空閑司機(jī)請求數(shù)據(jù)。然后，對每個(gè)司機(jī)的請求位置和時(shí)間分別利用本文提出的WTR 算法和對比算法進(jìn)行相應(yīng)的路線推薦。其中，路段限制參數(shù)L和時(shí)間限制參數(shù)T分別是5 km 和10 min。最后，根據(jù)式（10）～式（12）做出相應(yīng)的計(jì)算，對比實(shí)驗(yàn)結(jié)果如圖6 所示。

圖6（a）表示空閑司機(jī)的推薦數(shù)量與推薦路線花費(fèi)成本之間的實(shí)驗(yàn)結(jié)果，從圖中可以看出本文考慮等待時(shí)間因素的推薦算法與算法MNP、InExperence、Random相比均有所提升。其中，當(dāng)推薦次數(shù)為10 時(shí)，WTR 算法的花費(fèi)成本相比較MNP、InExperience、Random 分別減少了44.6%、53.2%、49.45%。當(dāng)推薦次數(shù)為100 時(shí)，分別減少了42.3%、51.5%、45.2%；當(dāng)推薦次數(shù)等于1 000 時(shí)，分別減少了35.7%、40.1%、41%。對于整體的趨勢而言，隨著推薦次數(shù)的增加，推薦性能的百分比下降，這是因?yàn)殡S著空閑司機(jī)的增多，可接載的乘客數(shù)量變得越來越少，這對于所有的推薦方法來說都將很難找到乘客，因此推薦成本的差距會變得越來越小。

圖6（b）表示空閑司機(jī)的推薦數(shù)量與推薦路線閑逛時(shí)間之間的實(shí)驗(yàn)結(jié)果，從圖中可以看出本文考慮等待時(shí)間因素的推薦算法與算法MNP、InExperence 和Random 相比均有所提升。其中當(dāng)推薦次數(shù)為10 時(shí)，WTR 算法的閑逛時(shí)間與算法MNP、InExperience、Random 相比分別減少了21.2%、33.3%、29.7%；當(dāng)推薦次數(shù)為100 時(shí)，分別減少了18.3%、28.5%、12.2%；當(dāng)推薦次數(shù)等于1 000時(shí)，分別減少了13.3%、12.2%、12.7%。隨著推薦次數(shù)的增加，閑逛時(shí)間的提升百分比不斷下降。這是因?yàn)殡S著乘客需求的減少，任何一種推薦方法都難以接載到乘客，其閑逛時(shí)間的差距也會逐漸減小。

圖6 實(shí)驗(yàn)結(jié)果對比Fig.6 Comparison of experimental results

圖6（c）表示空閑司機(jī)的推薦數(shù)量與推薦路線閑逛距離之間的實(shí)驗(yàn)結(jié)果，從圖中可以看出本文提出的推薦算法WRT 與算法MNP、InExperence、Random 相比均有所提升。其中，當(dāng)推薦次數(shù)為10 時(shí)，WTR 算法的閑逛距離與算法MNP，InExperience、Random 相比分別減少了41.7%、53%、48%；當(dāng)推薦次數(shù)為100 時(shí)，分別減少了43.6%、57.3%、46.4%；當(dāng)推薦次數(shù)為1 000 時(shí)，分別減少了46.4%、58.2%、76.1%。對于花費(fèi)成本和閑逛時(shí)間的變化趨勢，閑逛距離隨著推薦次數(shù)的增加呈上升趨勢，原因是本文算法考慮了等待時(shí)間因素，當(dāng)推薦次數(shù)逐漸增加而乘客需求不斷減少時(shí)，任何一種推薦方法都難以接到乘客。不同于MNP、InExperience、Random算法，本文所提算法在這種情況下更多選擇了停留等待的決策來減少行駛距離所帶來的成本。

由以上分析可以得出，本文所提基于候客點(diǎn)規(guī)劃的空閑出租車路線推薦算法通過考慮某些路段的等待因素，可以讓空閑司機(jī)更快地接載到乘客，從而減少司機(jī)的閑逛時(shí)間和閑逛距離，提高出租車的運(yùn)輸效率。

5 結(jié)束語

現(xiàn)有的空閑司機(jī)路線推薦算法在考慮真實(shí)路網(wǎng)環(huán)境時(shí)忽略了路段可等待因素，導(dǎo)致所推薦的路線花費(fèi)成本較高。為此，本文提出一種基于候客點(diǎn)規(guī)劃的空閑出租車路線推薦算法。通過處理出租車軌跡數(shù)據(jù)及統(tǒng)計(jì)每個(gè)路段的歷史接載信息，將軌跡點(diǎn)與真實(shí)路段進(jìn)行匹配，并利用改進(jìn)的多層感知機(jī)對出租車的接載概率進(jìn)行建模。此外，在考慮路段可等待因素的基礎(chǔ)上設(shè)計(jì)一種路線推薦算法。在真實(shí)的上海出租車軌跡數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，相較于MNP、InExperence、Random 等算法，本文所提算法在花費(fèi)成本、巡航時(shí)間以及巡航距離方面均有明顯減少。下一步將通過研究司機(jī)的目的地偏好，在本文工作基礎(chǔ)上為空閑司機(jī)設(shè)計(jì)個(gè)性化的推薦機(jī)制。