(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210975141.X (22)申请日 2022.08.15 (71)申请人 深圳大学 地址 518000 广东省深圳市南 山区南海大 道3688号 (72)发明人 孙维泽　杨昭孟　关宪章　黄磊　 吴沛林　苏国亮　 (74)专利代理 机构 深圳市精英专利事务所 44242 专利代理师 周永敬 (51)Int.Cl. G06F 30/18(2020.01) G06F 30/20(2020.01) G06F 113/14(2020.01) (54)发明名称 多管道排布方法及相关 设备 (57)摘要 本发明提供了一种多管道排布方法及相关 设备， 方法包括， 读取建筑物的原始Rev it设计图 纸的图纸信息； 根据图纸信息在python服务平台 构造栅格化3D模型； 读取多条管道的起点和终 点； 根据多条管道的起点和终点， 通过A*算法进 行管道寻径及通过GA算法进行管道寻径优化， 得 到管道排布路径。 本发明的有益效果在于： 能够 很好地解决多管道联合排布时的整体空间分配 问题。 权利要求书2页 说明书7页 附图4页 CN 115310245 A 2022.11.08 CN 115310245 A 1.一种多管道排布方法， 其特 征在于： 包括 步骤， S10、 读取建筑物的原 始Revit设计图纸信息； S20、 在python服务平台构造栅格化3D模型； S30、 读取并存 储多条管道的起 点和终点； S40、 根据多条 管道的起 点和终点， 通过A*算法进行 管道寻径； S50、 通过GA算法和管道微调算子进行 管道路径优化， 得到管道路径。 2.如权利要求1所述的多管道排布方法， 其特征在于： 通过A*算法进行管道寻径包括步 骤， S411、 初始化OPEN表和CLOSED表， 其中， OPEN表采用数组实现的二叉堆， 用于存放未遍 历的栅格； CLOSED表采用数组存 储， 用于存放己检测过的栅格； S412、 将管道的起 点放入OPEN表中,设场景中有n个栅格， 起 点为S， 终点 为E； S413判断OPEN表是否为空， 为空的话表示搜索过程失败， 退出程序， 否则进行下一步 骤； S414、 将OPEN表中首部的栅格V0移出作为路径的下一个栅格， 并将栅格V0存储进CLOSED 表， 表示当前栅格已经 过检测； S415、 判断V0是否为终点栅格E， 如果是则表示路径搜索成功， 执行路径修复， 否则进行 下一步骤； S416、 以V0为中心， 探索V0的相邻栅格Vi(i<n)， 计算 其估价函数值； S417、 判断Vi是否存在于OPEN表或CLOSED表： 如果Vi不存在于OPEN表和CLOSED表， 则选 择将其存放于OPEN表， 并连接V0与Vi两个栅格； 如果Vi己存在于OPEN表， 则对OPEN表中的F (V)值进行更新， 即取较小的F(V)新值代替OPEN表中较大的F(V)旧值， 连接V0与Vi两个栅格； 如果Vi己存在于 CLOSED表或是障碍点则忽略此顶点， 返回上一 步骤继续探索V0的相邻栅格； S418、 OPEN表中F(V )值最小的栅格通过二叉堆更新被排序至堆顶， 之后跳转至步骤 S413； S419、 执行路径修复； S420、 在所有路径修复后， 完成管道寻径。 3.如权利要求2所述的多管道排布方法， 其特 征在于： 路径修复步骤 包括， S421、 进行 管道路径自我交叉检测， 将冗余管道路径删除； S422、 进行折返 路径检测， 将折返点之间的路径删除完成路径的去重； S423、 进行 连续转弯路径检测， 使用A*算法重新 寻径， 取消连续 转弯。 4.如权利 要求3所述的多管道排布方法， 其特征在于： 以V0为中心， 探索V0的相邻栅格Vi (i<n)， 计算 其估价函数值采用的公式为， F(n)＝kg·g(n)+kh·h(n) g(n)＝a·L(n)+b·B(n)+c·Eo(n)+d·Eh(n) h(n)＝|E ‑V0| 其中， g(n)是路径从起点S到Vi的代价评估函数， L(n)为路径长度代价， B(n)为转弯代 价， Eo(n)为未靠墙排管/平行排管代价， Eh(n)为高度代价， a～d为相应的权重系数， 代价具 体的计算规则是： 单位栅格长度的路径损失加1； 单位转弯损失加1； 单位管道栅格未靠墙/ 靠管排布损失加1； 单位管道栅格相 对假天花高度每损失一个栅格高度损失加1， h(n)是栅权　利　要　求　书 1/2 页 2 CN 115310245 A 2格Vi与终点的曼哈顿距离 。 5.如权利要求4所述的多管道排布方法， 其特征在于： 通过GA算法进行管道寻径优化包 括步骤， S431、 输入多条 管道的起 点和终点； S432、 选取排管区域中靠墙且高度最高的区域作为中间点生成的区域， 在区域内生成 随机中间点， 与起 点终点结合得到中间点 集； S433、 使用A*算法连接每一个点集的中间点， 形成一组初始路径， 重 复生成20组初始路 径； S434、 对已生成的初始路径进行评估， 对每一组路径的适应度进行评分， 并保留评分最 高的最优路径best_paths； S435、 根据每组路径的适应度， 采用轮盘赌的方式筛选出19组路径， 与步骤S434得到的 最佳路径一 起共20组路径进入下一次GA算法的迭代循环； S436、 分别从两组管道随机挑选一条路径， 在 路径上随机寻找交叉点， 调用A*算法在交 叉点之间形成新的路径， 与原 始路径交叉重组形成新的路径组合； S437、 选取同一组内的两条管道， 挑选距离相近的转弯点作为交换点， 交换转弯点， 并 对转弯点前后的路径调用A*算法重新 生成， 形成新的路径组； S438、 对于组内的每一条路径， 随机挑选一个突变点， 调用A*算法重新生成突变点到终 点之间的路径， 形成新的路径组； S439、 判断迭代次数是否达到设定值， 如果未达到则回到步骤S434， 进行下一轮进化迭 代， 否则退 出进化流程， 输出最佳路径best_paths。 6.如权利要求1所述的多管道排布方法， 其特征在于： 对每一组路径的适应度进行评分 采用的公式为， fobj＝K‑( α·fL+β·fB+γ·fEO+δ·fEH) 其中， K为一个足够大的正数， 保证fobj的值始终大于0， fL为管道组路径长度损失， fB为 管道组路径转弯数目损失， fEO为管道组中未靠墙排布栅格的损失， fEH为管道组栅格高度损 失， α， β， γ， δ 分别是四类损失的权 重。 7.一种多管道排布装置， 其特 征在于： 包括， 图纸信息读取模块， 读取建筑物的原 始Revit设计图纸； 3D模型构造模块， 在 python服务平台构造栅格化3D模型； 起点终点读取存 储模块， 预设多条 管道的起 点和终点； 寻径模块， 用于根据多条 管道的起 点和终点， 通过A*算法进行初始管道路径搜索； 优化模块， 通过GA算法和管道微调进行 管道寻径优化， 得到管道排布路径。 8.一种计算机设备， 其特征在于： 所述计算机设备包括存储器及处理器， 所述存储器上 存储有计算机程序， 所述处理器执行所述计算机程序时实现如权利要求 1至6中任一项所述 的多管道排布方法。 9.一种存储介质， 其特征在于： 所述存储介质存储有计算机程序， 所述计算机程序被处 理器执行时可实现如权利要求1至 6中任一项所述的多管道排布方法。权　利　要　求　书 2/2 页 3 CN 115310245 A 3