關于出租車載客地點序列推薦技術的研究

陳軼非 李治軍 姜守旭

摘要：在大城市中，出租車已成為實現智能交通運輸系統不可或缺的一環。然而，由于一些出租車司機的駕駛經驗，和對城市活動的熟悉程度的不足，使得其在尋找乘客時會采取毫無目的的隨機漫游策略。這就導致了出租車司機的收益不高，同時也造成了能源的消耗以及環境的污染。針對此問題，將提出出租車載客地點的推薦模型，使得模型給出的推薦地點序列能獲得較高的期望收益。具體來說，將基于出租車GPS軌跡數據建立出租車載客地點的馬爾科夫決策過程模型，并給出求解該模型的2種算法。仿真實驗結果顯示，與典型的TopK方法相比，給出的推薦結果能更好地提高單位時間內出租車司機的收益。

關鍵詞：智能交通系統； 馬爾科夫決策過程； 空間數據挖掘； 軌跡數據處理

中圖分類號：TP391 文獻標識碼：A文章編號：2095-2163（2013）06-0070-04

0引言

在人們日常的出行活動中，出租車正扮演著越來越重要的角色。如今，已經有數量眾多的現代人選擇出租車來作為其代步的出行方式。根據最近一份關于紐約出租車服務的調查[1]，結果顯示有41%的調查者每周都會乘坐出租車，有25%的調查者甚至每天都會乘坐出租車。然而，為了方便人們的出行，一些大城市（如紐約、東京、倫敦和北京）都會有大量的空載出租車隨機行駛在城市區域中。這些空載出租車的隨機行駛不僅會浪費出租車的汽油，造成環境的污染，而且會造成城市中額外的交通事故。因此，怎樣規劃空載出租車的行駛路線使其快速發現乘客，提高出租車的利用率，從而有效減輕資源消耗和環境污染，則成為一個亟待解決的嚴峻挑戰。

近年來，為了出租車的調度和安全，許多大城市（如紐約、北京和新加坡）中的出租車均配置了GPS傳感器。這些出租車會以一定的頻率（如2分鐘）向數據中心報告其當前所處的位置[2]。除了地理位置和時間戳信息，出租車的載客狀態信息也會通過重量傳感器或者出租車的計程器被記錄下來。因此，每天都會產生大量的伴隨著出租車載客狀態的GPS軌跡信息。這些軌跡信息的產生也引發了學術界對出租車地點推薦問題的關注和興趣。文獻[3]提出了一個推薦出租車司機至一系列載客點的模型，目的是使得出租車司機的收益最大化。該模型使用了skyline路徑查詢的方法，同時將問題形式化為移動序列推薦（mobile sequential recommendation）問題。文獻[4]提出了出租車司機尋找乘客的學習策略（漫游/等待）。該文獻使用了L1-Norm SVM的學習方法篩選得出用于尋找乘客策略的分類特征。文獻[5]提出了一種能預測出租車收益地點的方法。該方法建立了空間-時間收益地圖，并根據歷史數據計算出的潛在收益將臨近區域內的司機在該地圖上進行評分。

與上述研究類似，本文也將提出一種基于GPS軌跡信息的出租車載客地點推薦系統。其中，系統的輸入為空載出租車當前的地理位置和時間，輸出為預推薦的一系列的載客地點，使得這些載客地點能夠實現單位時間內的收益最大化。但與已有研究不同的是，本文將建立基于馬爾科夫決策過程[6]（Markov Decision Process， MDP）的推薦模型，同時將融合2方面的特征：

（1）能以較大的概率發現乘客；

（2）推薦地點離當前地點的距離不是太遠（否則物質上和時間上的開銷都較大）。

實驗結果表明，模型給出的推薦結果將有助于減少出租車隨機漫游的時間，為出租車司機帶來更多的收益。

1預備知識

整個MDP過程可表示如下：S0a0S1a1S2a2…，所能獲得的總的回報為R（s0，a0）+γR（s1+a1）+γ2R（s2，a2）+…。MDP的優化目標就是采取某組策略（動作），使得該回報值最大化。

2出租車載客地點的MDP模型的建立

2.1狀態集合的建立

首先，將建立MDP的狀態。可令狀態s表示為三元組s=（p，t，x），其中p表示出租車所在的地點，t表示出租車所處的時刻，x表示出租車當前的載客狀態：x=0未載客

1載客。現在將對出租車所處的時空狀態進行離散化處理。

首先，將出租車的空間位置信息表示在有限的道路網絡內，這樣p就可以抽象成某種空間實體，如其所屬的某條路段r，或者離出租車最近的路口c等；如果沒有城市道路網絡的精確數據，也可以將虛擬的道路網絡劃分成固定大小的網格，將p表示為出租車所在的網格，如此就將連續的空間地點離散成為有限個空間狀態的集合。

其次，將時間維度也離散成有限的時間區間。一般地，由于城市中的許多活動均帶有一定的周期性，如上下班，火車到站等；同時，這些活動在工作日和雙休日內的發生時刻又有著各自的規律性，因此，對時間也將依據2個維度進行劃分：

（1）按照周幾（1-7）或是工作日和雙休日進行劃分；

（2）按照一天內的時間區間進行劃分。

對于（2）的劃分，可以取相等的時間間隔，如Δt=1小時將每天劃分成[00：00～01：00），[01：00～02：00）等24個時間區間；或者根據一些相關的特征來劃分時間段，如將一天劃分成早晨上班高峰時段，工作時段，下午下班高峰時段，晚間時段等。這樣，t就可以表示在這些離散的區間內。于是，將時間也離散成了有限的狀態。

2.2動作集合的建立

根據空間狀態的建立方法，可以將一個動作定義為：選取和當前地點相鄰的某個抽象點（該點和之前空間狀態的建立方法相對應，如該抽象點可以是某個相鄰的路段r，或者是某個相鄰的網格）。因此，總的動作集合A便可定義為空間點集P的一個子集：AP。在此，點p與p′“相鄰”的定義為：p無需經過其他抽象點（路段，網格等）便可以直接到達p′，并簡記為p→p′。于是，當出租車處于某個抽象點p時，所能選取的動作集合可以表示為{p′|p|→p′}。令s（i）表示選取狀態s=（p，t，x）中的第i個分量，那么，一個狀態s的動作集合A（s）則表示為A（s）={p′|p=s（1），p|→p′}。這樣，便建立了總體的動作集合A，以及每個狀態下的可行的動作子集A（s）。

2.3轉移函數的建立

在建立狀態集合S和動作集合A后，便可以將出租車的每個GPS軌跡點對應至相應的s和a上，再利用極大似然估計法，便可以求出每個轉移函數Psa（s′）的近似估計值P^sa（s′），計算公式如下：

P^sa（s′）=狀態s下執行a到達狀態s′的次數狀態s下執行的a次數（1）

如果樣本數不足，使得P^sa（s′）=00，就可以認為不存在該概率分布的先驗知識，于是將其設置為簡單的均勻分布，即P^sa（s′）=1|B|，其中B={s|s（1）=a}。由此即能較準確地估計得到所有情形下的狀態轉移函數。

2.4回報函數的建立

和轉移函數類似，在運行MDP之前，回報函數也是未知的。因此，也可以利用采樣的方法，對回報函數進行估計。本文將采用一種簡單的均值方法，計算公式如下：

R^（s，a）=∑ni=1Ri（s，a）n（2）

其中，n為觀察到在狀態s采取動作a的總次數，Ri（s，a）表示第i次觀察得到的回報值。而觀測值Ri（s，a）則可以根據實際的出租車收益情況進行估計。舉例來說，如果從P點執行動作a=p′到達p′，那么根據出租車在p和p′時是否處于載客狀態，可以將Ri（s，a）分成以下4種情況討論。令出租車在點p的載客狀態記為xp，p和p′的歐幾里得距離記為dist（p，p′），則Ri（s，a）的定義如下：

其中，r為出租車平均每公里掙得的收益（即乘客所支付的費用），c為出租車平均每公里的開銷（油費，零件損耗等），表示異或運算。第3部分中的1/2則基于一個均勻分布的假設，即改變狀態的地點是均勻分布在p和p′之間的。這就對應于先驗知識未知或缺少的情況。

如果樣本數不足，得到R^（s，a）=00的形式，則將該R^（s，a）設置為-c×dist（p，p′），即假設在該情況下，無法拉到乘客。

綜上，利用式（2）和（3）便能估計得到每個R（s，a）的值。

2.5折價因子的建立

折價因子控制了當前的決策對未來的影響程度，或者是希望以多大的權重將未來的收益累加到當前的即時收益中。一般均設置為一個不以時間變化的常數。本文依照學術界的主流做法，取γ=0.95，即表示未來收益的權重非常大。

3出租車載客地點的MDP模型的求解

在建立MDP模型后，本節將討論如何對MDP模型進行求解。為求解得到最優化的MDP策略和回報值，需再定義如下2個概念：

（1）確定性策略（deterministic policy）π：S→A，定義了在某一狀態s∈S下需采取的動作π（s）∈A；更一般的策略π可定義為隨機策略（stochastic policy）：S→∏（A），其中，∏（A）表示的是在動作集合A上的概率分布空間，π（s，a）表示的是在狀態下采取動作a的概率。

（2）策略π的值函數（value function）Vπ（s）定義為Vπ：S→R，表示從狀態s出發采取策略π所能獲得的加權總回報值的期望：Vπ（s1）=E[R（s1，π（s1））+γR（s2，π（s2））+γ2R（s3，π（s3））+…|π]，其中si∈S為在時刻i所處的狀態。MDP的目標便是求出最優策略π*，使得π*的值函數Vπ*（s1）=maxπ{E[R（s1，π（s1））+γR（s2，π（S2））+γ2R（s3，π（S3））+…|π]}

為求解基于MDP模型，需基于以下2個重要定理：

定理1（貝爾曼方程[7]）給定MDP模型M=（S，A，P，γ，R）和策略π：S→A，則對所有的s∈S，a∈A，Vπ滿足以下關系：

其中，在迭代階段，可以使用同步更新和異步更新兩種方法對V進行迭代更新操作。

在同步更新中，可以計算得到每個狀態s∈S下的新的V（s）值，再用這些值覆蓋所有舊的V（s）的值。在這種情況下，該算法可以看做是實現了“貝爾曼備份”的操作，對當前值函數進行了一次值估計，然后將該估計值映射到新的值函數中。

在異步更新中，可根據某種順序循環操作所有的狀態s，并在每一次的循環中即時更新狀態s對應的V（s）。

4實驗分析

4.1數據來源

本文采用的GPS出租車軌跡數據集[8]來自于清華大學復雜工程系統實驗室（Complex Engineered Systems Lab），這些數據通過實驗室所部署的傳感器網絡系統采集得到。該數據集采獲了北京市大約28 000輛出租車在1個月內行駛軌跡的GPS數據，大約覆蓋了北京市42%的出租車數量（總數目約為67 000輛），因此該數據集構建了一個極具代表性的樣本空間。同時，從時間的角度，這份數據集覆蓋了工作日、雙休日，以及節假日。這就真實地反映了出租車在不同時段、不同交通情形下（擁堵、暢通）的活動模式。

本文同時也節取北京的交通道路網絡做為實驗對象，該網絡有106 579個道路節點，以及141 380個道路區間。因此，本文的數據以及實驗對象均為真實可靠的。

4.2數據預處理

對于海量的數據源，將進行一些預處理過程：

（1）行程發現。根據出租車的計程器數據，可以知道出租車是否載客的狀態（X載客=1 or 0），由此可以將行程定義為從X載客變化起的時刻ts至X載客保持該狀態直至結束的時刻te，在此段時間te-ts內所行駛的軌跡，可以將所有司機駕駛的GPS軌跡劃分成一段段如上定義的行程。

（2）地圖匹配。將利用一種對低樣本率的軌跡也具有良好表現性能的匹配算法IVMM[9]，憑此可將每段行程上的點匹配至真實的地圖中，從而將行程信息轉換為一些實際的路段信息。

4.3實驗結果

為了衡量MDP模型序列推薦的性能，本文將進行仿真實驗。實驗中將根據統計的結果模擬得到各個地點的狀態轉移函數Psa（s′），并以載客距離比例、載客時間比例兩個不同的值作為推薦性能的衡量指標。同時，將以TopK算法為參照算法，以對比MDP的性能。實驗結果如圖1、圖2所示。

首先，分析圖1，在乘車需求高峰時段，MDP的載客時間比例大于TopK，而在低谷時段，MDP的載客時間比例卻略小于TopK。原因在于乘車需求較小的時段，TopK給出的地點常常更容易遇到載客，而MDP卻由于需考慮到前往這些地點的路途開銷，因此算法將直接建議在附近局部最優的地點停留，而非前往全局最優的地點。

其次，分析圖2。可以發現，無論在哪個時間段內，MDP的載客距離比例始終要大于TopK，原因就在于TopK通常需要前往全局最優點，而MDP只選擇局部最優的位置。特別地，在乘車需求較低的時段內，兩者的差距會變得更大。而載客的距離往往決定了實際的打車費用，因此，從實際收益的角度來看，MDP的性能要好于TopK。

5結束語

為了使出租車司機能獲得較高的期望收益，本文針對出租車司機載客地點選擇問題進行了研究。在基于出租車GPS軌跡數據的基礎上，建立了解決出租車載客地點序列推薦問題的馬爾科夫決策過程模型，并給出求解該模型的兩種算法。仿真實驗結果顯示，與典型的TopK方法相比，本文給出的推薦結果能更好地提高出租車司機單位時間內的收益值，因此驗證了模型的有效性。不過該模型卻依然有其局限性，即沒有考慮環境的動態因素，而只考慮了單個司機的情形。如果有多個出租車司機均選擇了相同的推薦地點，那么極有可能造成出租車司機之間在推薦地點競爭乘客的情形，同時也容易造成推薦地點路段的擁堵。因此，在未來的工作中，將進一步研究多個出租車司機并存的環境中如何選擇載客地點的問題。這可以通過引入博弈論、隨機博弈等理論加以深入研究。

參考文獻：

[1]New York City Taxi and Limousine Commission. Taxi of Tomorrow Survey Results， Feb 2011. http：//www.nyc.gov/html/tlc/downloads/pdf/tot_survey_results_02_10_11.pdf.

[2]YUAN J， ZHENG Y， XIE X， et al. Driving with knowledge from the physical world[C]//Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2011： 316-324.

[3]GE Y， XIONG H， TUZHILIN A， et al. An energy-efficient mobile recommender system[C]// Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM， 2010： 899-908.

[4]LI B， ZHANG D， SUN L， et al. Hunting or waiting？ Discovering passenger-finding strategies from a large-scale real-world taxi dataset[C]//Pervasive Computing and Communications Workshops （PERCOM Workshops）， 2011 IEEE International Conference on. IEEE， 2011： 63-68.

[5]POWELL J W， HUANG Y， BASTANI F， et al. Towards reducing taxicab cruising time using spatio-temporal profitability maps[M]. Advances in Spatial and Temporal Databases. Springer Berlin Heidelberg， 2011： 242-260.

[6]PUTERMAN M L. Markov decision processes： discrete stochastic dynamic programming[M]. New York， Wiley， 2009.

[7]SUTTON R S， BARTO A G. Reinforcement learning： An introduction[M]. Cambridge： MIT press， 1998.

[8]Complex Engineered Systems Lab Taxi Dataset. http：//sensor.ee.tsinghua.edu.cn/datasets.

[9]YUAN J， ZHENG Y， ZHANG C， et al. An interactive-voting based map matching algorithm[C]//Mobile Data Management （MDM）， 2010 Eleventh International Conference on. IEEE， 2010： 43-52.