一種基于柵格網的無路網路徑規劃方法

倪冰潔

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

0 引言

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

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

1 地理信息系統

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

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

2 設計原理

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

圖1 無路網路徑規劃設計思路

無路網路徑規劃設計核心要點包含4 個步驟。

(1)地理環境柵格化:獲取目標區域的地理環境數據,并根據需求對地理環境進行柵格劃分,形成柵格網。

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

在不同地理環境下的通行速度模型。

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

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

2.1 地理信息柵格化

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

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

圖2 地理環境圖柵格劃分原理

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

圖3 柵格劃分原理

2.2 通行模型

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

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

2.3 通行時間柵格設計

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

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

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

通行時間計算公式為:

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

表2 常見通行因子

2.4 最優路徑計算

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

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

3 結語

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