面向路徑優(yōu)化的變分辨率柵格成本表面模型建模方法

劉 震,余 洋,李建松,肖少輝

1.武漢大學(xué)遙感信息工程學(xué)院,湖北武漢 430079;2.北京洛斯達(dá)科技有限公司,北京 100120

面向路徑優(yōu)化的變分辨率柵格成本表面模型建模方法

劉 震1,余 洋1,李建松1,肖少輝2

1.武漢大學(xué)遙感信息工程學(xué)院,湖北武漢 430079;2.北京洛斯達(dá)科技有限公司,北京 100120

成本表面模型是在連續(xù)空間中進(jìn)行路徑優(yōu)化的基礎(chǔ)。目前,在連續(xù)空間中進(jìn)行路徑優(yōu)化多是基于單分辨率成本表面模型的,但在使用該模型解決諸如輸電、調(diào)水、公路和鐵路、輸油輸氣等路徑優(yōu)化問(wèn)題時(shí),存在一些缺點(diǎn),例如數(shù)據(jù)冗余、計(jì)算成本高、易受地物“邊緣效應(yīng)”影響等。針對(duì)這些問(wèn)題,本文提出一種面向路徑優(yōu)化的變分辨率柵格成本表面模型,并詳細(xì)闡述這種數(shù)據(jù)模型的設(shè)計(jì)思想和建模方法。試驗(yàn)結(jié)果證明,該模型能有效地對(duì)地物密集度和地形復(fù)雜度進(jìn)行建模,解決單分辨率模型遇到的問(wèn)題。將該模型與傳統(tǒng)的單分辨率成本表面模型的計(jì)算結(jié)果進(jìn)行對(duì)比分析,表明本文建立的模型在多種環(huán)境下均能選出合理的路徑,且計(jì)算效率得到明顯提高。

地理信息系統(tǒng);路徑優(yōu)化;變分辨率;成本表面模型;建模

1 引 言

路徑優(yōu)化是指基于某些地理數(shù)據(jù)(柵格或矢量的),給定路徑的起點(diǎn)和終點(diǎn),以及有關(guān)約束條件,計(jì)算最優(yōu)(成本最低、時(shí)間最短、對(duì)環(huán)境影響最小等)線路的方法。路徑優(yōu)化分為兩種類型,一種是在離散空間中,基于預(yù)先定義的網(wǎng)絡(luò)數(shù)據(jù)模型,選擇一條最優(yōu)路徑,稱之為基于網(wǎng)絡(luò)的最優(yōu)路徑選擇,主要用于路徑網(wǎng)絡(luò)已經(jīng)存在的情況,例如,研究人員基于已知網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)分析[1-2],人們?cè)诔鲂袝r(shí)經(jīng)常會(huì)查詢線路[3]或使用導(dǎo)航服務(wù)[4]。另一種是在連續(xù)空間中,基于建立的成本表面數(shù)據(jù)模型選出一條最優(yōu)路徑,稱之為基于成本表面的路徑優(yōu)化,主要用于連續(xù)空間中的線路分析,例如,道路的規(guī)劃[5-8],輸電線路的選址[9-10],鋪設(shè)天然氣管線[11],有毒物質(zhì)擴(kuò)散路徑分析,野生動(dòng)物最佳遷移路徑分析[12],步行路徑的選擇[13-14]或運(yùn)用在生態(tài)學(xué)中[15-17]等。

基于網(wǎng)絡(luò)的最優(yōu)路徑選擇以圖論為基礎(chǔ),將尋找最優(yōu)路徑的問(wèn)題轉(zhuǎn)化為圖搜索問(wèn)題[18]。然而,圖論適合解決離散數(shù)據(jù)網(wǎng)絡(luò)的查詢問(wèn)題,不適合在連續(xù)空間中進(jìn)行路徑分析[19]。為了解決這個(gè)問(wèn)題,目前在連續(xù)空間進(jìn)行路徑優(yōu)化的常用方法是首先將這個(gè)連續(xù)空間進(jìn)行柵格化,劃分為相同大小的單元格,每個(gè)單元的值是經(jīng)過(guò)它的成本值或困難程度,這些單元格構(gòu)成了“成本表面模型”,如圖1所示;然后,根據(jù)選擇的鄰域模式,把成本表面中每個(gè)單元的中心或邊界上的點(diǎn)[20]看做是節(jié)點(diǎn),將每個(gè)節(jié)點(diǎn)與其鄰域中的節(jié)點(diǎn)看做是有邊相連,以經(jīng)過(guò)的節(jié)點(diǎn)的成本值的和作為邊的權(quán)重,這樣就可以將整個(gè)成本表面當(dāng)做是一個(gè)網(wǎng)絡(luò)加權(quán)圖;最后利用最優(yōu)路徑算法,在成本表面上就可以獲得一組從起點(diǎn)到終點(diǎn)的單元格,節(jié)點(diǎn)連線就是規(guī)劃出的最優(yōu)路徑。

圖1 單分辨率成本表面模型Fig.1 Single resolution cost surface model

上述過(guò)程生成的成本表面模型是規(guī)則鑲嵌的柵格數(shù)據(jù)模型,它的每個(gè)單元格的大小相同,稱之為單分辨率成本表面模型。單分辨率成本表面模型結(jié)構(gòu)簡(jiǎn)單,易于實(shí)現(xiàn),文獻(xiàn)[5—14,21—24]均使用的是這種模型。但該模型不能適應(yīng)它所表達(dá)的現(xiàn)象[25],在路徑優(yōu)化中使用會(huì)存在以下問(wèn)題:

(1)這種模型不能在有效表達(dá)地物密集度和地形復(fù)雜度的同時(shí)避免數(shù)據(jù)冗余。分辨率低時(shí),不能精確表達(dá)地物密集度或地形變化度,影響計(jì)算結(jié)果的準(zhǔn)確性。分辨率高時(shí),雖然能表達(dá)地物的密集度或地形變化度,但會(huì)造成數(shù)據(jù)大量冗余,增加計(jì)算成本。

(2)使用單分辨率成本表面經(jīng)常會(huì)遇到圖1中的情況。圖中A、B、C是3個(gè)面狀地物(如林地、居民地、自然保護(hù)區(qū)等等)。S是起點(diǎn),E是終點(diǎn)。理想的路線應(yīng)該是L1,但計(jì)算機(jī)選線時(shí)往往會(huì)繞道而行,走類似L2的路徑。這是由于當(dāng)?shù)匚锛词怪桓采w單元格的一部分時(shí),該單元格因?yàn)橛辛说匚锏某杀拘畔⒍鴮?dǎo)致計(jì)算機(jī)為了降低成本繞遠(yuǎn)路,稱這種現(xiàn)象為地物的“邊緣效應(yīng)”。

不規(guī)則鑲嵌的方式能避免數(shù)據(jù)冗余,適應(yīng)它所表達(dá)的對(duì)象[25]。文獻(xiàn)[17,26]采用不規(guī)則鑲嵌的方式分別構(gòu)建了不規(guī)則景觀圖和景觀模型,雖然這些模型適用于生態(tài)學(xué)中,不適于路徑優(yōu)化,但其思想具有借鑒意義。四叉樹(shù)結(jié)構(gòu)[27]是不規(guī)則鑲嵌中一種比較常用的方式,文獻(xiàn)[19,20]介紹了基于四叉樹(shù)的柵格數(shù)據(jù)模型,但是對(duì)其鄰域模式、成本值計(jì)算等缺乏探討。本文在以往研究的基礎(chǔ)上,基于四叉樹(shù)數(shù)據(jù)結(jié)構(gòu)的思想,采用不規(guī)則鑲嵌的方式,設(shè)計(jì)了一種面向路徑優(yōu)化的變分辨率柵格成本表面模型。本文詳細(xì)介紹了它的設(shè)計(jì)思想、鄰域模式、成本值計(jì)算方式,并將其與單分變率成本表面的選線結(jié)果進(jìn)行對(duì)比。

2 變分辨率柵格成本表面模型設(shè)計(jì)

相對(duì)于單分辨率成本表面模型,變分辨率成本表面模型是由相互鄰接、大小不同的單元格組成的。兩種模型都能用于路徑優(yōu)化,但由于它們采用不同的鑲嵌方式,繼而其實(shí)現(xiàn)原理、單元格的鄰域模式、成本值的計(jì)算方式都會(huì)有所差異。

2.1 基本原理

變分辨率柵格成本表面模型是基于四叉樹(shù)的思想構(gòu)建。四叉樹(shù)是一個(gè)分層的數(shù)據(jù)結(jié)構(gòu),它不斷地將那些具有多重性質(zhì)的單元格四分為大小相等的子單元格,直到所有的單元格都具有唯一的性質(zhì)(如該單元格只屬于居民地類)。圖2[25]是一個(gè)三值的8× 8的柵格層及其對(duì)應(yīng)的四叉樹(shù),從四叉樹(shù)圖中可以看出它是先將一個(gè)連續(xù)域細(xì)分為4個(gè)子域(NW、NE、SE、SW),然后對(duì)具有多重值的子域進(jìn)行不斷的分割。

圖2 四叉樹(shù)結(jié)構(gòu)Fig.2 Quad trees structure

在連續(xù)空間進(jìn)行路徑優(yōu)化需要考慮多種影響因素,如居民地、自然保護(hù)區(qū)、林地、耕地、規(guī)劃區(qū)、地質(zhì)情況、地形、氣象區(qū)、降雨量等,將連續(xù)空間以規(guī)則鑲嵌的方式柵格化后,某些因素不會(huì)完全覆蓋某些單元格或者某一因素(如地形)在某些單元格內(nèi)變化劇烈,這時(shí),就以四叉樹(shù)的方式來(lái)對(duì)這些單元格進(jìn)行細(xì)分。例如,在地物所在的區(qū)域,對(duì)與地物邊緣相交的單元格進(jìn)行細(xì)分,被地物完全包含的或不與地物鄰接的單元格不進(jìn)行細(xì)分;在地形起伏劇烈的地區(qū),如山地,對(duì)單元格進(jìn)行細(xì)分,在地形平坦的區(qū)域不進(jìn)行細(xì)分。這樣在地物的邊緣部分和山地的單元格就被劃分得很細(xì),能降低地物的“邊緣效應(yīng)”和有效表達(dá)地形復(fù)雜度,而在地物的內(nèi)部、地物稀疏的部分及平坦區(qū)域的單元格被劃分得較粗,避免了數(shù)據(jù)冗余。圖3即是基于這種設(shè)計(jì)思想所構(gòu)造的變分辨率柵格成本表面模型。

圖3 變分辨率柵格成本表面模型Fig.3 Variable-resolution cost surface model

2.2 單元格的鄰域模式

只有成本表面,卻沒(méi)有指定單元格的鄰域模式是不能進(jìn)行路徑分析的。因?yàn)檫@就像圖搜索中只給圖的節(jié)點(diǎn)但不給節(jié)點(diǎn)之間的邊一樣。單分辨率成本表面模型鄰域模式很多,有4、8、16、32等鄰域。變分辨率柵格成本表面模型的單元格大小不一,它的每個(gè)單元格的鄰域包含的單元格的個(gè)數(shù)都是不確定的,因此不能像單分辨率成本表面那樣以鄰域中單元格的個(gè)數(shù)來(lái)區(qū)分鄰域模式。

為了確定變分辨率成本表面中每個(gè)單元格的鄰域,本文以半徑為單元格邊長(zhǎng)的圓形區(qū)域作為該模型鄰域選擇的依據(jù)。如圖4所示,淺灰色單元格為深灰色單元格的鄰域,圖4(a)—(c)中的淺灰色單元格分別與1倍、1.5倍、2倍邊長(zhǎng)為半徑的圓內(nèi)部相交。圖4(a)中的鄰域單元格緊鄰深灰色單元格(邊緣相交),稱為單層鄰域,稱圖4(b)、圖4(c)中的鄰域?yàn)槎嘀剜徲颉?/p>

圖4 變分辨率表面模型的單元格鄰域模式Fig.4 The neighborhood pattern of variable resolution cost surface model

2.3 成本值計(jì)算

成本表面模型中每個(gè)單元格都存放著經(jīng)過(guò)該單元格的成本值。成本值是多種影響因素值與其相應(yīng)權(quán)重的乘積之和。在路徑規(guī)劃中,要考慮很多種影響因素,如居民地、道路、湖泊、河流等。每種影響因素的重要性不同,需分配不同的權(quán)重。

變分辨率成本表面的單元格成本值計(jì)算較為復(fù)雜。本文將其單元格成本值C分為地形成本值Cterrain(坡度、高程變化等地形相關(guān)因素所造成的成本值)和非地形成本值Cother。C由式(1)計(jì)算。wi和fi是第i個(gè)影響因素的權(quán)重和影響因素值,n為影響因素的個(gè)數(shù)

當(dāng)采用單層鄰域時(shí),單元格到其鄰域的成本值F( Cj,Ck)由式(4)計(jì)算,F( Cj,Ck)terrain, F(Cj,Ck)other分別為單元格到其鄰域的地形和非地形成本值。式中,Cj、Ck為單元格j、k的成本值;L為單元格j與k中心點(diǎn)間的空間距離;fdis為距離的權(quán)重;Emin為最小單元格的邊長(zhǎng);Ej、Ek為單元格j和k的邊長(zhǎng);Cterrainj、Cterraink為單元格j和k的地形成本;Cotherj、Cotherk為單元格j和k的非地形成本。

3 試驗(yàn)分析與應(yīng)用

為了測(cè)試該數(shù)據(jù)模型,選取了位于河北省承德市境內(nèi)的3塊不同區(qū)域作為試驗(yàn)數(shù)據(jù)。這3個(gè)試驗(yàn)區(qū)域分別是平坦區(qū)域、山地區(qū)域和平原山地混合區(qū),具有不同的地形和不同密度的地物。這3部分試驗(yàn)數(shù)據(jù)包含DEM、居民地、林地、耕地、道路等數(shù)據(jù)。

在試驗(yàn)中,單分辨率成本表面采用8鄰域模式,變分辨率成本表面采用單層鄰域,使用Dijkstra算法進(jìn)行路徑分析。在路徑分析中,主要會(huì)涉及地形、地表地物、距離3類影響因素。在地物影響因素中,居民地對(duì)通過(guò)它的路徑產(chǎn)生的成本值(阻抗值)往往會(huì)大于湖泊或河流等所產(chǎn)生的(由于路徑可能會(huì)對(duì)人體產(chǎn)生危害而遭抵制或會(huì)造成高昂的拆遷成本等),具有代表性;在地形因素中,坡度是最具代表性的。因此本文在路徑分析中只考慮“居民地”、“坡度”和空間距離3種因素。試驗(yàn)中各因素的權(quán)重取值范圍設(shè)定在[0, 1]之間,各因素權(quán)值是根據(jù)選線經(jīng)驗(yàn)多次試驗(yàn)得出的經(jīng)驗(yàn)值。

3.1 地物密集的平坦區(qū)域試驗(yàn)分析

第1個(gè)研究區(qū)域居民地密集、地形平坦,坡度對(duì)線路選址的影響可忽略不計(jì)。在該區(qū)域中線路既不能穿過(guò)居民地,又應(yīng)越短越好,居民地、距離對(duì)線路的影響相當(dāng),因此坡度、居民地、距離的權(quán)值依次為0、0.5、0.5。圖5(a)中灰色多邊形為居民地,灰色背景為DEM。圖5(b)—(d)以單元格成本值為背景,單元格的顏色越深成本越高。

圖5(b)中的路徑是在分辨率較低的單分辨率成本表面上進(jìn)行路徑規(guī)劃的結(jié)果,它們受到地物“邊緣效應(yīng)”的影響,為了避開(kāi)居民地而繞的很遠(yuǎn)。圖5(c)、圖5(d)中的路徑是在分辨率較高的單分辨率成本表面上和變分辨率成本表面模型上進(jìn)行路徑規(guī)劃的結(jié)果。它們規(guī)避了地物,并且比圖5(b)中的路徑短。表1中的數(shù)據(jù)表明,圖5(d)中成本表面的單元格數(shù)量和計(jì)算成本明顯低于圖5(c)中的。這說(shuō)明,在平原地區(qū),變分辨率成本表面不僅能像高分辨率成本表面那樣有效表達(dá)地物的邊緣部分,避免受到地物“邊緣效應(yīng)”的影響,而且還能避免數(shù)據(jù)冗余,降低計(jì)算成本。

圖5 地物密集的平坦區(qū)域選線結(jié)果Fig.5 Experiment results on a flat region with dense ground features

表1 平坦區(qū)域成本表面單元格數(shù)量與規(guī)劃路徑時(shí)間Tab.1 The number of cells and time consumed in path routing on a flat region

3.2 地物稀疏的山地區(qū)域試驗(yàn)分析

第2塊試驗(yàn)區(qū)地形起伏較大,居民地稀疏,路徑受“邊緣效應(yīng)”影響較小,受地形影響較大。在該區(qū)域內(nèi)線路應(yīng)盡量繞開(kāi)坡度較大的區(qū)域,避免穿過(guò)居民地,因此坡度和居民地的權(quán)重應(yīng)該賦予較大值,而距離的權(quán)重應(yīng)該較小,坡度、居民地、距離的權(quán)重依次為0.5、0.4、0.1。選線的結(jié)果如圖6所示。

圖6 地物稀疏的山地的選線結(jié)果Fig.6 Experiment results on a mountain area with sparse ground features

圖6(b)中的路徑是在分辨率較低的單分辨率成本表面上規(guī)劃出的結(jié)果,可以看出線路AB明顯經(jīng)過(guò)了陡峭的山地。在高分辨率成本表面上和變分辨率成本表面上規(guī)劃的路徑,在規(guī)避地物的同時(shí),都繞過(guò)了坡度較大的區(qū)域,如圖6(c)、圖6(d)所示。這是因?yàn)榈头直媛实某杀颈砻娌荒芫?xì)表達(dá)地形復(fù)雜度,而高分辨率或變分辨率成本表面模型能有效表達(dá)地形復(fù)雜度,使選出的路徑更加合理。從表2可知,相對(duì)圖6(c)、圖6(d)中的單元格數(shù)量和計(jì)算成本更少。這說(shuō)明在山地采用變分辨率成本表面模型不僅能有效表達(dá)地形復(fù)雜度,還能避免數(shù)據(jù)冗余和降低計(jì)算成本。

表2 山地區(qū)域成本表面單元格數(shù)量與規(guī)劃路徑時(shí)間Tab.2 The number of cells and time consumed in path routing on a mountain area

3.3 地形地物復(fù)雜區(qū)域試驗(yàn)分析

第3塊區(qū)域居民地密集、平原山地皆有。在該區(qū)域選取的路徑應(yīng)盡量避免通過(guò)地勢(shì)陡峭區(qū)域,避免穿過(guò)居民地,同時(shí)也應(yīng)較多顧及空間距離因素,坡度、居民地、距離權(quán)重依次設(shè)為0.5、0.38、0.12。圖7展示了該區(qū)域內(nèi)的選線結(jié)果。

該區(qū)域居民地密集,地形復(fù)雜,在低分辨率成本表面上很難得出有效路徑。圖7(b)中的AB路徑末端、CD路徑中部與尾部都跨越了山脈。在變分辨率和高分辨率成本表面上規(guī)劃出的路徑較為合理,既沒(méi)受到地物“邊緣效應(yīng)”影響也避過(guò)了地勢(shì)險(xiǎn)峻的地方,如圖7(c)、圖7(d)所示。圖7(c)、圖7(d)中的路徑基本一致,但是圖7(d)中的單元格數(shù)量和計(jì)算成本明顯低于圖7(c)中的,如表3所示。這說(shuō)明在地形地物復(fù)雜區(qū)域,變分辨率成本表面模型能在精確表達(dá)地形復(fù)雜度和地物密集度的同時(shí)降低數(shù)據(jù)冗余,提高計(jì)算效率。

表3 復(fù)雜區(qū)域成本表面單元格數(shù)量與規(guī)劃路徑時(shí)間Tab.3 The number of cells and time consumed in path routing on an area with complex terrain and dense ground features

3.4 應(yīng) 用

同單分辨率成本表面一樣,變分辨率成本表面模型也可以應(yīng)用于道路、管線、電力線路等方面路徑分析。本文根據(jù)某地實(shí)際數(shù)據(jù)進(jìn)行了輸電線路的路徑分析,將機(jī)選線路和人選線路進(jìn)行對(duì)比后發(fā)現(xiàn),人工線路與機(jī)選線路的最大偏離距離為400 m。這說(shuō)明雖然機(jī)選線路無(wú)法替代人工選線,但機(jī)選線路可以為人工選線提供向?qū)ё饔谩Ｔ谟?jì)算機(jī)選擇出線路后,選線人員即可在其400 m的緩沖區(qū)內(nèi)進(jìn)行選線,而不用在長(zhǎng)26 km、寬14 km的范圍內(nèi)盲選,這樣能提高人工選線的速度,降低人工選線的工作量。選線結(jié)果如圖8所示,圖中灰色虛線為人工選線,灰色實(shí)線為機(jī)選線路。機(jī)選線路和人工線路的偏離距離以L(單位:m)來(lái)表示,各L值所對(duì)應(yīng)的部分占機(jī)選線路的長(zhǎng)度比例如表4所示。

圖8 機(jī)選線路與人工線路Fig.8 Paths routed by computer and people

表4 各L值對(duì)應(yīng)部分在機(jī)選線路所占的長(zhǎng)度比例Tab.4 Length ratio on computer selected path corresponding to different L%

4 結(jié) 論

面向路徑優(yōu)化的變分辨率柵格成本表面模型基于四叉樹(shù)的思想構(gòu)建,該模型能有效適應(yīng)地形起伏和不同密集程度的地物。根據(jù)3個(gè)研究區(qū)域的試驗(yàn)結(jié)果可以得出以下主要結(jié)論:①基于該成本表面,選出的線路都是符合要求的,該成本表面能很好適用于平原、山地、地物密集或稀疏區(qū)等多種地形、地物環(huán)境;②與單分辨率成本表面相比,使用該模型進(jìn)行路徑優(yōu)化可以在精確表達(dá)地形起伏程度、地物密集度的同時(shí),避免數(shù)據(jù)冗余,降低計(jì)算成本;③使用該模型規(guī)劃出的路徑能夠避免地物“邊緣效應(yīng)”的影響。本文雖然將變分辨率成本表面應(yīng)用在電力線路的選擇中,但它在諸如鐵路、公路等線路的選址方面得到的應(yīng)用還較少,因此,采用這種成本表面進(jìn)行的選線應(yīng)用依舊是下一階段的研究重點(diǎn)。除此之外,在線路選址中,合適的鄰域模式能有效避免線路的失真,如何擴(kuò)展該模型的鄰域模式也是需要關(guān)注的一個(gè)方面。

致謝:感謝北京洛斯達(dá)科技有限公司提供試驗(yàn)數(shù)據(jù)以及智能選線項(xiàng)目組成員給予的技術(shù)協(xié)作。

[1] WANG Jiechen,MAO Haicheng,YANG Dezhi.United Structure of Point-Arc for Network Graph and It’s Application in GISs Shortest Path Searching[J].Acta Geodaetica et Cartographica Sinica,2000,29(1):47-51.(王杰臣,毛海城,楊得志.圖的節(jié)點(diǎn)-弧段聯(lián)合結(jié)構(gòu)表示法及其在GIS最優(yōu)路徑選取中的應(yīng)用[J]測(cè)繪學(xué)報(bào),2000,29 (1):47-51.)

[2] ZHENG Nianbo,LU Feng,LI Qingquan,et al.The Adaption of A?Algorithm for Least-time Pahts in Time-dependent Transportation Networks with Turn Delays[J].Acta Geodaetica et Cartographica Sinica,2010,39(5):534-539.(鄭年波,陸鋒,李清泉,等.顧及轉(zhuǎn)向延誤的時(shí)間依賴A?最短路徑算法[J].測(cè)繪學(xué)報(bào),2010,39(5):534-539.)

[3] LIU B.Route Finding by Using Knowledge about the Road Network[J].IEEE Transactions on Systems,Man,and Cybernetics,1997,27(4):436-448.

[4] FANG Z X,LI Q Q,ZHANG X,et al.A GIS Data Model for Landmark-based Pedestrian Navigation[J].International Journal of Geographical Information Science,2012, 26(5):817-838.

[5] COLLISCHONN W,PILAR J V.A Direction Dependent Least-Cost-Path Algorithm for Roads and Canals[J].International Journal of Geographical Information Science, 2000,14(4):397-406.

[6] YU C Q,LEE J,MUNRO-STASIUK M J.Extensions to Least-Cost Path Algorithms for Roadway Planning[J].International Journal of Geographical Information Science, 2003,17(4):361-376.

[7] SAHA A K,ARORA M K,GUPTA R P,et al.GISBased Route Planning in Landslide-Prone Areas[J].Inter-national Journal of Geographical Information Science, 2005,19(10):1149-1175.

[8] ATKINSON D M,DEADMAN P,DUDYCHA D,et al.Multi-Criteria Evaluation and Least Cost Path Analysis for an Arctic All-Weather Road[J].Applied Geography,2005, 25(4):287-307.

[9] MONTEIRO C,RAMIREZ-ROSADO I J,MIRANDA V,et al.GIS Spatial Analysis Applied to Electric Line Routing Optimization[J].IEEE Transactions on Power Delivery,2005,20(2):934-942.

[10] BAGLI S,GENELETTI D,ORSI F.Routeing of Power Lines through Least-Cost Path Analysis and Multicriteria Evaluation to Minimise Environmental Impacts[J].Environmental Impact Assessment Review,2011,31(3): 234-239.

[11] LIU Xuefeng,MENG Lingkui,LI Shaohua,et al.A Cheapest Route Analysis Based on Raster GIS and Its Application [J].Bulletin of Surveying and Mapping,2004(6):43-45.(劉學(xué)鋒,孟令奎,李少華,等.基于柵格GIS的最優(yōu)路徑分析及其應(yīng)用[J].測(cè)繪通報(bào),2004(6):43-45.)

[12] QIN Kun,GUAN Zequn,LI Deren,et al.The Best Route Analysis Based on Raster Data[J].Remote Sensing for Land and Resources,2002(2):38-41.(秦昆,關(guān)澤群,李德仁,等.基于柵格數(shù)據(jù)的最佳路徑分析方法研究[J].國(guó)土資源遙感,2002(2):38-41.)

[13] REES W G.Least-Cost Paths in Mountainous Terrain[J].Computers and Geosciences,2004,30(3):203-209.

[14] YAN Rui,LONG Yi,ZHENG Yue,et al.An Optimal Walking Path Algorithm Considering Terrain Influence [J].Geometics and Information Science of Wuhan University, 2012,37(5):564-569.(嚴(yán)瑞,龍毅,鄭玥,等.顧及地形起伏的步行最優(yōu)路徑分析算法[J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2012,37(5):564-569.)

[15] ADRIAENSEN F,CHARDON J P,DE BLUST G,et al.The Application of‘Least-Cost’Modelling as a Functional Landscape Model[J].Landscape and Urban Planning, 2003,64(4):233-247.

[16] RAYFIELD B,FORTIN M J,FALL A.The Sensitivity of Least Cost Habitat Graphs to Relative Cost Surface Values[J].Landscape Ecology,2010,25(4):519-532.

[17] ETHERINGTON T R.Least-Cost Modelling on Irregular Landscape Graphs[J].Landscape Ecology,2012,27(7): 957-968.

[18] MILLER H J,SHAW S L.Geographic Information Systems for Transportation[M].Oxford:Oxford University Press,2001.

[19] ANTIKAINEN H.Comparison of Different Strategies for Determining Raster-Based Least-Cost Paths with a Minimum Amount of Distortion[J].Transactions in GIS, 2013,17(1):96-108.

[20] BEMMELEN J V,QUAK W,HEKKEN M V,et al.Vector vs.Raster-Based Algorithms for Cross Country Movement Planning[R].Hague:TNO Physics and Electronics Laboratory,1993.

[21] GONCALVES A B.An Extension of GIS-Based Least-Cost Path Modeling to the Location of Wide Paths[J].International Journal of Geographical Information Science, 2010,24(7):983-996.

[22] XU J P,LATHROP R G.Improving Cost-Path Tracing in a Raster Data Format[J].Computers and Geosciences, 1994,20(10):1455-1465.

[23] XU J P,LATHROP R G.Improving Simulation Accuracy of Spread Phenomena in a Raster-Based Geographic Information System[J].International Journal of Geographical Information Science,1995,9(2):153-168.

[24] DOUGLAS D H.Least-cost Path in GIS Using an Accumulated Cost Surface and Slopelines[J].Cartographica: The International Journal for Geographic Information and Geovisualization,1994,31(3):37-51.

[25] HUISMAN O,BYROLF A D E.Principles of Geographic Information Systems[M].Enschede:ITC,2009.

[26] TISCHENDORF L.Modelling Individual Movements in Heterogeneous Landscapes:Potentials of a New Approach[J].Ecological Modelling,1997,103(1):33-42.

[27] FINKEL R A,BENTLEY J L.Quad Trees:A Data Structure for Retrieval on Composite Keys[J].Acta Informatica, 1974,4(1):1-9.

(責(zé)任編輯:宋啟凡)

A Variable-resolution Raster Cost Surface Model for Path Optimization

LIU Zhen1,YU Yang1,LI Jiansong1,XIAO Shaohui2

1.School of Remote Sensing Information Engineering,Wuhan University,Wuhan 430079,China;2.Beijing North-Star Technology Co.Ltd,Beijing 100120,China

The establishment of cost surface model forms the basis for conducting path optimization in continuous spaces.In most cases,path optimisation calculation in continuous spaces is based on a singleresolution cost surface model,which,however,would trigger problems in the meanwhile such as data redundancy,high computational costs,susceptibility to the“edge effect”of ground features,etc.,when it is applied in solving path optimisation problems regarding constructions of power lines,pipelines,roads, railways and so forth.With the purpose of solving the above-mentioned problems,a variable-resolution raster cost surface model is proposed for path optimisation,elaborating its design ideas and modelling method.The experimental results show that,by establishing this model,not only can the ground feature density and terrain complexity be modeled effectively,but the problems arising from the application of the single-resolution model can also be settled.After a comparative analysis on the calculation result of this model and that of the traditional single resolution cost surface model,findings show that the proposed model is capable of achieving reasonable paths in varied environments with high computational efficiency.Key words:GIS;path optimization;variable resolution;cost surface model;modeling

LIU Zhen(1987—),male,PhD candidate, majors in path planning,transmission line automatic tower spotting etc.

YU Yang

P208

A

1001-1595(2014)05-0474-07

國(guó)家科技支撐計(jì)劃(2012BAJ15B04);數(shù)字制圖與國(guó)土信息應(yīng)用工程國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室開(kāi)放研究基金(GCWD201203);中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金(2012213020211)

2013-09-05

劉震(1987—),男,博士生,主要從事路徑分析、輸電線路桿塔自動(dòng)排位等研究。

E-mail:xiaozhenliu111111＠163.com

余洋

E-mail:polestaryuchen＠yeah.net

LIU Zhen,YU Yang,LI Jiansong,et al.A Variable-resolution Raster Cost Surface Model for Path Optimization[J].Acta Geodaetica et Cartographica Sinica,2014,43(5):474-480.(劉震,余洋,李建松,等.面向路徑優(yōu)化的變分辨率柵格成本表面模型建模方法[J].測(cè)繪學(xué)報(bào),2014,43(5):474-480.)

10.13485/j.cnki.11-2089.2014.0085

修回日期:2014-03-15