基于蒙特卡羅樹搜索的出租車路徑推薦方法

韓東軒 路丹丹 鄭斯杰 吳亞東,3

1(西南科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院 四川 綿陽 621000) 2(西南科技大學(xué)工程技術(shù)中心 四川 綿陽 621000) 3(四川輕化工大學(xué)計算機學(xué)院 四川 自貢 643000)

0 引 言

近年來，城市交通路網(wǎng)完善，同時由于滴滴等打車平臺的興起，打車出行成為乘客的首選。但是城市的交通呈現(xiàn)明顯的潮汐狀態(tài)，由于城市道路高峰期的擁堵情況，出租車無法以最快速度到達(dá)潛在客戶所在位置；同樣，由于平峰期出租車空載時間較長，存在潛在客戶與出租車之間距離較遠(yuǎn)的問題。以上兩種情況均會造成接客頻率下降、運力浪費、環(huán)境污染、城市交通資源利用不高的情況。而現(xiàn)階段的研究普遍為出租車與乘客之間的路徑優(yōu)化問題，并未涉及面向出租車進(jìn)行路徑推薦使得出租車能夠在下一條通過的路徑中有最大概率接載潛在乘客。上限置信區(qū)間算法(The Upper Confidence Bound Algorithm，UCB)在蒙特卡羅樹搜索(Monte Carlo Tree Search，MCTS)的選擇步驟中，用來評估值最大的子節(jié)點，這個值被命名為UCB值。樹圖置信算法(Upper Confidence Bound Apply to Tree，UCT)把MCTS與UCB算法聯(lián)系在一起，使得道路交通的路徑推薦結(jié)果，在時間和空間搜索速度和效率方面具有傳統(tǒng)搜索算法無可比擬的優(yōu)勢。針對上述問題，本文研究和實現(xiàn)一種基于MCTS的出租車路徑推薦方法，解決出租車與潛在乘客之間最短路徑路線推薦問題，提出一種路徑推薦模型。與Garg等[1]的論文相比，本文方法使用Python NetworkX簡化了路網(wǎng)實現(xiàn)方法，并利用三維粒子隱喻車輛刻畫推薦結(jié)果以簡化路徑推薦模型的實現(xiàn)方式，可視化道路潛在乘客以及出租車運行狀態(tài)以幫助城市管理者和用戶進(jìn)行理解。對紐約真實出租車數(shù)據(jù)的應(yīng)用案例研究表明，本文方法的推薦質(zhì)量明顯高于現(xiàn)有方法。

1 相關(guān)工作

1.1 出租車路徑推薦

租車路徑推薦一直以來都是網(wǎng)約車平臺管理者和城市交通管理者關(guān)注的問題。孔蕙心[2]設(shè)計了一種基于實時客流分布的路線推薦算法，采用K-means聚類算法對載客推薦點進(jìn)行劃分，計算出載客概率，為出租車司機推薦接客點。劉相言等[3]設(shè)計一種出租車綜合推薦系統(tǒng)，為出租車在空載和載客狀態(tài)下推薦成本最低行駛路線，同時設(shè)計了拼車決策，降低了出租車成本。戚欣等[4]使用一種改進(jìn)的A*算法實現(xiàn)路徑規(guī)劃，對軌跡進(jìn)行聚類分析，在路網(wǎng)的基礎(chǔ)上構(gòu)建k個路段的熱點路段圖，為出租車司機提供最優(yōu)的路徑規(guī)劃方法，縮短空駛時間。Garg等[1]采用蒙特卡羅樹搜索算法(MCTS)搜索司機與乘客之間的最短距離，使用上限置信區(qū)間算法計算道路的權(quán)重，將道路重要性較高的結(jié)果推薦給空閑的出租車司機，減少空閑出租車司機的行駛時間，并且該系統(tǒng)在異常情況(體育賽事、演唱會等)具有良好的魯棒性。Wang等[5]設(shè)計了TaxiRec框架來評估和發(fā)現(xiàn)潛在乘客的道路集群，該框架提出了極端學(xué)習(xí)機模型評估每個道路集群的潛在乘客找尋潛力，并為道路提供聚類建議。Hwang等[6]提出出租車巡航位置推薦系統(tǒng)，考慮了出租車當(dāng)前位置與推薦位置之間的距離，下一名乘客的等待時間以及預(yù)期的乘車費用，采用位置對位置的圖模型獲取乘客下車位置與下一個乘客上車位置之間的關(guān)系，采用開關(guān)模型估計行程票價，并開發(fā)基于該推薦系統(tǒng)的虛擬出租車巡航系統(tǒng)，表明在出租車巡航位置推薦上該系統(tǒng)的有效性。

1.2 蒙特卡羅樹搜索應(yīng)用

MCTS算法于2006年Alpha Go應(yīng)用中被世人熟知。近年來由于通用計算的發(fā)展，MCTS算法目前在游戲?qū)?、路徑?guī)劃等方面有著很好的前景。在Lenz等[7]提出一種應(yīng)用于自動駕駛車輛的MCTS協(xié)同組合運動規(guī)劃算法，在此基礎(chǔ)上提出并行決策、智能駕駛模型的微觀交通仿真和協(xié)同成本函數(shù)，展示了在車輛無須相互通信的情況下的自動駕駛結(jié)果。Sabar等[8]提出一種基于MCTS超啟發(fā)式框架，將低層次啟發(fā)式的搜索空間建模為一個決策樹，并使用MCTS遍歷該樹，以確定應(yīng)用于當(dāng)前狀態(tài)的低層次啟發(fā)式的最佳序列。該框架可以運用于帶時間窗的車輛路徑規(guī)劃問題等領(lǐng)域，證明了框架的通用性。Powley等[9]設(shè)計一種模擬連續(xù)實時域的路徑規(guī)劃和轉(zhuǎn)向的控制器，使用MCTS方法來規(guī)劃和引導(dǎo)細(xì)粒度路徑，該方法可以應(yīng)用于運動規(guī)劃和控制領(lǐng)域，并與人類對手相抗衡。Haeri等[10]提出兩種VNE算法：MaVEn-M算法使用多商品流算法，MaVEn-S使用最短路徑算法進(jìn)行虛擬鏈路映射，并使用MCTS為馬爾可夫決策過程框架形式化虛擬節(jié)點設(shè)計節(jié)點映射的動態(tài)策略，設(shè)計盈利能力作為目標(biāo)函數(shù)，得出該算法可以使基礎(chǔ)設(shè)施的提供商利潤最大化。

2 目標(biāo)研究

路徑推薦模型目的是向出租車推薦潛在乘客所在街道的位置，解決出租車與潛在乘客之間最短路徑路線推薦問題。城市中乘客的乘車需求看似隨機分布，實際上潛在乘客產(chǎn)生的概率卻具有一定規(guī)律，路徑推薦模型需要表達(dá)乘客概率分布的問題；當(dāng)出租車周邊具有多個潛在乘客時，需要根據(jù)潛在乘客產(chǎn)生的概率，向出租車推薦最優(yōu)路徑，使得出租車通過推薦的道路時能夠有較大概率接到乘客；潛在乘客的產(chǎn)生是動態(tài)變化的，需要考慮出租車到潛在乘客之間的最短路徑問題，確保出租車能夠在潛在乘客動態(tài)變化過程中接到乘客。

2.1 乘客概率分布

潛在乘客的乘車需求在城市中宏觀下看似隨機分布，但是乘客產(chǎn)生的概率卻伴隨時間和地區(qū)的特征而具有一定規(guī)律。一天當(dāng)中，城市的中心例如商業(yè)區(qū)、商務(wù)區(qū)(CBD)等可能具有持續(xù)較大乘客產(chǎn)出概率，而這些潛在乘車需求所處道路或者與該道路相連接的道路必然會被推薦給出租車；在上下班高峰期，城市區(qū)域與區(qū)域之間，例如住宅區(qū)與商業(yè)區(qū)之間，住宅區(qū)與CBD之間的通行需求較高，出租車載客呈現(xiàn)區(qū)域?qū)^(qū)域特征，而處于住宅區(qū)的上車需求必然會被推薦給出租車，出租車將會呈現(xiàn)向距離最近的住宅區(qū)涌動的趨勢，當(dāng)出租車下客后，會在商業(yè)區(qū)或者CBD出現(xiàn)較多的空載出租車，而這時，周邊非熱門區(qū)域的潛在乘車需求可能無法被滿足；在半夜或平峰期的城市周邊，除了酒吧街、小吃街等通宵營業(yè)的區(qū)域具有較大乘客產(chǎn)出概率，乘客呈現(xiàn)隨機趨勢分布在城市的各個地方，此時需要向出租車推薦距離最近的乘客和最短接乘路線，避免出租車較長時間空載。為了解決以上問題，本文模型根據(jù)紐約出租車載客情況歷史數(shù)據(jù)進(jìn)行訓(xùn)練，在道路路網(wǎng)上投放乘客坐標(biāo)，并使用可視化技術(shù)將乘客概率分布展現(xiàn)在對應(yīng)的地圖上，便于城市管理者和用戶更好地掌握一天中城市內(nèi)乘客產(chǎn)出概率分布情況。

2.2 出租車接客最短路徑

當(dāng)出租車接受推薦模型的結(jié)果時，我們需要規(guī)劃一條從出租車出發(fā)到達(dá)乘客所在道路的路徑，即出租車接客最短路徑。該路徑的產(chǎn)生需要模型在真實的路段網(wǎng)絡(luò)中進(jìn)行搜尋，所以本文模型在構(gòu)建路段網(wǎng)絡(luò)時，將道路用邊表示，道路與道路之間的連接用節(jié)點表示。網(wǎng)絡(luò)中每一個節(jié)點是一個狀態(tài)，最短路徑搜索的方法是從一個節(jié)點移動到另一個節(jié)點。搜索開始時，路徑推薦模型選擇最優(yōu)結(jié)果作為出租車的出發(fā)路段，如果被選擇的邊沒有找到乘客，那么從當(dāng)前位置重新選擇一條邊，這個過程持續(xù)到乘客被找到。直觀地來說，由于乘客產(chǎn)出概率是動態(tài)變化的，所以不能簡單地從歷史數(shù)據(jù)中獲取靜態(tài)的乘客產(chǎn)出位置來計算出租車接客的最短路徑。為了解決這個問題，本文模型在獲取兩個節(jié)點間最短路徑長度時，采用了迪杰斯特拉算法獲取從當(dāng)前位置到周邊各道路的最短路徑。

2.3 出租車競爭

對出租車進(jìn)行路徑推薦時不光要考慮當(dāng)前最大乘客概率，還要考慮出租車之間的競爭關(guān)系，因為同一個乘客只能乘坐一輛出租車，因此，當(dāng)確定乘客產(chǎn)出概率的分布后，采用蒙特卡羅樹搜索(MCTS)路徑推薦模型必須知道當(dāng)前出租車周邊路線中的客戶數(shù)量，以確保多輛出租車不會被分配同一個客戶。推薦模型向當(dāng)前出租車推薦計算輸出的乘客出現(xiàn)權(quán)重值最高的道路。而在計算權(quán)重值時，如何平衡出租車的競爭關(guān)系，是一個待解決的問題。為了解決這一問題，本文設(shè)置了一個基于MCTS的離線學(xué)習(xí)模型，使用該離線模型學(xué)習(xí)位于道路附近的歷史乘客請求并獲得UCB值。將該離線學(xué)習(xí)模型訓(xùn)練后，便可應(yīng)用于出租車動態(tài)路徑推薦的過程中。

2.4 在線推薦

推薦模型分為兩個階段：離線學(xué)習(xí)模型與在線推薦階段。在出租車動態(tài)巡游的過程中，使用在線推薦模型對出租車進(jìn)行路徑推薦。在該階段，出租車作為查詢節(jié)點，推薦模型向該節(jié)點推薦最大UCB值，出租車按照推薦結(jié)果巡游整條道路并到達(dá)推薦道路的另一端，這時候在線推薦模型將驗證車輛是否接到乘客。如果出租車沒有接到乘客，那么推薦結(jié)果將形成負(fù)反饋輸入到推薦模型中，推薦模型將會減少該條道路的推薦概率。此時推薦模型會基于當(dāng)前出租車查詢節(jié)點位置生成一個新的推薦結(jié)果用于下一次出租車巡游。如果出租車接到乘客，會給該部分帶來正反饋。即使處于在線狀態(tài)下，推薦結(jié)果也會反饋到離線和在線兩個模型中，權(quán)重值將會動態(tài)更新，該模型具有較強實時性。

總的來說，本文的主要貢獻(xiàn)如下：(1) 本文提出一種基于MCTS的路徑推薦方法，該方將樹搜索思想應(yīng)用于城市路網(wǎng)中，通過這種方法，出租車可以獲得在線路徑推薦。(2) 本文為空閑出租車司機制定路線，使得車輛到達(dá)潛在乘客需求的距離最小化。(3) 本文對紐約的真實出租車數(shù)據(jù)進(jìn)行了測試，例如在交通變化或者異常情況下的適應(yīng)，發(fā)現(xiàn)該方法的推薦質(zhì)量明顯高于現(xiàn)有方法。

3 蒙特卡羅樹搜索路徑推薦模型

3.1 推薦模型流程

本文提出的路徑推薦模型流程如圖1所示。

圖1 路徑推薦模型流程

本文所使用的路徑推薦模型分為2部分，第1部分使用Python NetworkX[11]構(gòu)建地圖中道路和道路之間的關(guān)系，即道路路網(wǎng)，而道路路網(wǎng)與出租車載客歷史數(shù)據(jù)作為訓(xùn)練樣本訓(xùn)練。第2部分是將乘客需求和出租車當(dāng)前位置輸入至已經(jīng)訓(xùn)練后的蒙特卡羅樹搜索(MCTS)路徑推薦模型中，路徑推薦模型通過計算給出推薦路徑結(jié)果，出租車按照推薦結(jié)果行駛后具有最大的接到乘客的概率。

3.2 路網(wǎng)構(gòu)建

為了解決地圖上的路徑搜尋問題，本系統(tǒng)采用復(fù)雜網(wǎng)絡(luò)分析庫Python NetworkX[11]基于OSM地圖進(jìn)行道路網(wǎng)絡(luò)構(gòu)建，將道路用邊表示，道路與道路之間的連接用節(jié)點表示，構(gòu)建結(jié)果是可視化在OSM地圖上的道路線條，該過程是在可視化系統(tǒng)中建立基本的道路信息和道路關(guān)系信息，便于樹搜索算法進(jìn)行路徑推薦。路網(wǎng)構(gòu)建輸入為路網(wǎng)信息字典，輸出為網(wǎng)絡(luò)G′，構(gòu)建的步驟如下：

Step1構(gòu)建路網(wǎng)信息字典NodesInfoDict，初始化網(wǎng)絡(luò)G。

Step2讀取道路信息數(shù)據(jù)Nodes.csv，解析道路開始與結(jié)束的GPS坐標(biāo)值。

Step3將道路ID作為關(guān)鍵字Key、道路信息(道路長度L、所在區(qū)域R、區(qū)域類型T等)作為輸入值value，存入NodesInfoDict。

Step4讀取道路關(guān)系數(shù)據(jù)Links.csv，獲取道路之間的連接，源路段S，目標(biāo)路段T。

Step5當(dāng)Sin NodesInfoDict或T in NodesInfoDict，執(zhí)行下一步，否則執(zhí)行Step 4。

Step6在網(wǎng)絡(luò)中增加一個邊G.addEdge(S,T,weight=NodeInfoDict[S].L)。

Step7在網(wǎng)絡(luò)中增加一個邊G.addEdge(T,S,weight=NodeInfoDict[T].L)。

Step8返回網(wǎng)絡(luò)G′。

3.3 乘客最大概率算法

在本文中，采用多臂老虎機算法是為了使得在最少的路途花費時間中得到最大的載客概率，即獲得最優(yōu)的道路UCB值。在蒙特卡羅樹搜索算法的選擇過程中，將子節(jié)點看作老虎機進(jìn)行隨機選擇，就像解決多臂老虎機問題一樣選擇下一個節(jié)點i。而算法執(zhí)行時并不知道哪個子節(jié)點i的收益高，而是付出一定的代價來發(fā)現(xiàn)哪個節(jié)點的收益高。

定義1多臂老虎機的手臂即為本文蒙特卡羅樹搜索選擇步驟中子節(jié)點i，即下一個被選中的路徑。

定義2多臂老虎機的選擇收益值Qr(a)即為本文蒙特卡羅樹搜索選擇步驟中的下一個被選中的路徑的潛在乘客存在的概率。

定義3在一個多臂老虎機問題中，當(dāng)m條手臂中的每一條手臂被選擇時都有一個期望的收益值。

在第r輪被挑選的路徑表示為Ar,對應(yīng)的收益值記為Wr,將一條任意的路徑p的期望收益值表示為Qr(a)。

Qr(a)=E[wr|Ar=p]

(1)

(2)

使用該算法獲得的路徑最大概率和通過選擇最佳的路徑所獲得的那些概率的差距，被稱作累計遺憾值，并且使用該算法的目標(biāo)是最小化它的累計遺憾值。

定義4累計遺憾值是由于沒有選擇實際最佳路徑的損失。r輪的累計遺憾值被表示為：

(3)

式中：C(p)是手臂p在r輪被選擇的次數(shù)。

3.4 UCT算法

樹圖置信算法(Upper Confidence Bound Apply to Tree,UCT)把蒙特卡羅樹搜索算法(MCTS)與UCB算法聯(lián)系在一起，在本系統(tǒng)中，對于計算道路交通的路徑推薦結(jié)果，在時間和空間搜索速度和效率方面具有傳統(tǒng)搜索算法無可比擬的優(yōu)勢。上限置信區(qū)間算法(The Upper Confidence Bound Algorithm，UCB)在蒙特卡羅樹搜索的選擇步驟中用來評估值最大的子節(jié)點，這個值被命名為UCB值。MCTS是通過多次模擬得到大部分節(jié)點的UCB值，并在下一次模擬中根據(jù)前序步驟中最大的UCB值來選擇有價值的節(jié)點繼續(xù)模擬，最終將這些UCB值反向傳播后輸出，作為路徑推薦的評估依據(jù)。UCB算法的計算公式如下：

(4)

在UCT算法運行過程中，系統(tǒng)輸入出租車初始位置、乘客乘車需求坐標(biāo)，通過路徑推薦模型的運算后，輸出道路的UCB值。UCB值表示道路的權(quán)重，即定義一條路徑p，其UCB值較高時，出租車經(jīng)過這條路徑p，可以更容易接到乘客。也可以將UCB值理解為道路的乘客產(chǎn)出速率，道路UCB值越高的地方，司機越容易選擇該條道路。

在本文方法中，UCT算法的流程為：

步驟1選擇。選擇過程是根據(jù)當(dāng)前獲得所有的子節(jié)點的統(tǒng)計結(jié)果，選擇最優(yōu)的子節(jié)點。系統(tǒng)輸入出租車初始位置，即當(dāng)前路網(wǎng)方向允許的第一個路口，稱為根節(jié)點R，輸出當(dāng)前UCB值最大的子節(jié)點imax。在此步驟中，系統(tǒng)采用多臂老虎機算法隨機選擇根節(jié)點R的下一個路網(wǎng)節(jié)點(子節(jié)點i)。

算法使用UCB公式作為搜索樹選擇遍歷的評估函數(shù)，來估計UCB值最高的最優(yōu)節(jié)點，在搜索樹選擇遍歷期間，采用式(5)進(jìn)行選擇。

(5)

式中：Si表示節(jié)點i的值(初始節(jié)點為R)；xi表示節(jié)點i的經(jīng)驗平均值；C表示常數(shù)；t表示模擬的總數(shù)，模擬過程見Step 3。搜索樹選擇遍歷時，由式(5)返回的當(dāng)前具有最大UCB值的節(jié)點作為被選中的子節(jié)點imax，同時在遍歷期間，一旦找到更大UCB值節(jié)點i，就更新子節(jié)點imax。

步驟2擴展。擴展是在當(dāng)前的統(tǒng)計結(jié)果不足以計算出下一個步驟時，隨機選擇一個子步驟。系統(tǒng)輸入上一步的根節(jié)點R，輸出根節(jié)點R的完全遍歷標(biāo)記。擴展過程實際是把根節(jié)點R的所有子節(jié)點i全部訪問一次。對每一個子節(jié)點i的訪問均會執(zhí)行算法的Step 1-Step 4。例如，在算法的第一次搜索中，算法最終處于樹的某一子節(jié)點imax根部，可以認(rèn)為算法未訪問其他子節(jié)點i，所以在訪問一個子節(jié)點后，算法會執(zhí)行Step 3。若該被訪問的節(jié)點已經(jīng)執(zhí)行過Step 3，那么算法將會將該節(jié)點作為初始節(jié)點。如果一個根節(jié)點R的所有子節(jié)點都被訪問，那么認(rèn)為Step 2結(jié)束。

步驟3模擬。模擬過程是模擬游戲博弈樹的過程。系統(tǒng)輸入某一子節(jié)點imax，執(zhí)行Step 1，輸出下一步應(yīng)該到達(dá)的路網(wǎng)節(jié)點。Step 3可以反復(fù)執(zhí)行多次。模擬過程運用單次博弈策略，也就是說從當(dāng)前狀態(tài)(某一個隨機計算的初始節(jié)點)開始評估近似的樹節(jié)點，最終在終端節(jié)點結(jié)束。模擬過程中，算法采用Rollout策略進(jìn)行移動，Rollout見式(6)。

RolloutPolicy:Si→ai

(6)

式中：Si表示節(jié)點i的值；該函數(shù)輸入當(dāng)前的搜索狀態(tài)，輸出下一次移動的選擇結(jié)果。在MCTS的模擬中，Rollout函數(shù)可以多次運行，本系統(tǒng)設(shè)計了迪杰斯特拉算法獲取最短路徑來運行Rollout，迪杰斯特拉算法從根節(jié)點R開始向外擴展，在路網(wǎng)中尋找R到子節(jié)點i的最短路徑。

步驟4反向傳播。反向傳播是根據(jù)模擬的結(jié)果，計算對應(yīng)路徑上統(tǒng)計記錄的值。算法在完成模擬步驟后，將UCB值最高的結(jié)果傳給出租車的初始位置R，并將該子節(jié)點i標(biāo)記為已訪問狀態(tài)。出租車即可以按照該結(jié)果行駛。該步驟輸入結(jié)果為子節(jié)點imax的值Si，輸出結(jié)果為新節(jié)點inext。

3.5 最短路徑求解

本模型在構(gòu)建路段網(wǎng)絡(luò)時，將道路用邊表示，道路與道路之間的連接用節(jié)點表示。蒙特卡羅樹搜索是在當(dāng)前狀態(tài)空間內(nèi)給定隨機樣本去尋找最佳行為的一種方法，在MCTS的搜索過程中，搜索空間以樹的形態(tài)存在，如果搜索過程從父節(jié)點到子節(jié)點，那么兩個節(jié)點就被連接[1]，所以每個節(jié)點都是一種狀態(tài)。而路段網(wǎng)絡(luò)中每一個節(jié)點都是一個狀態(tài)，并且搜索行為是通過邊從一個節(jié)點移動到另一個節(jié)點。在線推薦過程中，通過初始化出租車當(dāng)前位置作為查詢節(jié)點，利用MCTS的搜索結(jié)果選擇最高UCB值作為出租車的出發(fā)路段(邊)，出租車對該路段進(jìn)行巡游，如果該邊沒有找到乘客，那么模型就會繼續(xù)通過MCTS進(jìn)行搜索并對出租車做下一次推薦，直到乘客被找到。然而乘客需求是動態(tài)變化的，所以最高的UCB值也不能是靜態(tài)的。為了滿足這種動態(tài)的搜索過程，本模型在搜索兩個節(jié)點之間的路徑長度時，采用了迪杰斯特拉算法來獲取乘客的上下車點。迪杰斯特拉算法是從一個節(jié)點到其他節(jié)點的最短路徑算法，以搜索樹的父節(jié)點為起始點，向外擴展，直到找到乘客需求即擴散到終點為止。

3.6 在線推薦階段

在在線推薦階段，推薦系統(tǒng)不僅向出租車推薦路線，同時還對于出租車是否接到乘客的結(jié)果來更新模型。該階段與離線學(xué)習(xí)的區(qū)別是：

(1) 查詢節(jié)點：真實的出租車作為查詢節(jié)點來進(jìn)行，而不是歷史數(shù)據(jù)中的節(jié)點。

(2) 潛在乘客需求不再是歷史數(shù)據(jù)獲得。路徑推薦的成功是由實時的道路數(shù)據(jù)決定的，出租車接受推薦建議后若沒有接到乘客，那么會進(jìn)行下一次推薦。最終出租車接到乘客后，相應(yīng)的權(quán)重值將會反饋到出租車經(jīng)過的所有路段。

在線推薦階段的流程如下：

步驟1設(shè)定某一真實出租車為查詢節(jié)點。

步驟2獲取離線學(xué)習(xí)階段中該節(jié)點附近的UCB值。

步驟3出租車駛向UCB值最高的道路。

步驟4若出租車未接到乘客，那么執(zhí)行步驟1，同時進(jìn)行負(fù)反饋，使用MCTS更新出租車經(jīng)過道路的所有UCB值至離線學(xué)習(xí)系統(tǒng)。

步驟5若出租車接到乘客，完成查詢。

以上步驟通過算法偽代碼表示如下：

輸入：路徑p的初始節(jié)點R。

輸出：路徑p的子節(jié)點imaxUCB值ρUCBp。

1.設(shè)定路網(wǎng)所有道路UCB值ρUCBp=0

2.設(shè)定第r輪初始值r=0

3.循環(huán)：對于每個路徑p，則設(shè)置Si=0

4.限定搜索總數(shù)t在設(shè)定范圍[tmin,tmax]中

5.基于UCB算法與式(3)：

7.更新遍歷的所有道路上的ρUCBp

8.否則，直接更新

3.7 路徑推薦模型特性

路徑推薦模型分為兩個階段：離線學(xué)習(xí)階段和在線推薦階段。模型特性如下：

(1) 動態(tài)性：傳統(tǒng)的出租車路線預(yù)測技術(shù)是從歷史數(shù)據(jù)中建立一次推薦模型[12-13],和傳統(tǒng)技術(shù)不同的是，本文提出的是動態(tài)性推薦模型，基于在線推薦階段出租車的成果或失敗的反饋來更新過去的推薦結(jié)果。

(2) 多樣性：MCTS能夠利用不斷地反饋建議來做到推薦模型的多樣性。如果區(qū)域的上下班高峰期等開始形成，那么出租車經(jīng)過區(qū)域形成正反饋，這一過程導(dǎo)致該區(qū)域增加更多的出租車。另一方面，如果區(qū)域的熱力信息降低，負(fù)反饋將被反饋到模型中。

(3) 多輛出租車競爭平衡：通過動態(tài)性推薦模型的使用，MCTS算法可以適應(yīng)多個出租車之前的競爭。在傳統(tǒng)技術(shù)[13]上，靜態(tài)模型的結(jié)果使用殆盡后模型會推薦相同的線路給出租車司機；推薦過程不能推薦兩條目的地相同的路線給同一出租車司機[12]，若存在上下班高峰期或機場火車站到站后，這些區(qū)域內(nèi)沒有足夠的出租車。

(4) 時間片(time-slot)獨立：乘客乘車需求是隨著時間變化的，傳統(tǒng)的推薦模型將歷史數(shù)據(jù)劃分成獨立的時間片，以便于推薦模型可以按照獨立的時間建立[13]，但在實際道路中，這種方法[13]存在不成立的情況。本文MCTS不需要將數(shù)據(jù)分割成時間片，從而形成更加實用的推薦平臺。

4 推薦模型實驗

本文設(shè)計兩個實驗來對路徑推薦方法進(jìn)行說明。

實驗1，離線學(xué)習(xí)階段實驗，模型對歷史數(shù)據(jù)進(jìn)行學(xué)習(xí)獲得道路的UCB權(quán)重值。

實驗2，UCB可視化實驗，本方法采用D3.js庫進(jìn)行前端可視化展現(xiàn)，目的是直觀地呈現(xiàn)UCB推薦路徑的結(jié)果，進(jìn)一步驗證和解釋路徑推薦方法。

4.1 實驗數(shù)據(jù)介紹

出租車歷史乘車數(shù)據(jù)集由Brian等[14]的開源紐約市出租車運行數(shù)據(jù)集提供，該數(shù)據(jù)集記錄了2010年至2013年的紐約市的約7億條出租車乘車記錄。本文從中選取了2011年約1.7億的歷史數(shù)據(jù)集作為訓(xùn)練樣本；該路網(wǎng)關(guān)系數(shù)據(jù)集反映了紐約市約26萬條路網(wǎng)關(guān)系。紐約市處于平原地帶，所以路網(wǎng)呈現(xiàn)井字型分布，道路標(biāo)志完善，在使用NetworkX建立路網(wǎng)時，可以使用邊之間的關(guān)系進(jìn)行抽象建立，便于研究。

4.2 實驗環(huán)境介紹

本實驗在PC環(huán)境下完成，實驗環(huán)境為：

CPU：E3- 1231 V3；內(nèi)存：16 GB；顯卡：NVIDIA GTX960；系統(tǒng)版本：Windows 10。

4.3 離線學(xué)習(xí)階段實驗

本實驗使用紐約市出租車運行的歷史數(shù)據(jù)集，由推薦系統(tǒng)對該數(shù)據(jù)集進(jìn)行離線學(xué)習(xí)獲得道路的UCB值，并證明UCB值與被推薦路徑的關(guān)系。同時，本例作為路徑推薦模型的離線學(xué)習(xí)結(jié)果部分，通過樣本集進(jìn)行隨機搜索獲得紐約市曼哈頓地區(qū)的道路UCB值，這些遍布所有道路的UCB值是作為出租車巡游過程中在線推薦的基準(zhǔn)，為真實的出租車路徑推薦提供基礎(chǔ)推薦值。

本例從歷史數(shù)據(jù)中隨機篩選出1 000輛出租車以及1 000個乘客需求。選定紐約曼哈頓地圖作為研究載體，曼哈頓地區(qū)道路數(shù)據(jù)集中有12 000條邊。定義1輛出租車作為查詢節(jié)點采用MCTS計算1次而獲得UCB值，從而得到下一條道路的推薦為1個round。當(dāng)每1輛出租車平均搜索1個round時，出租車僅僅搜索了以自己為根節(jié)點的周邊子節(jié)點，并未遍歷整個曼哈頓地區(qū)，所以本例反復(fù)運行了3 000個round。每一次(3 000 round)運行時間為16分鐘左右。

該次計算實驗結(jié)果為26 600個UCB值。本例隨機抽取計算結(jié)果，數(shù)據(jù)樣例見表1。

表1 UCB值結(jié)果樣例

表1中，ID維度表示道路的ID編號，Production Rate表示乘客產(chǎn)出概率，UCB維度表示UCB的計算結(jié)果。

由表1可以看出，計算后的UCB值無上限，但是在可視化結(jié)果中，本系統(tǒng)將其正則化為0～1的分布，再映射在色度條中，通過色度來區(qū)分UCB值的高低。本例計算的結(jié)果存在乘客產(chǎn)出速率(Production Rate)高，但是UCB值低，或者乘客產(chǎn)出速率低，但是UCB值高的情況。該情況分析見表2。

表2 乘客產(chǎn)出與UCB值的關(guān)系

乘客產(chǎn)出速率與UCB值的高低無正相關(guān)關(guān)系，所以不分析乘客產(chǎn)出速率高、UCB值高或者乘客產(chǎn)出速率低、UCB值低的情況。

4.4 可視化設(shè)計實驗

針對出租車，本文使用三維粒子隱喻車輛，接著采用粒子的運動效果描述出租車的運動情況，從而獲知車輛在行駛過程的道路選擇情況，此外，用戶能夠同時觀察城市里所有車輛的實時運行情況。針對道路選擇情況，這里使用色度刻畫道路的UCB大小，如圖2所示，色度深的地方，表明該路段為UCB值高的路段。一方面能夠幫助我們調(diào)整模型的參數(shù)快速對模型進(jìn)行優(yōu)化，另一方面能夠幫助城市管理者實時地對城市道路的運行情況進(jìn)行監(jiān)控。

圖2 路徑推薦結(jié)果可視化

假設(shè)道路p1至pn的UCB值較高，即該段道路色度較深，那么用戶可以通過可視化設(shè)計獲得以下信息：

(1) 道路p1乘客乘車請求較多或持續(xù)具有乘客請求。

(2) 與道路p1相連接的道路p2的乘客請求較多，出租車接客必會經(jīng)過道路p1。

(3) 道路p1的乘客請求較多，p1周邊相連接的道路p2,3,…,n均可通向p1，道路p2,3,…,n具有高UCB值。

另一方面，本系統(tǒng)對于UCB進(jìn)行藍(lán)色編碼，讓UCB值可視化作為路網(wǎng)繪制的載體，在地圖上進(jìn)行路網(wǎng)的展現(xiàn)。用戶在使用該系統(tǒng)時，將真實的道路信息和UCB值進(jìn)行對應(yīng)，可以直觀高效地識別出乘客需求較高的道路。

5 應(yīng)用案例

本案例使用由Brian等[14]的開源紐約市出租車運行數(shù)據(jù)集，將4.3節(jié)中紐約市曼哈頓區(qū)域出租車歷史數(shù)據(jù)作為訓(xùn)練集，并與Qu等[12]和Verma等[13]的方法進(jìn)行對比。

Qu等[12]提出的模型是空閑出租車路徑預(yù)測技術(shù)，本文以該技術(shù)為基礎(chǔ)。

Verma等[13]將城市分為幾個區(qū)域，并設(shè)定區(qū)域的道路為推薦路徑。與Qu等[12]和本文推薦方法不同的是，Verma等[13]需要獲得出租車載客和下客的位置，以及出租車在空閑時段的軌跡。由于Verma等[13]并未使用紐約出租車運行數(shù)據(jù)集，所以本文建立基于紐約出租車運行數(shù)據(jù)集的Verma等[13]方法模型以便進(jìn)行比較。

5.1 評估框架

為了評估系統(tǒng)性能，本文將數(shù)據(jù)集分為兩部分：訓(xùn)練集和測試集。學(xué)習(xí)過程將在訓(xùn)練集中完成，而后在測試集上進(jìn)行驗證。為了進(jìn)行驗證，本文規(guī)定了查詢時間范圍[t,t+r]，如果在[t,t+r]的R中接載乘客，則推薦路徑p成功。當(dāng)最終找到乘客時，該乘客請求將會從測試集中移除，以保證不會分配相同的需求。

本案例使用隨機選擇方法構(gòu)造隨機訓(xùn)練集，選擇曼哈頓地區(qū)的出租車司機中的X%作為訓(xùn)練集，X是隨機訓(xùn)練集的大小。

5.2 評價指標(biāo)

本文使用改進(jìn)比例(%)來評價MCTS與Qu等[12]和Verma等[13]的性能差異。通常來說，改進(jìn)比例(%)能夠更好地反映本模型帶來的性能差異。在數(shù)學(xué)上，改進(jìn)比例(%)定義如下：

(7)

式中：dB為Qu等[12]或Verma等[13]方法的結(jié)果；dMCTS為使用本文推薦模型的結(jié)果。-1表明Qu等[12]或Verma等[13]方法推薦的路徑長度較短。

5.3 推薦質(zhì)量

出租車每時每刻不斷請求路徑推薦，隨著推薦查詢越來越多，由于測試集中的乘客乘車請求是有限的，系統(tǒng)的推薦結(jié)果會變得很困難。特別指出，查詢數(shù)量指的是出租車進(jìn)行搜索的次數(shù)。

通過圖3和圖4可以得到，MCTS推薦的性能更好。但正如圖4所示，Qu等[12]的改進(jìn)比例高達(dá)60%，而Verma等[13]的改進(jìn)比例高達(dá)160%。MCTS能夠采用動態(tài)推薦模型來實現(xiàn)推薦質(zhì)量改進(jìn)，隨著出租車請求增加，節(jié)點查詢概率改變，因此基于靜態(tài)模型的預(yù)測受到影響。

圖3 MCTS推薦性能與查詢數(shù)量的關(guān)系

圖4 Verma等[13]和Qu等[12]推薦性能與查詢數(shù)量的關(guān)系

其次，圖3和圖4中，MCTS與另外兩種的性能差距最初增加，然后飽和并且下降。這種現(xiàn)象是因為最初乘客密度高，所以推薦系統(tǒng)更容易找到乘客。然而，隨著未乘車的乘客數(shù)量減少，推薦任務(wù)變得更加困難，Verma等[13]和Qu等[12]的推薦質(zhì)量下降，但MCTS保持較高推薦性能。此外，當(dāng)幾乎所有乘客都被分配時，所有推薦技術(shù)都變得十分困難，推薦質(zhì)量的差距減小。

接下來本文研究推薦質(zhì)量與訓(xùn)練集大小的關(guān)系。特別指出，訓(xùn)練集大小指訓(xùn)練集占整個數(shù)據(jù)集的比例。圖5和圖6的結(jié)果表示，訓(xùn)練集很小時，改進(jìn)比例更高。隨著訓(xùn)練集的增加，MCTS的改進(jìn)比例減少。需要注意的是，這個結(jié)果并不代表MCTS隨著訓(xùn)練集大小的增加而變差，它只是顯示了MCTS與Verma等[13]和Qu等[12]的性能差距。在MCTS推薦模型中，離線階段獲得的推薦結(jié)果用于在線學(xué)習(xí)階段，因此，訓(xùn)練數(shù)據(jù)較少時不會對在線學(xué)習(xí)造成影響。但Verma等[13]和Qu等[12]卻需要大量的訓(xùn)練數(shù)據(jù)來學(xué)習(xí)推薦策略以獲得與MCTS相同的推薦質(zhì)量。

圖5 MCTS推薦質(zhì)量與訓(xùn)練集大小的關(guān)系

圖6 Verma等[13]和Qu等[12]推薦質(zhì)量與訓(xùn)練集大小的關(guān)系

6 結(jié) 語

本文提出一種最短路徑搜索和推薦的方法，該方法使用蒙特卡羅樹搜索(MCTS)來找尋出租車與潛在乘客需求之間的最短路徑，使得預(yù)測潛在客戶成為可能。該方法以搜索樹的形式抽象出租車路網(wǎng)空間，并可以不斷訓(xùn)練路網(wǎng)的動態(tài)特性，例如非周期性或特殊的乘客需求，使得出租車路徑推薦的效率更高，使出租車走向無人駕駛成為可能。本文主要研究乘客和出租車之間的交互關(guān)系，而未進(jìn)行交通異常現(xiàn)象和道路通量的考慮，下一步可以從時間維度以及道路通量入手，采用有限元方法對道路數(shù)據(jù)進(jìn)行分解，以獲得更加精準(zhǔn)的結(jié)果。