利用最短路径算法确定地理网络中心服务范围

胡于杰,李 响

(华东师范大学地理信息科学教育部重点实验室,上海 200062）

利用最短路径算法确定地理网络中心服务范围

胡于杰,李 响

(华东师范大学地理信息科学教育部重点实验室,上海 200062）

设施服务范围指在一定限制条件下(如时间、费用或路程等）设施所能提供服务的最大空间领域,在道路网络环境中,它通常由一系列结点及边组成[1]。例如,某救助站在接到求救电话后10 min所能到达的区域;某物流公司在配送货物时500元花费所能到达的区域等。在GIS中称寻找这类区域的问题为中心服务范围问题。对于中心服务范围的研究有助于解决消防站、学校及医院等公共设施的服务范围划分问题。传统方法(如广度优先遍历算法）通常用以服务设施所在位置为中心、以时间(或距离）为半径形成的圆形区域所构成的等时区(或等距区）表示服务范围。这种表示方法用直线距离评价通达性,只是一个概略的结果[2],不能反映从服务设施到需求点的实际通达情况。为此,本文在总结中心服务范围典型算法的基础上,提出利用最短路径算法确定中心服务范围的方法。

1 地理网络中心服务范围的形式化定义

中心服务范围是指从中心点出发,在限定条件下可达的区域,由一系列结点及边构成的网络子集:

其中,c代表网络的某个中心,N代表网络的结点集合,E代表边集合,ωc代表网络中心的限制费用,ωci为中心点c至网络结点i的累计费用,ωij为边eij的费用[3]。

从中心出发任意路径的费用不能超过中心的限制费用。在实际生活中,这种费用可以是时间、路程及花费的金钱等。

2 利用最短路径算法确定地理网络中心服务范围

2.1 数据存储结构

本文利用自定义的类结构存储网络结点及网络边,描述如下(为便于描述,下文将“费用”理解为“阻值”）:

该结构可以完整地反映网络中结点与其邻接结点及边的关系,能很好地反映网络的拓扑关系。在此基础上构建了结点间的关联矩阵,用于最短路径算法。

2.2 最短路径算法

本算法是对Dijkstra最短路径算法[4]的改进(简称“最短路径算法”）。首先,将网络中所有结点初始化为未标记结点,除中心外所有结点的阻值(即费用）赋为无穷大。然后从起点(第一次搜索的起点为网络中心）开始搜索与其有路径连通的未标记结点,赋以合理的阻值,并将起点标记为已标记结点,再以阻值不为无穷大的未标记结点为起点开始搜索,重复上述过程,直到某结点的阻值超过网络中心的阻值或所有结点均为已标记结点为止。最后,基于结点及边的阻值搜索并存储所有在中心阻值范围内的边,这些边和结点的集合为网络中心的服务范围。结合2.1中的数据结构,算法描述如下:

(1）将所有结点的dist置为∞,pre_node置为null,ischecked置为false;将起点from_node的dist置为0;定义网络中心阻值为distance。

(2）定义变量M IN_ID,用于存储每次搜索过程中起点的编号;定义变量M IND,用于存储上述结点的阻值。1）判断所有结点ischecked属性,若全为true,则跳出第2步;2）在所有ischecked属性为false的结点中搜索,若某结点nodei满足nodei.dist＜∞,则M IND=nodei.dist,M IN_ID=nodei. id;3）判断M IND与网络中心阻值distance的大小,若前者大于后者,则跳出第2步;4）令nodeMIN_ID.ischecked=true;5）在所有结点中搜索与编号为M IN_ID的结点有路径连通的结点nodej,若nodej.dist＞M IND+arck.im pedence(其中arck代表以nodei为起点,nodej为终点的边,编号为k）,则令nodej.dist=M IND+arck.im pedence;nodej.pre_node=nodeMIN_ID。

(3）对所有已标记结点进行判断。1）若网络中某条边arck满足如下关系:arck.node_from.id==from_node.id或arck.node_to.id==from_node.id,且arck.im pedence＜distance,则将边arck加入结果集中,即arck.isA dded=true;2）若边arck满足如下关系:arck.node_from.dist+arck.impedence＜distance或arck.node_to.dist+arck.im pedence＜distance,则将边arck加入结果集中,即arck.isA d ded=true。

本算法第1步为搜索过程初始化,第2步为结点赋阻值,第3步搜索并存储所有在中心阻值范围内的边。其中,即使某结点的ischecked属性为true,它仍可参加为其邻接结点赋最小阻值的运算过程,因此将不会产生“漏边”现象;而广度优先遍历算法在某结点被访问后,后续的遍历过程将不再考虑该结点,有可能产生“漏边”现象,需要大量的后续处理来弥补,从而增加了算法的运算时间。

3 应用实例

以美国加利福尼亚州部分县的道路交通网络为例,结合面向对象语言C#及A rcGIS Engine设计实现了利用最短路径算法确定地理网络中心服务范围系统,通过输入网络的中心及相应的阻值(本实验中为距离）,所有在中心服务范围内的道路均在地图上高亮显示。

在主频为3.0 GHz、内存为2 G、硬盘为160 G的环境中针对7组不同的数据进行实验,其数据量依次增大(表1）。为了比较结果的准确性及算法的运算效率,针对每组数据,随机选择一个网络结点作为中心位置,同时给定一个40 km的中心阻值,将最短路径算法和广度优先遍历算法[3]分别应用于上述7个数据集中,在道路网络数据量不断增大的情况下,两种算法的运算时间如图1a所示。

表1 实验用的7组数据

由图1a可知,随着道路网络数据量的增大,两种算法在计算网络中心服务范围过程中的运算时间逐渐增长。其中,最短路径算法的运算时间增长平稳,而广度优先遍历算法却出现了明显的“拐点”,自该拐点后,运算时间增幅急剧增大。以第7组数据集为例,最短路径算法的运算时间仅为广度优先遍历算法的4.9%,大幅提高了运算效率。为进一步分析中心阻值对算法运算效率的影响,选取第5组道路网络,并随机选取一个网络结点作为中心位置,依次给出25组数据,运行上述两种算法,比较运算时间,结果如图1b。

由图1b可知,当网络中心阻值小于14 km时,两种算法的运算时间基本接近;当网络中心阻值大于14 km后,随着网络中心阻值的增大,二者的运算时间均不断增长,但广度优先遍历算法的运算时间明显比最短路径算法的运算时间增幅大,且增幅随着网络中心阻值的增大不断变大。以中心阻值56 km为例,最短路径算法的运算时间仅为广度优先遍历算法的2.6%。

此外,为了解网络形态对算法运算效率的影响,同样以第5组网络数据为研究对象,通过给定中心阻值,变换中心位置,观察运算时间的变化。实验中,以道路网络不同区域的稠密程度来展现不同的网络形态,城市道路网密度是城市道路中心线总长度与城市用地面积之比[5],基于此定义,得到网络内不同区域的密度(表2）,在密度不同的区域中随机选择7个网络中心,并随机给定中心阻值36 km,分别利用两种算法计算网络中心服务范围,运算时间如图1c所示。

表2 7组数据所处区域的道路网络密度

图1 最短路径算法和广度优先遍历算法运算时间比较

以道路网络密度4 km/km2为界,根据表2可知,编号为1 378、2 498、3 007、5 261的点位于网络的稠密区,而其他3点位于网络的稀疏区。结合实际情况可得如下结论:在本组实验条件下,最短路径算法的运算效率比广度优先遍历算法高。以网络中心编号1 378的点为例,最短路径算法的运算时间为广度优先遍历算法的3.3%,而且,随着中心所处区域网络密度的变化,相对于广度优先遍历算法而言,最短路径算法的运算时间基本不变。

4 结论

本文提出了一种基于最短路径算法计算地理网络中心服务范围的新方法,针对同一网络数据集,最短路径算法比广度优先遍历算法所需时间更短,随着网络尺度或中心阻值的增大,二者运算时间均有提高,但广度优先遍历算法运算时间增幅远高于最短路径算法;当网络中心位置发生变化时,最短路径算法比广度优先遍历算法所需运算时间更少,运算效率更稳定。

本文提出的方法仅适用于单个中心服务范围的划分问题,当网络中存在多个中心点时,一种方法就是将其作为多个单中心问题分别解决,但当服务范围间存在竞争关系时,需同时考虑多个中心的影响,这将成为进一步的研究方向。

[1] 白玲,王家耀.基于GIS的地理网络模型研究[J].信息工程大学学报,2000,1(4）:96-98.

[2] 龚洁晖,白玲.确定地理网络中心服务范围的一种算法[J].测绘学报,1998,27(4）:357-362.

[3] 史照良,黄继安.基于特征的非平面 GIS-T数据模型在中心服务范围中的应用[J].现代测绘,2004,27(1）:3-6.

[4] D IJKSTRA E W.A note on two p roblem s in connexion w ith graphs[J].Numerische Mathematik,1959,1:269-271.

[5] 沈建武,吴瑞麟.城市道路与交通[M].武汉:武汉大学出版社, 2006.104-105.

2009-12-14;

2010-03-03

胡于杰(1987-）,男,硕士,研究方向为空间覆盖模型及优化算法。E-mail:hueujee@mail.com