支持熱力圖等級偏好的路徑規劃算法?

孫煥良 馬曉慧 王亞星 劉俊嶺

（1.沈陽建筑大學計算機科學與工程學院 沈陽 110168）

（2.遼寧省城市建設大數據管理與分析重點實驗室 沈陽 110168）

（3.國家特種計算機工程技術研究中心沈陽分中心 沈陽 110168）

1 引言

基于位置的服務廣泛應用于人們的日常生活，路徑規劃作為基于位置的服務的基本功能之一，通常為用戶提供出行的路線參考。從起點到終點的最短路徑查詢在路徑規劃中得到大規模應用［3～11］。然而，在實際生活中，人們對路徑查詢提出了越來越多樣化的需求，例如，尋找風景優美的路徑［12～13］、安全性高的路徑［14～15］、感覺愉快的路徑［18］等。

熱力圖是以不同的顏色直觀地反映數據分布、密度以及變化狀況的一種圖示，不同顏色對應不同的數據區間，使復雜的數據清晰化。近年來，熱力圖在諸多領域已具有廣泛的應用。城市人群熱力圖以顏色冷暖來反映不同地理區域內的人群密集程度，顏色越暖表示人群越密集，空氣質量熱力圖能夠精確地反映各個區域內的空氣質量狀況。

病毒流行期間，為避開人群保護自身免受感染，用戶希望能夠查詢到一條人群密度小的路徑。用戶外出時對空氣質量格外關注，通常希望得到一條途經空氣質量良好區域的路徑。以上需求不同于傳統的從起點到終點的最短路徑查詢，本文提出一種支持熱力圖等級偏好的路徑規劃問題。給定一片熱力圖，一個起點和一個終點，給定一個路徑成本預算，規劃出一條從起點到終點的路徑，該路徑花費的成本代價不超過給定的路徑成本預算，且某種熱力圖等級偏好的路段（稱為危險路段）長度最小化。

圖1 呈現了支持熱力圖等級偏好的路徑查詢問題的實例。圖中的3條路徑均以s為起點，d為終點。從圖中可以清晰地發現，路徑r1穿過的大部分區域為熱力等級最高的紅色；路徑r2為起點和終點之間路徑成本最低的最短路徑；路徑r3途徑的大部分區域為熱力等級低的紫色、綠色和藍色。當用戶傾向于經過人流密集的區域時，通常會選擇熱力等級高的路徑r1，反之選擇熱力等級低的路徑r3。路徑r1和r3會使用戶付出更多的成本代價，當超過用戶的預期代價后，通常會選擇最短路徑r2。

圖1 支持熱力圖等級偏好的路徑規劃

本文提出的支持熱力圖等級偏好的路徑規劃是一種新的路徑規劃問題。傳統的路徑規劃通常側重于尋找行程距離或時間最短的路徑，如文獻［3～6］提出了基于索引的有效處理最短路徑查詢的方法。還有一部分路徑規劃問題考慮了用戶偏好，文獻［12］提出一種算法ILS*（C），同時考慮弧的成本和值，查詢得到一條風景得分最高且不超過總旅行成本的路徑，文獻［14］在未給定旅游成本的情況下，設計算法旨在輸出一組路徑，在距離和安全性之間做出權衡。以上相關研究最大化路徑的效益值，最小化路徑成本。與上述研究不同，本文的研究目標是在路徑成本預算范圍內最小化危險路段長度。

本文所提出的路徑規劃問題主要涉及熱力圖數據，數據分布具有不規則性和多樣性，如何對熱力圖數據進行有效的組織，以及如何設計有效的算法在路徑成本預算內減少路徑中危險路段的長度是本文面臨的挑戰。本文在對熱力圖數據進行處理時，采用基于網格的索引，一個網格與一個熱力等級相對應。根據熱力圖中熱力等級的實際分布，對危險區域進行預處理，提出一種熱力等級最小區域邊界矩形生成處理方法。基于A*算法的思想，提出一種兩階段危險網格替換算法。由于該算法需遍歷大量網格，為簡化路徑查詢方式，在熱力等級最小區域邊界矩形生成算法的基礎上提出一種基于危險區域規避圖路徑查詢算法。

本文的主要貢獻如下：

1）定義了一種新的路徑規劃問題，即支持熱力圖等級偏好的路徑規劃。

2）在歐式空間內，提出了基于危險網格替換的A*算法，以減少危險網格的個數。提出了一種基于危險區域規避圖路徑查詢算法，簡化路徑搜索的方式，以減少路徑搜索過程中的時間和空間代價。

3）實驗在真實的熱力圖數據集上進行，以危險路徑的長度、算法運行時間等為指標驗證所提算法的有效性。

2 相關工作

2.1 最短路徑查詢

作為在線地圖應用中的基本操作，最短路徑查詢的高效處理得到了廣泛的研究。最基本的算法包括Dijkstra和A*算法，A*算法是一種經典的最短路徑搜索方法［1～2］。由于它們在沒有任何輔助索引的情況下搜索空間，查詢效率不夠高效。基于索引的算法能夠顯著提高查詢性能，例如收縮層次結構（Contraction Hierarchy，CH）［3～4］、Hub 標簽（Hub Labeling，HL）［5～6］等。

在高度動態的環境中，使用批處理最短路徑算法，無需索引結構，在多個查詢之間共享計算［7～8］。文獻［9］將動態網絡視為快照序列，對它們進行聚集，選擇一些作為典型快照并為其建立索引。維護索引的算法在路網發生變化時，直接刷新索引，文獻［10］使用壓縮層次結構作為底層最短路徑計算方法，文獻［11］采用基于樹分解的Hub標簽作為底層索引。

本文提出的路徑查詢并非計算最短路徑，而是基于熱力圖數據，將熱力圖劃分為若干大小相等的網格，根據每一個網格對應的熱力等級劃分為安全網格和危險網格，尋找經過危險網格長度最小化的路徑。

2.2 偏好路徑查詢

除了最短路徑查詢，近年來偏好路徑查詢也得到了諸多研究，以滿足用戶對路徑查詢的多樣化需求。大多數偏好路徑查詢問題可以被描述為弧定向問題（Arc Orienteering Problem，AOP），應用包括找到最佳風景的路徑［12～13，20～22］、安全的路徑［14～15，23］和感覺快樂的路徑［18］等。

AOP問題是NP難題，為了解決這個難題，常見的方法是在路線上設置各種約束，使尋找的解決方案盡可能接近最優解。文獻［16］對個性化多樣性需求建模，并使用用戶偏好和約束修剪搜索空間的策略，提出了top-k 路線搜索問題的最優解，文獻［17］為確保路線的風景質量，對必看的景點做出限制。除此之外，文獻［19］提出分支切割方法和迭代局部搜索算法，來解決騎行規劃AOP 問題的變體。文獻［20～21］提出行駛時間和值雙重時間依賴的AOP 問題，文獻［20］中的算法僅提高單條最快路徑的質量，而文獻［21］中的算法基于初始路徑群提高解決方案的質量。

本文提出的路徑規劃是一種典型的偏好路徑查詢，在有限的路徑成本預算下，查詢到一條危險路段長度最小化的路徑。本文的研究是在熱力圖等級約束中進行，結合熱力圖的分布特點進行路徑規劃。

3 問題定義

定義1（熱力等級）熱力等級θ代表了在一定范圍內某種特征密集程度，利用1，2，…，n 表示，其中1為最低級，n為最高級。

在城市人群熱力圖中，七種不同的顏色對應七種不同的熱力等級，從小到大依次為灰色、紫色、藍色、綠色、黃色、橙色、紅色。最低等級為1 級對應灰色，代表該區域人群密度最低，最高等級為7 級對應紅色，代表該區域內人群最密集。

定義2（帶有網格結構的熱力圖）給定一片熱力圖，將其劃分為若干個大小相等的網格，網格結構的熱力圖表示為H。每一個網格g∈H 均為正方形，表示為（x，y，θ），x 和y 分別表示該網格位置的橫縱坐標編號，θ表示該網格的熱力等級，網格g 的邊長表示為g.l。

如果路徑經過一個危險網格g，g 的危險長度取正方形對角線長度 2 l，表示為g.risk，非危險網格長度為0。熱力圖數據分布具有不規則性，當一個網格內出現多個不同熱力等級時，采用近似處理方式，將網格中的最高熱力等級設置為該網格所對應的熱力等級。

定義3（支持熱力圖等級偏好的路徑規劃）基于帶有網格結構的熱力圖H，給定起點s，終點d，路徑成本預算B。支持熱力圖等級偏好的路徑規劃Q（s，d，B，k）返回一條路徑成本代價l 不超過路徑成本預算B，且經過熱力等級大于等于k級（1

支持熱力圖等級偏好的路徑規劃問題需要同時滿足兩個約束條件，一是路徑花費的成本代價小于給定的路徑成本預算B，二是路徑S 中危險區域的長度小于任何其他同時滿足兩個約束條件的路徑Sn，約束條件表示如式（2）所示。

圖2 為查詢示例。給定帶有網格結構的熱力圖，s 為起點，d 為終點，成本預算B 為24，帶有顏色的網格為危險網格。假設向上、下、左、右四個方向尋路，相鄰網格之間移動的代價為1，向左上、左下、右上、右下四個方向尋路，相鄰網格之間移動的代價為1.4。滿足約束條件的情況下，查詢路徑為s-a-b-c-d，即圖中用黑虛線表示的路徑。

圖2 支持熱力圖等級偏好的路徑規劃示例

下面分析支持熱力圖等級偏好的路徑規劃問題的查詢代價。假定每個網格的出度為μ，即經過該網格后有μ種選擇，在路徑成本預算約束下可通過的網格個數為τ，則代價為μτ，支持熱力圖等級偏好的路徑規劃問題是NP難問題。

4 查詢處理

4.1 基于危險網格替換的A*算法

基于A*算法的思想，本文提出一種兩階段的危險網格替換算法。算法由求解最短路徑和危險網格替換優化兩部分組成，第一階段，以起終點之間的最短路徑作為初始解；第二階段，對初始解中包含的危險網格進行替換，從而查詢到一條滿足路徑成本預算，且經過危險路段長度最小化的路徑。

如算法1 所示：使用A*算法搜索得到從起點s到終點d的最短路徑作為初始解（第1行）。找到初始解中熱力等級大于等于k 的網格，將其中相鄰的部分合并（第2 行）。合并后的每一段危險網格記為Si，危險路段的個數為count，優化階段分別進行替換。再一次使用A*算法，得到危險路段的替換路徑Se（第3 行～4 行）。對替換路徑Se是否滿足條件進行判斷，如果替換路徑中無熱力等級大于等于k 的網格，并且替換后路徑成本花費小于路徑成本預算B，則將會降低路徑中危險網格的個數，對危險路段進行替換，更新路徑S。若不滿足其中的任意一個條件，則意味著路徑替換失敗，不進行路徑的更新，保留路徑S 中的危險網格（第5 行～8 行）。將每一段的危險路段都遍歷完成后，得到優化后的路徑S并返回（第9行）。

算法1 基于危險網格替換的A*算法

圖3為算法1的示例，路徑成本花費B為22，其他條件同上節。第一階段得到初始解s-a-e-d，即從s 到d 的最短路徑。其中，S1、S2和S3為需要替換的危險路段，根據替換條件，只有路徑a-b-c-e 對a-S2-e 的替換有效，初始路徑被更新為s-a-b-c-e-d。更新后的路徑縮短了危險路段的長度，且路徑花費不超過B。

圖3 基于危險網格替換的A*算法示例

基于危險網格替換的A*算法，初始解中熱力等級大于等于k 的網格將會被替換掉且更新后的路徑圍繞在初始解周圍，以保證更新后的路徑滿足路徑成本預算。但是，如果初始解中包含較多的危險網格，將進行多次的危險網格替換，必然會增加時間和空間成本。如果初始解中危險網格周圍圍繞著諸多危險網格，則不滿足路徑中危險路段長度最小化的需求，路徑替換失敗，導致初始解中危險網格的替換具有局限性。

算法的時間復雜度分析如下，A*算法的平均時間復雜度為O（NlogN）（N為問題規模），本節提出的算法基于A*算法的思想，第一階段計算最短路徑，第二階段對最短路徑中的危險網格進行替換，均采用A*算法，因此基于危險網格替換的A*算法的時間復雜度將高于A*算法。

4.2 基于危險區域規避圖路徑查詢算法

上節提出了一種基于危險網格替換的A*算法，在查詢過程中，當網絡的數據量較大時，查詢算法效率無法支持在線系統應用。為了提高查詢效率，本文提出了一種基于危險區域規避圖路徑查詢算法。通過將熱力圖中的危險區域近似成矩形結構，生成最大化避開矩形結構的危險區域規避圖，從而查詢出一條不超過路徑成本預算B 且經過危險區域長度最短的路徑。

定義4（熱力等級最小區域邊界矩形）基于帶有網格結構的熱力圖，將熱力等級大于等于k 級（1 < k ≤n，n 為最大熱力等級）的危險區域用最小外接矩形包圍起來，生成熱力等級最小區域邊界矩形（Thermal level minimum region boundary rectangle，TMBR）。其范圍由矩形的四個頂點表示，即R.P0、R.P1、R.P2、R.P3。

在熱力圖中，由于熱力等級分布具有分散性，生成多個TMBR，TMBR 的集合記為R。下文中，將每個TMBR 記為Ri，i 的值從0 開始，為根據縱向位置排序TMBR的序號。

本節所提算法的查詢過程如算法2 所示：根據熱力圖中熱力等級的分布情況，調用算法3 createMBR（k，H），對危險區域做近似處理，生成TMBR（第1 行）。為避開危險區域，在生成的TMBR 基礎上，調用算法4 evadeGraph（s，d，R），在線生成用于路徑查詢的危險區域規避圖G（第2行）。在圖G中調用A*算法（第3行），最終返回滿足兩個約束條件的路徑S（第4行～5行）。算法生成邊界矩形過程可以在查詢執行前進行，當查詢到來時在線生成規避圖，然后進行路徑查詢。

算法2 基于危險區域規避圖路徑查詢算法

4.2.1 熱力等級最小區域邊界矩形生成算法

根據熱力圖中不同熱力等級區域的實際分布情況，本文在網格索引的基礎上，使用最小邊界矩形，將危險區域近似成矩形結構，生成熱力等級最小區域邊界矩形TMBR。

生成每一個TMBR 需要不斷合并擴展，如算法3 createMBR（k，H）所示。當一個未合并的危險網格h 存在時，設置變量up、down、left、right 分別表示危險網格向上、下、左、右四個方向拓展的距離。當危險網格上方為危險網格時，up將向上移動一個單位，即up-1，并將（up，left）、（up，right）范圍內的網格合并；反之，則不進行合并，變量的值不變（第1行～4 行）。在對下、左、右三個方向進行合并判斷時同理（第5行～13行）。當危險區域的四周均不存在危險網格時，四個變量值均已更新完成，確定TMBR的范圍并返回（第14行～15行）。

算法3 createMBR（k，H）

4.2.2 危險區域規避圖生成算法

危險區域規避圖是根據一定的判斷規則在路徑起終點與TMBR 之間形成的，由諸多有效邊和有效頂點組成。每一條有效邊需要同時滿足三個條件：第一，當前頂點同TMBR 的頂點之間的連線不經過任何危險區域；第二，TMBR 的頂點同終點之間的連線經過的危險區域長度小于連接當前頂點同終點的直線之間經過的危險區域長度；第三，TMBR 的頂點同終點之間的連線不經過自身所在矩形。同時滿足三個條件后，則當前頂點為有效頂點，即下一次尋找有效邊的新起點。路徑查詢在圖上進行，不僅簡化了查詢方式節約時間和空間成本，而且能夠盡可能地避開危險區域，滿足用戶偏好。

危險區域規避圖生成過程如算法4 evade-Graph（s，d，R）所示，初始化存儲頂點的隊列qv和存儲有效邊的隊列qe，起點s 添加進入qv（第1 行～2行）。當隊列不為空時，當前頂點為qv中首元素，并使用變量count 記錄起終點之間經過的第一個TMBR 的序號（第3 行～4 行）。若當前頂點同終點之間經過危險區域，將當前頂點與第一個經過的TMBR的四個頂點依次相連，根據上述三條判斷規則，滿足條件的邊加入qe，頂點加入qv，若當前頂點不是起點s，則將當前頂點同終點創建的邊加入qe（第5行～11 行）。若當前頂點同終點之間不經過任何危險區域，則直接連接兩頂點構建的邊（第12行～13行）。直至所有有效邊創建完成，返回圖G（第14行）。

算法4 evadeGraph（s，d，R）

危險區域規避圖的創建過程如圖4 所示：起點s和終點d所連接的邊經過的第一個TMBR為R1，將s 依次與R1的四個頂點相連尋找有效邊。邊之間未經過任何危險區域，且邊之間經過的危險路段長度小于起終點之間危險路段的長度，因此邊為有效邊，頂點R1.P0為有效頂點；同理，邊為有效邊，頂點R1.P2為有效頂點，邊和無效。接著以首元素R1.P0為新起點尋找新的有效邊，其與d 之間經過的第一個TMBR 為R2，根據判斷規則，邊和邊為有效邊，頂點R2.P0和R2.P2為有效頂點，并將頂點R1.P0與終點d相連。循環執行該過程，當所有邊判斷完成后，生成危險區域規避圖。

圖4 危險區域規避圖生成示例

危險區域規避圖中的邊具有兩個重要特點：第一，位于兩個不同TMBR 的頂點創建的邊一定為安全邊，沒有經過任何一個危險矩形；第二，當前頂點與終點d 創建的邊可能既有安全邊，也有危險邊，且危險邊長度一定小于起終點路徑中危險路段的長度。這種特點大大地降低了危險邊的數量和長度，使得路徑查詢時可以盡可能地避開危險路段。

上一節提出的算法在網格上進行，返回的路徑由諸多網格構成，本節提出的算法在危險區域規避圖上進行，返回的路徑由邊構成，簡化了路徑查詢的方式。基于危險區域規避圖進行路徑查詢過濾掉大量危險邊，對比算法示例可以發現，圖4 中有效邊和有效頂點的數量遠少于圖3 中網格的數量，當網絡數量為N 時時間復雜度將小于O（NlogN），減少了時間和空間成本，提升了算法的執行效率。

5 實驗分析

本節利用真實的熱力圖數據集對所提算法進行實驗測試，對比分析不同算法的實驗結果。

熱力圖數據采集自百度城市熱力圖平臺，本文實驗采用北京市2021 年3 月份的數據，每10min 采集一次，共采集到4120 張，采集到的數據量能夠驗證本文所提算法的有效性。熱力圖數據進行網格化處理后，包含網格位置的橫坐標編號x、縱坐標編號y 和網格位置的熱力等級等屬性，數據樣例如表1所示。

表1 實驗數據集樣例

根據人群密集程度將熱力圖中的熱力等級劃分為7 級，從1 級到7 級，熱力等級逐級升高，人群密集程度逐漸增加。本節定義的危險等級為7 級，危險區域為熱力等級為7級的區域。

針對支持熱力圖等級偏好的路徑規劃問題，本文設計實現了基于危險網格替換的A*Grid 算法和基于危險區域規避圖路徑查詢算法avoidGraph。由于現有相關工作中沒有基于熱力圖進行支持熱力圖等級偏好的路徑查詢算法，因此本文將A*算法和采用文獻［12］替換思想設計的算法A*Grid 算法作為對比算法。

5.1 算法的精度比較

本節分別基于帶有不同網格粒度和不同起終點歐式距離的熱力圖對算法的查詢精度進行比較。各個測試中，路徑長度單位（即路徑成本）為200*200 粒度網格中每一個網格的邊長。采集同一時刻下同一區域內的熱力圖，分別添加200*200、100*100、50*50 大小的網格結構，起終點歐式距離設置為3km，測試不同網格粒度對算法查詢精度的影響。歐式距離分別取3km、6km、9km、12km和15km，選擇網格粒度為200*200 的熱力圖，測試不同起終點歐式距離對算法查詢精度的影響。為了更準確地比較各個算法的查詢精度，實驗分別運行10次，取其平均值作為最終結果。

圖5（a）和圖5（b）分別展示了不同網格粒度下和不同起終點歐式距離下危險路徑長度的變化情況。以A*算法計算的起終點之間最短路徑經過的危險路段長度為對比，從圖中可以看出優化后的路徑中危險路段的長度均不大于初始路徑中危險路段的長度，這是因為avoidGraph算法和A*Grid算法均在給定的路徑成本預算范圍內，多付出一些路徑成本避開危險區域。avoidGraph 算法優化后的路徑經過的危險區域長度最短，因為在危險區域規避圖的創建過程中，過濾掉了大量經過危險區域的無效邊，僅保留安全邊或危險長度短的有效邊。使用A*Grid算法優化后的路徑，危險路徑長度變短但危險路段依舊存在，因為路徑規劃過程中存在兩種可能性，第一種可能是危險網格周圍分布著大量危險網格，導致無法進行網格的替換；另一種可能是替換路段后路徑成本花費超過給定的路徑成本預算，為了控制路徑成本，不得不選擇一條經過危險區域的路徑。

圖5 不同約束條件對危險路段長度的影響

如圖5（a）所示：A*算法計算的最短路徑中，隨著粒度變粗危險路段的長度呈現上升趨勢。這是因為粗網格粒度代表近似的計算，當網格粒度從200*200 變為100*100、50*50 的過程中，一些安全區域被近似計算為危險區域，擴大了危險區域的范圍，導致危險路段的長度增加。如圖5（b）所示：隨著起終點之間歐式距離的增加，A*算法計算的起終點最短路徑中危險路段的長度增加，因為起終點之間距離越長，經過危險路段的可能性越高。需要說明的是路徑中危險路段的長度與起終點之間危險區域的分布有關，與起終點之間歐式距離的長度不成比例關系。

圖6（a）測試了網格粒度對路徑成本的影響，網格粒度越大查詢安全路徑所花費的成本越高，與圖5 中危險路段的長度呈現相同的變化趨勢。圖6（b）比較了路徑成本隨起終點歐式距離的變化情況，以A*算法計算出的最短路徑成本代價為對比，圖中可以看出，隨著歐式距離的增加，路徑查詢所需要的代價隨之增加。當歐式距離或網格粒度相同時，A*Grid算法查詢到的優化路徑所需的成本明顯要高于avoidGraph 算法所需的成本，這是由于A*Grid算法是沿著網格進行尋路，路徑只能沿著特定方向進行，而avoidGraph 算法在生成的危險區域規避圖上進行尋路，路徑搜索本質上是沿歐氏距離進行的，而且前者搜索路徑的次數比后者要多，因此前者消耗的成本要明顯多于后者。

圖6 不同約束條件對路徑成本的影響

5.2 算法的效率比較

本節分別測試在不同網格粒度和起終點歐氏距離下，A*算法、A*Grid 算法以及avoidGraph 算法運行10000次路徑查詢所需時間，其他條件同上節。

圖7（a）展示了熱力圖網格粒度對于算法效率的影響。相同網格粒度下，avoidGraph 算法運行效率最高，A*Grid 算法運行效率最低；網格粒度由細到粗變化時，算法運行消耗時間大幅下降。圖7（b）展示了算法運行效率隨起終點歐式距離的變化情況。歐式距離相同時，avoidGraph 算法查詢效率最高，A*Grid算法查詢效率最低；對于同一種算法，歐式距離的增加時，算法查詢所需時間增加。特別當歐式距離大于9km 時，A*Grid 算法和A*算法的運行時間增長較快。原因是avoidGraph 算法路徑規劃在圖上進行，而A*Grid 算法和A*算法在網格中進行，圖中頂點和邊的數目遠小于網格的數量；A*Grid 算法是一種兩階段算法，在使用A*算法獲取最短路徑后，需對路徑中的危險網格進行替換，因此時間效率最低。

圖7 不同約束條件對算法效率的影響

6 結語

本文提出一種支持熱力圖等級偏好的路徑規劃問題。設計了兩種查詢優化算法，包括基于危險網格替換的A*算法和基于危險區域規避圖的路徑查詢算法。利用真實的數據集進行了充足的實驗，驗證所提出算法的有效性。

由于熱力圖是實時更新的，在未來的工作中可以根據獲得的熱力圖數據，進行熱力圖模式發現，形成在時間和空間上相近規律的生成模式。根據用戶選擇的不同的出行方式，即步行、騎行和駕駛，可以確定用戶的預計到達時間。根據給定的出發時間、起點和終點確定相應的熱力圖模式。初始查詢在單片圖上進行，若在用戶未到達終點時間內，區域的熱力圖模式發生變化，則把相應的模式引入，在新的熱力圖模式上進行后續的查詢。