基于舒適度的騎行路徑推薦系統設計與開發

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

（1. 河海大學物聯網工程學院，常州 213000；2. 河海大學商學院，常州 213000）

0 引言

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

1 系統總體設計

1.1 系統架構

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

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

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

圖1 系統架構

1.2 路徑推薦系統的功能模塊

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

圖2 系統功能設計

（1）路網數據預處理。本系統采用的原始路網數據來自開源地圖網站OpenStreetMap［3］。為了實現路段分割，首先，從獲取到的路網地圖中篩選出與騎行道路相關的Ways 元素；其次，對篩選出的Ways 元素在交點處進行分割，使其具有向左右行駛的拓撲結構。

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

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

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

2 騎行舒適度評價體系構建

2.1 評價指標的選取

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

指標具體含義解釋如下：

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

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

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

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

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

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

2.2 指標的量化方式

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

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

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

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

2.3 基于主成分分析法的權重計算

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

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

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

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

Step 3.參數旋轉，計算主要參數權值，計算過程如公式（6）所示，采用線性回歸方程對主參數進行回歸計算。

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

權重計算結果見表2。

表2 舒適度指標權重計算結果

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

3 路網預處理及路網匹配

3.1 路網地圖預處理

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

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

圖3 道路分割示意圖

3.2 軌跡數據與路網地圖匹配

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

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

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

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

圖4 騎行軌跡點處理結果

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

4 基于帶權路網推薦舒適路徑

4.1 舒適度賦值路網地圖

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

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

圖5 舒適度指標賦值路網

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

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

MLD算法的實現可以分為以下三個步驟：

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

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

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

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

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

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

MLD算法具體實現流程如下：

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

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

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

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

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

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

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

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

4.3 推薦路徑結果展示與分析

通過對河海大學（常州校區）及其周邊區域實地勘測并采集騎行數據，構建舒適度評價體系，實現最舒適路徑、用時最少路徑、距離最短路徑推薦，結果如圖7和圖8所示。

圖8 三種推薦方式結果對比（二）

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

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

5 結語

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