李建伏, 王思博, 宋國平

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

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

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

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

1 預備知識

1.1 基本定義

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

1.2 長短期記憶模型

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

為解決梯度消失或梯度爆炸問題, 目前已提出了許多改進算法, 其中LSTM[11]應用最廣泛. LSTM和RNN具有相同的鏈式結(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和σ為標準激活函數(shù)，xt表示t時刻的輸入向量，ht表示t時刻隱藏層的輸出向量.

1.3 A*算法

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

1.4 MCMC采樣技術(shù)

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

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

(6)

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

2 2P++算法

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

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

2) 借助MCMC采樣技術(shù)將用戶的出行偏好引入A*算法中, 在道路網(wǎng)絡中尋找一條既短又符合用戶出行偏好的路徑. 為方便, 在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é)點的選擇不僅取決于當前節(jié)點, 還取決于先前節(jié)點, 即路徑上節(jié)點之間存在長期依賴關(guān)系. 受LSTM的啟發(fā), 本文提出一種基于LSTM的從歷史軌跡數(shù)據(jù)提取偏好的方法.

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

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

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

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

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

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

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

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

(7)

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

算法1MCMC(OPEN,a).

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

輸出： 擴展節(jié)點;

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

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

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

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

步驟5) fori=1 toa

步驟6) 在OPEN表中隨機選取節(jié)點x；

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

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

步驟9)si←x;

步驟10) elsesi←si-1;

步驟11) End for;

步驟12) returnsi.

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

算法2A*_MCMC.

輸入： 道路網(wǎng)絡G, 起始點O, 目標點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é)點并放入CLOSE表中;

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

步驟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計算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計算Pr(xc);

步驟18) End for

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

步驟20) returnPO→D.

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

3 實驗分析

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

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

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

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

3.2 路徑準確度對比

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

(8)

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

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

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

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)驗信息, 所以A*算法在高峰時間段和非高峰時間段的路徑距離相同; L2R和2P++算法在高峰時段規(guī)劃的路徑比非高峰時段更長, 與人們傾向于在高峰時間段選擇繞路行駛以避免道路擁堵的事實相符. 2) 相對于2P++和L2R算法, A*算法的路徑最短, L2R算法在高峰時段和非高峰時段計算的路徑長度相對于A*算法計算的路徑長度分別延長了12%和7.6%, 2P++算法在高峰和非高峰時段計算的路徑長度相對于A*算法計算的路徑長度分別延長了7.4%和4.1%. 這是由于L2R和2P++算法通常選擇經(jīng)驗路段, 因此路徑較長. 但2P++算法規(guī)劃出的路徑比L2R算法更短, 與L2R算法計算的路徑相比, 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ī)劃路徑的行程時間均隨起始點和目的點之間距離的增加而增加. 2) 對于非高峰時間段(圖3(B)), 無論是軌跡密集區(qū)域的節(jié)點還是軌跡稀疏區(qū)域的節(jié)點, 在起始點與目的點距離較短時(OD對1～5), A*算法規(guī)劃路徑的行程時間少于L2R算法和2P++算法. 但隨著路徑長度的增加, A*算法趨于花費更多的行程時間, 這是由于在非高峰時段, 道路上車輛較少且相對暢通, 當行駛距離較短時行程時間更具優(yōu)勢. 3) 對于高峰時間段(圖3(A)), 無論是軌跡密集區(qū)域節(jié)點還是軌跡稀疏區(qū)域節(jié)點, 除編號為1,2,11的OD對外, 在其他17個OD對上, L2R和2P++算法的行程時間均遠優(yōu)于A*算法, 2P++與L2R算法返回路徑的行程時間相近.

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

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

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

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