Research on route search based on improved Dijkstra algorithm
-
摘要: 进路搜索是计算机联锁的核心部分,其准确性及高效性对保证行车安全至关重要。建立铁路站场结构的有向图模型,将站场进路搜索问题转化为有向图的遍历问题;根据铁路站场简化图的特点,从数据存储结方式和队列结构2个方面改进传统Dijkstra算法,采用广度优先搜索方式,提出以最短路径为目标函数的进路搜索策略;编制仿真程序对该算法进行验证,结果表明:基于改进Dijkstra算法能够正确、高效地完成多种类别进路搜索。
-
关键词:
- 进路搜索 /
- 有向图 /
- Dijkstra算法 /
- 最短路径
Abstract: Route searching is one of the core parts of computer interlocking and its efficiency and accuracy is vital to ensure the safety of traffic control. A directed graph model based on the structure of railway station yard is modeled and the problem of searching routes in a railway station yard is then converted as the problem of traversing a directed graph. According to the characteristics of simplified railway station yard graph, traditional Dijkstra algorithm is improved from the aspects of data storage and queue structure, breadth-first search is adopted, and a route searching strategy with the shortest path as objective function is proposed. Furthermore, a simulation program is built to verify this algorithm and the simulation results show that this improved Dijkstra algorithm can complete searching types of routes accurately and efficiently.-
Keywords:
- route searching /
- directed graph /
- Dijkstra algorithm /
- shortest path
-
随着我国铁路建设的发展,至2020年底,铁路营业里程已达14.6万km,因而,将铁路客站等重要基础设施数字化,是提高铁路运营管理水平,实现铁路“又好又快发展”目标的重要举措。现阶段,除新建线路外,铁路还有大量的既有线路,其原始数据均为计算机辅助设计(CAD,Computer Aided Design)数据,如仍沿用手工作业模式,既无法保证建筑信息模型(BIM,Building Information Modeling)所需数据的完整性和准确性,也无法适应大批量作业的需求。因此,铁路行业亟需研究高效先进的技术,实现BIM的自动化生成。
目前,BIM自动化生成的相关研究主要集中在图纸识别方面。例如:李正敏等人[1]提出的工程图文本信息的提取方法;王尔健等人[2]提出的区域划分法,即结合矢量分析识别工程图上的几何形状关系;李党等人[3]提出的集中提高智能识别建筑平面图形精度及正确率的方法;汪同庆等人[4]提出的基于数据交换格式(DXF,Data Exchange Format)文件的几何特征识别方法;储节磊等人[5]对于无固定起点、无精确尺寸、无统一比例的平面矢量图形,提出了相似性比较识别方法。这些既有工作对于研究铁路BIM自动化生成技术,尤其是二维图纸信息的数字化提取方法,提供了有益借鉴。然而,现有的研究在铁路BIM自动化快速建模方面尚不充分,结合市场需求,本文着重研究铁路客站BIM自动化生成技术。
1 技术体系
铁路客站BIM自动化生成的基本过程包括二维图纸数据采集、匹配BIM标准构件库、自动化生成BIM、快速布置和优化BIM。围绕生成过程的实现,本文从以下方面提出了铁路客站BIM自动化生成技术体系主要内容,如图1所示。
1.1 铁路客站二维图纸自动分析识别
通过分析二维图纸的关键信息,实现BIM所需数据的自动获取[6],按照一定的结构分类标准转化为铁路客站BIM多维数据,为自动构建构件库和BIM自动化生成提供支持。
1.2 铁路客站BIM多维数据管理解决方案
通过建立完整的数据仓库,可以沉淀二维数据资产,并将铁路客站建设过程的多维数据与BIM相关联。具体为,铁路客站BIM多维数据管理为BIM自动化生成提供数据支持,同时BIM自动化生成技术为铁路客站BIM多维数据管理提供数据分类标准等。
1.3 铁路客站BIM标准构件库
根据铁路BIM联盟标准,分专业、分类别全方面实现客站标准构件库,以期为BIM自动化生成提供构件支持,同时也为铁路客站BIM快速布置及优化提供模型标准支持。
1.4 铁路客站BIM自动化生成
根据铁路客站BIM物理和功能特性,结合二维图纸分析读取的关键数据和BIM建模方法,将数据的二维几何表现形式转换为三维几何表现形式,实现建模的快速、规范、可调整,为铁路客站BIM构件的快速布置及优化提供深度学习样本支持。
1.5 铁路客站BIM快速布置及优化
根据标准构件特性,完成构件间逻辑判断,通过扣减规则及自动碰撞检测实现BIM的自动组装和优化路径,进一步完善BIM的准确度,形成共享知识和信息资源。
2 关键技术
铁路客站BIM自动化生成关键技术主要包括二维图纸智能识别技术、模型自动化生成技术、标准构件自动布置与优化技术、BIM数据库建构技术等。考虑到BIM数据库建构技术较为成熟,本文仅对前3项关键技术进行深度研究。铁路客站BIM自动化生成技术流程如图2所示。
2.1 二维图纸智能识别技术
二维图纸智能识别指多专业构件实体对象的自动识别。二维图纸转换为模型数据需要的“翻译”工作体量庞大,实现二维图纸中墙、板、柱、梁、风管、给排水管、暖通水管、桥梁、路基等对象的智能识别是解决这一问题的关键。根据二维图纸内容特点,本文提出基于DXF的数据读取[7-8]、矢量图形识别和图形巡径模糊识别的二维图纸智能识别技术,智能识别的关键技术如图3所示。其中,基于DXF的数据读取技术主要用于二维图纸点数据、文字数据和块数据的识别采集;矢量图形识别技术主要用于表数据和矢量数据的识别采集;图形巡径模糊识别技术主要用于几何数据的识别采集。通过自动分析和获取二维图纸的关键数据,为后续将数据的二维几何表现形式转换为三维几何表现形式奠定基础。
2.2 模型自动化生成技术
铁路客站BIM自动化生成技术是将二维图纸中提取的模型所需关键数据进行解析[9-10],自动判断其类型、参数,并将其与标准构件库相结合,进而实现二维表现形式转换为三维表现形式。模型自动化生成技术包括三维引擎显示、二维和三维联动交互等,模型自动化生成技术的主要内容如图4所示。
(1)同源异构表现技术主要用于二维点数据、文字数据、表数据与三维模型数据的联动和实时传输,实现真实数据转化为三维模型相关数据的目的。
(2)数据库由基础数据和算法数据2大类组成。数据库建构以网状数据库为主,不仅可以支持以项目级别存储数据,也可以支持以专业级别、构件级别的存储数据,更有利于深度学习算法的实现。
(3)标准构件库包含建筑、结构、暖通、给排水、电气等构件资源。标准构件库中的构件需要进行预分类,并在图元数据中将其视为一个集合进行处理,以提高对标准构件的识别效率。此外,在根据BIM关键数据自动匹配标准构件库的过程中,由于原始的二维图纸的标准化程度易受到制图人习惯的影响,因此BIM自动化生成是一个不断学习和更新的过程。
(4)三维引擎显示,即模型点击渲染后可自动渲染,或者通过色卡、光源等调整后进行渲染。
2.3 标准构件自动布置与优化技术
构件快速布置和优化技术是用于正向三维设计的重要技术,涉及模型参数化、设计逻辑规则、扣减规则和碰撞检测等,是人工智能(AI,Artificial Intelligence)与数字建筑相结合的典型应用,其核心是对碰撞、避让等规则的深度学习和AI审图。结合铁路客站工程特点,基于数据库中构件的物理特性和功能特性的数字化表达,建立BIM构件之间的逻辑关系,可实现标准构件的自动布置及优化,如图5所示。
在技术实现特点方面,为了保证标准构件自动布置效率与效果,从以下两方面入手:(1)结合标准构件库—数据库—三维显示耦合作用机理,建立建筑物的构件、位置和数据处理相关关系,实现数据的联动约束和动态更新;(2)通过完整和具备逻辑关系的数据库,以云计算的方式实现多通道数据处理能力,继而实现由图形处理器(GPU,Graphics Processing Unit)与中央处理器(CPU,Central Processing Unit)共同处理、以大数据和深度学习为基础的标准构件自动布置与优化。此外,考虑到模型数据量庞大的特性,将流程化算法和逻辑化算法拆分为单点算法,触发快速调用算法机制,继而确保多通道数据处理能力。
3 应用效果
本文研究的BIM自动化生成技术已应用于我国某铁路客站工程管理信息化实践中,应用效果如下。
3.1 实现施工现场三维可视化
应用二维图纸智能识别技术采集该工程项目的电子图纸数据信息,基于预先建成的标准构件库和BIM多维数据仓库及相关算法,将二维图纸数据转化为三维模型数据;利用BIM的三维可视化效果实现三维展现,使得施工现场平面布置效果与现场尽量保持一致,如图6所示。此外,利用BIM自动化生成技术得到的三维模型,能够与设计参数及管理要求等相关数据实时关联,实现了铁路客站数字模型与可视化模型的实时、高度集成,形成对工程项目及其内部要素关系的有效模拟。借助于BIM的三维可视化效果,能够使工程管理人员和专业技术人员充分掌握相关设计信息,辅助提高工程施工人员的作业能力。
3.2 提高BIM建模效率与准确性
应用标准构件自动布置和优化技术,有效解决了构件扣减和碰撞优化问题,显著减少了构件之间的人工匹配操作,提高了铁路客站BIM建模效率与准确性,提升了铁路客站BIM建模自动化水平。随着应用规模的扩大、深度学习算法的持续改进,以及AI技术的更新迭代,BIM自动化生成技术的应用将进一步降低铁路客站BIM建模的边际成本。
3.3 提升铁路客站施工管理质量
通过建立BIM、模拟现场场景和管理活动,能够支持管理人员和专业技术人员对铁路客站建设的交通组织、大型设备配置、材料堆场、临建设施使用等主要阶段的管理进行优化,使工程施工合理有序。通过将三维模型与铁路客站安全风险预控、质量跟踪管理等应用的融合,增强工程安全管理、质量管理的全面性和即时性,有效促进质量管理优化和安全管理优化。
3.4 推动铁路BIM标准构件体系建设
利用基于数据库构件的物理特性和功能特性的数字化表达方式,构建铁路客站标准构件库,有助于推动铁路BIM标准构件体系建设,实现铁路BIM标准构件资源的共建、共享;有助于促进标准构件与客站产业化、建筑工业化的深度融合,以及工程建设科技成果的工程应用,进而推动铁路客站建设向标准化、集成化、信息化和工业化转型升级。
4 结束语
实现铁路客站BIM自动化生成对于提升铁路工程建设管理水平、降低施工成本意义重大。要实现铁路客站BIM自动化生成技术完全自主可控和大规模推广应用,还需要进一步加强对三维显示、深度学习等相关基础理论、基础算法的研究,同时,结合铁路客站工程建设管理的需求和特点,加快研发BIM自动化生成相关软件产品,与既有的铁路工程管理信息系统融合,在实践中不断优化和改进相关软件的功能及性能。
-
表 1 邻接表数据结构定义
vector<vector<global_Node_Adj>>m_vec_adj邻接表 第0列 第1列 第2列 第0行m_vec_adj[0] m_num 0 1 m_name “24” “X3” m_id 2 1 m_distance 第1行m_vec_adj[1] m_num 1 m_name “X3” m_id 1 m_distance INF ... ... ... ... ... 第23行m_vec_adj[23] m_num 23 24 m_name “D18” “20” m_id 1 2 m_distance INF 3 第24行m_vec_adj[24] m_num 24 25 26 m_name0 “20” “X4” “X6” m_id 2 1 1 m_distance INF 59 59 表 2 站场图CSV数据格式
起点字符串 起点类型 终点字符串 终点类型 距离 24 2 X3 1 3 SF 1 D6 1 241 D6 1 6 2 3 6 2 8 2 88 6 2 D8 1 68 D8 1 18 2 207 18 2 D20 1 27 D20 1 22 2 3 ... ... ... ... ... 20 2 X6 1 59 表 3 站场图边数组格式
起点数字 起点字符串 起点类型 终点数字 终点字符串 终点类型 距离 0 24 2 1 X3 1 3 2 SF 1 3 D6 1 241 3 D6 1 4 6 2 3 4 6 2 5 8 2 88 4 6 2 6 D8 1 68 ... ... ... ... ... ... ... 20 D4 1 21 D14 1 230 -
[1] 赵志熙.计算机联锁系统技术[M].北京: 中国铁道出版社, 1999: 233-237. [2] 谢 林,杨 扬. 基于二维坐标信息进路搜索算法研究 [J]. 铁路计算机应用,2015,24(8):16-19. DOI: 10.3969/j.issn.1005-8451.2015.08.005 [3] 梁艺凡,谭 丽,冯 挺. A*进路搜索算法的研究与实现 [J]. 铁道标准设计,2013(2):17-20. [4] 康文雄,许耀钊. 节点约束型最短路径的分层Dijkstra算法 [J]. 华南理工大学学报(自然科学版),2017,45(1):66-72. [5] 王海梅,周献中. 一种限制搜索区域的最短路径改进算法 [J]. 南京理工大学学报(自然科学版),2011,33(5):638-642. [6] 严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京: 清华大学出版社, 1997. [7] 耿 杰,蔡伯根,王 剑,等. 基于深度优先搜索的铁路站场遍历算法研究 [J]. 铁道学报,2012,34(4):51-56. DOI: 10.3969/j.issn.1001-8360.2012.04.009 [8] 肖 蒙,宁海安,赵志荣. 基于有向图的进路搜索算法研究与设计 [J]. 自动化与仪器仪表,2012(6):69-73. DOI: 10.3969/j.issn.1001-9227.2012.06.027 [9] 蔚 洁,杨怀雷,成汝震. 基于Dijkstra算法的最优路径搜索方法 [J]. 河北师范大学学报(自然科学版),2008,32(5):590-593. [10] 樊守伟,严 艳,张少杰,等. Dijkstra算法与旅游路径优化田 [J]. 西安邮电大学学报,2014,19(1):121-124. [11] 赵艳丽. 实际路网最短路径算法优化与实现[D]. 广州: 华南理工大学, 2015. [12] 吴 鹏,寇玮华,许木南,等. 基于Dijkstra和深度优先搜索的进路搜索算法研究 [J]. 交通运输工程与信息学报,2017,15(4):38-43. DOI: 10.3969/j.issn.1672-4747.2017.04.006 -
期刊类型引用(1)
1. 杨文成,霍磊,郑玢,赵鹏,乔俊飞,张小虎. 基于IFC标准和数据库技术的铁路站场自动化BIM建模方法. 铁道标准设计. 2023(10): 78-85 . 百度学术
其他类型引用(0)