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

李建伏, 王思博, 宋國(guó)平

(中國(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)用中, 路徑長(zhǎng)度不是人們選擇出行路徑的唯一標(biāo)準(zhǔn). 為使規(guī)劃的路徑能滿(mǎn)足用戶(hù)的實(shí)際需求, 路徑規(guī)劃被進(jìn)一步形式化為多目標(biāo)最短路徑問(wèn)題[1]或多約束最短路徑問(wèn)題[2-3], 即將用戶(hù)的出行偏好建模為多個(gè)目標(biāo)或約束. 但用戶(hù)的出行偏好受多種因素影響, 而這些因素如何影響用戶(hù)偏好未知, 甚至用戶(hù)自己也無(wú)法準(zhǔn)確地表達(dá)其出行偏好. 因此, 不能準(zhǔn)確地描述用戶(hù)出行偏好已成為限制多目標(biāo)路徑規(guī)劃或多約束路徑規(guī)劃發(fā)展的瓶頸.

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

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

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

1.1 基本定義

在路徑規(guī)劃中, 道路網(wǎng)絡(luò)通常表示為有向圖G=(V,E), 其中:V={v1,v2,…,vn}表示n個(gè)節(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)序列, 其中兩個(gè)相鄰節(jié)點(diǎn)通過(guò)一條邊連接. 路徑P的長(zhǎng)度記為len(P). 軌跡T是移動(dòng)對(duì)象的行進(jìn)過(guò)程在地理空間中生成的GPS序列, 通常由一系列按時(shí)間順序排列的位置點(diǎn)表示, 即T={(x1,t1),(x2,t2),…,(xl,tl)}, 其中xj(1≤j≤l)是移動(dòng)對(duì)象在tj(1≤j≤l)時(shí)刻的位置.

1.2 長(zhǎng)短期記憶模型

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

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

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

1.3 A*算法

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

1.4 MCMC采樣技術(shù)

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

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

(6)

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

2 2P++算法

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

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

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

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

2.1 基于LSTM的出行偏好提取

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

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

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

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

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

訓(xùn)練結(jié)束后, 根據(jù)Pr(x)=Pr(vi+1|vo→vi), 使用LSTM模型預(yù)測(cè)每個(gè)節(jié)點(diǎn)x作為局部路徑P(v0→vi)下一個(gè)節(jié)點(diǎn)vi+1的概率. 在LSTM中, 循環(huán)網(wǎng)絡(luò)中一個(gè)循環(huán)單元前向傳播的時(shí)間開(kāi)銷(xiāo)[15]為O(n2), 其中n是輸入的維數(shù), 即本文道路網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù). 對(duì)于包含t個(gè)節(jié)點(diǎn)(t?n)的局部路徑P, 使用LSTM預(yù)測(cè)局部路徑P下一個(gè)節(jié)點(diǎn)的時(shí)間復(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ū)別在于選擇下一個(gè)要擴(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ù)測(cè)作為當(dāng)前路徑下一個(gè)節(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ù)測(cè)作為當(dāng)前路徑下一個(gè)節(jié)點(diǎn)的概率，f(x)和f(si-1)分別表示按A*算法計(jì)算的節(jié)點(diǎn)x和si-1的評(píng)估函數(shù)值. 當(dāng)節(jié)點(diǎn)x具有更低的f(x)值、 更高的Pr(x)值時(shí),x被選擇作為下一個(gè)擴(kuò)展節(jié)點(diǎn)的概率增加.

算法1MCMC(OPEN,a).

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

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

步驟1) if (OPEN表長(zhǎng)度為1)

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

步驟3) if (OPEN表長(zhǎng)度≥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給出了通過(guò)Metropolis-Hastings選擇下一個(gè)擴(kuò)展節(jié)點(diǎn)的過(guò)程, 其中所有待擴(kuò)展節(jié)點(diǎn)均存儲(chǔ)在OPEN表中,a為Markov鏈的長(zhǎng)度. 根據(jù)算法1, 時(shí)間開(kāi)銷(xiāo)主要為從OPEN表中選擇f(x)最小的節(jié)點(diǎn)(步驟4))和節(jié)點(diǎn)采樣過(guò)程(步驟5)～11)). 在步驟4)中, 最壞情形下, 在OPEN表中找到具有最小f的節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n), 其中n是G中節(jié)點(diǎn)的數(shù)量. 在步驟5)～11)中, 使用LSTM預(yù)測(cè)節(jié)點(diǎn)x作為局部路徑PO→x下一個(gè)節(jié)點(diǎn)的概率Pr(x)的時(shí)間復(fù)雜度為O(n2). 經(jīng)過(guò)a次采樣, 計(jì)算接受概率并獲取采樣點(diǎn)的時(shí)間復(fù)雜度為O(an2), 通常a?n. 因此, 通過(guò)MCMC選擇下一個(gè)要擴(kuò)展的節(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo)為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的代價(jià)值f(O)(步驟1)); 然后, 將O置于OPEN表中, 并將CLOSE表初始化為一個(gè)空列表(步驟2),3)). 步驟4)～18)是路徑搜索的迭代過(guò)程, 整個(gè)搜索過(guò)程分為兩部分: 第一部分根據(jù)算法1從OPEN表中利用MCMC采樣選擇下一個(gè)擴(kuò)展節(jié)點(diǎn)x(步驟5),6)); 第二部分是擴(kuò)展節(jié)點(diǎn)x, 即生成x的鄰接節(jié)點(diǎn)xc(步驟7)～18)). 根據(jù)算法1, 通過(guò)MCMC選擇下一個(gè)擴(kuò)展節(jié)點(diǎn)的時(shí)間開(kāi)銷(xiāo)為O(n2). 對(duì)于x的鄰接節(jié)點(diǎn)xc, 生成xc的時(shí)間開(kāi)銷(xiāo)是OPEN表的遍歷過(guò)程(步驟10)～17)). A*算法每次擴(kuò)展節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n2), 則最差情形下, 擴(kuò)展x節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n2). 最多可進(jìn)行n次節(jié)點(diǎn)擴(kuò)展, 因此, 整個(gè)A*_MCMC的時(shí)間復(fù)雜度為O(n3), 與A*算法具有相同的時(shí)間復(fù)雜度.

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

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

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

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

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

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

規(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種算法針對(duì)20個(gè)OD對(duì)得到的路徑準(zhǔn)確度如圖2所示, 其中: (A)為算法規(guī)劃高峰時(shí)間段路徑的準(zhǔn)確度； (B)為算法規(guī)劃非高峰時(shí)間段的準(zhǔn)確度.

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

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

3.3 路徑長(zhǎng)度對(duì)比

表1列出了A*,L2R和2P++ 3種算法針對(duì)20個(gè)OD對(duì)在高峰時(shí)間段和非高峰時(shí)間段返回路徑的平均長(zhǎng)度.

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

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

3.4 行程時(shí)間對(duì)比

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

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

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

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

表2 3種算法在不同時(shí)段的總行程時(shí)間(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*算法; 對(duì)于平均路徑長(zhǎng)度, 無(wú)論在高峰時(shí)段還是非高峰時(shí)段, 2P++算法性能均優(yōu)于L2R算法, 而低于A*算法; 對(duì)于總行程時(shí)間, 2P++算法均優(yōu)于A*和L2R算法. 因此, 2P++算法更穩(wěn)定, 并且其規(guī)劃路徑具有較高的準(zhǔn)確度、 較短的行駛距離和行程時(shí)間.

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