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

• • 上一篇    下一篇

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

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

  1. 华南师范大学地理科学学院, 广州 510631
  • 收稿日期:2015-06-29 修回日期:2015-08-17 出版日期:2016-02-10 发布日期:2016-02-04
  • 通讯作者: 罗文斐 E-mail:603798255@qq.com;luowenfei@m.scnu.edu.cn
  • 作者简介:

    作者简介:林浩嘉(1993-),男,广东揭阳人,本科生,主要从事地理信息科学研究。E-mail: 603798255@qq.com

  • 基金资助:
    国家级大学生创新创业训练计划项目(201410574039)

Hierarchical Optimal Path Algorithm Based on Multi-Storey Building Space

LIN Haojia(), LUO Wenfei*()   

  1. 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 E-mail:603798255@qq.com;luowenfei@m.scnu.edu.cn

摘要:

由于多层建筑空间相对于室外环境存在按楼层分层的三维空间特性,在室内路径分析中需考虑楼层空间位置信息对最优路径规划的影响,而传统基于节点之间的网络连通拓扑模型的最优路径规划方法并没有空间概念,不能很好地应用于室内路径分析。为此,针对室内最优路径规划问题,基于多层建筑空间的层次特性,采用分层结构化的方法,提出结构化动态网络分析模式,实现了室内分层最优路径算法。该算法将各楼层路网和楼层连接均视为独立结构,根据停靠点的楼层分布情况,逐楼层动态构建跨越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