汪陳晨，周茂林，楊 芹，牟倍民，吳慈恒，金永霞*

（1. 河海大學物聯(lián)網(wǎng)工程學院，常州 213000；2. 河海大學商學院，常州 213000）

0 引言

由于騎行方式易受環(huán)境、交通狀況、道路設施等因素影響，騎行者在選擇出行路徑時越來越關(guān)注舒適度，為出行者提供舒適安全的騎行路徑推薦方案成為城市交通建設的迫切需要［1］。本文開發(fā)一套基于舒適度評價的騎行路徑推薦系統(tǒng)，綜合道路客觀情況與騎行者主觀體驗構(gòu)建科學的舒適度評價體系，對各路段騎行舒適度進行量化，采用多級迪杰斯特拉算法實現(xiàn)路徑推薦并可視化呈現(xiàn)給用戶，為騎行者出行路徑規(guī)劃提供參考。

1 系統(tǒng)總體設計

1.1 系統(tǒng)架構(gòu)

基于Ubuntu22.04 安裝開源路由器OSRM，結(jié)合云計算技術(shù)開發(fā)與地理信息數(shù)據(jù)庫，實現(xiàn)數(shù)據(jù)云存儲、云數(shù)據(jù)定期更新，提供舒適、高效、數(shù)字化的騎行舒適路線規(guī)劃模式。

系統(tǒng)通過終端設備智能化采集戶外騎行軌跡數(shù)據(jù)，實現(xiàn)位置經(jīng)緯度定位、軌跡數(shù)據(jù)采集、三軸速度與加速度實時獲取和計算等功能，存儲數(shù)據(jù)至云端；采用阿里云服務器搭建路徑推薦服務平臺，實現(xiàn)記錄軌跡數(shù)據(jù)、推薦舒適路徑等功能，支持存儲地圖路網(wǎng)數(shù)據(jù)、用戶騎行數(shù)據(jù)；用戶端顯示當前定位，并根據(jù)起止點推薦舒適路徑。

系統(tǒng)整體框架如圖1 所示，包含六個層次：運行環(huán)境、數(shù)據(jù)庫、數(shù)據(jù)層、業(yè)務層、傳輸層和終端接入層。本系統(tǒng)部署在阿里云服務器，使用PostgreSQL 存儲地圖數(shù)據(jù)。PostgreSQL［2］是一個功能強大、源代碼開放的客戶/服務器關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，在PostgreSQL 中構(gòu)建地理信息數(shù)據(jù)庫（GIS database）和地理編碼數(shù)據(jù)庫（Nomination database），其中Nomination database主要用于搜索功能；數(shù)據(jù)層主要實現(xiàn)對路網(wǎng)數(shù)據(jù)、軌跡數(shù)據(jù)的處理，需要增加路段或路網(wǎng)發(fā)生改變時，及時進行數(shù)據(jù)更新；業(yè)務層提供用戶位置的實時定位、騎行數(shù)據(jù)分析、舒適路徑推薦、顯示路徑詳細信息、設備管理等功能；通過全球定位系統(tǒng)和公網(wǎng)通信實現(xiàn)數(shù)據(jù)傳輸，為終端用戶提供城市交通管理、騎行質(zhì)量調(diào)查以及路線規(guī)劃服務。

圖1 系統(tǒng)架構(gòu)

1.2 路徑推薦系統(tǒng)的功能模塊

本系統(tǒng)主要研究利用GPS 定位實現(xiàn)對用戶的位置信息服務。系統(tǒng)的功能設計如圖2所示。

圖2 系統(tǒng)功能設計

（1）路網(wǎng)數(shù)據(jù)預處理。本系統(tǒng)采用的原始路網(wǎng)數(shù)據(jù)來自開源地圖網(wǎng)站OpenStreetMap［3］。為了實現(xiàn)路段分割，首先，從獲取到的路網(wǎng)地圖中篩選出與騎行道路相關(guān)的Ways 元素；其次，對篩選出的Ways 元素在交點處進行分割，使其具有向左右行駛的拓撲結(jié)構(gòu)。

（2）軌跡與路網(wǎng)匹配。GPS 點采樣過程存在誤差導致采樣點發(fā)生位置的偏移［4］，從而該軌跡點所對應的騎行數(shù)據(jù)不能對應到正確的路段上，這對我們衡量路段的舒適度造成一定的干擾。因此本系統(tǒng)通過路網(wǎng)匹配算法對其進行糾偏［5］，使軌跡點對應到正確的路段上。

（3）構(gòu)建舒適度評價指標體系。在云平臺技術(shù)和交通大數(shù)據(jù)廣泛應用的條件下，騎行軌跡數(shù)據(jù)為舒適度評價提供了數(shù)據(jù)依據(jù)，同時，道路設施、環(huán)境條件等客觀因素對舒適度也有較大影響，因此將騎行軌跡數(shù)據(jù)與影響騎行的客觀因素相結(jié)合探索騎行質(zhì)量分析與評價方法。同時收集300份調(diào)查問卷，使用主成分分析法計算每個指標的影響權(quán)重。

（4）路徑推薦。根據(jù)熵權(quán)法計算每條路段最終的舒適度值，將其賦值到處理過的路網(wǎng)地圖上，采用多級迪杰斯特拉算法進行舒適路徑的推薦。

2 騎行舒適度評價體系構(gòu)建

2.1 評價指標的選取

選擇合適的舒適度評價方法是評價道路騎行質(zhì)量的關(guān)鍵，騎行路段的舒適度與道路基建、交通情況、自然環(huán)境相關(guān)，需要綜合考慮騎行者的感知水平和道路設施、環(huán)境條件等客觀因素。本文選取了通過路口等待時間、并行機動車流量、道路遮蔭率、道路幾何線性、車道隔離欄設置和道路平整程度作為評價舒適度的指標。

指標具體含義解釋如下：

（1）過街等待時間：指騎行經(jīng)過“十”字路口或“丁”字路口時等待交通信號燈的平均時長；

（2）并行機動車流量：指與非機動車道相鄰的機動車道上機動車的流量；

（3）遮蔭率：指正午時分非機動車道兩側(cè)喬木投下的陰影面積占非機動車道面積的比例；

（4）道路幾何線性：指道路是否筆直以及轉(zhuǎn)彎情況；

（5）車道隔離欄設置：指非機動車道與機動車道設置隔離欄情況；

（6）道路平整度：指騎行車道是否平整，即是否存在大面積的凹陷、隆起或局部的坑洼。

2.2 指標的量化方式

在選取的六個指標中，前五個為道路客觀實際情況，利用實地考察和AR 實景地圖觀察等方式獲取路段實際情況，并對其進行分級量化。第六個指標，道路平整度的計算是通過收集騎行者的騎行數(shù)據(jù)，將軌跡點匹配至路網(wǎng)上，計算每條路段對應的垂直加速度的方差CovRt，計算如公式（1）：

其中：ai表示路段上各點加速度，a表示路段平均加速度，n表示路段軌跡點數(shù)量。路段的方差越大表明該路段垂直加速度越不穩(wěn)定，道路越顛簸，道路平整度越差；路段的方差越小則說明該道路平整度越好。具體的量化方式見表1，量化值5 表明舒適度最高，量化值1 表明舒適度最低。

表1 舒適度指標分級量化標準

為了數(shù)據(jù)計算的方便和去除量綱影響，對前5 個指標采用公式（2）進行正向化處理，對最后一項指標采用公式（3）進行逆向化處理。

2.3 基于主成分分析法的權(quán)重計算

設計舒適度指標影響程度打分問卷，分別將上述六個指標設置1～9 分的影響程度，1 分為完全無關(guān)，9 分為極度相關(guān)。通過“問卷星”平臺收集到約300份問卷量后，利用探索性因子分析法和驗證性因子分析法統(tǒng)計問卷結(jié)果，并用主成分分析法計算各項指標的權(quán)重。主成分分析法（principal component analysis，PCA）是一種統(tǒng)計方法，將原來變量重新組合成一組新的相互無關(guān)的綜合變量，同時根據(jù)實際需要從中取出幾個較少的綜合變量盡可能多地反映原來變量的信息。設a個需要分析的目標與b個指標構(gòu)成的矩陣Xa×b為樣本矩陣，主成分分析法計算步驟如下。

Step 1.對樣本矩陣進行標準化處理，Zij為對Xij進行標準化處理后的指標，如公式（4）所示：

其中：μj和σij的計算方式如公式（5）所示：

Step 2. 計算評價指標的參數(shù)矩陣、指標矩陣T特征值的方差的貢獻比率和貢獻比率總和。如果貢獻比率總和高于85%，那么確定主要參數(shù)值符合計算獲得的參數(shù)矩陣。

Step 3.參數(shù)旋轉(zhuǎn)，計算主要參數(shù)權(quán)值，計算過程如公式（6）所示，采用線性回歸方程對主參數(shù)進行回歸計算。

Step 4.計算評價目標的總權(quán)值，如公式（7）所示：

權(quán)重計算結(jié)果見表2。

表2 舒適度指標權(quán)重計算結(jié)果

采用熵權(quán)法將計算出的權(quán)重與各路段的指標值計算得到最終的舒適度值，并賦值給分割好的路網(wǎng)地圖。

3 路網(wǎng)預處理及路網(wǎng)匹配

3.1 路網(wǎng)地圖預處理

OSM 本身帶有相應的API 接口供開發(fā)者使用，將OSM 格式地圖下載到本地，使用ArcMap地圖軟件對其進行分割，然后進行軌跡和路網(wǎng)匹配。

從OSM 項目獲取到的道路數(shù)據(jù)采用了基于XML的拓撲數(shù)據(jù)結(jié)構(gòu)，包含三種基本數(shù)據(jù)類型，即點（Nodes）、路（Ways）和關(guān)系（Relations）。其中Nodes 標識了空間中點的位置；Ways 標識了道路；Relations 標識了元素間的關(guān)系。本系統(tǒng)篩選出與騎行道路相關(guān)的Ways 元素，在道路交點處進行路段的分割，使其具有拓撲結(jié)構(gòu)，在交點處能夠向左向右行駛，更加接近真實情況。圖3為道路分割示意圖。

圖3 道路分割示意圖

3.2 軌跡數(shù)據(jù)與路網(wǎng)地圖匹配

本系統(tǒng)使用隱馬爾可夫（HMM）模型進行軌跡和路網(wǎng)的匹配。HMM 模型是關(guān)于時序的概率模型，描述由一個隱藏的馬爾可夫鏈隨機生成不可觀測的狀態(tài)隨機序列，再由各個狀態(tài)生成一個觀測值而產(chǎn)生觀測隨機序列的過程。將該算法應用在路網(wǎng)匹配領(lǐng)域，可以將帶有誤差的自行車騎行GPS 軌跡點成功匹配到電子路網(wǎng)地圖的相應位置，形成連續(xù)的行車軌跡。

該模型可以用5 個元素來描述，包括2 個狀態(tài)集合和3 個概率矩陣，分別為隱含狀態(tài)S、可觀測狀態(tài)O、狀態(tài)轉(zhuǎn)移概率矩陣A、觀測狀態(tài)概率矩陣B和初始狀態(tài)概率矩陣π［6］。

在路網(wǎng)匹配過程中，首先根據(jù)待匹配GPS軌跡點的位置在路網(wǎng)地圖中找出可能該點正在行駛的路段集合，即候選路段集合；然后根據(jù)匹配算法計算各候選點將各候選路段作為匹配路徑的概率，修正沒有定位在實際道路上的GPS 定位點；最后使用維特比算法，根據(jù)觀測概率模型和狀態(tài)轉(zhuǎn)移概率模型計算出概率最大的路段，求解出最優(yōu)路徑。HMM 路網(wǎng)匹配算法如下：

對軌跡點的處理結(jié)果如圖4 所示。圖4（a）中將軌跡點數(shù)據(jù)直接映射在路網(wǎng)上，可見軌跡點分布不均勻并且有部分缺失，對其進行線性插值處理后如圖4（b）所示，軌跡點分布更加密集，將提高后續(xù)匹配算法的準確率；HMM 算法匹配結(jié)果如圖4（c）所示，軌跡點在匹配后精準投影到路網(wǎng)上。

圖4 騎行軌跡點處理結(jié)果

利用路網(wǎng)匹配算法對軌跡點進行糾偏后，可以通過軌跡點對應的垂直加速度值計算出該軌跡點所在路段的垂直加速度方差。

4 基于帶權(quán)路網(wǎng)推薦舒適路徑

4.1 舒適度賦值路網(wǎng)地圖

根據(jù)表2計算得到的權(quán)重結(jié)果，將各指標按照對應權(quán)重加權(quán)求和，得到舒適度的綜合評分Z，如公式（8）所示：

將計算得到的舒適度值劃分為四個等級：不舒適（0～0.25）、舒適（0.25～0.5）、比較舒適（0.5～0.75）、非常舒適（0.75～1）。其中部分路段賦值結(jié)果如圖5所示。

圖5 舒適度指標賦值路網(wǎng)

4.2 基于多級迪杰斯特拉算法推薦路徑

多級迪杰斯特拉算法（Multi-level Dijkstra，MLD）是一種多層次覆蓋圖的路徑規(guī)劃算法，可以快速處理不同的度量，用以解決賦權(quán)圖的單源最短路徑問題［7］。MLD 算法在CRP 算法基礎上發(fā)展而來，由Delling 等［8］進行優(yōu)化，例如改進局部性、對搜索圖進行剪枝、多源執(zhí)行等，它可以使用用戶定制的度量，也可以動態(tài)更新路況。

MLD算法的實現(xiàn)可以分為以下三個步驟：

（1）與度量無關(guān)的預處理。為了減小圖的規(guī)模，加速搜索過程，將圖G劃分為不同的層次，每個層次包含一些頂點V和邊W。分層的公式如公式（9）所示：

其中：Gi表示第i層的圖，Pi表示第i層的劃分方法。分層的方法有多種，具體來說，就是在每個層次上將一些相鄰的頂點和邊合成一個新的頂點和邊，從而得到一個更小的圖。層次越高，包含的頂點和邊越少，越能反映圖的全局結(jié)構(gòu)。將分層的過程重復多次以后，將得到一個足夠小的圖。分層后的圖之間存在一種映射關(guān)系，可以在不同層次上進行搜索和優(yōu)化。圖6（a）是原始單元格圖，預處理完成后，每個子圖中的每兩個邊界節(jié)點之間的最短路徑形成團集，如圖6（b）所示，團集將以矩陣的方式存儲。

圖6 原始單元格圖、團集和骨架圖

（2）依賴度量的自定義。在劃分好的每個層次上，為每個頂點計算該頂點到其他頂點舒適度值、最舒適路徑樹等輔助信息，這些信息可以在查詢時快速地訪問和利用，減少時間和空間開銷。將舒適度值作為頂點之間的權(quán)重，計算每個頂點到目標頂點的最舒適路徑的過程如公式（10）所示：

其中ComfotI(v，w)表示第I層上頂點v和w之間的最大舒適度值；ComfotI(v,I)表示第I層上頂點v和地標I之間的最大舒適度值；ComfotI(I,w)表示第I層上地標I和頂點w之間的最大舒適度值。每個子圖中的每個邊界結(jié)點到其他邊界結(jié)點的最舒適路徑形成一個并集，構(gòu)成骨架圖，如圖6（c）所示，骨架圖可以為查詢縮減搜索空間和時間。

（3）查詢路徑。利用預處理分層和自定義處理后得到的信息，對給定的源點和目標點采用雙向的Dijkstra 算法在骨架圖中進行查詢。從最高層開始，在每個層次，從源點和目標點分別開始搜索，利用地標和三角不等式估計任意兩個頂點之間的舒適度值，選擇舒適度值最大進行擴展，當兩個搜索方向相遇時，即為一條候選路徑。然后在下一個層次上繼續(xù)搜索，直至找到最優(yōu)的路徑。

MLD算法具體實現(xiàn)流程如下：

輸入：一個圖G，一個起點s，一個終點t

輸出：從s到t的最舒適路徑

Step 1. 將圖G分割為不同等級的層次提取出每層的頂點V和邊W。每個子圖中每兩個邊界頂點之間形成團集。

Step 2.對每個團集中的頂點，找到它到其他邊界頂點的最短路徑，然后將這些最短路徑作為邊，連接起來，形成一個覆蓋圖。一個團集到另一個團集的最短距離為一個快捷路徑。

Step 3.對覆蓋圖進行剪枝，刪除不是快捷路徑的邊，得到骨架圖。骨架圖是由每個團集到其他團集的最短路徑樹組成的并集。

Step 4.對每個層次的骨架圖進行定制，根據(jù)舒適度值計算每個快捷路徑的權(quán)值，并進行存儲。

Step 5.對每個層次的骨架圖進行搜索，從最高層開始，利用雙向Dijkstra 算法找到源點s 到目標點t 的最舒適路徑，然后在下一層細化這條路徑，直到在最底層得到最終的舒適路徑。

MLD 算法能夠快速處理不同的度量，并且可以動態(tài)更新路況和用戶定制的度量，利用多層次的圖劃分，可以減少搜索空間和時間。另外，它可以并行化地執(zhí)行，每層的查詢可以獨立進行，提高效率和可擴展性。

4.3 推薦路徑結(jié)果展示與分析

通過對河海大學（常州校區(qū)）及其周邊區(qū)域?qū)嵉乜睖y并采集騎行數(shù)據(jù)，構(gòu)建舒適度評價體系，實現(xiàn)最舒適路徑、用時最少路徑、距離最短路徑推薦，結(jié)果如圖7和圖8所示。

圖8 三種推薦方式結(jié)果對比（二）

圖7結(jié)果顯示，最舒適路徑和用時最少路徑推薦結(jié)果相同，雖然（c）方案距離最短，但存在并行車流量大、路面設置隔離欄因素，導致舒適度等級降低，所以不作為舒適路徑首選。而（a）和（b）方案的結(jié)果一致，表明該路徑不僅舒適度等級高，用時也短。

圖8結(jié)果顯示，三種方案推薦的路徑各不相同，由于（b）方案中存在并行機動車流量大、設置車道隔離欄的路段，（c）方案中存在路面平整度低、道路幾何線性復雜等問題，所以兩者的舒適度等級不如（a）方案高。

5 結(jié)語

本文基于舒適度評價體系設計并開發(fā)一套騎行路徑推薦系統(tǒng)。該系統(tǒng)綜合客觀環(huán)境因素與主觀騎行體驗，選擇通過路口等待時間、并行機動車流量、道路遮蔭率、道路幾何線性、車道隔離欄設置和道路平整程度六個評價指標，計算出各路段的舒適度權(quán)重。針對帶權(quán)路網(wǎng)地圖，采用多級迪杰斯特拉算法查詢出最優(yōu)路徑，完成路徑推薦。本系統(tǒng)旨在將傳統(tǒng)的出行方式與互聯(lián)網(wǎng)系統(tǒng)結(jié)合，為選擇騎行出行的人們規(guī)劃舒適安全的路徑提供參考。