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

楊 琴，劉鵬程，羅 靜

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

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

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

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

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

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

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

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

1 模型建立

1.1 最短路徑模型

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

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

1.2 成本計算

本模型網(wǎng)絡(luò)拓撲數(shù)據(jù)結(jié)構(gòu)中各弧段的成本屬性為通行在該路段所影響的人數(shù)，該屬性的計算是本文兩類路徑求解的關(guān)鍵。

1.2.1 最隱蔽路徑成本計算

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

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

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

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

2）計算緩沖區(qū)在某行政單元內(nèi)的人數(shù)：

式中，xij表示緩沖區(qū)與某行政單元相交的面積；mij是緩沖區(qū)在該行政單元內(nèi)的人數(shù)。

3）計算弧段k的緩沖區(qū)總?cè)藬?shù)：

將緩沖區(qū)在各行政單元的影響人數(shù)累加，求得該條道路k的影響人數(shù)，即道路k成本W(wǎng)（ek）。

1.2.2 最聚人氣路徑成本計算

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

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

2 案例介紹與分析

2.1 數(shù)據(jù)處理

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

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

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

1）數(shù)據(jù)預(yù)處理。對武漢市行政區(qū)矢量化，道路數(shù)據(jù)在2009年武漢市公路地圖的基礎(chǔ)上參考Google地圖予以修正，利用ArcGIS 10.1對武漢市道路網(wǎng)配準、矢量化并進行拓撲檢查，正確構(gòu)建拓撲關(guān)系，保證網(wǎng)絡(luò)的連通性。圖1為武漢中心地區(qū)不同等級道路圖。為進行網(wǎng)絡(luò)分析，預(yù)先進行了數(shù)據(jù)整理。

2）成本計算。將武漢市道路網(wǎng)按道路等級作緩沖分析，不同等級道路緩沖寬度參照表1。圖2為不同道路按等級建立的緩沖區(qū)。根據(jù)武漢市各鄉(xiāng)鎮(zhèn)街道人數(shù)（2010年），按式（2）計算出武漢市各鄉(xiāng)鎮(zhèn)街道的人口密度。

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

圖2 道路分等級建立緩沖區(qū)

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

圖3 道路緩沖區(qū)域人口密度

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

2.2 實驗結(jié)果與分析

2.2.1 實驗結(jié)果

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

表2 實驗結(jié)果比較

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

2.2.2 實驗分析

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

圖5 路徑計算結(jié)果

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

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

圖6 路徑所經(jīng)道路單位長度影響人數(shù)變化圖

3 結(jié) 語

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

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

[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 中顧及能見度影響的最優(yōu)路徑研究[J].測繪科學(xué)技術(shù)學(xué)報,2014, 31(2):185-189

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

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

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

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

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

P208

B

1672-4623（2016）03-0056-04

10.3969/j.issn.1672-4623.2016.03.018

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

2015-04-21。

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