基于出行偏好和路徑長度的路徑規(guī)劃方法

李建伏, 王思博, 宋國平

(中國民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 天津 300300)

路徑規(guī)劃是指從道路網(wǎng)絡(luò)中尋找從起始節(jié)點(diǎn)到目的節(jié)點(diǎn)的最優(yōu)路徑. 傳統(tǒng)路徑規(guī)劃算法通常利用經(jīng)典的圖搜索算法(如Dijkstra, Floyd和A*算法)在道路網(wǎng)絡(luò)中尋找最短路徑. 但在實(shí)際應(yīng)用中, 路徑長度不是人們選擇出行路徑的唯一標(biāo)準(zhǔn). 為使規(guī)劃的路徑能滿足用戶的實(shí)際需求, 路徑規(guī)劃被進(jìn)一步形式化為多目標(biāo)最短路徑問題[1]或多約束最短路徑問題[2-3], 即將用戶的出行偏好建模為多個目標(biāo)或約束. 但用戶的出行偏好受多種因素影響, 而這些因素如何影響用戶偏好未知, 甚至用戶自己也無法準(zhǔn)確地表達(dá)其出行偏好. 因此, 不能準(zhǔn)確地描述用戶出行偏好已成為限制多目標(biāo)路徑規(guī)劃或多約束路徑規(guī)劃發(fā)展的瓶頸.

近年來, 隨著全球定位系統(tǒng)(global positioning system, GPS)技術(shù)的發(fā)展及移動設(shè)備的普及, 已產(chǎn)生并收集了大量用戶出行的軌跡數(shù)據(jù). 軌跡數(shù)據(jù)中蘊(yùn)含用戶的出行偏好, 從而為獲得用戶的出行偏好并進(jìn)一步制定最優(yōu)路徑規(guī)劃提供了可行性. 基于軌跡的路徑規(guī)劃目前已成為該領(lǐng)域廣泛關(guān)注的問題. 理想情況下, 連接任意兩點(diǎn)的每條路徑均被足夠多的歷史軌跡覆蓋, 此時, 基于軌跡的路徑規(guī)劃算法只需計(jì)算每條路徑的出現(xiàn)頻次并返回頻次最多的路徑即可. 實(shí)際上, 大量軌跡都集中在某些局部區(qū)域, 在很多節(jié)點(diǎn)對之間未被歷史軌跡覆蓋. 因此, 現(xiàn)有基于軌跡的路徑規(guī)劃算法的基本策略是先根據(jù)歷史軌跡數(shù)據(jù)中蘊(yùn)含的用戶偏好對道路網(wǎng)絡(luò)重新建模, 然后再在新網(wǎng)絡(luò)中尋找最優(yōu)路徑. Cui等[4]根據(jù)用戶的歷史軌跡數(shù)據(jù)和矩陣分解方法先構(gòu)建行為-頻率矩陣, 然后使用樸素Bayes模型計(jì)算路徑; Jia等[5]根據(jù)用戶的歷史出行數(shù)據(jù), 用深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)用戶對每條邊的偏好權(quán)重向量; Chen等[6]用Markov鏈模型先計(jì)算出道路網(wǎng)絡(luò)中每對節(jié)點(diǎn)之間的轉(zhuǎn)移概率, 然后在搜索階段將其作為流行度指標(biāo)找出兩節(jié)點(diǎn)之間的最大概率路線； Luo等[7]在文獻(xiàn)[6]的基礎(chǔ)上, 在指定時間區(qū)間內(nèi)綜合考慮后綴最優(yōu)、 長度不敏感等關(guān)鍵屬性, 提出了一種基于時間周期的頻繁路徑查詢算法. 但上述研究均依賴于歷史軌跡數(shù)據(jù), 只適用于在被歷史軌跡覆蓋的區(qū)域做路徑規(guī)劃. 為實(shí)現(xiàn)在任何區(qū)域都能做路徑規(guī)劃, Guo等[8]提出了一種稱為L2R的路徑規(guī)劃方法, L2R通過遷移學(xué)習(xí)將軌跡連通區(qū)域中的路由偏好轉(zhuǎn)移到非連通區(qū)域, 雖能實(shí)現(xiàn)任意兩點(diǎn)之間的路徑規(guī)劃, 但對于歷史軌跡稀疏或不被歷史軌跡覆蓋的區(qū)域準(zhǔn)確性較差.

由上述分析可見, 基于最短路徑的路徑規(guī)劃算法只考慮了道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu), 而未考慮用戶的出行偏好； 基于軌跡的路徑規(guī)劃方法則過度依賴于用戶的歷史出行軌跡, 當(dāng)歷史軌跡數(shù)據(jù)不充分時, 算法性能較差. 為充分利用歷史軌跡中用戶的出行偏好并更合理地規(guī)劃路徑, 本文將現(xiàn)有基于軌跡的路徑規(guī)劃和基于最短路徑的路徑規(guī)劃相結(jié)合, 提出一種新的路徑規(guī)劃方法——2P++算法. 2P++算法與基于最短路徑的路徑規(guī)劃相同, 即利用圖搜索算法在道路網(wǎng)絡(luò)中尋求最優(yōu)路徑. 2P++算法采用的圖搜索算法是A*算法. 不同于現(xiàn)有基于最短路徑的規(guī)劃方法, 2P++路徑規(guī)劃算法的目的是能規(guī)劃出一條不僅距離較短且更符合用戶出行偏好的路徑. 實(shí)際上, 找到滿足以上兩個目標(biāo)的路徑是一個雙目標(biāo)優(yōu)化問題, 解決該優(yōu)化問題非常耗時. 為快速找到滿足上述兩個目標(biāo)的路徑, 2P++算法使用MCMC(Markov Chain Monte Carlo)采樣技術(shù)將用戶的出行偏好加入到A*算法中. 此外, 2P++算法中獲取用戶出行偏好的方法不同于現(xiàn)有基于軌跡的路徑規(guī)劃方法, 本文采用長短期記憶模型(long short term memory, LSTM)獲取歷史軌跡中蘊(yùn)含的用戶出行偏好.

1 預(yù)備知識

1.1 基本定義

在路徑規(guī)劃中, 道路網(wǎng)絡(luò)通常表示為有向圖G=(V,E), 其中:V={v1,v2,…,vn}表示n個節(jié)點(diǎn)的集合,vi為道路交叉點(diǎn)或道路終點(diǎn), 本文混淆使用i或vi表示節(jié)點(diǎn)；E={e1,e2,…,em}表示m條邊的集合,ek=(i,j)(i,j∈V)表示從節(jié)點(diǎn)vi到vj的有向路段,ek的權(quán)重記為cost(i,j). 路徑規(guī)劃的目的是尋找網(wǎng)絡(luò)G中從起始節(jié)點(diǎn)O到目標(biāo)節(jié)點(diǎn)D的最優(yōu)路徑. 從O到D的路徑PO→D是節(jié)點(diǎn)序列, 其中兩個相鄰節(jié)點(diǎn)通過一條邊連接. 路徑P的長度記為len(P). 軌跡T是移動對象的行進(jìn)過程在地理空間中生成的GPS序列, 通常由一系列按時間順序排列的位置點(diǎn)表示, 即T={(x1,t1),(x2,t2),…,(xl,tl)}, 其中xj(1≤j≤l)是移動對象在tj(1≤j≤l)時刻的位置.

1.2 長短期記憶模型

循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network, RNN)[9]是一種前饋神經(jīng)網(wǎng)絡(luò), 適用于對序列數(shù)據(jù)建模, 并已廣泛應(yīng)用于自然語言處理、 語音識別、 車輛路線預(yù)測[10]等領(lǐng)域. 在RNN中, 一個節(jié)點(diǎn)在當(dāng)前時刻的輸出不僅受當(dāng)前輸入的影響, 而且還受先前時刻輸出的影響, 歷史決策信息被保留在網(wǎng)絡(luò)的隱藏狀態(tài)中. 從網(wǎng)絡(luò)結(jié)構(gòu)看, RNN非常適于學(xué)習(xí)序列之間的長期依賴關(guān)系, 但由于訓(xùn)練過程中梯度消失和梯度爆炸問題, 傳統(tǒng)RNN無法捕獲序列中的長期依賴關(guān)系.

為解決梯度消失或梯度爆炸問題, 目前已提出了許多改進(jìn)算法, 其中LSTM[11]應(yīng)用最廣泛. LSTM和RNN具有相同的鏈?zhǔn)浇Y(jié)構(gòu), 不同之處在于LSTM在RNN基本單元中增加了輸入門it、 遺忘門ft、 輸出門ot和記憶單元ct. 門控制單元通過打開和關(guān)閉門結(jié)構(gòu)決定存儲什么及何時允許讀、 寫和擦除操作. LSTM單元各部分狀態(tài)更新公式為

其中Wi,Wf,Wo,Wc為權(quán)重矩陣，bi,bf,bo,bc表示偏置向量，tanh和σ為標(biāo)準(zhǔn)激活函數(shù)，xt表示t時刻的輸入向量，ht表示t時刻隱藏層的輸出向量.

1.3 A*算法

A*算法[12]是基于啟發(fā)式的圖搜索算法. A*算法的基本思想是從起始節(jié)點(diǎn)開始, 優(yōu)先擴(kuò)展當(dāng)前最有希望最快到達(dá)目的節(jié)點(diǎn)的節(jié)點(diǎn), 直到得到目的節(jié)點(diǎn)或所有節(jié)點(diǎn)都已擴(kuò)展. A*算法定義了一個評估函數(shù)f(x)=g(x)+h(x)衡量節(jié)點(diǎn)x的“有希望”程度, 其中g(shù)(x)表示從起始節(jié)點(diǎn)到節(jié)點(diǎn)x實(shí)際路徑的代價值,h(x)表示從節(jié)點(diǎn)x到目的節(jié)點(diǎn)最優(yōu)路徑的代價估計(jì)值. 當(dāng)被搜索圖中的節(jié)點(diǎn)數(shù)為n時, A*算法中每次擴(kuò)展節(jié)點(diǎn)的時間復(fù)雜度為O(n2), 最差情形下, 整個A*算法的時間復(fù)雜度為O(n3)[13].

1.4 MCMC采樣技術(shù)

MCMC主要用于對復(fù)雜數(shù)據(jù)采樣, 常用的MCMC采樣技術(shù)是Metropolis-Hastings. Metropolis-Hastings的基本思想是先從樣本空間S中隨機(jī)選擇一個樣本作為初始狀態(tài)s0, 然后根據(jù)下列迭代過程構(gòu)造一個Markov鏈： 在第i次迭代中, 隨機(jī)選擇一個樣本x作為候選采樣點(diǎn), 并根據(jù)下式計(jì)算x的接受概率π, 即x將以概率π被接受為下一個采樣點(diǎn)si，表示為

π=min{1,p(x)/p(si-1)},

(6)

其中p(x)和p(si-1)分別表示x和si-1的出現(xiàn)概率. 當(dāng)Markov鏈的長度設(shè)為a時, 將重復(fù)上述過程a次后獲得的sa作為最終采樣點(diǎn). 接受概率π的定義決定了采樣點(diǎn)的特點(diǎn),π通常根據(jù)實(shí)際應(yīng)用采用不同的定義.

2 2P++算法

2P++算法主要包括以下兩個模塊：

1) 用LSTM模型從軌跡數(shù)據(jù)中獲取用戶的出行偏好；

2) 借助MCMC采樣技術(shù)將用戶的出行偏好引入A*算法中, 在道路網(wǎng)絡(luò)中尋找一條既短又符合用戶出行偏好的路徑. 為方便, 在2P++算法中將利用A*和MCMC搜索最優(yōu)路徑的過程稱為A*_MCMC. 2P++算法的框架結(jié)構(gòu)如圖1所示.

圖1 2P++算法的框架結(jié)構(gòu)Fig.1 Framework of 2P++ algorithm

2.1 基于LSTM的出行偏好提取

在路徑規(guī)劃中, 下一個節(jié)點(diǎn)的選擇不僅取決于當(dāng)前節(jié)點(diǎn), 還取決于先前節(jié)點(diǎn), 即路徑上節(jié)點(diǎn)之間存在長期依賴關(guān)系. 受LSTM的啟發(fā), 本文提出一種基于LSTM的從歷史軌跡數(shù)據(jù)提取偏好的方法.

構(gòu)建該LSTM偏好提取過程如下：

1) 選用HMM地圖匹配算法[14], 將車輛軌跡T={(x1,t1),(x2,t2),…,(xl,tl)}匹配到道路網(wǎng)絡(luò)G中相應(yīng)的路段上, 得到路徑P={v1,v2,…,vt};

2) 將G中的每個節(jié)點(diǎn)均編碼為n維獨(dú)熱編碼, 其中n是G中節(jié)點(diǎn)個數(shù), 并將匹配好的路徑表示為編碼序列;

3) 將與路徑相對應(yīng)的編碼序列輸入到LSTM模型中, 用以訓(xùn)練LSTM模型. 本文將softmax層作為LSTM模型的輸出層, 輸出層中有n個神經(jīng)元, 每個神經(jīng)元對應(yīng)于道路網(wǎng)絡(luò)G中的一個節(jié)點(diǎn), 因此, LSTM模型的輸出是n維向量(Pr(v1),Pr(v2),…,Pr(vn)), 其中Pr(vi)表示節(jié)點(diǎn)vi選為局部路徑P下一個節(jié)點(diǎn)的概率.

訓(xùn)練結(jié)束后, 根據(jù)Pr(x)=Pr(vi+1|vo→vi), 使用LSTM模型預(yù)測每個節(jié)點(diǎn)x作為局部路徑P(v0→vi)下一個節(jié)點(diǎn)vi+1的概率. 在LSTM中, 循環(huán)網(wǎng)絡(luò)中一個循環(huán)單元前向傳播的時間開銷[15]為O(n2), 其中n是輸入的維數(shù), 即本文道路網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù). 對于包含t個節(jié)點(diǎn)(t?n)的局部路徑P, 使用LSTM預(yù)測局部路徑P下一個節(jié)點(diǎn)的時間復(fù)雜度為O(n2).

2.2 基于A*和MCMC的路徑搜索算法

A*_MCMC遵循基本A*算法的框架, 即從當(dāng)前所有待擴(kuò)展節(jié)點(diǎn)中不斷選擇節(jié)點(diǎn)x進(jìn)行擴(kuò)展, 直至找到目的節(jié)點(diǎn)或所有節(jié)點(diǎn)都已擴(kuò)展為止. A*和A*_MCMC的主要區(qū)別在于選擇下一個要擴(kuò)展節(jié)點(diǎn)的方法: A*算法直接選擇具有最小f(x)值的節(jié)點(diǎn)x; 而A*_MCMC使用Metropolis-Hastings根據(jù)接受概率π選擇擴(kuò)展節(jié)點(diǎn)x, 使節(jié)點(diǎn)x不僅有較小的f(x)值, 并且被LSTM預(yù)測作為當(dāng)前路徑下一個節(jié)點(diǎn)的概率值Pr(x)較高.

在Metropolis-Hastings中, 接受概率π決定了采樣點(diǎn)的特征. A*_MCMC接受概率π定義為

(7)

其中，Pr(x)和Pr(si-1)分別表示x和si-1節(jié)點(diǎn)被LSTM預(yù)測作為當(dāng)前路徑下一個節(jié)點(diǎn)的概率，f(x)和f(si-1)分別表示按A*算法計(jì)算的節(jié)點(diǎn)x和si-1的評估函數(shù)值. 當(dāng)節(jié)點(diǎn)x具有更低的f(x)值、 更高的Pr(x)值時,x被選擇作為下一個擴(kuò)展節(jié)點(diǎn)的概率增加.

算法1MCMC(OPEN,a).

輸入： OPEN表, 采樣次數(shù)a;

輸出： 擴(kuò)展節(jié)點(diǎn);

步驟1) if (OPEN表長度為1)

步驟2) return OPEN表中節(jié)點(diǎn);

步驟3) if (OPEN表長度≥2)

步驟4) 選取OPEN表中f值最小節(jié)點(diǎn)s0;

步驟5) fori=1 toa

步驟6) 在OPEN表中隨機(jī)選取節(jié)點(diǎn)x；

步驟7) 根據(jù)式(7)計(jì)算接受概率π；

步驟8) if (π>rand(0,1));

步驟9)si←x;

步驟10) elsesi←si-1;

步驟11) End for;

步驟12) returnsi.

算法1給出了通過Metropolis-Hastings選擇下一個擴(kuò)展節(jié)點(diǎn)的過程, 其中所有待擴(kuò)展節(jié)點(diǎn)均存儲在OPEN表中,a為Markov鏈的長度. 根據(jù)算法1, 時間開銷主要為從OPEN表中選擇f(x)最小的節(jié)點(diǎn)(步驟4))和節(jié)點(diǎn)采樣過程(步驟5)～11)). 在步驟4)中, 最壞情形下, 在OPEN表中找到具有最小f的節(jié)點(diǎn)的時間復(fù)雜度為O(n), 其中n是G中節(jié)點(diǎn)的數(shù)量. 在步驟5)～11)中, 使用LSTM預(yù)測節(jié)點(diǎn)x作為局部路徑PO→x下一個節(jié)點(diǎn)的概率Pr(x)的時間復(fù)雜度為O(n2). 經(jīng)過a次采樣, 計(jì)算接受概率并獲取采樣點(diǎn)的時間復(fù)雜度為O(an2), 通常a?n. 因此, 通過MCMC選擇下一個要擴(kuò)展的節(jié)點(diǎn)的時間開銷為O(n2).

算法2A*_MCMC.

輸入： 道路網(wǎng)絡(luò)G, 起始點(diǎn)O, 目標(biāo)點(diǎn)D,采樣次數(shù)a;

輸出： 路徑PO→D;

步驟1)f(O)←g(O)+h(O);

步驟2) OPEN←{O};

步驟3) CLOSE←{ };

步驟4) while OPEN表不為空do

步驟5)x←MCMC(OPEN,a);

步驟6) OPEN表中刪除x節(jié)點(diǎn)并放入CLOSE表中;

步驟7) for eachxc∈Neighbor (x)/*擴(kuò)展x的鄰接節(jié)點(diǎn)*/

步驟8) if (xc==D)轉(zhuǎn)步驟19);

步驟9) elseg_t←g(x)+cost(x,xc);h_t=h(xc);

步驟10) if (xc?OPEN)

步驟11)g(xc)←g_t;h(xc)←h_t;f(xc)←g_t+h_t;

步驟12) 將xc加入到OPEN表中;

步驟13) 根據(jù)LSTM計(jì)算Pr(xc);

步驟14) if (xc∈OPEN)

步驟15) if (g_t

步驟16)g(xc)←g_t;h(xc)←h_t;f(xc)←g_t+h_t;

步驟17) 根據(jù)LSTM計(jì)算Pr(xc);

步驟18) End for

步驟19) 從D沿父節(jié)點(diǎn)回溯直至O，得到路徑PO→D;

步驟20) returnPO→D.

算法2給出了A*_MCMC的偽代碼. 首先, 計(jì)算起始節(jié)點(diǎn)O的代價值f(O)(步驟1)); 然后, 將O置于OPEN表中, 并將CLOSE表初始化為一個空列表(步驟2),3)). 步驟4)～18)是路徑搜索的迭代過程, 整個搜索過程分為兩部分: 第一部分根據(jù)算法1從OPEN表中利用MCMC采樣選擇下一個擴(kuò)展節(jié)點(diǎn)x(步驟5),6)); 第二部分是擴(kuò)展節(jié)點(diǎn)x, 即生成x的鄰接節(jié)點(diǎn)xc(步驟7)～18)). 根據(jù)算法1, 通過MCMC選擇下一個擴(kuò)展節(jié)點(diǎn)的時間開銷為O(n2). 對于x的鄰接節(jié)點(diǎn)xc, 生成xc的時間開銷是OPEN表的遍歷過程(步驟10)～17)). A*算法每次擴(kuò)展節(jié)點(diǎn)的時間復(fù)雜度為O(n2), 則最差情形下, 擴(kuò)展x節(jié)點(diǎn)的時間復(fù)雜度為O(n2). 最多可進(jìn)行n次節(jié)點(diǎn)擴(kuò)展, 因此, 整個A*_MCMC的時間復(fù)雜度為O(n3), 與A*算法具有相同的時間復(fù)雜度.

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

3.1 基本數(shù)據(jù)

為檢驗(yàn)本文算法的有效性, 下面通過實(shí)驗(yàn)將2P++算法與L2R算法[8](經(jīng)驗(yàn)路徑算法)和基于A*算法的最短路徑規(guī)劃算法(簡稱A*)進(jìn)行比較.

實(shí)驗(yàn)中使用的數(shù)據(jù)主要為北京市某區(qū)域的電子地圖及該地區(qū)2012-04的23 800條出租車軌跡. 該道路網(wǎng)絡(luò)包括302個節(jié)點(diǎn)和586條邊. 在不同時間段, 城市道路網(wǎng)絡(luò)中的交通狀況不同, 駕駛員將根據(jù)其駕駛經(jīng)驗(yàn)相應(yīng)地調(diào)整出行路線. 因此, 規(guī)劃路徑時需考慮時間這一重要因素. 根據(jù)北京市道路交通的特點(diǎn), 將一天分為高峰時間段和非高峰時間段. 高峰時間段包括7:00—10:00和16：00—20:00, 其余時間為非高峰時間段. 歷史軌跡數(shù)據(jù)分為兩部分： 一部分包括在高峰時間段出現(xiàn)的9 500條軌跡； 另一部分包括在非高峰時間段出現(xiàn)的14 300條軌跡. 實(shí)驗(yàn)中分別對比在高峰和非高峰時間段3種算法的性能.

為測試算法在歷史軌跡密集和稀疏情形下的性能, 本文根據(jù)車輛軌跡分布先將路網(wǎng)分為軌跡密集區(qū)域和軌跡稀疏區(qū)域, 再分別從軌跡密集和稀疏區(qū)域中各選擇10對起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)對(簡稱OD對). 對來自軌跡密集區(qū)域的10個OD對按它們之間距離從短到長的順序依次進(jìn)行1～10編號, 對來自軌跡稀疏區(qū)域的另外10個OD對按距離從短到長的順序依次進(jìn)行11～20編號. 實(shí)驗(yàn)中, 將20個OD對作為3種路徑規(guī)劃算法的輸入, 然后分別比較每種算法對每個OD對返回路徑的準(zhǔn)確度、 長度和行程時間.

3.2 路徑準(zhǔn)確度對比

規(guī)劃路徑P的準(zhǔn)確度定義為P與真實(shí)路徑P*的相似度. 相似度越高, 路徑規(guī)劃算法的準(zhǔn)確性越好. 用文獻(xiàn)[16]中定義的路徑相似度函數(shù)pSim(P,P*)計(jì)算規(guī)劃路徑P與真實(shí)路徑P*之間的相似度, 計(jì)算公式為

(8)

3種算法針對20個OD對得到的路徑準(zhǔn)確度如圖2所示, 其中: (A)為算法規(guī)劃高峰時間段路徑的準(zhǔn)確度； (B)為算法規(guī)劃非高峰時間段的準(zhǔn)確度.

圖2 3種算法在不同時間段的準(zhǔn)確度對比Fig.2 Comparison of accuracy of three algorithms in different time periods

由圖2可見: 1) 無論是高峰時間段還是非高峰時間段, 2P++算法在軌跡密集區(qū)域(前10個OD對)與軌跡稀疏區(qū)域(后10個OD對)的準(zhǔn)確度基本相同, A*算法結(jié)果類似. 表明A*和2P++算法相對穩(wěn)定, 不易受歷史軌跡數(shù)據(jù)分布的影響. 2) L2R算法在軌跡密集區(qū)域的準(zhǔn)確度明顯高于其在軌跡稀疏區(qū)域的準(zhǔn)確度, 表明L2R算法高度依賴于歷史軌跡的分布, 與L2R算法的本質(zhì)一致, 即當(dāng)一對節(jié)點(diǎn)之間存在軌跡時, 返回最流行軌跡中包含的路徑. 此時, L2R算法獲得的路徑必然與流行路徑最相似. 因此, L2R具有最高的精度. 當(dāng)節(jié)點(diǎn)之間的一些軌跡不是流行軌跡或它們之間沒有軌跡時, L2R通過偏好遷移學(xué)習(xí)方法推斷它們之間的路徑, 并與它們之間的部分最短路徑進(jìn)行拼接, 從而降低了L2R算法的在軌跡稀疏區(qū)域的準(zhǔn)確性. 3) 在整體上, 無論是高峰時段還是非高峰時段, 對于所有20個OD對, L2R和2P++算法的準(zhǔn)確度均高于A*算法, 表明從歷史軌跡中提取的駕駛經(jīng)驗(yàn)有效地指導(dǎo)了路徑規(guī)劃； 對于來自軌跡密集區(qū)域的節(jié)點(diǎn), L2R算法比2P++算法更準(zhǔn)確； 對于來自軌跡稀疏區(qū)域的節(jié)點(diǎn), 2P++算法比L2R算法更準(zhǔn)確.

3.3 路徑長度對比

表1列出了A*,L2R和2P++ 3種算法針對20個OD對在高峰時間段和非高峰時間段返回路徑的平均長度.

表1 3種算法在不同時段的平均路徑長度(m)Table 1 Average path lengths (m) of three algorithms in different time periods

由表1可見： 1) 由于未考慮歷史經(jīng)驗(yàn)信息, 所以A*算法在高峰時間段和非高峰時間段的路徑距離相同; L2R和2P++算法在高峰時段規(guī)劃的路徑比非高峰時段更長, 與人們傾向于在高峰時間段選擇繞路行駛以避免道路擁堵的事實(shí)相符. 2) 相對于2P++和L2R算法, A*算法的路徑最短, L2R算法在高峰時段和非高峰時段計(jì)算的路徑長度相對于A*算法計(jì)算的路徑長度分別延長了12%和7.6%, 2P++算法在高峰和非高峰時段計(jì)算的路徑長度相對于A*算法計(jì)算的路徑長度分別延長了7.4%和4.1%. 這是由于L2R和2P++算法通常選擇經(jīng)驗(yàn)路段, 因此路徑較長. 但2P++算法規(guī)劃出的路徑比L2R算法更短, 與L2R算法計(jì)算的路徑相比, 2P++算法在高峰時間段和非高峰時間段的路徑長度分別縮短了4.2%和3.4%.

3.4 行程時間對比

3種算法對20個OD對規(guī)劃路徑的行程時間如圖3所示, 其中: (A)為3種算法在高峰時間段規(guī)劃路徑的行程時間； (B)為3種算法在非高峰時間段規(guī)劃路徑的行程時間. 路徑的行程時間越短, 算法越好.

圖3 3種算法在不同時段的路徑行程時間對比Fig.3 Comparison of route travel time of three algorithms in different time periods

由圖3可見： 1) 無論是高峰時間段還是非高峰時間段, 3種算法規(guī)劃路徑的行程時間均隨起始點(diǎn)和目的點(diǎn)之間距離的增加而增加. 2) 對于非高峰時間段(圖3(B)), 無論是軌跡密集區(qū)域的節(jié)點(diǎn)還是軌跡稀疏區(qū)域的節(jié)點(diǎn), 在起始點(diǎn)與目的點(diǎn)距離較短時(OD對1～5), A*算法規(guī)劃路徑的行程時間少于L2R算法和2P++算法. 但隨著路徑長度的增加, A*算法趨于花費(fèi)更多的行程時間, 這是由于在非高峰時段, 道路上車輛較少且相對暢通, 當(dāng)行駛距離較短時行程時間更具優(yōu)勢. 3) 對于高峰時間段(圖3(A)), 無論是軌跡密集區(qū)域節(jié)點(diǎn)還是軌跡稀疏區(qū)域節(jié)點(diǎn), 除編號為1,2,11的OD對外, 在其他17個OD對上, L2R和2P++算法的行程時間均遠(yuǎn)優(yōu)于A*算法, 2P++與L2R算法返回路徑的行程時間相近.

為更準(zhǔn)確地展現(xiàn)3種算法得到規(guī)劃路徑的行程時間, 表2列出了3種算法得到20條規(guī)劃路徑的總行程時間. 由表2可見, 無論在高峰時段還是非高峰時段, 2P++和L2R算法均比A*算法好, 且2P++算法略優(yōu)于L2R算法. 比較表1和表2可見, 最短路徑不一定具有更快的行程時間, 這主要是因?yàn)樵谌粘３鲂袝r, 人們傾向于選擇道路條件更快捷的路線, 而不是最短的路徑.

表2 3種算法在不同時段的總行程時間(min)Table 2 Total travel time (min) of three algorithms in different time periods

上述結(jié)果表明： 在軌跡數(shù)據(jù)稀疏的區(qū)域, 2P++算法的路徑準(zhǔn)確度優(yōu)于L2R算法和A*算法； 在軌跡數(shù)據(jù)密集的區(qū)域, 2P++算法的路徑準(zhǔn)確度低于L2R算法, 高于A*算法; 對于平均路徑長度, 無論在高峰時段還是非高峰時段, 2P++算法性能均優(yōu)于L2R算法, 而低于A*算法; 對于總行程時間, 2P++算法均優(yōu)于A*和L2R算法. 因此, 2P++算法更穩(wěn)定, 并且其規(guī)劃路徑具有較高的準(zhǔn)確度、 較短的行駛距離和行程時間.

綜上所述, 針對現(xiàn)有路徑規(guī)劃方法不能同時考慮路徑長度和用戶偏好的問題, 本文將基于軌跡的路徑規(guī)劃方法和基于最短路徑的路徑規(guī)劃方法相結(jié)合, 提出了一種新路徑規(guī)劃方法——2P++算法. 2P++算法首先使用LSTM模型訓(xùn)練軌跡數(shù)據(jù)并獲取用戶的出行偏好, 然后使用MCMC采樣技術(shù)將獲取的出行偏好加入到A*算法的搜索過程中, 使規(guī)劃的路線能在距離較短的基礎(chǔ)上更符合用戶的出行偏好. 理論分析表明, 2P++算法與A*算法的時間復(fù)雜度相同. 實(shí)驗(yàn)結(jié)果表明, 2P++算法更穩(wěn)定, 且其規(guī)劃的路徑具有較高的準(zhǔn)確度、 較短的行駛距離和行程時間.