基于地理國情監測數據的路徑規劃研究

梁子亮 付 超

(江蘇省基礎地理信息中心，江蘇 南京 210013)

1 概述

在測繪生產中，小比例尺地形圖調繪、地理國情監測等項目需要作業員進行外業巡查，即利用外業工作底圖實地進行核對、檢查；相片控制測量、放線測量等項目則需要作業員在盡可能短的時間內完成所有點狀要素的測繪工作。近年來，測繪工作參與到越來越多的自然資源調查中，以第三次全國國土調查為例，作業員需要以實地現狀認定地類的原則，對作業底圖中的圖斑實地核實確認圖斑地類，并標注信息，調繪圖斑邊界。在以上項目中，測繪外業路徑規劃將直接影響到工作的效率。如何進行路徑規劃，是圖論學科中的一個非常重要的研究方向。在實際應用中，路徑規劃不僅僅要解決尋找兩點之間最短距離的問題，還要考慮所遇到的阻抗，以求得到最快、最短甚至是最優的路徑，在確定最佳路徑時，所有成本屬性均可用作阻抗[1]。在本研究中，選擇時間作為阻抗，并添加部分約束條件用于適應不同的出行工具及天氣因素。在圖論中，有較多算法可以實現最短路徑的搜索, 最典型、最常用的算法為Dijkstra算法[2]，本文基于地理國情監測數據[3]，利用ArcGIS軟件，實現基于Dijkstra算法的外業路徑規劃。

2 試驗區概況

新沂市隸屬于徐州市，位于江蘇省北部，西邊與邳州市相鄰，東邊與沭陽縣及東?？h相鄰，南邊與宿遷市相鄰，北邊與山東省郯城縣相鄰。新沂市東西最大跨度為62.9 km，南北最大跨度為41.0 km，面積約1 592 km2。新沂是亞歐大陸橋東起第一座樞紐城市，隴海與新長、膠新鐵路，京滬高速與連霍高速、徐連高速公路，G205與S323，S249在新沂市形成了“三縱三橫”的交通網絡格局[4]。新沂市周邊80 km范圍內分布著徐州觀音機場、連云港白塔埠機場和山東臨沂機場，構成了快速便捷的立體交通網絡。本研究從地理國情監測資料中提取了新沂市的鄉村道路(LVLL)、城市道路(LCTL)及公路(LRDL)，并人為添加了863個測繪要素。

3 Dijkstra算法過程

目前在GIS應用領域[5,6]，路徑規劃所采用的算法主要是Dijkstra算法，其被用于計算一個要素到其他所有要素的最短的距離，適用于測繪外業的始點確定、作業路徑不確定的情況[7]。該算法可以簡述為：

設G=(V,E)是一個帶權有向圖，把圖中節點集合V分成兩組，第一組為已求出最短路徑的節點集合S，第二組為其余未確定最短路徑的節點集合U，按最短路徑長度的遞增順序把節點加入到S中，并保持從V到S中各節點的最短路徑長度不大于從V到U中任何節點的最短路徑長度。此外，每個節點對應一個距離，S中節點的距離就是從V到此節點的最短路徑長度，U中節點的距離，是從V到此節點只包括S中的節點為中間節點的當前最短路徑長度，其計算步驟可以簡述為[8]：

1)初始時，S只包含源點，即S={V}，V的距離為0。U包含除V外的其他節點，即:U={其余頂點}，若V與U中節點V有邊，則正常有權值，若U不是V的出邊鄰接點，則權值為∞；

2)從U中選取一個距離V最小的節點K，把K加入S中(即V到K的最短路徑長度)；

3)以K為新考慮的中間點，修改U中各節點的距離；若從源點V到節點U的距離(經過節點K)比原來距離(不經過節點K)短，則修改節點U的距離值，修改后的距離值的節點K的距離加上邊上的權；

4)重復步驟2)和3)直到所有節點都包含在S中[8]。

4 算法實現

4.1 測繪要素的聚合

類似于地理國情監測、國土調查等項目的測繪要素具有局部點位密度大的特點，為避免路徑中出現較多支路影響作業效率，需要對測繪要素進行一定的聚合。本研究提出按照道路格網結合點間距進行聚合的思路，并按照如下步驟執行：

1)提取地理國情監測成果中的鄉村道路、城市道路及公路的線狀圖層，并新建測繪要素點層；2)將三個道路圖層融合至一個線狀圖層；3)將步驟2)生成的線狀圖層轉為面狀圖層，并為圖層中的每個子面賦予唯一的標識碼；4)將步驟3)生成的面狀圖層的子面標識碼賦值于落入其中的測繪要素；5)將測繪要素按照步驟4)中標識碼屬性進行“點轉線”操作，生成線圖層；6)將步驟5)生成的線圖層轉點，該點應落于線內部；7)從測繪要素中剔除與步驟5)生成的線圖層相交的點；8)將步驟6)與步驟7)的兩個點層合并，生成最終的聚合點層。

經過上述的聚合操作，測繪要素由863個降低至573個，聚合前后的點位分布如圖1，圖2所示。

由圖1及圖2可見，經過點位聚合，測繪要素的局部密度大為降低，每個道路格網中僅保留了一個測繪要素，便于優化后續的路徑分析成果。

4.2 路徑規劃的實現

地理國情監測數據將鄉村道路分為了鄉村路、機耕路及農村硬化道路三種不同的類型，其中，鄉村路與機耕路一般不為硬化道路，鄉村路則較難被汽車通過。為設計更符合實際情況的路徑規劃，根據鄉村道路的三種類型，制定以下出行規則：1)陰雨天氣中，汽車及電動自行車可在城市道路、公路及農村硬化道路上通行，盡可能避免在機耕路上通行，禁止在鄉村路上通行；2)晴朗天氣中，汽車可在城市道路、公路、農村硬化道路及機耕路上通行，禁止在鄉村路上通行；3)晴朗天氣中，電動自行車可在所有道路上通行。

根據以上規則，將距離出發點最近的測繪要素作為起始點，進行最短路徑規劃，所得結果局部效果見圖3～圖5。

由圖3～圖5可知，本文實現了573個測繪要素在不同天氣因素及不同出行方式下的路徑規劃，其路徑長度分別為830.343 km，830.333 km及828.176 km，所得路徑不僅簡潔，更能滿足不同測繪生產任務的需求。

5 結語

本文對新沂市863個測繪要素進行了聚合，最終得到測繪要素573個，并基于天氣因素、出行工具及路況因素等約束件，利用Dijkstra算法提出了一種測繪外業路徑規劃方法。結果表明，與經驗判斷法相比，本文所得方法能夠有效提高工作效率，可為測繪外業路徑規劃提供參考。