李軍，郭育煒，葉威

(中山大學(xué)，智能工程學(xué)院，廣州510006)

0 引言

傳統(tǒng)最優(yōu)出行路徑多是根據(jù)路段的交通阻抗計(jì)算獲取，且城市道路中路段交通阻抗最具代表性的指標(biāo)為出行時(shí)間，但出行時(shí)間極具不確定性。雖然交通大數(shù)據(jù)技術(shù)為道路阻抗的估算提供了支撐，但獲取路段阻抗特別是交通擁堵狀態(tài)下的阻抗仍有較大困難。另一方面，由于交通狀態(tài)的復(fù)雜性，出行者的實(shí)際出行路徑往往與利用阻抗計(jì)算出的路徑有較大差異。因此，直接利用數(shù)據(jù)驅(qū)動(dòng)的方式尋找最優(yōu)出行路徑逐漸成為研究熱點(diǎn)[1]。

出行者位置轉(zhuǎn)移的選擇通?？梢悦枋龀鲂姓咴诔鲂羞^程中的實(shí)際選擇行為[2]?；诔鲂姓呶恢棉D(zhuǎn)移的研究當(dāng)中，基于Markov 及其改進(jìn)模型的研究是較新型的方法，主要思想是以路網(wǎng)中的節(jié)點(diǎn)或路段為狀態(tài)空間，出行者的行駛過程為狀態(tài)間的轉(zhuǎn)移，從而構(gòu)建全局最優(yōu)路徑預(yù)測方法[3-6]。這些研究采用數(shù)據(jù)驅(qū)動(dòng)方法，實(shí)現(xiàn)對出行者下一個(gè)位置的預(yù)測，取得了較高的精度；大多數(shù)研究利用較繁雜的機(jī)器學(xué)習(xí)過程，對尋找最優(yōu)路徑而言，其實(shí)現(xiàn)效率往往較低。城市中，人們對出行環(huán)境較熟悉，可假設(shè)歷史出行數(shù)據(jù)當(dāng)中隱含出行者對最優(yōu)路徑的選擇，因此有學(xué)者基于特定條件下的歷史出行軌跡，獲取其轉(zhuǎn)向規(guī)律并進(jìn)行最優(yōu)路徑規(guī)劃[7-8]。這些方法通過歷史出行軌跡的某些規(guī)律或指標(biāo)分析，實(shí)現(xiàn)路徑預(yù)測。但在實(shí)際應(yīng)用當(dāng)中，存在有效軌跡選取方式不合理的問題：一是不同出行時(shí)段內(nèi)的交通狀況存在較大差異，對最優(yōu)路徑預(yù)測結(jié)果具有一定影響，應(yīng)將其納入考慮；二是數(shù)據(jù)樣本量不足，并非所有車輛均可提供相應(yīng)軌跡數(shù)據(jù)，且起點(diǎn)、終點(diǎn)數(shù)量眾多，針對特定的起點(diǎn)和終點(diǎn)，完全匹配的路徑數(shù)量不多，再考慮出發(fā)時(shí)刻的匹配，其數(shù)量更少，樣本量不足以統(tǒng)計(jì)分析。

考慮城市道路擁擠網(wǎng)絡(luò)多為通勤時(shí)段，出行者多會(huì)選擇最優(yōu)路徑出行，考慮出行者認(rèn)知的隨機(jī)性，認(rèn)為所面臨的路網(wǎng)狀態(tài)為“隨機(jī)用戶均衡(SUE)”，即在所有出行者均認(rèn)為自身已選擇最優(yōu)路徑的前提下，依據(jù)歷史出行數(shù)據(jù)為特定起點(diǎn)與終點(diǎn)間的出行進(jìn)行最佳路徑的規(guī)劃。城市出租車出行中，司機(jī)對道路網(wǎng)絡(luò)都較為熟悉，可以假設(shè)歷史行程當(dāng)中被選擇頻率最高的就是最優(yōu)路徑。因此，本文提出一種基于路段間轉(zhuǎn)移概率的最優(yōu)路徑預(yù)測方法，一方面避免路段阻抗的計(jì)算，另一方面考慮不同交通狀況存在的影響，以及解決歷史數(shù)據(jù)量不足的問題。包括有效軌跡集的構(gòu)建，路段間轉(zhuǎn)移概率的計(jì)算，以及最大概率路徑求解算法的設(shè)計(jì)，并將最大概率路徑作為最優(yōu)出行路徑的預(yù)測結(jié)果。最后通過廣州市某個(gè)區(qū)域的出租車軌跡數(shù)據(jù)作為案例，驗(yàn)證方法的合理性。

1 基于路段間轉(zhuǎn)移概率的最優(yōu)路徑預(yù)測建模

考慮典型的出行路徑選擇問題，在一個(gè)道路網(wǎng)絡(luò)給定出行起點(diǎn)r與終點(diǎn)s，以及出發(fā)時(shí)刻，本文利用數(shù)據(jù)驅(qū)動(dòng)方式，為出行者尋找最優(yōu)的出行路徑。通過計(jì)算路段間的轉(zhuǎn)移概率，構(gòu)建出行者對路段選擇的Markov過程，計(jì)算路徑被選擇的概率，將最大概率路徑作為最優(yōu)路徑的預(yù)測結(jié)果。最優(yōu)路徑的預(yù)測主要包括兩個(gè)部分：一是從歷史數(shù)據(jù)中提取有效軌跡，統(tǒng)計(jì)獲取路段間的轉(zhuǎn)移概率；二是設(shè)計(jì)基于路段間轉(zhuǎn)移概率的最優(yōu)出行路徑預(yù)測算法。

1.1 有效軌跡提取及轉(zhuǎn)移概率計(jì)算

選取有效軌跡時(shí)面臨兩方面問題。其一，不同時(shí)間段中，路網(wǎng)存在不同程度的擁堵狀況，交通特性與路段阻抗具有不同變化，并非所有歷史數(shù)據(jù)與現(xiàn)時(shí)的最優(yōu)選擇一致；其二，在多數(shù)情況下，起點(diǎn)r與終點(diǎn)s間的軌跡數(shù)量極少，不足以進(jìn)行分析。

對于出行時(shí)段問題，根據(jù)城市路網(wǎng)交通特性，將一天中的時(shí)間劃分為早高峰、晚高峰與非高峰(早晚高峰除外的其他時(shí)段)這3個(gè)時(shí)段。根據(jù)出行時(shí)間點(diǎn)，選取對應(yīng)時(shí)段的軌跡集。為解決歷史數(shù)據(jù)不足問題，將歷史數(shù)據(jù)的選擇從給定的點(diǎn)擴(kuò)展到其出行小區(qū)，認(rèn)為同一個(gè)交通小區(qū)中所產(chǎn)生的出行具有相似特性，通過區(qū)域劃分?jǐn)U大軌跡數(shù)據(jù)的選取范圍，將起點(diǎn)所在區(qū)域前往終點(diǎn)所在區(qū)域的軌跡作為軌跡集。

具體步驟為：將研究范圍內(nèi)的交通路網(wǎng)劃分為若干個(gè)區(qū)域，并判斷起點(diǎn)r與終點(diǎn)s所在區(qū)域，分別記為區(qū)域O與區(qū)域D，如圖1所示。

圖1 區(qū)域劃分示意圖Fig.1 Diagram of area division

在所有軌跡中，提取同時(shí)滿足出行時(shí)段與出行區(qū)域條件的歷史軌跡：①軌跡行程所處時(shí)段與給定的出行時(shí)間所處時(shí)段一致；②軌跡行程由區(qū)域O前往區(qū)域D。將篩選所得軌跡構(gòu)建為有效軌跡集，記為ΓOD。數(shù)據(jù)雖未能覆蓋總體樣本，但其數(shù)據(jù)具有代表性。其一，通過從時(shí)間、空間兩個(gè)維度上擴(kuò)大范圍獲取更多數(shù)據(jù)量，不影響方法有效性的驗(yàn)證；其二，本文采用的數(shù)據(jù)為城市出租車，出租車司機(jī)是對交通路網(wǎng)熟悉程度較高的群體，其選擇具有代表性；其三，采用數(shù)據(jù)跨越時(shí)段較長，同時(shí)按照不同時(shí)段對數(shù)據(jù)進(jìn)行劃分，大量浮動(dòng)車數(shù)據(jù)具有隨機(jī)性，短時(shí)間采樣不均勻性造成的誤差，可以通過長時(shí)間的歷史數(shù)據(jù)來彌補(bǔ)。

將路網(wǎng)表示為網(wǎng)絡(luò)圖G=(V,A)，其中，A表示網(wǎng)絡(luò)中的路段集合，A={al|l=1,2,…,Ia}，al表示一個(gè)路段，Ia為網(wǎng)絡(luò)中路段數(shù)量；V表示網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，V={vi|i=1,2,…,Iv}，vi表示一個(gè)節(jié)點(diǎn)，Iv為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量。若路段al分別以vi1、vi2為起點(diǎn)、終點(diǎn)，i1,i2∈[1 ,Iv] ，記為al=(vi1,vi2)。

將網(wǎng)絡(luò)中的路段作為Markov 鏈的狀態(tài)空間，路段間轉(zhuǎn)移概率定義為Markov鏈的轉(zhuǎn)移概率。統(tǒng)計(jì)ΓOD中的軌跡，獲得路段間轉(zhuǎn)移概率及起始路段的選擇概率。

假設(shè)兩個(gè)路段al1與al2，l1,l2∈[ ]1,Ia，則路段al1到al2的轉(zhuǎn)移概率為

式中：Fl1為路段al1的所有下游路段集合；為軌跡集ΓOD中，先后依次經(jīng)過路段al1與路段al2的軌跡數(shù)量；為軌跡集ΓOD中，經(jīng)過路段al1的軌跡數(shù)量。

因軌跡起點(diǎn)是點(diǎn)而非路段，故需要計(jì)算從起點(diǎn)r出發(fā)，選擇每個(gè)起始路段al(l∈[1 ,Ia])的概率為

式中：為軌跡集ΓOD中，先后依次經(jīng)過r與路段al的軌跡數(shù)量；NrOD為軌跡集ΓOD中，經(jīng)過r的軌跡數(shù)量。

如圖2所示，假設(shè)由起點(diǎn)r出發(fā)的起始路段有a1、a2、a3且由ΓOD統(tǒng)計(jì)得到先后依次經(jīng)過節(jié)點(diǎn)r與各路段的軌跡數(shù)量比例為0.2 、0.7 、0.1，則；假設(shè)路段a2的下游路段有a5、a6、a7且由ΓOD統(tǒng)計(jì)得到先后依次經(jīng)過路段a2與各下游路段的軌跡比例為0.4 、0.5 、0.1，則

1.2 最優(yōu)出行路徑預(yù)測方法

對r與s間的某一條路徑，定義其選擇概率為：起點(diǎn)r的起始路段概率與每相鄰兩個(gè)路段間轉(zhuǎn)移概率的乘積。假設(shè)L:r →al1→al2→…→alx-1→alx →s()al1,al2,…,alx∈A是r與s間的一條路徑，則L的選擇概率pL為

圖2 路段間轉(zhuǎn)移概率Fig.2 Link-to-link transition probability

例如，圖2中路徑L1:r →a2→a6→a10→s的選擇概率為

依據(jù)上述定義，在r與s之間的所有路徑中，必然存在一條選擇概率最大的路徑。本方法將r與s之間概率最大的路徑作為最優(yōu)預(yù)測路徑。參照Dijkstra 算法求解最短路徑問題的過程，設(shè)計(jì)最大概率路徑求解算法如下(此處只以求解r與s兩點(diǎn)間的最大概率路徑為目標(biāo))。

定義算法涉及符號(hào)：Τ(vi)為節(jié)點(diǎn)vi的臨時(shí)標(biāo)號(hào)，表示r到vi的臨時(shí)性最大概率；Ρ(vi)為節(jié)點(diǎn)vi的永久標(biāo)號(hào)，表示r到vi的確定性最大概率；SΤ為具有臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)集合；SΡ為具有永久標(biāo)號(hào)的節(jié)點(diǎn)集合；λ(vi)為從r到節(jié)點(diǎn)vi的最大概率路徑上，vi的前一個(gè)節(jié)點(diǎn)。

Step 0 初始化。令SΤ=V，SΡ=?；對每一個(gè)vi∈V，令Τ(vi)=0，λ(vi)初始時(shí)為空值。

Step 1 尋找每個(gè)節(jié)點(diǎn)vj(j∈[1,Iv])滿足(r,vj)∈A；記(r,vj)=aj′，令vj的臨時(shí)標(biāo)號(hào)

Step 2 在SΤ中尋找節(jié) 點(diǎn)vq(q∈[1,Iv])滿足，為vq賦予永久標(biāo)號(hào)Ρ(vq)=Τ(vq)，并令SΡ=SΡ?{vq} ，SΤ=SΤ-{vq} 。

Step 3 如果vq=s，進(jìn)入Step 5；否則，進(jìn)入Step 4。

Step 4 記[λ(vq),vq]=aq′。尋找vq的每個(gè)下游節(jié) 點(diǎn)vt(t∈[1 ,Iv] 且滿足(vq,vt)∈Fq且vt∈SΤ)，若，其中，at′=(vq,vt)，則更新Τ(vt)的 值 為，且 令λ(vt)=vq；若，則不更新Τ(vt)和λ(vt)；若不存在vt滿足(vq,vt)∈Fq′且vt∈SΤ，則令Τ(vq)=0 。返回Step 2。

Step 5 由s向r回溯，依次搜索節(jié)點(diǎn)vj1,vj2,…,vjy(j1,j2,…,jy∈[1 ,Iv])滿足vj1=λ(s)、vj2=λ(vj1)、…、vjy=λ(vjy-1)、r=λ(vjy)，則最大概率路徑為：r →vjy →vjy-1→...→vj2→vj1→s。

2 案例分析

以廣州市為例驗(yàn)證預(yù)測路徑的合理性。為全面驗(yàn)證方法合理性，考慮區(qū)域劃分大小，不同時(shí)間段，起終點(diǎn)位置3 個(gè)因素的影響，分不同情況進(jìn)行實(shí)驗(yàn)。①對劃分區(qū)域的粗化與細(xì)化分別驗(yàn)證，共2種情況；②對早高峰、非高峰、晚高峰時(shí)段分別驗(yàn)證，共3種情況；③交換起點(diǎn)r與終點(diǎn)s的位置分別驗(yàn)證，共2 種情況。針對3 方面因素不同情況的組合，進(jìn)行12次驗(yàn)證。

隨機(jī)給定位于廣州市天河區(qū)的一對起終點(diǎn)(相距約5 km)。依據(jù)以下規(guī)則對區(qū)域進(jìn)行粗劃分與細(xì)劃分：不分割城市行政區(qū)界，行政區(qū)界內(nèi)不分割主要道路、公路和河流等地理交通要素，并綜合考慮所獲取數(shù)據(jù)量的充足性，圖3為區(qū)域劃分結(jié)果，其中，r與s所在區(qū)域分別記為O、D。早高峰、非高峰、晚高峰時(shí)段分別為7:00-9:00、12:00-14:00、17:00-19:00。在2014年2月24日-3月21日的工作日提取與出行時(shí)間相對應(yīng)時(shí)段內(nèi)的出租車歷史軌跡，選取由區(qū)域O前往區(qū)域D的軌跡，得到有效軌跡集ΓOD。

統(tǒng)計(jì)軌跡集ΓOD，得到軌跡所包含的路段，r的起始路段選擇概率，路段到路段的轉(zhuǎn)移概率，建立路徑選擇的Markov過程。根據(jù)最優(yōu)出行路徑預(yù)測方法，求解得到r與s之間的最大概率路徑。

2014年2月24日-3月21日期間工作日內(nèi)與出行時(shí)間相對應(yīng)時(shí)段的出租車軌跡當(dāng)中，選取r與s之間的軌跡，作為驗(yàn)證軌跡。對驗(yàn)證軌跡按照被選擇的頻率大小進(jìn)行排序，此處僅統(tǒng)計(jì)頻率最高的4條軌跡。12 次實(shí)驗(yàn)的預(yù)測路徑與相應(yīng)的驗(yàn)證軌跡如圖4所示，每一次實(shí)驗(yàn)結(jié)果如表1所示。

由表1可得，預(yù)測路徑有7 次實(shí)驗(yàn)與頻率最高的軌跡一致，有4次實(shí)驗(yàn)與頻率第2的軌跡一致，有1 次實(shí)驗(yàn)與頻率第4 的軌跡一致。實(shí)驗(yàn)4 只預(yù)測出頻率第4的軌跡，這是因?yàn)樵摯螌?shí)驗(yàn)中驗(yàn)證軌跡樣本量不足(只有20多條)。頻率第2的軌跡數(shù)量僅比頻率第4 的軌跡多1 條，說明驗(yàn)證數(shù)據(jù)量不足導(dǎo)致結(jié)果出現(xiàn)較大偶然性。

圖3 區(qū)域劃分Fig.3 Division of areas

圖4 路徑編號(hào)Fig.4 Identifier of routes

本文以區(qū)域之間數(shù)據(jù)預(yù)測起終點(diǎn)的最優(yōu)出行路徑，本身為基于數(shù)據(jù)驅(qū)動(dòng)的估算方法，計(jì)算結(jié)果為頻率第2軌跡屬正常結(jié)果。表1結(jié)果說明，本方法對所采集數(shù)據(jù)產(chǎn)生的結(jié)果而言具有顯著的有效性。

除驗(yàn)證預(yù)測結(jié)果的總體準(zhǔn)確性，同時(shí)比較分析單方面因素產(chǎn)生的影響，如表2所示。

由表2可知，單方面因素影響如下：

(1)區(qū)域劃分大小不同，預(yù)測準(zhǔn)確性均較高、差異較小，表明區(qū)域劃分大小對預(yù)測準(zhǔn)確性影響較小。

(2)時(shí)間段不同，非高峰、晚高峰時(shí)段的預(yù)測結(jié)果準(zhǔn)確性較高，早高峰時(shí)段略低，表明不同時(shí)間段內(nèi)的預(yù)測準(zhǔn)確性具有一定差異。

(3)起終點(diǎn)位置不同，預(yù)測準(zhǔn)確性均較高，差異較小，表明不同起終點(diǎn)位置對預(yù)測準(zhǔn)確性影響較小。

表1 預(yù)測路徑與驗(yàn)證軌跡比較Table 1 Comparison between predicted route and verified trajectory

表2 單方面因素結(jié)果比較Table 2 Comparison of one-sided factors

3 結(jié)論

本文提出將數(shù)據(jù)驅(qū)動(dòng)、出行時(shí)段與出行區(qū)域劃分相結(jié)合的最優(yōu)出行路徑預(yù)測方法，解決了路段阻抗計(jì)算困難和數(shù)據(jù)量不足的問題，結(jié)果總體準(zhǔn)確性高，且具有數(shù)據(jù)易獲取，執(zhí)行過程簡便的優(yōu)點(diǎn)，體現(xiàn)出在已有采集數(shù)據(jù)情況下的有效性。此外，分析各方面因素的結(jié)果表明，不同區(qū)域劃分大小和不同起終點(diǎn)位置對預(yù)測準(zhǔn)確性影響較小，不同出行時(shí)間段對預(yù)測準(zhǔn)確性具有一定的差異性影響。因此，利用本文方法預(yù)測最優(yōu)出行路徑時(shí)，應(yīng)注意時(shí)間段的合理劃分，而對于區(qū)域劃分則可適當(dāng)擴(kuò)大，以獲取較充足的數(shù)據(jù)量。

另外，從“系統(tǒng)最優(yōu)”層面來看，本文便于理解出行者的行為，挖掘出行者出行規(guī)律，對交通管理與規(guī)劃的實(shí)行措施具有一定價(jià)值。