盧云輝，曹健，孫曉茹

(大連市勘察測繪研究院有限公司，遼寧大連 116061)

1 背景

隨著人類文明的進(jìn)步，市政公共基礎(chǔ)設(shè)施(電力及電信設(shè)施網(wǎng)絡(luò)、道路交通、水網(wǎng)、熱力管網(wǎng)等)有了長足的發(fā)展。公共設(shè)施的維護(hù)、管理與規(guī)劃單憑人力已經(jīng)不能滿足要求，這就需要我們用計(jì)算機(jī)來進(jìn)行輔助工作。在GIS中，這些基礎(chǔ)設(shè)施可以被抽象理解為“網(wǎng)絡(luò)系統(tǒng)”。“網(wǎng)絡(luò)系統(tǒng)”是指由許多相互連接的線段構(gòu)成的網(wǎng)狀系統(tǒng)，網(wǎng)絡(luò)模型就是對(duì)現(xiàn)實(shí)世界中網(wǎng)絡(luò)系統(tǒng)的抽象表達(dá)［1］。例如在燃?xì)夤芫W(wǎng)中，管線等線狀物被抽象為線段，在網(wǎng)絡(luò)中稱為網(wǎng)絡(luò)弧段;閥門、三通等點(diǎn)狀物被抽象為點(diǎn)，在網(wǎng)絡(luò)中稱為網(wǎng)絡(luò)結(jié)點(diǎn)等。

網(wǎng)絡(luò)分析就是在網(wǎng)絡(luò)模型上通過相關(guān)算法解決實(shí)際問題的過程，如路徑分析、服務(wù)區(qū)分析、最近設(shè)施查找等。

2 網(wǎng)絡(luò)分析的基本概念

網(wǎng)絡(luò)是由若干線性實(shí)體互連而成的一個(gè)系統(tǒng)，資源由網(wǎng)絡(luò)來傳輸，實(shí)體間的聯(lián)絡(luò)也由網(wǎng)絡(luò)來達(dá)成。構(gòu)成網(wǎng)絡(luò)的最基本元素是線性實(shí)體以及這些實(shí)體的連接交匯點(diǎn)。前者常被稱為網(wǎng)線或弧段(link)，后者一般稱為結(jié)點(diǎn)(node)。

網(wǎng)線構(gòu)成網(wǎng)絡(luò)的骨架，是資源傳輸或通訊聯(lián)絡(luò)的通道，可以代表公路、鐵路、航線、水管、煤氣管、河流等;結(jié)點(diǎn)是網(wǎng)線的端點(diǎn)或網(wǎng)線匯合點(diǎn)，可以表示交叉路口、中轉(zhuǎn)站、河流匯合點(diǎn)等。

除了上述基本網(wǎng)絡(luò)元素之外，網(wǎng)絡(luò)還可能有若干附屬元素，如在資源分配中用來表示資源發(fā)散地點(diǎn)或資源匯聚地點(diǎn)的中心(center)，對(duì)資源傳輸或通訊聯(lián)絡(luò)起阻斷作用的障礙(barrier)等。

針對(duì)網(wǎng)絡(luò)分析的需要，作為網(wǎng)絡(luò)基本元素的網(wǎng)線和結(jié)點(diǎn)除自身的常規(guī)屬性外，還要具備一些特殊的屬性數(shù)據(jù)。比如，為了實(shí)施路徑分析和資源分配，網(wǎng)線數(shù)據(jù)應(yīng)包含正反兩個(gè)方向上的阻礙強(qiáng)度(如流動(dòng)時(shí)間、耗費(fèi)等)以及資源需求量(如學(xué)生人數(shù)、水流量等)，而結(jié)點(diǎn)數(shù)據(jù)也應(yīng)包括資源需求量。特別是在有些GIS平臺(tái)(如SuperMap，ArcGIS)中，結(jié)點(diǎn)還可以具有轉(zhuǎn)角數(shù)據(jù)，從而可以更加細(xì)致地模擬資源流動(dòng)時(shí)的轉(zhuǎn)向特性。具體地說，每個(gè)結(jié)點(diǎn)可以擁有一個(gè)轉(zhuǎn)向表(turntable)，其中的每一項(xiàng)說明了資源從某一網(wǎng)線經(jīng)該結(jié)點(diǎn)到另一網(wǎng)線時(shí)所受的阻礙強(qiáng)度。

圖1 轉(zhuǎn)向表示例圖

3 網(wǎng)絡(luò)模型介紹

在GIS中，雖然存在類型繁多的網(wǎng)絡(luò)，但根據(jù)其特質(zhì)歸納一下，主要可以分為以下兩種網(wǎng)絡(luò)模型:

(1)公共設(shè)施管線網(wǎng)絡(luò)

公共設(shè)施網(wǎng)絡(luò)是具有方向的網(wǎng)絡(luò)。即介質(zhì)(水流、電流等)會(huì)根據(jù)網(wǎng)絡(luò)本身的規(guī)則在網(wǎng)絡(luò)中流動(dòng)。例如水流的路徑是預(yù)先設(shè)定好的，它也可以改變，但這種改變不是由水流本身決定，而是由工作人員開關(guān)閥門來改變網(wǎng)絡(luò)的流向，即通過改變網(wǎng)絡(luò)的流通規(guī)則來實(shí)現(xiàn)的。

(2)交通網(wǎng)絡(luò)模型

交通網(wǎng)絡(luò)是沒有方向的網(wǎng)絡(luò)，這意味著流通介質(zhì)(行人或傳輸?shù)馁Y源)可以自行決定方向、速度和目的地。例如，司機(jī)在街道上開車行駛，他可以選擇轉(zhuǎn)彎的方向及行駛的方向等。同時(shí)也可以有一定的限制，例如，單行線、不允許左轉(zhuǎn)彎等，這與公共設(shè)施管線網(wǎng)絡(luò)完全不同。

網(wǎng)絡(luò)數(shù)據(jù)模型，就是將上述兩種模型數(shù)據(jù)化的成果，用于存儲(chǔ)網(wǎng)絡(luò)拓?fù)潢P(guān)系。網(wǎng)絡(luò)數(shù)據(jù)模型包含了網(wǎng)絡(luò)線數(shù)據(jù)集和網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)據(jù)集，還包含了兩種對(duì)象之間的空間拓?fù)潢P(guān)系。在SuperMap Object的網(wǎng)絡(luò)數(shù)據(jù)集中，線數(shù)據(jù)集為主數(shù)據(jù)集，點(diǎn)數(shù)據(jù)集為子數(shù)據(jù)集。通過模擬現(xiàn)實(shí)世界里相應(yīng)事物的相互關(guān)系來構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)集是使用SuperMap Object提供的網(wǎng)絡(luò)分析功能進(jìn)行網(wǎng)絡(luò)分析的前提。

4 網(wǎng)絡(luò)分析基本功能的實(shí)現(xiàn)

網(wǎng)絡(luò)分析能夠?qū)崿F(xiàn)的功能有很多，本文介紹幾種最常用的功能的實(shí)現(xiàn)。

4.1 最佳路徑分析

從網(wǎng)絡(luò)模型的角度看，最佳路徑求解就是在指定網(wǎng)絡(luò)中的兩結(jié)點(diǎn)間尋找一條阻礙強(qiáng)度最小的路徑，必須按照結(jié)點(diǎn)的選擇順序訪問網(wǎng)絡(luò)中的結(jié)點(diǎn)。“阻礙強(qiáng)度最小”有多種理解，如基于單因素考慮的時(shí)間最短、費(fèi)用最低、路況最佳等。

圖2 路徑分析示例圖

最佳路徑的產(chǎn)生基于網(wǎng)線和結(jié)點(diǎn)的阻礙強(qiáng)度。例如，如果要找最快的路徑，阻礙強(qiáng)度要預(yù)先設(shè)定為通過網(wǎng)線或在結(jié)點(diǎn)處轉(zhuǎn)彎所花費(fèi)的時(shí)間;如果要找費(fèi)用最小的路徑，阻礙強(qiáng)度就應(yīng)該是費(fèi)用。當(dāng)網(wǎng)線在順逆兩個(gè)方向上的阻礙強(qiáng)度都是該網(wǎng)線的長度，而結(jié)點(diǎn)無轉(zhuǎn)角數(shù)據(jù)或轉(zhuǎn)角數(shù)據(jù)都是0時(shí)，最佳路徑就成為最短路徑［2］。

具體實(shí)現(xiàn)的方法為soNetworkAnalyst類中的Find-Path方法:

soSelection FindPath(objNetworkDataset AssoDatasetVector，nFromNode As Long，nToNode As Long，bShortestOnly As Boolean)

objNetworkDataset為事先建立的網(wǎng)絡(luò)數(shù)據(jù)集，nFromNode和nToNode分別為所求路徑的起始結(jié)點(diǎn)和終止結(jié)點(diǎn)的ID號(hào)。

4.2 最近設(shè)施查找分析

最近設(shè)施分析是指在網(wǎng)絡(luò)上給定一個(gè)事件點(diǎn)和一組設(shè)施點(diǎn)(如學(xué)校、醫(yī)院、超市等公共設(shè)施)，為事件點(diǎn)查找以最小耗費(fèi)(時(shí)間或路徑)能到達(dá)的一個(gè)或幾個(gè)設(shè)施點(diǎn)，結(jié)果顯示從事件點(diǎn)到設(shè)施點(diǎn)的最佳路徑，耗費(fèi)，及行駛方向。

具體實(shí)現(xiàn)的方法為soNetworkAnalystEx類中的ClosestFacilityEx2方法:

BooleanClosestFacilityEx2(objEventAsVARIANT，objFacilitiesAs object，nFacilityCount As Long，objPath-ResultSetting As soPathResultSetting，objPathResultInfo As soPathResultInfo)

objEvent為事件點(diǎn)，objFacilities為設(shè)施點(diǎn)坐標(biāo)串，objPathResultSetting為最近設(shè)施查找結(jié)果設(shè)置，objPathResultInfo為最近設(shè)施查找結(jié)果信息。

4.3 連通性分析

人們常常需要知道從某一結(jié)點(diǎn)或網(wǎng)線出發(fā)能夠到達(dá)的全部結(jié)點(diǎn)或網(wǎng)線，或者兩結(jié)點(diǎn)之間是否存在一條連通的弧段。這一類問題稱為連通性分析。例如在新埋設(shè)一段管線時(shí)，可以先求得某區(qū)域是否與主管線連通，再?zèng)Q定埋設(shè)的范圍。

具體實(shí)現(xiàn)的方法為soNetworkAnalyst類中的Find-ConnectedNodes方法:

soSelectionFindConnectedNodes(objNetworkDataset As soDatasetVector，nNode As Long，nDirection As sePathFindingDirection，nLevel As Long)

nNode為網(wǎng)絡(luò)數(shù)據(jù)集中某結(jié)點(diǎn)的ID，基于該結(jié)點(diǎn)查找所有在等級(jí)內(nèi)與其連通的結(jié)點(diǎn)。nDirection為通達(dá)點(diǎn)查找的方向。

將得到的結(jié)果數(shù)據(jù)集與待分析的另外一點(diǎn)進(jìn)行比對(duì)，如果該點(diǎn)在結(jié)果數(shù)據(jù)集中，則兩點(diǎn)連通，反之則不連通。

4.4 上游追蹤分析

如圖3，假設(shè)以水流代表設(shè)施網(wǎng)絡(luò)中流動(dòng)的物質(zhì)，Q點(diǎn)是一個(gè)匯點(diǎn)，那么Q點(diǎn)將接收水流的輸入，流向如圖中的箭頭所示的方向，那么，圖中的 A、B、C、L、E、F、G 結(jié)點(diǎn)都是Q點(diǎn)的上游結(jié)點(diǎn)，也稱為Q點(diǎn)的上游，因?yàn)閺倪@些結(jié)點(diǎn)流出的水最后都流入了Q點(diǎn);而弧段AB、BC、CL、LQ、EB、FG、GL是Q點(diǎn)的上游弧段，也稱為Q點(diǎn)的上游。

圖3 上游分析示意圖

在爆管分析中，經(jīng)常用到上游追蹤分析:通過對(duì)管線損壞點(diǎn)進(jìn)行上游追蹤分析計(jì)算，可以求得須關(guān)閉的最少閥門數(shù)。具體實(shí)現(xiàn)方法為soNetworkAnalystEx類中的UpStream方法:

Boolean UpStream(nTraceOriginID As Long，strDirectionField As String，objArcIDs As soLongArray)

nTraceOriginID為上游追蹤分析起點(diǎn)的ID號(hào)，str-DirectionField為流向字段，objArcIDs為結(jié)果上游弧段的ID數(shù)組。根據(jù)弧段的屬性字段得出上游的閥門ID號(hào)，然后通過查詢比對(duì)求出需關(guān)閉的閥門ID號(hào)。

圖4 爆管分析示例圖

4.5 下游追蹤分析

如圖5，類似于上游追蹤分析，假設(shè)以水流代表設(shè)施網(wǎng)絡(luò)中流動(dòng)的物質(zhì)，Q點(diǎn)是一個(gè)源點(diǎn)，水流將從Q點(diǎn)流出，流向如圖中的箭頭所示的方向，那么，圖中的A、B、C、L、E、F、G 結(jié)點(diǎn)都是 Q 點(diǎn)的下游結(jié)點(diǎn)，也稱為 Q點(diǎn)的下游，因?yàn)閺倪@些結(jié)點(diǎn)接收了Q點(diǎn)流出的水;而弧段 BA、CB、LC、QL、BE、GF、LG 是 Q 點(diǎn)的下游弧段，也稱為Q點(diǎn)的下游。

圖5 下游分析示意圖

在關(guān)閉某閥門后，如得知受到影響的所有下游區(qū)域，此時(shí)就需要用到下游追蹤分析。具體實(shí)現(xiàn)方法為soNetworkAnalystEx類中的DownStream方法:

Boolean DownStream(nTraceOriginID As Long，str-DirectionField As String，objArcIDs As soLongArray)

nTraceOriginID為下游追蹤分析起點(diǎn)的ID號(hào)，str-DirectionField為流向字段，objArcIDs為結(jié)果下游弧段的ID數(shù)組。結(jié)果中的下游弧段及其相關(guān)的結(jié)點(diǎn)即為受閥門關(guān)閉影響的區(qū)域。

圖6 影響區(qū)域分析示例圖

5 總結(jié)

本文以SuperMap Object的網(wǎng)絡(luò)分析接口為例，介紹了一些網(wǎng)絡(luò)分析的基本應(yīng)用方式。網(wǎng)絡(luò)分析應(yīng)用上的普及，大大簡化了以前那些需要手動(dòng)計(jì)算分析管理的工作內(nèi)容，在各行各業(yè)中都發(fā)揮了相當(dāng)重要的作用。目前，網(wǎng)絡(luò)分析已經(jīng)廣泛地應(yīng)用于電子導(dǎo)航、交通旅游、城市規(guī)劃管理、物流運(yùn)輸以及電力、通訊、等各種管線管網(wǎng)的布局設(shè)計(jì)和查詢分析中，對(duì)于現(xiàn)代化的城市空間網(wǎng)絡(luò)的數(shù)據(jù)管理有著重要的意義。

［1］超圖公司．SuperMap Objects Java 6R技術(shù)文檔——網(wǎng)絡(luò)分析［R］．

［2］曾文，徐世文．地理信息系統(tǒng)中的常規(guī)網(wǎng)絡(luò)分析功能及相關(guān)算法［J］．地球科學(xué)·中國地質(zhì)大學(xué)學(xué)報(bào)，1998(04)．

［3］Minieka E;李家瀅，趙關(guān)旗譯．網(wǎng)絡(luò)和圖的最優(yōu)化算法［M］．北京:中國鐵道出版社，1984．

［4］孟亞峰，張淑英．城市地下綜合管網(wǎng)地理信息系統(tǒng)［J］．工程設(shè)計(jì)CAD與智能建筑，2002(02)．

［5］張成才，孫喜梅，黃慧．SDE的實(shí)體——關(guān)系模型空間數(shù)據(jù)管理方式研究［J］．計(jì)算機(jī)工程與應(yīng)用，2003(02)．

［6］陳勇民，陳治安．基于GIS的城市排水管網(wǎng)規(guī)劃及管理系統(tǒng)的開發(fā)研究［J］．湖南大學(xué)學(xué)報(bào)，2002，29(3)．