EN中文

Journal of Geo-information Science >

2016 , Vol. 18 >Issue 2: 175 - 181

DOI: https://doi.org/10.3724/SP.J.1047.2016.00175

Orginal Article

Hierarchical Optimal Path Algorithm Based on Multi-Storey Building Space

  • LIN Haojia ,
  • LUO Wenfei , *
Expand
  • School of Geography, South China Normal University, Guangzhou 510631, China
*Corresponding author: LUO Wenfei, E-mail:

Received date: 2015-06-29

  Request revised date: 2015-08-17

  Online published: 2016-02-04

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Due to the stratified feature according to the floors in the multi-storey building space, the indoor path analysis is different from the outdoor path analysis, and the impact of floors, such as space location information, should be taken into consideration when the indoor optimal path planning is being carried out. However, the traditional optimal path planning method, which is based on network topology model between nodes, does not incorporate the space concept, which cannot be well applied to indoor path analysis. Aiming at solving the problem of indoor optimal path planning, based on the hierarchical characteristics of multi-storey building space, a structured dynamic network analysis model is put forward and the hierarchical optimal path algorithm is realized in this paper. In the algorithm, the network of each floor and the connections between floors are all regarded as independent structure. Firstly, the set of stops is divided into several sub sets according to the floor-distribution. Then, the stop distribution of the first floor is recorded and the first floor is regarded as the starting floor of the hierarchical optimal path analysis, and the path analysis for two consecutive floors is carried out floor by floor through dynamically constructing the structure network model spanning across every two consecutive floors. After that, the optimal path traversing all stops in the multi-storey building space is obtained. Compared to the traditional optimal path algorithm, the experimental results show that the proposed algorithm can obtain a more reasonable result for path planning, and the time efficiency is significantly improved. In addition, the structured dynamic network analysis model is more flexible, which allows to define specific floor conversion rules based on different requirements. The algorithm can be applied to large public buildings in cities, so that the indoor path analysis can be connected with the outdoor path analysis, making a more comprehensive path analysis.

Key words： multi-storey building space; TSP; structured network; dynamic network analysis; hierarchical optimal path

Cite this article

LIN Haojia , LUO Wenfei . Hierarchical Optimal Path Algorithm Based on Multi-Storey Building Space[J]. Journal of Geo-information Science, 2016 , 18(2) : 175 -181 . DOI: 10.3724/SP.J.1047.2016.00175

1 引言

空间网络分析（Spatial Network Analysis）是GIS空间分析的重要组成部分[1],包括路径分析、资源配置、连通分析、流分析等。其中,路径分析是核心问题[2],已被广泛应用于城市交通系统中。而城市交通系统的组成,除了作为主体部分的室外交通网络,还包括室内通行网络。随着地理网络分析在交通领域的深入应用,室外路径分析的研究已相对成熟,而室内路径分析仍有待开展。在全球科技和经济的快速发展下,高层建筑和大型公共建筑（如购物中心、商务大楼、图书馆、博物馆、飞机场、火车站、医院等）成为城市的主要组成部分,人在室内空间的活动范围和活动时间也相应增大,这使得室内路径分析的需求日益明显。一方面,在结构和功能错综复杂的大型公共建筑中,室内路径分析可使人们在陌生的室内环境中,通过最便捷的路径快速到达指定地点,提高效率;另一方面,城市大型公共建筑是人口密集场所,其潜在突发事件和各类事故发生的频率越高,而室内路径分析可在事故发生时提供紧急疏散和救援的最佳路径,挽救生命财产。因此,室内路径分析具有重要的现实意义。
室内路径分析与室外路径分析的不同之处在于室内的三维空间。传统的最优路径规划是基于节点之间的网络连通拓扑模型,也可用于三维空间中,如Lee[3-4]将室内三维实体（房间、门、过道等）统一抽象为节点,节点之间通过水平连接和垂直连接关系以图的形式建立三维网络连通拓扑模型,实现简单的路径分析。Stevens[5]等通过对二维的CAD数据建立点之间的三维拓扑关系来进行路径分析。Li[6]提出了基于概念格的室内模型,通过位置和出口之间的连接关系图,表明室内空间的连接关系。Becker[7]等将室内空间分为多个分别表达不同信息的层次,建立了多层次模型,其中的拓扑结构层表达了室内元素之间的拓扑关系。温永宁[8]等通过对房产数据特点的分析,以“路径”和“节点”为关键要素,表达楼宇内部的空间关系及拓扑结构,并应用于紧急疏散的楼宇路径构建中。但由于节点之间的网络连通拓扑模型,以连通权值表示各节点之间的连通性和连通成本,并没有空间概念,将其运用于三维空间中所得的路径将忽略空间上的位置信息,而室内路径分析中,需考虑楼层这一空间位置信息对最优路径规划的影响。另外,采用传统路径规划进行室内单楼层或几个楼层间的路径规划时,基于全局网络模型将增大问题规模,影响路径分析效率,特别是对于高层建筑。因此,要实现室内最优路径规划,首先,要构建能表达室内各位置连通性的网络模型,包括单楼层中和各楼层间的连通性;其次,在传统忽略空间位置信息的基于节点之间的网络连通拓扑模型的最优路径分析中,要考虑楼层信息对路径规划的影响,使所得路径规划结果更符合人的行为习惯;最后,算法还需有较好的效率,实现科学又高效的路径规划。
本文采用ArcGIS网络模型[9]进行三维空间网络模型的构建,采用分层结构化的方法,提出结构化动态网络分析模式,实现了室内最优路径规划算法。分层结构化动态网络可根据停靠点的分布情况,逐楼层动态构建跨越2个楼层的结构化网络模型,并以该网络模型进行跨楼层的路径分析,从而得到三维空间中遍历所有停靠点的最短旅行距离的最优路径。通过与传统最优路径算法比较,该算法得到的路径规划结果更符合人的行为习惯,并且在最优路径的解算上效率更高。其可应用于城市大型公共建筑中,让室内路径分析与室外路径分析进行对接,使路径分析更加全面。

2 三维最优路径问题

2.1 TSP问题及其算法

在最短路径分析中,最经典的算法是Dijkstra于1959年提出的按路径长度递增的次序产生最短路径的方法,可以给出从某定点到其他所有顶点的最短路径[2]。Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础,也是目前公认的求单源最短路径问题的最佳算法[10]。Zhan等曾对15种最短路径算法进行了测试,结果显示,Dijkstra算法是3种效果较好的算法之一,且最适合于计算两点间的最短路径问题[11]。而对于多点路径规划,假设集合V={V1,V2,…,Vn }为n个停靠点,从V1出发遍历这n个停靠点的路径是不同停靠点被访问的先后顺序的组合,共有(n-1)!种。最短路径为其中的某一种组合方式,如式（1）所示。
R = min ( R 1 , R 2 , … , R ( n - 1 ) ! ) （1）
式中：Ri表示第i种停靠点访问顺序的组合方式。而要得到最短路径所对应的组合方式,生成访问所有停靠点的最佳顺序,即旅行商问题（Traveling Salesman Problem,TSP）。TSP是一个组合NP（Non-deterministc Polynomial）难问题,难以获得其绝对最优解,通常求取相对最优解。对于TSP,国内外学者提出了多种启发式算法或近似算法的解算方法,如蚁群算法[12]、免疫算法[13]、遗传算法[14]、模拟退火算法[15]、贪心算法[16]、神经网络算法[17]、禁忌搜索算法[18]等,所得结果均为相对最优路径。例如,ArcGIS的Network Analyst扩展模块中,基于Dijkstra算法,通过在所有停靠点之间生成“起始-目的地”成本矩阵,然后基于禁忌搜索查找访问停靠点的最佳顺序,可在较短的时间内找到访问所有停靠点的最佳顺序,得到相对最优路径[19]。
在TSP的解算中,目前广泛认可的是基于Dijkstra算法的递推方法,进行最优路径分析时,从停靠点V1（起始点）出发,查找距离V1最近的停靠点V2,得到路径R(V1,V2);再从停靠点V2出发,查找距离V2最近的停靠点V3,得到路径R(V2,V3);依此类推,从停靠点Vi-1出发,查找距离Vi-1最近的停靠点Vi,得到路径R(Vi-1,Vi);直至得到R(Vn-1,Vn),最终得到遍历所有停靠点的路径（式（2））。
R ={R(V1,V2),R(V2,V3),…,R(Vn-1,Vn)} （2）
式中：n为停靠点总个数;R(Vi-1,Vi)表示2个停靠点之间的最短路径。

2.2 三维最优路径问题

与传统最优路径问题不同,在三维最优路径问题中,还需要考虑节点的层次信息（楼层）,同时,不同楼层之间只通过楼梯或电梯进行连接。当然,这可将三维空间中的各楼层路网看成二维中的部分路网,楼梯或电梯看成二维中的桥梁,以二维路径分析的方法来实现三维路径分析,得到基于全局网络模型的最优解R全局。然而,在全局路径分析中,楼层概念将被淡化,导致有可能会出现“低楼层-高楼层-中间楼层”或“低楼层-中间楼层-高楼层-中间楼层”的情况（图1）。要避免这种情况,可通过对楼层连接进行合理的权值定义（夸大楼层连接的连通成本）,但其基于全局网络,将增大问题规模,影响效率,显然不是最合理的方法。
Fig. 1 The situation of “low floor-high floor-middle floor”

图1 “低楼层-高楼层-中间楼层”情况

为此,通过在模型中引入层次的概念,该问题可表示为：假设停靠点分布在k个不同的楼层上,且各楼层停靠点数目分别为n1、n2、...、nk,将停靠点集V按停靠点所在楼层分为k个子集,则V = {V1,V2,…,Vk},其中,Vi表示分布在楼层i的所有停靠点所构成的集合,Vi = { Vi,1,Vi,2,…,Vi,ni};Vi,j为楼层i的第j个停靠点。根据式（1）,从Vi,1出发遍历楼层i的ni个停靠点,共有(ni-1)!种组合方式,则楼层i的最短路径为（式（3））：
Ri = min（Ri,1,Ri,2,…,Ri,(ni-1)!） （3）
式中:Ri,j表示楼层i的第j种停靠点访问顺序的组合方式。但是,所得路径结果中,Ri-1和Ri之间的楼层转换路径并不能表达,故式（3）只适用于起始楼层R1。对于其他楼层,需考虑楼层转换,可将Ri-1的终点加入到Vi 中,并作为起始点遍历Vi 中的所有停靠点,则遍历楼层i的ni个停靠点共有ni !种组合方式,根据式（1）和（3）,楼层i的最短路径为(式（4）)：
R i = min ( R i , 1 ， R i , 2 ， … ， R i , n i ! ) ( 1 ＜ i ≤ k ) min ( R i , 1 ， R i , 2 ， … ， R i , ( n i - 1 ) ! ) ( i = 1 ) （4）
因此,引入了层次概念后的分层多点路线规划的最优路径为（式（5））：
R = {R1,R2,……,Rk} （5）
式中：k为分布有停靠点的楼层数目。层次概念将多点路径规划抽象为多个TSP的解算,本文针对其提出分层最优路径算法。

3 分层最优路径算法

3.1 算法思想

(1) 分层结构化动态网络
分层最优路径算法采用结构化动态网络分析模式,将各楼层路网和楼层连接均视为独立结构,可根据停靠点的楼层分布,选择相应的路网数据动态地构建结构化网络模型并进行路径分析。设路网为N={N0,N1,N2,…,NK},其中,K为楼层总数,N0表示楼层连接（楼梯或电梯）,Ni表示楼层i的路网。当进行楼层i-1与楼层i之间的最优路径分析时,自动选取N={N0,Ni-1,Ni}路网集构建相应的结构化网络模型,以进行由楼层i-1至楼层i的最优路径分析。其相比基于全局网络模型的最优路径分析减小了问题规模。
(2) 跨楼层最优路径
基于分层结构化动态网络中由N={N0,Ni-1,Ni}路网集构建的结构化网络模型,进行由楼层i-1至楼层i的最优路径分析。设楼层i-1和楼层i的停靠点集分别为Vi-1= { Vi-1,1,Vi-1,2,…,Vi-1,ni-1 }和Vi = { Vi,1,Vi,2,…,Vi,ni},其中,Vi,j为楼层i的第j个停靠点。首先,进行楼层i-1的最优路径分析,采用式（2）的多点最优路径分析方法,得到Ri-1= {R(Vi-1,1,Vi-1,2),R(Vi-1,2,Vi-1,3),…,R(Vi-1,ni-1-1,Vi-1,ni-1)};然后,获取Ri-1的终点Vi-1,ni-1 并添加到Vi中,则Vi={Vi-1,ni-1,Vi,1,Vi,2,…,Vi,ni};最后,以Vi-1,ni-1 为起始点,进行楼层i的最优路径分析,得到Ri={R(Vi-1,ni-1,Vi,1),R(Vi,1,Vi,2),…,R(Vi,ni-1,Vi,ni)},即可得到由楼层i-1至楼层i的最优路径。
(3) 多楼层最优路径
根据上述跨楼层最优路径分析,进行多楼层最优路径分析。首先,将停靠点Vi,j按所在楼层分类,得到各楼层停靠点集Vi;然后,按一定楼层转换规则（可根据具体需求而定,此处以按楼层递增顺序进行说明）进行分层最优路径分析。设分布有停靠点的楼层F={F1,F2,…,Fk},首先,进行楼层F1的最优路径分析,若F1的停靠点个数大于1,则创建单层结构化网络,进行该楼层最优路径分析得到R1,再以R1的终点为楼层F2的起始点,遍历楼层F2所有停靠点,得到最优路径R2;若F1的停靠点个数等于1,则直接以该点为楼层F2的起始点,遍历楼层F2所有停靠点得R2。然后,进行楼层Fi（2<i≤k-1）的最优路径分析,在楼层Fi得出遍历该楼层所有停靠点的最优路径Ri后,以Ri的终点为楼层Fi+1的起始点,遍历楼层Fi+1所有停靠点,得到最优路径Ri+1,依此类推,即可得到按一定楼层转换规则遍历分布在各楼层的所有停靠点的最优路径（式（6））：
R分层 = {R1,R2,…,Rk} （6）
式中：Ri= {R(Vi-1,ni-1,Vi,1),R(Vi,1,Vi,2),…,R(Vi,ni-1, Vi,ni)},表示楼层Fi的最优路径。

3.2 算法实现

根据上述分析,可得算法1。
算法1
输入：路网N={N0,N1,N2,…,NK},停靠点集V。
定义：Floor表示楼层总数（等于K）,StarFloor表示路径分析起始楼层,EndFloor表示路径分析终止楼层,i表示路径分析当前楼层,初始化为1,V[i]表示各楼层停靠点集,Count[i]表示各楼层停靠点数目,Route[i]表示楼层i的最优路径,EndPoint表示Route[i]的终点,作为Route[i+1]的起始点。
输出：多楼层最优路径Route。
算法1步骤如下（图2）：
（1） 按楼层分类,得各楼层停靠点集V[i]和各楼层停靠点数目Count[i];
（2） 按楼层递增顺序,查找第一个分布有停靠点的楼层（Count[i] > 0）,若Count[i] > 1,则创建单层结构化网络N={Ni},进行该层最优路径分析,得到Route[i]并获取终点赋为EndPoint,并设置StarFloor = i;若Count[i] = 1,则将该停靠点赋为EndPoint,并设置StarFloor = i;
（3） i++,若i < Floor且Count[i] > 0,则设置EndFloor = i,将EndPoint加入到V[i]中;
（4） 创建跨楼层结构化网络N={N0,NStarFloor, NEndFloor},通过对V[i]进行跨楼层最优路径分析,得到Route[i];
（5） 获取Route[i]的终点赋为EndPoint,并设置StarFloor = i;
（6） 循环步骤（3）-（5）：进行其余分布有停靠点楼层的路径分析,直至i = Floor,得到遍历所有停靠点的多楼层最优路径Route。
Fig. 2 Flowchart of hierarchical structured dynamic network optimal path analysis

图2 分层结构化动态网络最优路径分析流程

3.3 算法结果分析

在时间复杂度的分析上,根据上述基于Dijkstra算法的递推方法,选取“查找最近停靠点”为主操作,每次操作相当于执行一次时间复杂度为O(n2)的Dijkstra算法,其中n为网络模型的节点规模,若有m个停靠点则需执行m次,总时间复杂度为O(mn2)[20]。设楼层总数为K,且各楼层节点规模分别为n1、n2、...、nK,停靠点分布于k个楼层上,且各楼层的数目分别为m1、m2、...、mk。对于全局路径分析,基于全局网络模型,总节点规模为 ∑ i = 1 K n i ,需执行次数为 ∑ j = 1 k m j ,则总时间复杂度为 O ( ∑ j = 1 k m j × ( ∑ i = 1 K n i ) 2 ) 。而对于分层结构化动态网络路径分析算法,每一次跨楼层最优路径分析均基于分层结构化网络,总结点规模为ni-1+ni,需执行次数为mi +1,则时间复杂度为 O ( m i + 1 ) ( n i - 1 + n i ) 2 ) ,而遍历所有停靠点最多需执行1次单楼层最优路径分析（F1的停靠点个数大于1时）和k-1次跨楼层最优路径分析,以执行k次跨楼层最优路径分析计算,则总时间复杂度为 O ( ∑ i = 1 k ( m i + 1 ) ( n i - 1 + n i ) 2 ) 。可见,分层结构化动态网络路径分析算法的时间复杂度与楼层总数K无关,在多楼层建筑中,分层结构化动态网络路径分析算法具有更小的时间复杂度。
在空间复杂度的分析上,全局路径分析算法采用全局规模的网络模型,其空间复杂度为 O ( ∑ i = 1 K n i ) ,而分层结构化动态网络路径分析算法,采用动态构建分层结构化网络的模式,并在每次路径分析后动态删除,再进行下一次的分层结构化网络动态构建,其空间复杂度为O(ni-1+ni)。

4 算法实验与应用实例

4.1 实验分析

据上述算法,基于ArcGIS Engine,采用C#语言,进行算法的系统实现并进行实验分析。
实验1：层数为20,各楼层节点数均为251,以几何距离定义节点之间的连通权值,楼层连接（楼梯）的连通成本不采取夸大（当前并无广泛认可的合理的夸大方法）。实验时通过不同的停靠点数目及分布情况的多组数据,每组数据均分别进行全局路径分析和分层结构化动态网络路径分析,并对2种路径规划结果进行比较与分析（表1）。此处以数据②通过图表详细说明（表2和图3）。实验中也有全局和分层2种方法路径规划结果相同的情况出现,在此不一一列举。由实验结果可见,2种路径分析方法所得路径在楼层顺序、停靠点到达顺序、楼梯选择、总长度和楼层转换成本均有可能不相同,原因如下：（1）全局路径分析中,根据式（2）,R(Vi-1,Vi)为从停靠点Vi-1出发,查找距离其最近的停靠点Vi所得到路径,最终到的R全局并不是绝对最短路径,而是满足各到达顺序上相邻的停靠点之间路径最短的相对最优路径;（2）分层结构化动态网络路径分析中,逐楼层进行动态路径分析,在完成楼层i的路径分析后,以终点为起始点在楼层i+1中开始查找距离其最近的停靠点,最终得到的R分层也并不是绝对最短路径,而是在保证楼层转换成本最小的条件下,满足各到达顺序上相邻的停靠点之间路径最短的相对最优路径。
Tab. 1 Comparison of path analysis results

表1 路径分析结果对比表

数据 停靠点数目 分布楼层数 方法 楼层顺序 总长度 / m 楼层转换成本 / W
① 2 2 全局 1-2 132.38 1
分层 1-2 132.38 1
② 4 3 全局 1-4-2 308.42 5
分层 1-2-4 311.12 3
③ 8 6 全局 1-2-7-5-10-12 805.34 15
分层 1-2-5-7-10-12 807.65 11
④ 16 10 全局 1-3-4-7-6-9-10-9-13-14-16 1361.98 19
分层 1-3-4-6-7-9-10-13-14-16 1357.10 15

注：W表示相邻两楼层间的转换成本

Tab. 2 The information of stops

表2 停靠点信息

停靠点 P1 P2 P3 P4
楼层 第1层 第1层 第2层 第4层
方位 南面 北面 东面 西面
Tab.3 Comparison of the execution time of path analysis

表3 路径分析执行时间对比表

数据 楼层总数K 停靠点分布楼层数k 停靠点数目∑j=1kmj T全局 (s) T分层 (s)
① 5 1 2 0.2012 0.2654
2 4 0.4722 0.5794
5 8 0.8504 1.4303
② 10 1 2 0.3903 0.2661
2 4 0.7811 0.5806
5 8 1.5632 1.4321
③ 20 1 2 0.8123 0.2668
2 4 1.6421 0.5864
5 8 3.3608 1.4322
10 16 6.7803 2.8802
④ 40 1 2 1.7011 0.2676
2 4 3.3203 0.5871
5 8 6.8415 1.4343
10 16 13.7352 2.8809
20 32 27.3613 5.8731

注：所有执行时间均通过多次进行求平均值,且包含起始楼层停靠点数目等于1或大于1的情况

Fig. 3 Comparison of path analysis results

图3 路径分析结果对比图

因此,2种路径分析方法所得结果均为相对最短路径,在不夸大楼层连接连通成本的情况下,总长度上并没有其中一种相对于另一种存在明显优势,但结合人的行为习惯,分层结构化动态网络路径分析所得到的路径规划结果更合理,其能使楼层转换成本最小。若以电梯为楼层连接方式,分层结构化动态网络路径分析将能使电梯乘坐次数和乘坐距离最小,减少时间成本。
实验2：实验数据为4组楼层总数不同的数据,4组数据的各楼层节点数均为112。实验时每组数据均通过不同的停靠点数目及分布进行多次路径分析,并对执行时间进行比较与分析（表3）。由实验结果可见,在全局楼层数较少的情况下,分层结构化动态网络分析在执行时间上并不占优;而当全局楼层数到达一定规模时,效率将明显提高,且其与停靠点分布楼层数相关,而与楼层总数无关。所以,分层结构化动态网络分析更适合较大规模的网络分析,可让多楼层建筑中的跨楼层路径分析更 高效。

4.2 应用实例

将该算法应用于图书馆服务与管理系统中,可向图书馆管理员和图书馆访问者提供书籍拿取（摆放）的最优路径规划服务,用户可根据实际需求选择楼梯或电梯（升降梯）模式,进行单点或多点的路径查询,直接得到遍历所需到达书架的最优路径,使书籍管理和书籍查找更直观高效（图4）。
Fig.4 Application of this algorithm in a library case

图4 在图书馆中的应用

5 结语

本文提出分层结构化动态网络模式,实现了多层建筑空间的分层最优路径算法。该算法相比于传统最优路径算法,具有以下特点：（1）更符合人的行为习惯,能使楼层之间的转换成本最小;（2）算法效率与楼层总数无关,更适合较大规模的网络分析,可让多层建筑中的跨楼层路径分析更高效;（3）由于该算法的结构化动态网络模式,可根据需求定义不同的楼层转换规则,更具灵活性。在应用方面,该算法可广泛应用于购物中心、商务大楼、图书馆、博物馆、飞机场、火车站、医院等城市大型公共建筑,让室内路径分析与室外路径分析进行对接,使路径分析更科学、全面、合理。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
黄杏元,马劲松,汤勤.地理信息系统概论[M].北京:高等教育出版社,1990:171-172.

[ Huang X Y, Ma J S, Tang Q.Introduction to geographic information system[M]. Beijing: Higher Education Press, 1990:171-172. ]

[2]
朱长青,史文中.空间分析建模与原理[M].北京:科学出版社,2006:115-121.

[ Zhu C Q, Shi W Z.Spatial analysis modeling and principle[M]. Beijing: Science Press, 2006:115-121. ]

[3]
Lee J.A 3D data model for representing topological relationships between spatial entities in built environments[D]. Columbus, OH: The Ohio State University, 2001.

[4]
Lee J.3D data model for representing topological relations of urban features[C]. Proceedings of the 21st Annual ESRI International User Conference, San Diego ,CA, USA, 2001.

[5]
Stevens M, Choi J.CAD data conversion to a node-relation structure for 3D sub-unit topological representation[J]. Journal of the Korean Geographical Society, 2006,41(2):188-194.

[6]
Li D, Lee D L.A lattice-based semantic location model for indoor navigation[C]. Proceedings of the Ninth International Conference on Mobile Data Management, IEEE Computer Society, 2008:17-24.

[7]
Becker T, Kolbe N T H. A multilayered space-event model for navigation in indoor spaces[J]. Lecture Notes in Geoinformation & Cartography, 2009:61-77.In this paper a new conceptual framework for indoor navigation is proposed. While route planning requires models which reflect the internal structure of a building, localization techniques require complementary models reflecting the characteristics of sensors and transmitters. Since the partitioning of building space differs in both cases, a conceptual separation of different space models into a multilayer representation is proposed. Concrete space models for topographic space and sensor space are introduced. Both are systematically subdivided into primal and dual space on the one hand and (Euclidean) geometry and topology on the other hand. While topographic space describes 3D models of buildings and their semantically subdivisions into storey鈥檚 and rooms, sensor space describes the positions and ranges of transmitters and sensors like Wi-Fi access points or RFID sensors. It is shown how the connection of the different layers of the space models describe a joint state of a moving subject or object and reduces uncertainty about its current position.

DOI

[8]
温永宁,张红平,闾国年,等.基于房产空间数据的楼宇空间疏散路径建模研究[J].地球信息科学学报,2011,13(6):788-796.紧急情况下人员快速、安全疏散是室内空间智能化导航和路径规划服务的研究热点.本文采用房产空间管理数据为数据源,以&quot;路径&quot;和&quot;节点&quot;为关键要素,设计了楼宇空间路径模型,用以表达楼宇内部的空间关系及拓扑结构.基于此模型进一步研究了用于紧急疏散的楼宇路径构建算法,论述了构建&quot;单楼层&quot;和&quot;多楼层&quot;路径过程中走廊(过道)路径提取、房间结点融合、楼宇三维路径模型构建等关键技术.最后设计了原型系统,集成寻径算法,验证了楼宇空间疏散路径建模的实用性.

DOI

[ Wen Y N, Zhang H P, Lv G N, et al.Estate spatial data based building space modeling for the evacuation route[J]. Journal of Geo-Information Science, 2011,13(6):788-796. ]

[9]
Zeiler M.Modeling our world: The ESRI guide to geodatabase design[M]. USA: ESRI Press, 2000:130-143.

[10]
何必,李海涛,孙更新.地理信息系统原理教程[M].北京:清华大学出版社,2010:150-151.

[ He B, Li H T, Sun G X.The principle of geographic information system[M]. Beijing: Tsinghua University Press, 2010:150-151. ]

[11]
Zhan F B.Three fastest shortest path algorithms on real road networks[J]. Journal of Geographic Information and Decision Analysis, 1997,1(1):69-82.

[12]
吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24:1328-1333.群居性昆虫行为的研究为计算机科学家提供了设计分布式控制和优化 算法的有力方法.对以蚁群算法为代表的群集智能的研究已经逐渐成为一个研究热点.该文首先在蚁群算法的基础上提出了相遇算法,提高了蚁群算法蚂蚁一次周游 的质量,然后将相遇算法与采用并行策略的分段算法相结合,提出一种基于蚁群算法的TSP问题分段求解算法.实验结果表明该算法有较好的有效性.

DOI

[ Wu B, Shi Z Z.An ant colony algorithm based partition algorithm for TSP[J]. Chinese Journal of Computers, 2001,24:1328-1333. ]

[13]
刘克胜,曹先彬,郑浩然,等.基于免疫算法的TSP问题求解[J].计算机工程,2000(1):1-2.

[ Liu K S, Cao X B, Zheng H R, et al. Solving TSP based on immune algorithm[J]. Computer Engineering, 2000(1):1-2. ]

[14]
高经纬,张煦,李峰,等.求解TSP问题的遗传算法实现[J].计算机时代,2004(2):19-21.TSP问题是一个典型的优化组合问题,现在有很多解决的方法.本文针对遗传算法求解TSP问题进行了研究,对选择、交叉和变异算子进行了算法设计,最后在Matlab软件上进行编程实现.结果表明,遗传算法在求解TSP问题时具有结果准确、收敛速度快等特点.

DOI

[ Gao J W, Zhang X, Li F, et al.Genetic algorithm for solving TSP problem[J]. Computer Era, 2004,2:19-21. ]

[15]
Meer K.Simulated annealing versus metropolis for a TSP instance[J]. Information Processing Letters, 2007,104(6):216-219.In a recent paper [I. Wegener, Simulated Annealing beats Metropolis in combinatorial optimization, in: L. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi, M. Yung (Eds.), Proc. ICALP 2005, in: LNCS, vol. 3580, 2005, pp. 589鈥601] Wegener gave a first natural example of a combinatorial optimization problem where for certain instances a Simulated Annealing algorithm provably performs better than the Metropolis algorithm for any fixed temperature. Wegener's example deals with a special instance of the Minimum Spanning Tree problem. In this short note we show that Wegener's technique as well can be used to prove a similar result for another important problem in combinatorial optimization, namely the Traveling Salesman Problem. The main task is to construct a suitable TSP instance for which SA outperforms MA when using the well known 2-Opt local search heuristic.

DOI

[16]
Gutin G, Yeo A.The greedy algorithm for the symmetric TSP[J]. Algorithmic Operations Research, 2007,1:33-36.We corrected proofs of two results on the greedy algorithm for the Symmetric TSP and answered a question in Gutin and Yeo, Oper. Res. Lett. 30 (2002), 97–99.

[17]
Cochrane E M, Beasley J E.The co-adaptive neural network approach to the euclidean traveling salesman problem[J]. Neural Networks, 2003,16(10):1499-1525.

[18]
Liu G Y, He Y, Qiu Y, et al.Research on influence of solving quality based on different initializing solution algorithm in tabu search[C]. IEEE 2002 International Conference on Communications, Circuits and Systems and West Sino Expositions, 2002:1141-1145.

[19]
ESRI. ArcGIS 10.2 for Desktop Help[M]. ArcGIS 10.2 for Desktop Help[M]. USA: ESRI Press, 2013.

[20]
Weiss M A.Data structures and algorithm analysis in C: second edition[M]. TX, USA: Addison-Wesley, 1997.

Options
Outlines

/

〈 〉