倪冰潔

(江蘇省測(cè)繪研究所,江蘇 南京 210013)

0 引言

各類商用導(dǎo)航軟件已經(jīng)成為民眾日常出行的必需品,尤其是其包含的路徑規(guī)劃及導(dǎo)航功能,能夠查找各類地址,提供駕車、騎行、步行等各類出行方式的路徑規(guī)劃能力,以及實(shí)時(shí)導(dǎo)航功能。 然而商用導(dǎo)航軟件主要針對(duì)城市路網(wǎng)進(jìn)行路徑規(guī)劃,能夠滿足城市出行使用,但無法滿足在特定地理環(huán)境下、特定人員及車輛的出行需求。 部分特種車輛在野外環(huán)境,如平原、山區(qū)、沼澤等,需要根據(jù)所駕駛車輛類型,規(guī)劃相關(guān)行駛路徑,從而達(dá)到快速到達(dá)某特定處所的目的,因而亟需一種路徑規(guī)劃方法,滿足此類使用需求。

本文針對(duì)特定場(chǎng)景下的路徑規(guī)劃需求,提出了一種基于柵格網(wǎng)的無路網(wǎng)路徑規(guī)劃方法,按照一定的大小對(duì)地理圖形進(jìn)行柵格化劃分,再針對(duì)每一個(gè)柵格,對(duì)耕地、林地、草地、戈壁、水域等不同地類計(jì)算通行時(shí)間,最終根據(jù)通行要求計(jì)算形成起始點(diǎn)、途經(jīng)點(diǎn)、結(jié)束點(diǎn)的最優(yōu)路徑。

1 地理信息系統(tǒng)

地理信息系統(tǒng)的定義是由兩個(gè)部分組成的。 一方面,地理信息系統(tǒng)是一門科學(xué),是描述、存儲(chǔ)、分析和輸出空間信息理論和方法的一門新興交叉學(xué)科。另一方面,地理信息系統(tǒng)是一個(gè)技術(shù)系統(tǒng),是以地理空間數(shù)據(jù)庫(kù)為基礎(chǔ),采用地理模型分析方法,適時(shí)提供多種空間和動(dòng)態(tài)的地理信息,為地理研究和地理決策服務(wù)的計(jì)算機(jī)技術(shù)系統(tǒng)[1]。

地理信息系統(tǒng)一般具有數(shù)據(jù)采集與輸入、數(shù)據(jù)編輯與更新、數(shù)據(jù)存儲(chǔ)與管理、空間查詢與分析、空間決策與支持等基本功能。 其中數(shù)據(jù)部分包含了大量的地理數(shù)據(jù),它表征地理圈或地理環(huán)境固有要素或物質(zhì)的數(shù)量、質(zhì)量、分布特征、聯(lián)系和規(guī)律等內(nèi)容。 常見的地理信息系統(tǒng)中所包含的地理數(shù)據(jù)包含了道路、水系、居民點(diǎn)、農(nóng)用地、特殊用地、林地、裸地等相關(guān)的數(shù)據(jù)[2]。 本文主要利用地理信息系統(tǒng)所包含的不同地形地類的數(shù)據(jù),以及地理信息系統(tǒng)提供的空間檢索分析方法,設(shè)計(jì)路徑規(guī)劃系統(tǒng)。

2 設(shè)計(jì)原理

現(xiàn)有路徑規(guī)劃功能均基于道路路網(wǎng)進(jìn)行規(guī)劃[3],但特殊情況下,所需要通過地域的成熟道路較少,通行時(shí)間要求比較高,通行方式不再局限于普通車輛,通行不再局限于在道路上通行,而是各類地形均可通行。 針對(duì)這種全地形、多通行工具的出行方式,設(shè)計(jì)了一種基于柵格網(wǎng)的無路網(wǎng)路徑規(guī)劃方法,主要設(shè)計(jì)思路如圖1 所示。

圖1 無路網(wǎng)路徑規(guī)劃設(shè)計(jì)思路

無路網(wǎng)路徑規(guī)劃設(shè)計(jì)核心要點(diǎn)包含4 個(gè)步驟。

(1)地理環(huán)境柵格化:獲取目標(biāo)區(qū)域的地理環(huán)境數(shù)據(jù),并根據(jù)需求對(duì)地理環(huán)境進(jìn)行柵格劃分,形成柵格網(wǎng)。

(2)設(shè)計(jì)通行模型:根據(jù)不同的通行工具,設(shè)計(jì)

在不同地理環(huán)境下的通行速度模型。

(3)計(jì)算通行時(shí)間柵格:根據(jù)地理環(huán)境柵格以及通行模型,計(jì)算某通行工具通過柵格所需要的時(shí)間,形成通行時(shí)間柵格圖。

(4)計(jì)算最優(yōu)路徑:根據(jù)通行時(shí)間柵格圖,從形成起點(diǎn)至終端的最短通行時(shí)間,所經(jīng)過的柵格集合為最優(yōu)通行路徑。

2.1 地理信息柵格化

地理信息柵格化是將地理信息服務(wù)所提供的各類地理環(huán)境圖層進(jìn)行柵格化劃分并對(duì)統(tǒng)一柵格內(nèi)的柵格地形進(jìn)行處理,主要有柵格劃分和柵格歸一化兩部分處理內(nèi)容。

柵格劃分是從物理上將地理位置進(jìn)行柵格化分割形成地理柵格圖,柵格可以是多種形式的,如正方形、正三角形等,本文以正方形的劃分方式進(jìn)行設(shè)計(jì)。柵格大小可以根據(jù)路徑規(guī)劃的精準(zhǔn)度需求進(jìn)行調(diào)整,如10 m×10 m、20 m×20 m 等,如圖2 所示,將地理環(huán)境圖所包含的道路、水網(wǎng)、耕地等各類地理圖層按20 m×20 m 大小劃分形成地理柵格。

圖2 地理環(huán)境圖柵格劃分原理

柵格歸一化處理是指在地理柵格劃分完以后,對(duì)地理柵格地形進(jìn)行歸一化處理,為后續(xù)計(jì)算通行時(shí)間做準(zhǔn)備。 以地理柵格內(nèi)所占權(quán)重面積最大的地形為主,各類地形的權(quán)重系數(shù)各不相同,劃分原理如圖3所示。

圖3 柵格劃分原理

2.2 通行模型

路徑規(guī)劃結(jié)果與所乘用的交通工具有著直接關(guān)系,交通工具所具備的能力與通行速度直接決定了路徑規(guī)劃的結(jié)果。 針對(duì)實(shí)際使用過程中的行駛需求以及常見的交通工具類型,設(shè)計(jì)通行模型。 通行模型以速度為主要因素,設(shè)定不同通行工具在不同地理環(huán)境下的通行速度[4],如表1 所示。

表1 各通行工具通行模型(單位:km/h)

2.3 通行時(shí)間柵格設(shè)計(jì)

通行時(shí)間是指通行工具在地理柵格中通行所需時(shí)間,以地理信息柵格劃分為基礎(chǔ)形成通行時(shí)間柵格,從而為后續(xù)計(jì)算最短通行時(shí)間做基礎(chǔ)。 根據(jù)正方形的地理信息柵格,計(jì)算通行時(shí)間可以考慮兩種方式,分別為對(duì)角線、對(duì)邊線,如圖4 所示。

圖4 柵格內(nèi)通行距離計(jì)算設(shè)計(jì)

對(duì)邊線方式,是地理信息柵格中通過的最短路徑,而對(duì)角線方式相對(duì)通行距離較長(zhǎng),可充分兼顧實(shí)際通行時(shí)所產(chǎn)生的額外通行距離。 因而本文計(jì)算通行距離時(shí),采取對(duì)角線方式。

通行時(shí)間計(jì)算公式為:

式中:T為通行時(shí)間;A為柵格的寬度;S為通行工具的平均通行速度;K為通行因子。 根據(jù)柵格地形因素額外增設(shè),如多種因素同時(shí)并存,考慮多個(gè)因子相乘,常見通行因子參見表2。

表2 常見通行因子

2.4 最優(yōu)路徑計(jì)算

按照2.1~2.3 所示方法,可計(jì)算每個(gè)柵格內(nèi)的通行時(shí)間,逐個(gè)計(jì)算地圖內(nèi)所有柵格的通行時(shí)間,形成地圖通行時(shí)間柵格圖。 在計(jì)算柵格與柵格之間如何通行時(shí),考慮以某柵格為中心,周邊8 個(gè)柵格通行時(shí)間最短的柵格為通行路徑。 在計(jì)算兩點(diǎn)之間最優(yōu)路徑時(shí),可轉(zhuǎn)化為計(jì)算兩點(diǎn)之間的最短通行時(shí)間,所經(jīng)過的柵格集合即為經(jīng)過分析規(guī)劃的最優(yōu)路徑[5],詳細(xì)過程如圖5 所示,圖中顏色變灰的柵格形成的路徑即為計(jì)算得出的最優(yōu)路徑。

圖5 通行時(shí)間柵格圖及最短路徑

3 結(jié)語

本文提供根據(jù)特種車輛在特殊場(chǎng)景下行駛所面臨的路徑規(guī)劃需求,提出了一個(gè)基于無路網(wǎng)的路徑規(guī)劃方法,采取“化整為零、化零為整”的總體思路,將地圖劃分為多個(gè)柵格進(jìn)行分析計(jì)算。 該方法可以彌補(bǔ)當(dāng)前商用導(dǎo)航無法在特殊地形下規(guī)劃路徑的不足,可以支撐特種車輛在特定需求下路徑導(dǎo)航的需求,具有較好的應(yīng)用意義。 但該方法還存在著一定的提升空間,如相關(guān)通行模型的參數(shù)、系數(shù)因子可進(jìn)一步校訂,所規(guī)劃的路徑需到現(xiàn)場(chǎng)進(jìn)行進(jìn)一步驗(yàn)證比對(duì),調(diào)整優(yōu)化參數(shù)及方法,從而滿足最終的使用需求。