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

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

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

0 引 言

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

1 相關工作

1.1 出租車路徑推薦

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

1.2 蒙特卡羅樹搜索應用

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

2 目標研究

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

2.1 乘客概率分布

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

2.2 出租車接客最短路徑

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

2.3 出租車競爭

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

2.4 在線推薦

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

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

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

3.1 推薦模型流程

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

圖1 路徑推薦模型流程

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

3.2 路網構建

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

Step1構建路網信息字典NodesInfoDict，初始化網絡G。

Step2讀取道路信息數據Nodes.csv，解析道路開始與結束的GPS坐標值。

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

Step4讀取道路關系數據Links.csv，獲取道路之間的連接，源路段S，目標路段T。

Step5當Sin NodesInfoDict或T in NodesInfoDict，執行下一步，否則執行Step 4。

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

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

Step8返回網絡G′。

3.3 乘客最大概率算法

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

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

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

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

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

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

(1)

(2)

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

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

(3)

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

3.4 UCT算法

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

(4)

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

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

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

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

(5)

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

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

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

RolloutPolicy:Si→ai

(6)

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

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

3.5 最短路徑求解

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

3.6 在線推薦階段

在在線推薦階段，推薦系統不僅向出租車推薦路線，同時還對于出租車是否接到乘客的結果來更新模型。該階段與離線學習的區別是：

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

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

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

步驟1設定某一真實出租車為查詢節點。

步驟2獲取離線學習階段中該節點附近的UCB值。

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

步驟4若出租車未接到乘客，那么執行步驟1，同時進行負反饋，使用MCTS更新出租車經過道路的所有UCB值至離線學習系統。

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

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

輸入：路徑p的初始節點R。

輸出：路徑p的子節點imaxUCB值ρUCBp。

1.設定路網所有道路UCB值ρUCBp=0

2.設定第r輪初始值r=0

3.循環：對于每個路徑p，則設置Si=0

4.限定搜索總數t在設定范圍[tmin,tmax]中

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

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

8.否則，直接更新

3.7 路徑推薦模型特性

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

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

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

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

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

4 推薦模型實驗

本文設計兩個實驗來對路徑推薦方法進行說明。

實驗1，離線學習階段實驗，模型對歷史數據進行學習獲得道路的UCB權重值。

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

4.1 實驗數據介紹

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

4.2 實驗環境介紹

本實驗在PC環境下完成，實驗環境為：

CPU：E3- 1231 V3；內存：16 GB；顯卡：NVIDIA GTX960；系統版本：Windows 10。

4.3 離線學習階段實驗

本實驗使用紐約市出租車運行的歷史數據集，由推薦系統對該數據集進行離線學習獲得道路的UCB值，并證明UCB值與被推薦路徑的關系。同時，本例作為路徑推薦模型的離線學習結果部分，通過樣本集進行隨機搜索獲得紐約市曼哈頓地區的道路UCB值，這些遍布所有道路的UCB值是作為出租車巡游過程中在線推薦的基準，為真實的出租車路徑推薦提供基礎推薦值。

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

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

表1 UCB值結果樣例

表1中，ID維度表示道路的ID編號，Production Rate表示乘客產出概率，UCB維度表示UCB的計算結果。

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

表2 乘客產出與UCB值的關系

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

4.4 可視化設計實驗

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

圖2 路徑推薦結果可視化

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

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

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

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

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

5 應用案例

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

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

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

5.1 評估框架

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

本案例使用隨機選擇方法構造隨機訓練集，選擇曼哈頓地區的出租車司機中的X%作為訓練集，X是隨機訓練集的大小。

5.2 評價指標

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

(7)

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

5.3 推薦質量

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

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

圖3 MCTS推薦性能與查詢數量的關系

圖4 Verma等[13]和Qu等[12]推薦性能與查詢數量的關系

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

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

圖5 MCTS推薦質量與訓練集大小的關系

圖6 Verma等[13]和Qu等[12]推薦質量與訓練集大小的關系

6 結 語

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