最隱蔽路徑和最聚人氣路徑模型的求解研究

楊 琴，劉鵬程，羅 靜

（1.地理過程分析與模擬湖北省重點實驗室, 湖北 武漢 430079；2.華中師范大學 城市與環境科學學院,湖北 武漢 430079）

最隱蔽路徑和最聚人氣路徑模型的求解研究

楊 琴1,2，劉鵬程1,2，羅 靜1,2

（1.地理過程分析與模擬湖北省重點實驗室, 湖北 武漢 430079；2.華中師范大學 城市與環境科學學院,湖北 武漢 430079）

基于道路通行車輛對其周邊人口及環境的影響，提出最隱蔽路徑模型和最聚人氣路徑模型，詳細給出了兩種路徑成本屬性的計算方法和各種路徑具體求解過程。結合武漢市道路網進行實驗分析，比較了不同路徑下的距離、人口差異及其原因。結果表明，模型具有合理性和可操作性，可為軍事、金融、媒體、公交等路徑選擇提供理論參考和具體計算方法。

最低成本路徑；最隱蔽路徑；最聚人氣路徑

最低成本路徑是指在道路網絡中從起點到終點所耗費某類資源最少的弧段串，由于所考慮的資源類型不同，最低成本路徑可以是時間最短、距離最短、費用最低等路徑[1]。最低成本路徑在公眾出行、城市規劃、電力傳輸、交通管理、軍事調度等領域都有重要應用[2-5]。對于最低成本路徑的計算和選擇，國外研究較早，Stefanakis和Kavouras[6]早在1995年就基于DEM數據，以坡度為行進的阻抗，獲取了最快路徑。同樣基于柵格DEM數據，Lee和 Stucky[7]將通視域和最低成本路徑相結合，提出了最大可視域路徑的計算方法，保證選擇的路徑能目睹最大面積的區域。Chandio[8]等從經濟學的視角采用多成本決策標準，給出了山坡上最適宜發展路徑的計算方法。國內也有相關研究，如王卉[9]等針對雨霧天氣下的動態交通路徑問題，以能見度為考慮因素，構建了從起點到終點的最佳路徑，為人們在惡劣天氣下選擇道路提供了依據。王云鵬[10]等針對危險品運輸中的安全問題，提出了危險化學品運輸風險最小路徑模型。翁敏[11]等和廖楚江[12]等在考慮公交線路最少換乘和距離最短的基礎上，提出了最優出行路徑和算法，為居民日常出行提供了方便。

如今，物流業、公共交通以及公眾出行對路徑的選擇，除了考慮主體的需求和感受外，有時候也需要考慮所選擇的路線對周圍環境和居民的影響。例如，已確定起點和終點的公交運行線路的選擇，考慮更多的是居民乘車的方便；晚間超大貨運卡車路線的選擇，考慮更多的是最大限度減少受噪聲影響的人數。基于此，本文提出了最隱蔽路徑和最聚人氣路徑的概念，并給出了求解方法。一般而言，商業宣傳、物流、公交線路等會選擇最聚人氣路徑，來達到宣傳效果的最大化、物流運輸效率的最高化以及為更多人提供公共交通服務，而軍事調度、金融、危險品的運輸等則會選擇最隱蔽的路徑，以便運輸的隱蔽、安全以及盡量減少受影響居民的數量。

1 模型建立

1.1 最短路徑模型

對于用三元組G=＜V，E，W＞表示的路網，其中V是節點集合，E是弧段的集合，W為成本的集合。對于任何弧段ek=（vi，vj）∈E（k為弧段的標號）, W（ek）表示弧段ek的成本。最短路徑模型為[11]：

式中，W（P）為最小成本，P為對應的最小成本路徑。給定實際的距離值、影響人數及不同屬性作為弧段的成本，便可求出最短路徑、最隱蔽路徑以及其他路徑。式（1）常采用Dijkstra模型求解,其基本思路是由近及遠尋找起點到其他所有節點的最佳路徑，直至達到目標終點[12]。

1.2 成本計算

本模型網絡拓撲數據結構中各弧段的成本屬性為通行在該路段所影響的人數，該屬性的計算是本文兩類路徑求解的關鍵。

1.2.1 最隱蔽路徑成本計算

最隱蔽路徑是指從所選起點到終點影響人數最少的路徑。在最隱蔽路徑的求解中，必須根據城市一定行政區劃（如街道）的人口數量及分布計算路網中每個弧段的影響人數（W（ek））。

對道路網中的所有弧段作緩沖區分析，由于各等級道路的通行能力、影響范圍存在差別，因此緩沖區的寬度也不相同。表1第5列是本文擬定的各類道路緩沖區的寬度：國道等級最高，寬度為500 m；鄉道等級最低，寬度為150 m，道路等級越高，道路影響范圍越大。對于道路網中的弧段k，其緩沖區人口密度按其所在行政單元的人口密度計算，求得緩沖區人口數作為弧段k的W（ek）值。弧段屬性的具體計算過程如下：

1）計算各行政單元的人口密度：

式中， si表示某行政單元的面積；mi為某行政單元的人數；pi為人口密度。

2）計算緩沖區在某行政單元內的人數：

式中，xij表示緩沖區與某行政單元相交的面積；mij是緩沖區在該行政單元內的人數。

3）計算弧段k的緩沖區總人數：

將緩沖區在各行政單元的影響人數累加，求得該條道路k的影響人數，即道路k成本W（ek）。

1.2.2 最聚人氣路徑成本計算

最聚人氣路徑指從所選起點到終點，距離相對較短影響人數最多的路徑。最低成本路徑是求取成本累計和的最小值，因此無法直接求解，需要構造特定屬性值，本文以單位影響人數對應的長度作為屬性（如式（5））。該屬性值和影響人數屬性呈反向變化，即該屬性值越小，影響人數最多，以保證Dijkstra模型求解最短路徑的順利實施。

式中， w'（ek）表示新屬性；w（ek）表示弧段k的影響人數；Lk是道路k的長度。將道路長度與道路影響人數的比值作為成本，計算能使累計和達到最小的路徑即為最聚人氣路徑。要使累積和最小，即Lk數值相對小，而w'（ek）相對大。

2 案例介紹與分析

2.1 數據處理

選取武漢市道路網進行分析，包括國道、省道、縣道、鄉道、城區主干道及次干道。由于高速公路的封閉性，構建道路網絡時與其他道路不具備連通性，將其排除在外。武漢市面積8 494 km2，常住人口1 073 萬人（2010年）。道路總長約為6 000 km，人均道路長度約為0.72 m。在各等級道路中鄉道最長，城區主干道最短。因城區人口集聚，城區主次干道影響的總人數和單位長度影響人數最多。各等級道路長度、單位長度影響人數、緩沖寬度等屬性見表1。

表1 武漢市道路類型屬性表

本實驗在1∶40 000的比例尺下采用墨卡托投影建立數據庫，數據處理的具體步驟如下：

1）數據預處理。對武漢市行政區矢量化，道路數據在2009年武漢市公路地圖的基礎上參考Google地圖予以修正，利用ArcGIS 10.1對武漢市道路網配準、矢量化并進行拓撲檢查，正確構建拓撲關系，保證網絡的連通性。圖1為武漢中心地區不同等級道路圖。為進行網絡分析，預先進行了數據整理。

2）成本計算。將武漢市道路網按道路等級作緩沖分析，不同等級道路緩沖寬度參照表1。圖2為不同道路按等級建立的緩沖區。根據武漢市各鄉鎮街道人數（2010年），按式（2）計算出武漢市各鄉鎮街道的人口密度。

圖1 武漢市中心局部道路等級圖

圖2 道路分等級建立緩沖區

將緩沖區域作為各等級道路影響范圍，結合武漢市鄉鎮街道的人口密度數據進行疊加分析，求取各等級道路緩沖區域與鄉鎮街道相交的區域xij，根據式（3）計算各鄉鎮街道內道路緩沖區域人口數量mij。圖3是疊加分析后的效果圖，顏色越深，表示人口密度越高，顯然，武漢市中心城區道路人口密度最高。對mij累加求和得到道路弧段k的影響人數，作為最隱蔽路徑的成本。圖4給出了通過三維立體圖展示的路徑的成本（影響人數），圖中道路影響人數密度越大，高度越高。武漢市中心城區人口密度高，道路網密集，道路影響人口密度大。最聚人氣路徑的成本可在道路影響人數的基礎上計算得出，根據式（5）計算得出各道路長度與其影響人數的比值，作為最聚人氣路徑的成本。

圖3 道路緩沖區域人口密度

圖4 武漢局部道路單位長度人數三維顯示

2.2 實驗結果與分析

2.2.1 實驗結果

根據武漢市道路要素創建網絡數據集，分別以道路長度、道路影響人數以及距離與影響人數的比值（單位影響人數對應的路網長度）為成本計算起點與終點間的最短路徑、最隱蔽路徑和最聚人氣路徑，選擇了3個案例進行了實驗。案例1是夜間超大貨運卡車運輸路線問題，為減少卡車噪聲對周圍居民的影響，選擇走最隱蔽路徑。以武漢市體育中心為起點，武漢天河機場為終點進行計算。案例2是光谷廣場的某超市為確定超市接送車線路，需要選擇從光谷廣場到漢口火車站的路線，為最大限度地方便沿途顧客，需選擇一條影響人數最多的路徑即最聚人氣路徑。實驗中計算了光谷廣場到漢口火車站的最聚人氣路徑，同時計算出最短路徑、最隱蔽路徑作比較。案例3是政府為宣傳的需要，以湯遜湖生態旅游區與四美塘公園為起點和終點，為達到宣傳效果的最大化，宣傳車必須選取一條影響人數最多的路徑。實驗中對3條路線分別計算了最短路徑、最隱蔽路徑以及最聚人氣路徑，計算結果數據如表2所示。圖5中①表示最短路徑，②表示最隱蔽路徑，③表示最聚人氣路徑。

表2 實驗結果比較

從表2可知，案例1中最隱蔽路徑比最短路徑長11.52 km，但在影響人數上，只有最短路徑影響人數的40%；最隱蔽路徑比最聚人氣路徑長約6 km，但影響人數只是后者的1/3。由此可知，雖然最隱蔽路徑需要更長的距離到達目的地，但是影響人數卻大大減少，在實例1中為可行路線。案例2中最聚人氣路徑距離介于最短路徑和最隱蔽路徑之間，雖然比最短路徑長約50%，但是道路的影響人數達到62萬多，是最短路徑影響人數的2倍，最隱蔽路徑的5倍多。可見，選擇這條最聚人氣路徑才能為更多的顧客提供方便。對于人口密度高且相近的城區，如何選擇一條人口影響數量多的道路，有效性更為顯著。案例3中最聚人氣路徑影響人數最多，但距離只比最短路徑多5 km；最隱蔽路徑最長，但是影響人數遠低于最短路徑，占最短路徑影響人數的19%；最聚人氣路徑與最隱蔽路徑影響人數相差5倍多。宣傳車在循環行駛中可根據實際情況選擇合適的路線。

2.2.2 實驗分析

為驗證圖5路徑計算結果，通過圖6并結合表2中路徑所經區域平均人口密度對3個案例的路徑進行分析。圖6表示3個案例中各路徑從起點到終點依次經過的節點間道路單位長度影響的人數，其中橫坐標表示依次經過的道路的序號，即式（1）中的弧段標號 k。圖6a中3條路徑單位長度影響人數先增后減，符合案例1從武漢市體育館出發，經過中心城區到達郊區的天河機場，人口密度先高后低的實際情況；最短路徑與最聚人氣路徑單位長度影響人數的變化基本一致，因而在計算結果中2條路徑比較接近；最隱蔽路徑與其他2條路徑單位長度影響人數的差異先大后小，因而計算結果中前半段3條路徑各異，到后半段路徑出現重合部分。圖6b中3條路徑單位長度影響人數變化曲線無重合，因而路徑各異；3條路徑影響人數的趨勢都是先增后減再增，符合圖5計算結果從武昌到漢口，經過長江，人口密度變化為高低高的實際情況。圖6c中最隱蔽路徑與其他2條路徑所經區域人口密度的均值遠低于其他2條路徑，道路單位長度影響人數也最低，因而計算結果中與其他2條路徑的差異明顯；最短路徑與最聚人氣路徑道路單位長度影響人數的變化基本一致，故計算結果差異也較小。

圖5 路徑計算結果

綜合3個案例，雖然路徑所經道路單位長度影響人數是波動的，但總的來說，最隱蔽路徑所經區域人口密度值最低，單位長度影響人數也最低；最聚人氣路徑所經區域人口密度最高，影響人數也最多。由此可知，道路所經區域的人口密度與道路影響人數呈正相關。

通過模型的計算產生的最隱蔽路徑會選擇人口密度低的區域，經過的道路單位長度的影響人數都較低，因而影響的總人數也最低；最聚人氣路徑反之，且在3 個案例中路徑單位長度影響人數曲線都與最短路徑相近，保證了影響人數最多距離相對較短，表明模型建立的可行性。

圖6 路徑所經道路單位長度影響人數變化圖

3 結 語

為解決車輛多種路徑選擇需求的問題，本文提出了最隱蔽路徑和最聚人氣路徑模型，結合實例進行分析比較，驗證了模型的合理性和可操作性，在軍事、金融、物流、媒體、公交等路徑選擇決策時，具有一定的參考價值。

由于數據等方面的限制，模型尚有不完善之處：首先因高速道路的封閉性及處理中的復雜性，模型構建沒有將其包括在內。其次，缺乏詳細的道路行駛方向、單雙行道數據，模型沒有對此設限制。最后，未考慮人口的流動性，道路是否施工，能否通行等實際情況，模型的適用性還有局限。技術的發展與完善將進一步完善本文提出的道路影響人數的獲取方式。在大數據熱潮下，將可通過通信位置等方式，獲取道路影響人口的實時分布狀況，這也是下一步研究的重點。

[1] Effat H A, Hassan O A. Designing and Evaluation of Three Alternatives High Way Routes Using the Analytical Hierarchy Process and the Least-cost Path Analysis, Application in Sinai Peninsula, Egypt[J]. The Egyptian Journal of Remote Sensing and Space Sciences, 2013(16):141-151

[2] Adriaensen F. The Application of ‘Least-cost’ Modeling as a Functional Landscape Model[J]. Landscape and Urban Planning, 2003, 64(4):233-247

[3] Douglas D H. Least-cost Path in GIS Using an Accumulated Cost Surface and Slope Lines[J]. Cartographic: the International Journal for Geographic Information and Geovisualization, 1994, 31(3): 37-51

[4] Motemurro D, Barnett S, Gale T.GIS Based Process Helps TransCanada Select Best Route for Expansion Line[J]. Oil Gas,1998,96(25): 63-71

[5] Bagli S, Geneletti D, Orsi F. Routing of Power Lines through Least-cost Path Analysis and Multicriteria Evaluation to Minimize Environmental Impacts[J].Environ Impact Assessment Review, 2011(31):234-239

[6] Stefanakis E, Kavouras M. On the Determination of the Optimum Path in Space[J]. Spatial Information Theory a Theoretical Basis for GIS,1995,988:241-257

[7] Lee J, Stucky D.On Applying Viewshed Analysis for Determining Least-cost Paths on Digital Elevation Models[J].International Journal of Geographical Information Science, 1998,12(8):891-905

[8] Chandio,I A. Computer Application in Routing of Road Using Least-cost Path Analysis in Hillside Development[J]. Research Journal of Environmental and Earth Sciences,2012,4(10):907-911

[9] 王卉,郭健,闞映紅.GIS 中顧及能見度影響的最優路徑研究[J].測繪科學技術學報,2014, 31(2):185-189

[10] 王云鵬,孫文財.基于ArcGIS的危險品城市運輸路徑優化模型[J].吉林大學學報:工學版,2009,39(1):45-49

[11] 翁敏,毋河海,杜清運,等.基于公交網絡模型的最優出行路徑選擇的研究[J].武漢大學學報：信息科學版,2004,29(6):500-503

[12] 廖楚江,蔡忠亮,杜清運,等.基于最少換乘的公交最優路徑算法的設計與實現[J].武漢大學學報:信息科學版,2006,31(10):904-907

[13] 朱長青,史文中.空間分析建模與原理[M].北京:科學出版社,2006

[14] 劉湘南.GIS空間分析原理與方法[M].北京:科學出版社,2005

P208

B

1672-4623（2016）03-0056-04

10.3969/j.issn.1672-4623.2016.03.018

楊琴 ，碩士，研究方向為地理制圖與時空數據挖掘。

2015-04-21。

項目來源：國家自然科學基金資助項目（41371183）；教育部人文社科規劃資助項目（12YJAZH222）。