多层建筑空间的分层最优路径算法实现

doi:10.3724/SP.J.1047.2016.00175

地球信息科学学报 ›› 2016, Vol. 18 ›› Issue (2): 175-181.doi: 10.3724/SP.J.1047.2016.00175

多层建筑空间的分层最优路径算法实现

林浩嘉(), 罗文斐^*()

华南师范大学地理科学学院, 广州 510631

收稿日期:2015-06-29 修回日期:2015-08-17 出版日期:2016-02-10 发布日期:2016-02-04
作者简介:
作者简介：林浩嘉(1993-),男,广东揭阳人,本科生,主要从事地理信息科学研究。E-mail: 603798255@qq.com
基金资助:
国家级大学生创新创业训练计划项目（201410574039）

Hierarchical Optimal Path Algorithm Based on Multi-Storey Building Space

LIN Haojia(), LUO Wenfei^*()

School of Geography, South China Normal University, Guangzhou 510631, China

Received:2015-06-29 Revised:2015-08-17 Online:2016-02-10 Published:2016-02-04
Contact: LUO Wenfei

摘要/Abstract

摘要：

由于多层建筑空间相对于室外环境存在按楼层分层的三维空间特性,在室内路径分析中需考虑楼层空间位置信息对最优路径规划的影响,而传统基于节点之间的网络连通拓扑模型的最优路径规划方法并没有空间概念,不能很好地应用于室内路径分析。为此,针对室内最优路径规划问题,基于多层建筑空间的层次特性,采用分层结构化的方法,提出结构化动态网络分析模式,实现了室内分层最优路径算法。该算法将各楼层路网和楼层连接均视为独立结构,根据停靠点的楼层分布情况,逐楼层动态构建跨越2个楼层的结构化网络模型并以该网络模型进行跨楼层的路径分析,从而得到多层建筑空间中遍历所有停靠点的最优路径。试验结果表明：相比传统最优路径算法,该算法在路径规划结果更加合理的情况下,时间效率有明显提高;另外,结构化动态网络分析模式可根据需求定义不同的楼层转换规则,更具灵活性。该算法可应用于城市大型公共建筑中,让室内路径分析与室外路径分析进行对接,使路径分析更科学、全面、合理。

关键词: 多层建筑空间, 旅行商问题, 结构化网络, 动态网络分析, 分层最优路径

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

林浩嘉, 罗文斐. 多层建筑空间的分层最优路径算法实现[J]. 地球信息科学学报, 2016, 18(2): 175-181.DOI:10.3724/SP.J.1047.2016.00175

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

图/表 7

图1

图2

表1

表2

表3

路径分析执行时间对比表

数据	楼层总数K	停靠点分布楼层数k	停靠点数目 $∑ j = 1 k m j$	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

表3

图3

图4

参考文献 20

[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. doi: 10.1007/978-3-540-87395-2_5
[8]	温永宁,张红平,闾国年,等.基于房产空间数据的楼宇空间疏散路径建模研究[J].地球信息科学学报,2011,13(6):788-796. doi: 10.3724/SP.J.1047.2011.00788
	[ 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. ] doi: 10.3724/SP.J.1047.2011.00788
[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. doi: 10.3321/j.issn:0254-4164.2001.12.014
	[ Wu B, Shi Z Z.An ant colony algorithm based partition algorithm for TSP[J]. Chinese Journal of Computers, 2001,24:1328-1333. ] doi: 10.3321/j.issn:0254-4164.2001.12.014
[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. doi: 10.3969/j.issn.1006-8228.2004.02.009
	[ Gao J W, Zhang X, Li F, et al.Genetic algorithm for solving TSP problem[J]. Computer Era, 2004,2:19-21. ] doi: 10.3969/j.issn.1006-8228.2004.02.009
[15]	Meer K.Simulated annealing versus metropolis for a TSP instance[J]. Information Processing Letters, 2007,104(6):216-219. doi: 10.1016/j.ipl.2007.06.016
[16]	Gutin G, Yeo A.The greedy algorithm for the symmetric TSP[J]. Algorithmic Operations Research, 2007,1:33-36.
[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.

停靠点	P1	P2	P3	P4
楼层	第1层	第1层	第2层	第4层
方位	南面	北面	东面	西面

多层建筑空间的分层最优路径算法实现

Hierarchical Optimal Path Algorithm Based on Multi-Storey Building Space

RichHTML

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 20

相关文章 0

Metrics

本文评价

推荐阅读 0

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