支持熱力圖等級(jí)偏好的路徑規(guī)劃算法?

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

（1.沈陽建筑大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽 110168）

（2.遼寧省城市建設(shè)大數(shù)據(jù)管理與分析重點(diǎn)實(shí)驗(yàn)室 沈陽 110168）

（3.國家特種計(jì)算機(jī)工程技術(shù)研究中心沈陽分中心 沈陽 110168）

1 引言

基于位置的服務(wù)廣泛應(yīng)用于人們的日常生活，路徑規(guī)劃作為基于位置的服務(wù)的基本功能之一，通常為用戶提供出行的路線參考。從起點(diǎn)到終點(diǎn)的最短路徑查詢?cè)诼窂揭?guī)劃中得到大規(guī)模應(yīng)用［3～11］。然而，在實(shí)際生活中，人們對(duì)路徑查詢提出了越來越多樣化的需求，例如，尋找風(fēng)景優(yōu)美的路徑［12～13］、安全性高的路徑［14～15］、感覺愉快的路徑［18］等。

熱力圖是以不同的顏色直觀地反映數(shù)據(jù)分布、密度以及變化狀況的一種圖示，不同顏色對(duì)應(yīng)不同的數(shù)據(jù)區(qū)間，使復(fù)雜的數(shù)據(jù)清晰化。近年來，熱力圖在諸多領(lǐng)域已具有廣泛的應(yīng)用。城市人群熱力圖以顏色冷暖來反映不同地理區(qū)域內(nèi)的人群密集程度，顏色越暖表示人群越密集，空氣質(zhì)量熱力圖能夠精確地反映各個(gè)區(qū)域內(nèi)的空氣質(zhì)量狀況。

病毒流行期間，為避開人群保護(hù)自身免受感染，用戶希望能夠查詢到一條人群密度小的路徑。用戶外出時(shí)對(duì)空氣質(zhì)量格外關(guān)注，通常希望得到一條途經(jīng)空氣質(zhì)量良好區(qū)域的路徑。以上需求不同于傳統(tǒng)的從起點(diǎn)到終點(diǎn)的最短路徑查詢，本文提出一種支持熱力圖等級(jí)偏好的路徑規(guī)劃問題。給定一片熱力圖，一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，給定一個(gè)路徑成本預(yù)算，規(guī)劃出一條從起點(diǎn)到終點(diǎn)的路徑，該路徑花費(fèi)的成本代價(jià)不超過給定的路徑成本預(yù)算，且某種熱力圖等級(jí)偏好的路段（稱為危險(xiǎn)路段）長度最小化。

圖1 呈現(xiàn)了支持熱力圖等級(jí)偏好的路徑查詢問題的實(shí)例。圖中的3條路徑均以s為起點(diǎn)，d為終點(diǎn)。從圖中可以清晰地發(fā)現(xiàn)，路徑r1穿過的大部分區(qū)域?yàn)闊崃Φ燃?jí)最高的紅色；路徑r2為起點(diǎn)和終點(diǎn)之間路徑成本最低的最短路徑；路徑r3途徑的大部分區(qū)域?yàn)闊崃Φ燃?jí)低的紫色、綠色和藍(lán)色。當(dāng)用戶傾向于經(jīng)過人流密集的區(qū)域時(shí)，通常會(huì)選擇熱力等級(jí)高的路徑r1，反之選擇熱力等級(jí)低的路徑r3。路徑r1和r3會(huì)使用戶付出更多的成本代價(jià)，當(dāng)超過用戶的預(yù)期代價(jià)后，通常會(huì)選擇最短路徑r2。

圖1 支持熱力圖等級(jí)偏好的路徑規(guī)劃

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

本文所提出的路徑規(guī)劃問題主要涉及熱力圖數(shù)據(jù)，數(shù)據(jù)分布具有不規(guī)則性和多樣性，如何對(duì)熱力圖數(shù)據(jù)進(jìn)行有效的組織，以及如何設(shè)計(jì)有效的算法在路徑成本預(yù)算內(nèi)減少路徑中危險(xiǎn)路段的長度是本文面臨的挑戰(zhàn)。本文在對(duì)熱力圖數(shù)據(jù)進(jìn)行處理時(shí)，采用基于網(wǎng)格的索引，一個(gè)網(wǎng)格與一個(gè)熱力等級(jí)相對(duì)應(yīng)。根據(jù)熱力圖中熱力等級(jí)的實(shí)際分布，對(duì)危險(xiǎn)區(qū)域進(jìn)行預(yù)處理，提出一種熱力等級(jí)最小區(qū)域邊界矩形生成處理方法?；贏*算法的思想，提出一種兩階段危險(xiǎn)網(wǎng)格替換算法。由于該算法需遍歷大量網(wǎng)格，為簡化路徑查詢方式，在熱力等級(jí)最小區(qū)域邊界矩形生成算法的基礎(chǔ)上提出一種基于危險(xiǎn)區(qū)域規(guī)避圖路徑查詢算法。

本文的主要貢獻(xiàn)如下：

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

2）在歐式空間內(nèi)，提出了基于危險(xiǎn)網(wǎng)格替換的A*算法，以減少危險(xiǎn)網(wǎng)格的個(gè)數(shù)。提出了一種基于危險(xiǎn)區(qū)域規(guī)避圖路徑查詢算法，簡化路徑搜索的方式，以減少路徑搜索過程中的時(shí)間和空間代價(jià)。

3）實(shí)驗(yàn)在真實(shí)的熱力圖數(shù)據(jù)集上進(jìn)行，以危險(xiǎn)路徑的長度、算法運(yùn)行時(shí)間等為指標(biāo)驗(yàn)證所提算法的有效性。

2 相關(guān)工作

2.1 最短路徑查詢

作為在線地圖應(yīng)用中的基本操作，最短路徑查詢的高效處理得到了廣泛的研究。最基本的算法包括Dijkstra和A*算法，A*算法是一種經(jīng)典的最短路徑搜索方法［1～2］。由于它們?cè)跊]有任何輔助索引的情況下搜索空間，查詢效率不夠高效?；谒饕乃惴軌蝻@著提高查詢性能，例如收縮層次結(jié)構(gòu)（Contraction Hierarchy，CH）［3～4］、Hub 標(biāo)簽（Hub Labeling，HL）［5～6］等。

在高度動(dòng)態(tài)的環(huán)境中，使用批處理最短路徑算法，無需索引結(jié)構(gòu)，在多個(gè)查詢之間共享計(jì)算［7～8］。文獻(xiàn)［9］將動(dòng)態(tài)網(wǎng)絡(luò)視為快照序列，對(duì)它們進(jìn)行聚集，選擇一些作為典型快照并為其建立索引。維護(hù)索引的算法在路網(wǎng)發(fā)生變化時(shí)，直接刷新索引，文獻(xiàn)［10］使用壓縮層次結(jié)構(gòu)作為底層最短路徑計(jì)算方法，文獻(xiàn)［11］采用基于樹分解的Hub標(biāo)簽作為底層索引。

本文提出的路徑查詢并非計(jì)算最短路徑，而是基于熱力圖數(shù)據(jù)，將熱力圖劃分為若干大小相等的網(wǎng)格，根據(jù)每一個(gè)網(wǎng)格對(duì)應(yīng)的熱力等級(jí)劃分為安全網(wǎng)格和危險(xiǎn)網(wǎng)格，尋找經(jīng)過危險(xiǎn)網(wǎng)格長度最小化的路徑。

2.2 偏好路徑查詢

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

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

本文提出的路徑規(guī)劃是一種典型的偏好路徑查詢，在有限的路徑成本預(yù)算下，查詢到一條危險(xiǎn)路段長度最小化的路徑。本文的研究是在熱力圖等級(jí)約束中進(jìn)行，結(jié)合熱力圖的分布特點(diǎn)進(jìn)行路徑規(guī)劃。

3 問題定義

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

在城市人群熱力圖中，七種不同的顏色對(duì)應(yīng)七種不同的熱力等級(jí)，從小到大依次為灰色、紫色、藍(lán)色、綠色、黃色、橙色、紅色。最低等級(jí)為1 級(jí)對(duì)應(yīng)灰色，代表該區(qū)域人群密度最低，最高等級(jí)為7 級(jí)對(duì)應(yīng)紅色，代表該區(qū)域內(nèi)人群最密集。

定義2（帶有網(wǎng)格結(jié)構(gòu)的熱力圖）給定一片熱力圖，將其劃分為若干個(gè)大小相等的網(wǎng)格，網(wǎng)格結(jié)構(gòu)的熱力圖表示為H。每一個(gè)網(wǎng)格g∈H 均為正方形，表示為（x，y，θ），x 和y 分別表示該網(wǎng)格位置的橫縱坐標(biāo)編號(hào)，θ表示該網(wǎng)格的熱力等級(jí)，網(wǎng)格g 的邊長表示為g.l。

如果路徑經(jīng)過一個(gè)危險(xiǎn)網(wǎng)格g，g 的危險(xiǎn)長度取正方形對(duì)角線長度 2 l，表示為g.risk，非危險(xiǎn)網(wǎng)格長度為0。熱力圖數(shù)據(jù)分布具有不規(guī)則性，當(dāng)一個(gè)網(wǎng)格內(nèi)出現(xiàn)多個(gè)不同熱力等級(jí)時(shí)，采用近似處理方式，將網(wǎng)格中的最高熱力等級(jí)設(shè)置為該網(wǎng)格所對(duì)應(yīng)的熱力等級(jí)。

定義3（支持熱力圖等級(jí)偏好的路徑規(guī)劃）基于帶有網(wǎng)格結(jié)構(gòu)的熱力圖H，給定起點(diǎn)s，終點(diǎn)d，路徑成本預(yù)算B。支持熱力圖等級(jí)偏好的路徑規(guī)劃Q（s，d，B，k）返回一條路徑成本代價(jià)l 不超過路徑成本預(yù)算B，且經(jīng)過熱力等級(jí)大于等于k級(jí)（1

支持熱力圖等級(jí)偏好的路徑規(guī)劃問題需要同時(shí)滿足兩個(gè)約束條件，一是路徑花費(fèi)的成本代價(jià)小于給定的路徑成本預(yù)算B，二是路徑S 中危險(xiǎn)區(qū)域的長度小于任何其他同時(shí)滿足兩個(gè)約束條件的路徑Sn，約束條件表示如式（2）所示。

圖2 為查詢示例。給定帶有網(wǎng)格結(jié)構(gòu)的熱力圖，s 為起點(diǎn)，d 為終點(diǎn)，成本預(yù)算B 為24，帶有顏色的網(wǎng)格為危險(xiǎn)網(wǎng)格。假設(shè)向上、下、左、右四個(gè)方向?qū)ぢ?，相鄰網(wǎng)格之間移動(dòng)的代價(jià)為1，向左上、左下、右上、右下四個(gè)方向?qū)ぢ罚噜従W(wǎng)格之間移動(dòng)的代價(jià)為1.4。滿足約束條件的情況下，查詢路徑為s-a-b-c-d，即圖中用黑虛線表示的路徑。

圖2 支持熱力圖等級(jí)偏好的路徑規(guī)劃示例

下面分析支持熱力圖等級(jí)偏好的路徑規(guī)劃問題的查詢代價(jià)。假定每個(gè)網(wǎng)格的出度為μ，即經(jīng)過該網(wǎng)格后有μ種選擇，在路徑成本預(yù)算約束下可通過的網(wǎng)格個(gè)數(shù)為τ，則代價(jià)為μτ，支持熱力圖等級(jí)偏好的路徑規(guī)劃問題是NP難問題。

4 查詢處理

4.1 基于危險(xiǎn)網(wǎng)格替換的A*算法

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

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

算法1 基于危險(xiǎn)網(wǎng)格替換的A*算法

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

圖3 基于危險(xiǎn)網(wǎng)格替換的A*算法示例

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

算法的時(shí)間復(fù)雜度分析如下，A*算法的平均時(shí)間復(fù)雜度為O（NlogN）（N為問題規(guī)模），本節(jié)提出的算法基于A*算法的思想，第一階段計(jì)算最短路徑，第二階段對(duì)最短路徑中的危險(xiǎn)網(wǎng)格進(jìn)行替換，均采用A*算法，因此基于危險(xiǎn)網(wǎng)格替換的A*算法的時(shí)間復(fù)雜度將高于A*算法。

4.2 基于危險(xiǎn)區(qū)域規(guī)避圖路徑查詢算法

上節(jié)提出了一種基于危險(xiǎn)網(wǎng)格替換的A*算法，在查詢過程中，當(dāng)網(wǎng)絡(luò)的數(shù)據(jù)量較大時(shí)，查詢算法效率無法支持在線系統(tǒng)應(yīng)用。為了提高查詢效率，本文提出了一種基于危險(xiǎn)區(qū)域規(guī)避圖路徑查詢算法。通過將熱力圖中的危險(xiǎn)區(qū)域近似成矩形結(jié)構(gòu)，生成最大化避開矩形結(jié)構(gòu)的危險(xiǎn)區(qū)域規(guī)避圖，從而查詢出一條不超過路徑成本預(yù)算B 且經(jīng)過危險(xiǎn)區(qū)域長度最短的路徑。

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

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

本節(jié)所提算法的查詢過程如算法2 所示：根據(jù)熱力圖中熱力等級(jí)的分布情況，調(diào)用算法3 createMBR（k，H），對(duì)危險(xiǎn)區(qū)域做近似處理，生成TMBR（第1 行）。為避開危險(xiǎn)區(qū)域，在生成的TMBR 基礎(chǔ)上，調(diào)用算法4 evadeGraph（s，d，R），在線生成用于路徑查詢的危險(xiǎn)區(qū)域規(guī)避圖G（第2行）。在圖G中調(diào)用A*算法（第3行），最終返回滿足兩個(gè)約束條件的路徑S（第4行～5行）。算法生成邊界矩形過程可以在查詢執(zhí)行前進(jìn)行，當(dāng)查詢到來時(shí)在線生成規(guī)避圖，然后進(jìn)行路徑查詢。

算法2 基于危險(xiǎn)區(qū)域規(guī)避圖路徑查詢算法

4.2.1 熱力等級(jí)最小區(qū)域邊界矩形生成算法

根據(jù)熱力圖中不同熱力等級(jí)區(qū)域的實(shí)際分布情況，本文在網(wǎng)格索引的基礎(chǔ)上，使用最小邊界矩形，將危險(xiǎn)區(qū)域近似成矩形結(jié)構(gòu)，生成熱力等級(jí)最小區(qū)域邊界矩形TMBR。

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

算法3 createMBR（k，H）

4.2.2 危險(xiǎn)區(qū)域規(guī)避圖生成算法

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

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

算法4 evadeGraph（s，d，R）

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

圖4 危險(xiǎn)區(qū)域規(guī)避圖生成示例

危險(xiǎn)區(qū)域規(guī)避圖中的邊具有兩個(gè)重要特點(diǎn)：第一，位于兩個(gè)不同TMBR 的頂點(diǎn)創(chuàng)建的邊一定為安全邊，沒有經(jīng)過任何一個(gè)危險(xiǎn)矩形；第二，當(dāng)前頂點(diǎn)與終點(diǎn)d 創(chuàng)建的邊可能既有安全邊，也有危險(xiǎn)邊，且危險(xiǎn)邊長度一定小于起終點(diǎn)路徑中危險(xiǎn)路段的長度。這種特點(diǎn)大大地降低了危險(xiǎn)邊的數(shù)量和長度，使得路徑查詢時(shí)可以盡可能地避開危險(xiǎn)路段。

上一節(jié)提出的算法在網(wǎng)格上進(jìn)行，返回的路徑由諸多網(wǎng)格構(gòu)成，本節(jié)提出的算法在危險(xiǎn)區(qū)域規(guī)避圖上進(jìn)行，返回的路徑由邊構(gòu)成，簡化了路徑查詢的方式?；谖ｋU(xiǎn)區(qū)域規(guī)避圖進(jìn)行路徑查詢過濾掉大量危險(xiǎn)邊，對(duì)比算法示例可以發(fā)現(xiàn)，圖4 中有效邊和有效頂點(diǎn)的數(shù)量遠(yuǎn)少于圖3 中網(wǎng)格的數(shù)量，當(dāng)網(wǎng)絡(luò)數(shù)量為N 時(shí)時(shí)間復(fù)雜度將小于O（NlogN），減少了時(shí)間和空間成本，提升了算法的執(zhí)行效率。

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

本節(jié)利用真實(shí)的熱力圖數(shù)據(jù)集對(duì)所提算法進(jìn)行實(shí)驗(yàn)測試，對(duì)比分析不同算法的實(shí)驗(yàn)結(jié)果。

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

表1 實(shí)驗(yàn)數(shù)據(jù)集樣例

根據(jù)人群密集程度將熱力圖中的熱力等級(jí)劃分為7 級(jí)，從1 級(jí)到7 級(jí)，熱力等級(jí)逐級(jí)升高，人群密集程度逐漸增加。本節(jié)定義的危險(xiǎn)等級(jí)為7 級(jí)，危險(xiǎn)區(qū)域?yàn)闊崃Φ燃?jí)為7級(jí)的區(qū)域。

針對(duì)支持熱力圖等級(jí)偏好的路徑規(guī)劃問題，本文設(shè)計(jì)實(shí)現(xiàn)了基于危險(xiǎn)網(wǎng)格替換的A*Grid 算法和基于危險(xiǎn)區(qū)域規(guī)避圖路徑查詢算法avoidGraph。由于現(xiàn)有相關(guān)工作中沒有基于熱力圖進(jìn)行支持熱力圖等級(jí)偏好的路徑查詢算法，因此本文將A*算法和采用文獻(xiàn)［12］替換思想設(shè)計(jì)的算法A*Grid 算法作為對(duì)比算法。

5.1 算法的精度比較

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

圖5（a）和圖5（b）分別展示了不同網(wǎng)格粒度下和不同起終點(diǎn)歐式距離下危險(xiǎn)路徑長度的變化情況。以A*算法計(jì)算的起終點(diǎn)之間最短路徑經(jīng)過的危險(xiǎn)路段長度為對(duì)比，從圖中可以看出優(yōu)化后的路徑中危險(xiǎn)路段的長度均不大于初始路徑中危險(xiǎn)路段的長度，這是因?yàn)閍voidGraph算法和A*Grid算法均在給定的路徑成本預(yù)算范圍內(nèi)，多付出一些路徑成本避開危險(xiǎn)區(qū)域。avoidGraph 算法優(yōu)化后的路徑經(jīng)過的危險(xiǎn)區(qū)域長度最短，因?yàn)樵谖ｋU(xiǎn)區(qū)域規(guī)避圖的創(chuàng)建過程中，過濾掉了大量經(jīng)過危險(xiǎn)區(qū)域的無效邊，僅保留安全邊或危險(xiǎn)長度短的有效邊。使用A*Grid算法優(yōu)化后的路徑，危險(xiǎn)路徑長度變短但危險(xiǎn)路段依舊存在，因?yàn)槁窂揭?guī)劃過程中存在兩種可能性，第一種可能是危險(xiǎn)網(wǎng)格周圍分布著大量危險(xiǎn)網(wǎng)格，導(dǎo)致無法進(jìn)行網(wǎng)格的替換；另一種可能是替換路段后路徑成本花費(fèi)超過給定的路徑成本預(yù)算，為了控制路徑成本，不得不選擇一條經(jīng)過危險(xiǎn)區(qū)域的路徑。

圖5 不同約束條件對(duì)危險(xiǎn)路段長度的影響

如圖5（a）所示：A*算法計(jì)算的最短路徑中，隨著粒度變粗危險(xiǎn)路段的長度呈現(xiàn)上升趨勢(shì)。這是因?yàn)榇志W(wǎng)格粒度代表近似的計(jì)算，當(dāng)網(wǎng)格粒度從200*200 變?yōu)?00*100、50*50 的過程中，一些安全區(qū)域被近似計(jì)算為危險(xiǎn)區(qū)域，擴(kuò)大了危險(xiǎn)區(qū)域的范圍，導(dǎo)致危險(xiǎn)路段的長度增加。如圖5（b）所示：隨著起終點(diǎn)之間歐式距離的增加，A*算法計(jì)算的起終點(diǎn)最短路徑中危險(xiǎn)路段的長度增加，因?yàn)槠鸾K點(diǎn)之間距離越長，經(jīng)過危險(xiǎn)路段的可能性越高。需要說明的是路徑中危險(xiǎn)路段的長度與起終點(diǎn)之間危險(xiǎn)區(qū)域的分布有關(guān)，與起終點(diǎn)之間歐式距離的長度不成比例關(guān)系。

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

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

5.2 算法的效率比較

本節(jié)分別測試在不同網(wǎng)格粒度和起終點(diǎn)歐氏距離下，A*算法、A*Grid 算法以及avoidGraph 算法運(yùn)行10000次路徑查詢所需時(shí)間，其他條件同上節(jié)。

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

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

6 結(jié)語

本文提出一種支持熱力圖等級(jí)偏好的路徑規(guī)劃問題。設(shè)計(jì)了兩種查詢優(yōu)化算法，包括基于危險(xiǎn)網(wǎng)格替換的A*算法和基于危險(xiǎn)區(qū)域規(guī)避圖的路徑查詢算法。利用真實(shí)的數(shù)據(jù)集進(jìn)行了充足的實(shí)驗(yàn)，驗(yàn)證所提出算法的有效性。

由于熱力圖是實(shí)時(shí)更新的，在未來的工作中可以根據(jù)獲得的熱力圖數(shù)據(jù)，進(jìn)行熱力圖模式發(fā)現(xiàn)，形成在時(shí)間和空間上相近規(guī)律的生成模式。根據(jù)用戶選擇的不同的出行方式，即步行、騎行和駕駛，可以確定用戶的預(yù)計(jì)到達(dá)時(shí)間。根據(jù)給定的出發(fā)時(shí)間、起點(diǎn)和終點(diǎn)確定相應(yīng)的熱力圖模式。初始查詢?cè)趩纹瑘D上進(jìn)行，若在用戶未到達(dá)終點(diǎn)時(shí)間內(nèi)，區(qū)域的熱力圖模式發(fā)生變化，則把相應(yīng)的模式引入，在新的熱力圖模式上進(jìn)行后續(xù)的查詢。