基于ARIMA模型和K-means聚類分析的動態(tài)規(guī)劃算法

徐建閩，臧 鵬，首艷芳

(1. 華南理工大學(xué) 土木與交通學(xué)院，廣東 廣州 510640； 2. 華南理工大學(xué) 廣州現(xiàn)代產(chǎn)業(yè)技術(shù)研究院, 廣東 廣州 510640)

0 引 言

尋找最短路徑是智能交通系統(tǒng)最重要的功能之一。無論是否處在疫情環(huán)境中，環(huán)境是否劇烈變化，實時自動化的信息采集方式均能保證信息采集的準(zhǔn)確性、安全性和清潔性[1-2]，所以研究基于浮動車數(shù)據(jù)的最短路徑算法具有深遠(yuǎn)的意義。

近年來，尋找最短路徑的主要方法通常分為兩類，即受干擾的最短路徑尋找和不受干擾的最短路徑尋找，采用的方法有：權(quán)重圖匹配法[3]、自適應(yīng)路徑尋找[4-6]和馬爾科夫決策模型[7]。而基于浮動車數(shù)據(jù)的算法多選擇權(quán)重圖匹配法。權(quán)重圖匹配法是根據(jù)多種參數(shù)，如道路距離、等級等設(shè)置權(quán)重，以求排除不可能的候選路段，從而降低了地圖匹配算法的計算復(fù)雜度。然而，權(quán)重的確定具有很強(qiáng)的主觀性，同時計算出來的最短路徑不一定是最優(yōu)解，所以研究排除干擾、耗時短且獲得最優(yōu)解的算法是現(xiàn)今研究的趨勢。

建立基于ARIMA模型和K-means聚類分析的動態(tài)規(guī)劃算法，并利用滴滴出行數(shù)據(jù)在成都市的二環(huán)區(qū)域內(nèi)進(jìn)行了測試，最后通過實驗結(jié)果表明，新的算法以較低的計算量提供了高質(zhì)量的時間解。

1 理論方法

1.1 ARIMA模型

時間序列模型可以通過把時間序列數(shù)據(jù)按照曲線擬合和參數(shù)估計的方法來建立數(shù)學(xué)模型的一種理論和方法，是參數(shù)化模型處理動態(tài)隨機(jī)數(shù)據(jù)的一種實用方法，可以預(yù)測未來。差分整合移動平均自回歸(ARIMA)模型經(jīng)常運用在交通環(huán)境中且預(yù)測效果良好[8-9]。ARIMA模型由3部分組成。

1.1.1 自回歸過程

Xt=α1Xt-1+α2Xt-2+…+αiXt-i+…+αpXt-p+βt

(1)

式中：αi為預(yù)測模型參數(shù)；Xt-i(i=1,…,p)為前p期數(shù)據(jù)；βt為隨機(jī)擾動項。

由于ARIMA模型預(yù)測軌跡旅行時間的精度受到數(shù)據(jù)缺失的影響較大，且信號燈對交叉口上、下游道路的作用高于交叉口上游或下游道路的作用，所以采用路段中點取樣法，即采樣點為路段中點，預(yù)測路段的旅行時間并與實際的旅行時間對比后將其組合來預(yù)測軌跡旅行時間。組合的方法能夠填補(bǔ)缺失數(shù)據(jù)，同時減少信號燈及突發(fā)事故的影響，使預(yù)測效果有所改善。

第i期軌跡旅行時間的計算公式為：

(2)

式中：xt-i,mn,lk為同期組合軌跡的路段旅行時間；n、m分別為路段起點的經(jīng)度、緯度；l、k分別為路段終點的經(jīng)度、緯度；x′t-i,mn,lk為同期路段旅行時間的預(yù)測值為式(3)：

(3)

為進(jìn)一步減小采樣時出現(xiàn)的區(qū)域性截斷和載體過少導(dǎo)致數(shù)據(jù)缺失等問題，采用如下處理規(guī)則：第i期的旅行時間xt-i通過前一段時間內(nèi)的旅行時間樣本數(shù)據(jù)進(jìn)行計算，若數(shù)據(jù)充足，則采用所有數(shù)據(jù)取平均值的方法；若數(shù)據(jù)缺失，則用已知的前期數(shù)據(jù)做線性推導(dǎo)。計算公式為：

(4)

式中：Si,p為第i期的軌跡旅行時間的采樣數(shù)據(jù)，共有A個；Si′和Si″為i期前i′時刻和i″時刻的2個能采集到的旅行時間數(shù)據(jù)，數(shù)據(jù)充足的標(biāo)準(zhǔn)為Q個。

1.1.2 差分過程

差分過程處理非線性、非平穩(wěn)的序列數(shù)據(jù)，并將非線性、非平穩(wěn)的序列數(shù)據(jù)轉(zhuǎn)化為平穩(wěn)的數(shù)據(jù)。式(5)為一階差分變形，能夠轉(zhuǎn)化為ARMA模型。同時，差分過程可以提高預(yù)測精度。

ΔXt=Xt-Xt-1

(5)

1.1.3 移動平均過程

移動平均過程是研究隨機(jī)擾動項的序列相關(guān)性。式(6)是q階的移動平均過程：

βt=δt-θ1δt-1-θ2δt-2-…-θqδt-q

(6)

ARIMA模型可以較為精準(zhǔn)的預(yù)測軌跡的旅行時間，但是無法找到區(qū)域內(nèi)最短路徑，所以建立基于ARIMA模型的動態(tài)規(guī)劃模型來實現(xiàn)目標(biāo)。

1.2 基于ARIMA模型的動態(tài)規(guī)劃模型

建立基于ARIMA模型的動態(tài)規(guī)劃模型，目標(biāo)函數(shù)為：

(7)

但是，隨著道路網(wǎng)規(guī)模的擴(kuò)大，訪問狀態(tài)會增加，動態(tài)規(guī)劃函數(shù)往往面臨維數(shù)災(zāi)難和運算過慢的問題，所以簡化為：

(8)

式中：x′mn, lk為每段路段的ARIMA模型的預(yù)測值，其公式為：

(9)

1.3 基于ARIMA模型和K-means聚類分析的動態(tài)規(guī)劃算法

動態(tài)規(guī)劃算法的挑戰(zhàn)之一是在為特定的狀態(tài)做出決策時，確保探索和利用策略之間的平衡。只使用探索策略可能會導(dǎo)致選擇似乎最優(yōu)值的決策而陷入局部最優(yōu)。另一方面，僅采取利用策略可能會導(dǎo)致隨機(jī)訪問每個狀態(tài)，這會大大增加計算時間和較差的估計值。

在文獻(xiàn)中，一些技術(shù)，如狀態(tài)約簡技術(shù)[10]和隨機(jī)前瞻算法[11-12]被用來解決以上問題。K-means 聚類分析[13]的起源是信號處理的一種向量量化方法，目的是把r個點劃分到s個聚類中，使得每個點都屬于離它最近的均值(即聚類中心)對應(yīng)的聚類中，以此作為聚類的標(biāo)準(zhǔn)。為集群耗時相似的路徑，從而避開耗時長的區(qū)域選擇耗時較短的路徑，減少查詢狀態(tài)的范圍，提高運算速度。將K-means的特征值作為路段的預(yù)測平均速度。

同時，為保證預(yù)測精度，建立基于ARIMA模型和K-means聚類分析的動態(tài)規(guī)劃算法(DPBAK)，具體步驟為：

步驟1輸入每段路的每期實際的旅行時間xt-i,mn, lk，路段的長度Smn, lk，聚類個數(shù)s。

步驟2用ARIMA模型預(yù)測xmn, lk。

步驟3K-means聚類分析將各個路段的按特征值分為s類，并從DLng和DLat集合中剔除不符合要求的路段集合。

步驟4用Dijkstra算法求解最短路徑。

步驟5輸出T。

這種基于浮動車數(shù)據(jù)的組合算法的優(yōu)點在于：①采樣時間短，可以減小每一階段的期望計算；②可以隨時計算未來的最短旅行時間，且越接近目的地越可靠；③快速計算不同位置的最優(yōu)值；④不會受外界干擾而引起大的波動。

1.4 對比算法

對于無法獲得最優(yōu)解的大型實例，筆者使用H.SHUAI等[12]提出的分段線性函數(shù)改進(jìn)的近似動態(tài)規(guī)劃(ADPED)進(jìn)行基準(zhǔn)測試，其得到的近似最優(yōu)解非常接近全局最優(yōu)解。

2 實驗及實驗結(jié)果

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

筆者的研究數(shù)據(jù)來源于滴滴出行“蓋亞”數(shù)據(jù)開放計劃(網(wǎng)址：https:∥gaia.didichuxing.com)的2016年10月成都市二環(huán)區(qū)域65 km2的快專車平臺的訂單司機(jī)軌跡數(shù)據(jù)。選擇2016年10月28日的數(shù)據(jù)，軌跡點的采集間隔是2～4 s，起點和終點分別是雙橋社區(qū)西南1門和藍(lán)谷公寓西南門(S-L)，如圖1。為簡化運算，將區(qū)域中的單行道等特殊車道剔除。

圖1 雙橋社區(qū)西南1門和藍(lán)谷公寓西南門地圖

2.2 運算環(huán)境

筆者提出的算法用python語言實現(xiàn)，所有的實驗均在個人電腦上進(jìn)行，具體配置為Intel Core i5 2.2 GHz處理器和4.00 GB內(nèi)存。

2.3 評價指標(biāo)

為評價算法的預(yù)測性能，選擇絕對百分誤差(MAPE)計算預(yù)測值與實際值的偏差，其計算公式為：

(10)

2.4 實驗結(jié)果

根據(jù)交通擁堵指數(shù)的5個級別，令k=5。算法從DLng和DLat集合中逐步剔除旅行時間由高到低的集合，如圖2，DPBAK-1是DPBAK算法剔除的速率集合[0,25.6]，DPBAK-2是DPBAK算法剔除的速率集合[0,38.12]，以此類推。實驗結(jié)果如圖3～圖6，如表1。

圖2 DPBAK算法在21:15部分聚類集合

表1 DPBAK與ADPED 對比

圖3 DPBAK- 1與ADPED對比

圖4 DPBAK-2與ADPED對比

實驗結(jié)果表明：算法較快運算出貼近最優(yōu)解的結(jié)果。與ADPED 相比，算法運算時間均低于2.010 min，平均百分誤差低于6.5%，無效值比率小于20%。這說明剔除擁堵或者說是速度較慢的路段集合，在一定范圍內(nèi)可以提高運算效率和準(zhǔn)確率。隨著對于集合剔除數(shù)量的增加，運算時間明顯降低，平均誤差值明顯減小。但是值得注意的是，運算時間的變化率和平均誤差在剔除最大的2個集合后不會明顯增加，平均誤差甚至?xí)杂性黾?，?中DPBAK-3、DPBAK-2、DPBAK-4的平均誤差分別為4.49%、3.87%和4.3%，運算時間分別為1.271 min(-36.8%)、1.413 min(-29.7%)和1.130 min(-43.8%)。這說明剔除過多的集合會減少查詢狀態(tài)，提高運算速度，但是剔除過多會導(dǎo)致兩種情況：繞路嚴(yán)重，增加旅行時間；或是無法得到可行解。從圖3～圖6及表1來看，算法與近似最優(yōu)解波動較為貼合。這證明了算法有效性。同時，剔除較多的集合后，無效值和MAPE異常值明顯出現(xiàn)在日間。這可能與日間的車速波動較大有關(guān)。隨著剔除的集合增加，無效值比例和MAPE異常值數(shù)量明顯增加。這也佐證了“剔除過多的集合會減少查詢狀態(tài)，提高運算速度，但是剔除過多會導(dǎo)致繞路嚴(yán)重增加旅行時間”的論點。

圖5 DPBAK-3與ADPED對比

圖6 DPBAK-4-與ADPED對比

3 結(jié) 論

建立了基于ARIMA和K-means聚類分析的動態(tài)規(guī)劃算法來預(yù)測最短路徑，并通過實驗得到以下結(jié)論：

1)提出了新的最短路徑算法且算法能較快運算出貼近最優(yōu)解的解。

2)剔除擁堵或速度較慢的路段集合，在一定范圍內(nèi)可以提高算法的運算效率(+8.2%到+43.8%)和降低誤差(3.81%到6.10%)。

3)剔除過多的集合會使算法性能提升，但剔除過多會導(dǎo)致得不到最優(yōu)解，甚至是得不到解的情況發(fā)生。

4)與ADPED 相比，算法運算時間均低于2.010 min，平均絕對百分誤差低于6.5%，無效值比率小于20%。