基于优化A<sup>*</sup>算法的选煤厂管路自动布置

肖林京; 姚培鑫; 刘瑞; 马山清; 马成瀚

doi:10.13272/j.issn.1671-251x.2022080085

基于优化A^*算法的选煤厂管路自动布置

doi: 10.13272/j.issn.1671-251x.2022080085

山东科技大学机械电子工程学院, 山东青岛　266590

详细信息

作者简介:
肖林京（1966—），男，山东临沂人，教授，博士，博士研究生导师，研究方向为深海采矿技术、装备智能化设计，E-mail：xiaolj2008@126.com。通信作者：姚培鑫（1996-），男，山东滨州人，硕士研究生，研究方向为装备智能化设计，E-mail：1358578197@qq.com。

中图分类号: TD94
计量
- 文章访问数: 217
- HTML全文浏览量: 50
- PDF下载量: 30
- 被引次数: 0
出版历程
- 收稿日期: 2022-08-30
- 修回日期: 2022-11-02
- 网络出版日期: 2022-10-28

Automatic layout of pipeline in coal preparation plant based on optimized A^* algorithm

College of Mechanical and Electronic Engineering, Shandong University of Science and Technology, Qingdao 266590, China

摘要

摘要: 管路设计是选煤厂设计的重要内容之一，目前选煤厂管路主要依靠人工设计，难度大、耗时长且管路布置质量难以保证。将A^*算法应用到三维的选煤厂管路自动布置中，搜索出的路径不符合管路设计要求。针对上述问题，提出了一种基于优化A^*算法的选煤厂管路自动布置方法。基于选煤厂管路布置规则，建立选煤厂布局空间模型，对布局空间模型进行网格化、数值化处理。针对A^*算法搜索出的路径会出现过多折弯的问题，对A^*算法的评价函数进行优化；针对A^*算法搜索速率较慢的问题，在评价函数中引入动态权重；针对经上述优化后A^*算法搜索出的管路路径会绕行有需求的设备的问题，引入方向导向策略以提高管路布置的工程实用性；为提高A^*算法运行效率，将Open表的数组结构替换为最小二叉堆结构。仿真结果表明：① 对A^*算法评价函数进行优化后，管路路径折弯次数减少80%左右，且折弯都为直角，符合选煤厂管路布置的实际情况；引入动态权重后，运行效率提升且能保证路径质量。② 引入方向导向策略前后管路路径长度并无变化，都满足选煤厂管路布置的基本约束规则；引入方向导向策略后的管路更倾向于在对管路有特定需求的设备附近规划，管路有并排布置的趋势，说明方向导向策略引入后管路的布置满足整体布局最优的要求，更符合选煤工程应用需求。③ 用Open表优化后的A^*算法效率明显提高，管路路径越长、中间障碍物越多，A^*算法效率提高越明显。设计并开发了选煤厂管路自动布置软件系统，实例验证结果表明，优化后的A^*算法提高了选煤厂管路设计的效率和质量，且具有更好的可视性。
- 选煤厂 /
- 管路自动布置 /
- 管路路径 /
- A^*算法 /
- 评价函数
Abstract: The pipeline design is one of the important contents of coal preparation plant design. At present, pipeline of coal preparation plant mainly depends on the manual design, which is difficult, time-consuming and difficult to guarantee the quality of pipeline layout. When A^* algorithm is applied to the automatic layout of three-dimensional pipeline in coal preparation plant, the searched path does not meet the requirements of pipeline design. In order to solve the above problems, an automatic pipeline layout method for coal preparation plant based on optimized A^* algorithm is proposed. Based on the pipeline layout rules of coal preparation plant, the layout space model of coal preparation plant is established. The grid and numerical processing are carried out on the layout space model. Aiming at the problem that the path searched by the A^* algorithm has excessive bending, the evaluation function of the A^* algorithm is optimized. To solve the problem of the slow search speed of the A^* algorithm, dynamic weight are introduced into the evaluation function. Aiming at the problem that the pipeline path searched by the A^* algorithm after the above optimization will bypass the required equipment, the direction-oriented strategy is introduced to improve the engineering practicability of pipeline layout. To improve the A^* algorithm's operation efficiency, the Open table's array structure is replaced with the minimum binary heap structure. The simulation result shows the following points. ① After optimizing the evaluation function of the A^* algorithm, the bending times of the pipeline path are reduced by about 80%. The ben is right angle, which accords with the actual situation of the pipeline layout in the coal preparation plant. After introducing the dynamic weight, the operation efficiency is improved and the path quality can be guaranteed. ② The path length of the pipeline before and after the direction-oriented strategy is introduced has no change. The lengths meet the basic constraint rule of the pipeline layout of the coal preparation plant. After the introduction of the direction-oriented strategy, the pipeline is more likely to be planned near the equipment with specific requirements for the pipeline. And the pipeline has a tendency to be arranged side by side. This indicates that the pipeline layout after the introduction of the direction-oriented strategy meets the requirements of the optimal overall layout, and is more consistent with the coal preparation engineering application. ③ The efficiency of A^* algorithm after Open table optimization is improved obviously. The longer the pipeline path and the more obstacles in the middle, the more significant the efficiency improvement of the A^* algorithm. The software system of automatic pipeline layout in the coal preparation plant is designed and developed. The application example of the optimized A^* algorithm is verified. The results show that the optimized A^* algorithm improves the efficiency and quality of piping design in the coal preparation plant, and has better visibility.
- coal preparation plant /
- automatic pipeline layout /
- pipeline route /
- A^* algorithm /
- evaluation function

HTML全文

图 1 方向导向策略

Figure 1. Direction-oriented strategy

下载: 全尺寸图片幻灯片

图 2 Open表的数组结构

Figure 2. Array structure of the Open table

下载: 全尺寸图片幻灯片

图 3 最小二叉堆结构

Figure 3. Minimum binary heap structure

下载: 全尺寸图片幻灯片

图 4 选煤厂布局空间

Figure 4. Layout space of coal preparation plant

下载: 全尺寸图片幻灯片

图 5 评价函数优化前后仿真结果

Figure 5. Evaluate the simulation results before and after function optimization

下载: 全尺寸图片幻灯片

图 6 引入方向导向策略前后管路路径对比

Figure 6. Comparison of pipe paths before and after introducing the direction oriented policy

下载: 全尺寸图片幻灯片

图 7 Open表优化前后算法运行时间对比

Figure 7. Comparison of algorithm operating time before and after Open-List optimization

下载: 全尺寸图片幻灯片

图 8 土建环境界面

Figure 8. Civil environment interface

下载: 全尺寸图片幻灯片

图 9 设备布局界面

Figure 9. Device layout interface

下载: 全尺寸图片幻灯片

图 10 管路布局界面

Figure 10. Pipe layout interface

下载: 全尺寸图片幻灯片

图 11 三维设计效果

Figure 11. 3D renderings

下载: 全尺寸图片幻灯片

表 1 障碍物对角坐标

Table 1. Obstacle diagonal coordinates dm

障碍物编号	对角坐标
1	(80,80,50)，(100,100,65)
2	(20,70,50)，(60,90,60)
3	(20,40,20)，(60,60,60)
4	(20,10,50)，(60,30,60)
5	(55,45,0)，(85,65,10)
6	(55,15,0)，(85,35,10)
7	(0,70,0)，(30,100,20)
8	(5,50,0)，(50,60,5)
9	(5,20,0)，(50,30,5)
10	(0,0,0)，(5,5,5)

下载: 导出CSV

表 2 权重系数对A^*算法的影响

Table 2. Effect of the weight coefficient on the A^* algorithm

权重系数	路径	时间/s	管路长度/dm	管路路径折弯次数	评价函数值
0	Ⅰ	50	250	5	300
	Ⅱ	39	125	5	175
	Ⅲ	12	90	3	120
1	Ⅰ	9.6	250	5	300
	Ⅱ	6	125	4	165
	Ⅲ	2.1	90	3	120
2	Ⅰ	4	275	10	375
	Ⅱ	2.7	155	7	225
	Ⅲ	0.8	90	3	120
γ	Ⅰ	5.5	250	6	310
	Ⅱ	3.6	130	4	180
	Ⅲ	1.3	90	3	120

下载: 导出CSV

参考文献(15)

[1]	刘辉. 重介选煤厂生产管道的工艺设计[J]. 洁净煤技术,2013,19(2):117-119. doi: 10.13226/j.issn.1006-6772.2013.02.029 LIU Hui. Production pipelines design in dense medium coal preparation plant[J]. Clean Coal Technology,2013,19(2):117-119. doi: 10.13226/j.issn.1006-6772.2013.02.029
[2]	GB 50937—2013选煤厂管道安装工程施工与验收规范[S]. GB 50937-2013 Code for construction and acceptance of piping installation in coal preparation plant[S].
[3]	黄波,韦彬,李志勇,等. 基于SolidWorks的选煤厂管道设计[J]. 煤炭工程,2014,46(10):91-93. doi: 10.11799/ce201410024 HUANG Bo,WEI Bin,LI Zhiyong,et al. Application and practice of coal preparation plant pipeline design based on SolidWorks[J]. Coal Engineering,2014,46(10):91-93. doi: 10.11799/ce201410024
[4]	韩小恒,云玉鹏,梁彦国,等. 选煤厂管道3D设计软件二次开发应用[J]. 煤炭加工与综合利用,2022(6):11-14. HAN Xiaoheng,YUN Yupeng,LIANG Yanguo,et al. The further-development and application of pipeline 3D design software for coal preparation plants[J]. Coal Processing & Comprehensive Utilization,2022(6):11-14.
[5]	柳强,毛莉. 基于MOPSO的航空发动机分支管路多目标布局优化[J]. 机械工程学报,2018,54(19):197-203. doi: 10.3901/JME.2018.19.197 LIU Qiang,MAO Li. Multi-objective layout optimization for branch pipe of aero-engine based on MOPSO[J]. Journal of Mechanical Engineering,2018,54(19):197-203. doi: 10.3901/JME.2018.19.197
[6]	WANG Yunlong,YU Yanyun,LI Kai,et al. A human-computer cooperation improved ant colony optimization for ship pipe route design[J]. Ocean Engineering,2018,150(15):12-20.
[7]	董宗然,楼偶俊,管官. 基于改进遗传算法的船舶管路布局设计[J]. 计算机工程与应用,2020,56(19):252-260. DONG Zongran,LOU Oujun,GUAN Guan. Ship pipe route design based on improved genetic algorithm[J]. Computer Engineering and Applications,2020,56(19):252-260.
[8]	许晓东,何丽丝,王德禹. 基于约束RRT算法的船舶管路自动布置技术[J]. 船舶工程,2021,43(6):18-23,29. doi: 10.13788/j.cnki.cbgc.2021.06.04 XU Xiaodong,HE Lisi,WANG Deyu. Automatic routing technology of ship pipe based on constraint RRT[J]. Ship Engineering,2021,43(6):18-23,29. doi: 10.13788/j.cnki.cbgc.2021.06.04
[9]	陶德俊,姜媛媛,刘延彬,等. 煤矿救援机器人路径平滑算法研究[J]. 工矿自动化,2019,45(10):49-54. doi: 10.13272/j.issn.1671-251x.2019050069 TAO Dejun,JIANG Yuanyuan,LIU Yanbin,et al. Research on path smoothing algorithm of coal mine rescue robot[J]. Industry and Mine Automation,2019,45(10):49-54. doi: 10.13272/j.issn.1671-251x.2019050069
[10]	GURUJI A K,AGARWAL H,PARSEDIYA D K. Time-efficient A^* algorithm for robot path planning[J]. Procedia Technology,2016,23(3):144-149.
[11]	吕文红,夏双双,魏博文,等. 基于改进A^算法的灾后井下无人机航迹规划[J]. 工矿自动化,2018,44(5):85-90. LYU Wenhong,XIA Shuangshuang,WEI Bowen,et al. Route planning of unmanned aerial vehicle in post-disaster underground based on improved A^ algorithm[J]. Industry and Mine Automation,2018,44(5):85-90.
[12]	潘长安. 基于改进A星算法的城市交通寻径的研究[D]. 泉州: 华侨大学, 2015. PAN Chang'an. Research on urban traffic routing based on improved A^* algorithm[D]. Quanzhou: Huaqiao University , 2015.
[13]	石英托,陈华,张连新,等. 基于改进A^算法的AGV转运机器人路径规划研究[J]. 制造技术与机床,2022(5):19-22. SHI Yingtuo,CHEN Hua,ZHANG Lianxin,et al. Research on path planning of AGV transport robot based on improved A^ algorithm[J]. Manufacturing Technology & Machine Tool,2022(5):19-22.
[14]	金澄,安晓亚,崔海福,等. 矢量瓦片地图线化简算法研究[J]. 地球信息科学学报,2019,21(10):1502-1509. doi: 10.12082/dqxxkx.2019.190214 JIN Cheng,AN Xiaoya,CUI Haifu,et al. An algorithm for simplifying linear elements of vector tile maps[J]. Journal of Geo-information Science,2019,21(10):1502-1509. doi: 10.12082/dqxxkx.2019.190214
[15]	王芝麟,乔新辉,马旭,等. 一种基于二叉堆的Dijkstra最短路径优化方法[J]. 工程数学学报,2021,38(5):709-720. doi: 10.3969/j.issn.1005-3085.2021.05.010 WANG Zhilin,QIAO Xinhui,MA Xu,et al. A Dijkstra shortest path optimization method based on binary heap[J]. Chinese Journal of Engineering Mathematics,2021,38(5):709-720. doi: 10.3969/j.issn.1005-3085.2021.05.010