一種基于柵格網(wǎng)的無路網(wǎng)路徑規(guī)劃方法

倪冰潔

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

0 引言

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

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

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

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

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

2 設計原理

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

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

無路網(wǎng)路徑規(guī)劃設計核心要點包含4 個步驟。

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

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

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

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

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

2.1 地理信息柵格化

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

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

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

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

圖3 柵格劃分原理

2.2 通行模型

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

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

2.3 通行時間柵格設計

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

圖4 柵格內通行距離計算設計

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

通行時間計算公式為:

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

表2 常見通行因子

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

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

圖5 通行時間柵格圖及最短路徑

3 結語

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