陳軼非 李治軍 姜守旭

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

關(guān)鍵詞：智能交通系統(tǒng)； 馬爾科夫決策過程； 空間數(shù)據(jù)挖掘； 軌跡數(shù)據(jù)處理

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-2163（2013）06-0070-04

0引言

在人們?nèi)粘５某鲂谢顒?dòng)中，出租車正扮演著越來越重要的角色。如今，已經(jīng)有數(shù)量眾多的現(xiàn)代人選擇出租車來作為其代步的出行方式。根據(jù)最近一份關(guān)于紐約出租車服務(wù)的調(diào)查[1]，結(jié)果顯示有41%的調(diào)查者每周都會(huì)乘坐出租車，有25%的調(diào)查者甚至每天都會(huì)乘坐出租車。然而，為了方便人們的出行，一些大城市（如紐約、東京、倫敦和北京）都會(huì)有大量的空載出租車隨機(jī)行駛在城市區(qū)域中。這些空載出租車的隨機(jī)行駛不僅會(huì)浪費(fèi)出租車的汽油，造成環(huán)境的污染，而且會(huì)造成城市中額外的交通事故。因此，怎樣規(guī)劃空載出租車的行駛路線使其快速發(fā)現(xiàn)乘客，提高出租車的利用率，從而有效減輕資源消耗和環(huán)境污染，則成為一個(gè)亟待解決的嚴(yán)峻挑戰(zhàn)。

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

與上述研究類似，本文也將提出一種基于GPS軌跡信息的出租車載客地點(diǎn)推薦系統(tǒng)。其中，系統(tǒng)的輸入為空載出租車當(dāng)前的地理位置和時(shí)間，輸出為預(yù)推薦的一系列的載客地點(diǎn)，使得這些載客地點(diǎn)能夠?qū)崿F(xiàn)單位時(shí)間內(nèi)的收益最大化。但與已有研究不同的是，本文將建立基于馬爾科夫決策過程[6]（Markov Decision Process， MDP）的推薦模型，同時(shí)將融合2方面的特征：

（1）能以較大的概率發(fā)現(xiàn)乘客；

（2）推薦地點(diǎn)離當(dāng)前地點(diǎn)的距離不是太遠(yuǎn)（否則物質(zhì)上和時(shí)間上的開銷都較大）。

實(shí)驗(yàn)結(jié)果表明，模型給出的推薦結(jié)果將有助于減少出租車隨機(jī)漫游的時(shí)間，為出租車司機(jī)帶來更多的收益。

1預(yù)備知識(shí)

整個(gè)MDP過程可表示如下：S0a0S1a1S2a2…，所能獲得的總的回報(bào)為R（s0，a0）+γR（s1+a1）+γ2R（s2，a2）+…。MDP的優(yōu)化目標(biāo)就是采取某組策略（動(dòng)作），使得該回報(bào)值最大化。

2出租車載客地點(diǎn)的MDP模型的建立

2.1狀態(tài)集合的建立

首先，將建立MDP的狀態(tài)。可令狀態(tài)s表示為三元組s=（p，t，x），其中p表示出租車所在的地點(diǎn)，t表示出租車所處的時(shí)刻，x表示出租車當(dāng)前的載客狀態(tài)：x=0未載客

1載客?，F(xiàn)在將對(duì)出租車所處的時(shí)空狀態(tài)進(jìn)行離散化處理。

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

其次，將時(shí)間維度也離散成有限的時(shí)間區(qū)間。一般地，由于城市中的許多活動(dòng)均帶有一定的周期性，如上下班，火車到站等；同時(shí)，這些活動(dòng)在工作日和雙休日內(nèi)的發(fā)生時(shí)刻又有著各自的規(guī)律性，因此，對(duì)時(shí)間也將依據(jù)2個(gè)維度進(jìn)行劃分：

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

（2）按照一天內(nèi)的時(shí)間區(qū)間進(jìn)行劃分。

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

2.2動(dòng)作集合的建立

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

2.3轉(zhuǎn)移函數(shù)的建立

在建立狀態(tài)集合S和動(dòng)作集合A后，便可以將出租車的每個(gè)GPS軌跡點(diǎn)對(duì)應(yīng)至相應(yīng)的s和a上，再利用極大似然估計(jì)法，便可以求出每個(gè)轉(zhuǎn)移函數(shù)Psa（s′）的近似估計(jì)值P^sa（s′），計(jì)算公式如下：

P^sa（s′）=狀態(tài)s下執(zhí)行a到達(dá)狀態(tài)s′的次數(shù)狀態(tài)s下執(zhí)行的a次數(shù)（1）

如果樣本數(shù)不足，使得P^sa（s′）=00，就可以認(rèn)為不存在該概率分布的先驗(yàn)知識(shí)，于是將其設(shè)置為簡(jiǎn)單的均勻分布，即P^sa（s′）=1|B|，其中B={s|s（1）=a}。由此即能較準(zhǔn)確地估計(jì)得到所有情形下的狀態(tài)轉(zhuǎn)移函數(shù)。

2.4回報(bào)函數(shù)的建立

和轉(zhuǎn)移函數(shù)類似，在運(yùn)行MDP之前，回報(bào)函數(shù)也是未知的。因此，也可以利用采樣的方法，對(duì)回報(bào)函數(shù)進(jìn)行估計(jì)。本文將采用一種簡(jiǎn)單的均值方法，計(jì)算公式如下：

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

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

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

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

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

2.5折價(jià)因子的建立

折價(jià)因子控制了當(dāng)前的決策對(duì)未來的影響程度，或者是希望以多大的權(quán)重將未來的收益累加到當(dāng)前的即時(shí)收益中。一般均設(shè)置為一個(gè)不以時(shí)間變化的常數(shù)。本文依照學(xué)術(shù)界的主流做法，取γ=0.95，即表示未來收益的權(quán)重非常大。

3出租車載客地點(diǎn)的MDP模型的求解

在建立MDP模型后，本節(jié)將討論如何對(duì)MDP模型進(jìn)行求解。為求解得到最優(yōu)化的MDP策略和回報(bào)值，需再定義如下2個(gè)概念：

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

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

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

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

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

在同步更新中，可以計(jì)算得到每個(gè)狀態(tài)s∈S下的新的V（s）值，再用這些值覆蓋所有舊的V（s）的值。在這種情況下，該算法可以看做是實(shí)現(xiàn)了“貝爾曼備份”的操作，對(duì)當(dāng)前值函數(shù)進(jìn)行了一次值估計(jì)，然后將該估計(jì)值映射到新的值函數(shù)中。

在異步更新中，可根據(jù)某種順序循環(huán)操作所有的狀態(tài)s，并在每一次的循環(huán)中即時(shí)更新狀態(tài)s對(duì)應(yīng)的V（s）。

4實(shí)驗(yàn)分析

4.1數(shù)據(jù)來源

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

本文同時(shí)也節(jié)取北京的交通道路網(wǎng)絡(luò)做為實(shí)驗(yàn)對(duì)象，該網(wǎng)絡(luò)有106 579個(gè)道路節(jié)點(diǎn)，以及141 380個(gè)道路區(qū)間。因此，本文的數(shù)據(jù)以及實(shí)驗(yàn)對(duì)象均為真實(shí)可靠的。

4.2數(shù)據(jù)預(yù)處理

對(duì)于海量的數(shù)據(jù)源，將進(jìn)行一些預(yù)處理過程：

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

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

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

為了衡量MDP模型序列推薦的性能，本文將進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中將根據(jù)統(tǒng)計(jì)的結(jié)果模擬得到各個(gè)地點(diǎn)的狀態(tài)轉(zhuǎn)移函數(shù)Psa（s′），并以載客距離比例、載客時(shí)間比例兩個(gè)不同的值作為推薦性能的衡量指標(biāo)。同時(shí)，將以TopK算法為參照算法，以對(duì)比MDP的性能。實(shí)驗(yàn)結(jié)果如圖1、圖2所示。

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

其次，分析圖2?？梢园l(fā)現(xiàn)，無論在哪個(gè)時(shí)間段內(nèi)，MDP的載客距離比例始終要大于TopK，原因就在于TopK通常需要前往全局最優(yōu)點(diǎn)，而MDP只選擇局部最優(yōu)的位置。特別地，在乘車需求較低的時(shí)段內(nèi)，兩者的差距會(huì)變得更大。而載客的距離往往決定了實(shí)際的打車費(fèi)用，因此，從實(shí)際收益的角度來看，MDP的性能要好于TopK。

5結(jié)束語

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

參考文獻(xiàn)：

[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.