Please wait a minute...
工程设计学报
工程设计学报  2016, Vol. 23 Issue (2): 188-194    DOI: 10.3785/j.issn.1006-754X.2016.02.013
建模、分析、优化和决策     
基于迷宫算法和遗传算法的船舶管路路径规划
隋海腾, 牛文铁
天津大学 机构理论与装备设计教育部重点实验室, 天津 300072
Ship pipe route planning method based on maze algorithm and genetic algorithm
SUI Hai-teng, NIU Wen-tie
Key Laboratory of Mechanism Theory and Equipment Design of Ministry of Education, Tianjin University, Tianjin 300072, China
 全文: PDF(2517 KB)   HTML
摘要： 船舶管路的多样性和布局环境中约束的复杂性导致管路设计效率低下.为辅助设计人员提高管路设计效率并减少人为错误,提出了一种新的管路设计方法.首先,基于轴平行包围盒简化管路布局空间,利用栅格法对其进行离散化,并赋予空间网格特定的能量值,构建管路布局优化问题的数学模型.其次,基于遗传算法的框架,引入改进迷宫算法,提出管路路径规划方法,其中:迷宫搜索中引入辅助点的概念,增加了遗传算法中初始种群的多样性,有利于提高遗传算法的全局搜索能力;提出了定长度的编码方法,简化了管路染色体处理难度,提高了算法性能;基于引入方向优先搜索策略的迷宫算法,设计定长度编码遗传算子,保证了子代个体的质量,提高算法的收敛速度.最后,基于仿真试验,验证算法的性能.试验结果表明了该方法的可行性和高效率,以及其对实际管路布局工作具有指导意义.
关键词： 管路布局;  迷宫算法;  遗传算法;  定长度编码    
Abstract: The diversity of piping systems and complexity of constrains in layout space lead to the low efficiency of ship pipe design. A new pipe route planning method was proposed to improve the design efficiency and reduce human errors. Based on the simplified layout space, the mathematical model was firstly built by the discretization of the layout space and the specific energy value which was given to the spatial network. Based on the constructed mathematical model, the improved maze algorithm and genetic algorithm were then combined together to conduct pipe route planning. The concept of auxiliary point was introduced to improve the maze searching performance, which guaranteed the diversity of initial population and enhanced the global search ability of genetic algorithm. A fixed-length coding method was also proposed to simplify the difficulty in handling the pipe chromosomes and improve the performance of algorithm. The direction oriented strategy was applied in maze retracing process to design the genetic operators with fixed-length chromosomes, which not only guaranteed the quality of children chromosomes but also improved the convergence speed of the algorithm. The simulation results verify the feasibility and effectiveness of this approach, and prove the guiding significance of the approach to actual ship pipe route planning.
Key words: pipe route planning    maze algorithm    genetic algorithm    fixed-length coding method
收稿日期: 2015-05-08 出版日期: 2016-04-28
CLC:  U662.9  
基金资助:

国家自然科学基金资助项目(51275340).
通讯作者: 牛文铁(1971—),男,内蒙古赤峰人,副教授,博士,从事设计理论与方法及数控机床数字化设计研究,E-mail:niuwentie@tju.edu.cn.     E-mail: niuwentie@tju.edu.cn
作者简介: 隋海腾(1989—),男,山东烟台人,硕士生,从事设计理论与方法研究,E-mail:suihaitengtju@tju.edu.cn.http://orcid.org//0000-0002-3364-1715
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
隋海腾
牛文铁

引用本文:

隋海腾, 牛文铁. 基于迷宫算法和遗传算法的船舶管路路径规划[J]. 工程设计学报, 2016, 23(2): 188-194.

SUI Hai-teng, NIU Wen-tie. Ship pipe route planning method based on maze algorithm and genetic algorithm. Chinese Journal of Engineering Design, 2016, 23(2): 188-194.

链接本文:

https://www.zjujournals.com/gcsjxb/CN/10.3785/j.issn.1006-754X.2016.02.013    或    https://www.zjujournals.com/gcsjxb/CN/Y2016/V23/I2/188

[1] PARK J H,STORCH R L.Pipe-routing algorithm development:case study of a ship engine room design[J].Expert Systems with Applications,2002,23(3):299-309.

[2] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1(1):269-271.

[3] LEE C Y.An algorithm for path connections and its applications[J].Ire Transactions on Electronic Computers,1961,10(3):346-365.

[4] 樊江,马枚,杨晓光.航空发动机外部管路自动敷设研究[J].机械设计,2003,20(7):21-23. FAN Jiang,MA Mei,YANG Xiao-guang.Research on automatic laying out for external pipeline of aero-engine[J].Journal of Machine Design,2003,20(7):21-23.

[5] HIGHTOWER D W.A solution to line routing problems on the continuous plane[C]//Proceedings of 6th Design Automation Workshop.IEEE,1969:1-24.

[6] ITO T.A genetic algorithm approach to piping route path planning[J].Journal of Intelligent Manufacturing,1999,10(1):103-114.

[7] ITO T.Developments in applied artificial intelligence[C].Berlin:Springer,2002:547-556.

[8] 范小宁,林焰,纪卓尚.船舶管路三维布局优化的变长度编码遗传算法[J].中国造船,2007,48(1):82-90. FAN Xiao-ning,LIN Yan,JI Zhuo-shang.A variable length coding genetic algorithm to ship pipe path routing optimization in 3D space[J].Shipbuilding of China,2007,48(1):82-90.

[9] SANDURKAR Sunand,WEI Chen.GAPRUS—genetic algorithms based pipe routing using tessellated objects[J].Computers in Industry,1999,38(3):209-223.

[10] REN Tao,ZHU Zhi-liang,DIMIROVSKI G M,et al.A new pipe routing method for aero-engines based on genetic algorithm[J].Proceedings of the Institution of Mechanical Engineers,Part G:Journal of Aerospace Engineering,2014,228(3):424-434.

[11] JIANG Wen-ying,LIN Yan,CHEN Ming,et al.An ant colony optimization-genetic algorithm approach for ship pipe route design[J].International Shipbuilding Progress,2014,61(3):163-183.

[12] 范小宁,林焰,纪卓尚.多蚁群协进化的船舶多管路并行布局优化[J].上海交通大学学报,2009,43(2):193-197. FAN Xiao-ning,LIN Yan,JI Zhuo-shang.Multi ant colony cooperative co-evolution for optimization of ship muti pipe parallel routing[J].Journal of Shanghai Jiaotong University,2009,43(2):193-197.

[13] LIU Qiang,WANG Chen-gen.A discrete particle swarm optimization algorithm for rectilinear branch pipe routing[J].Assembly Automation,2011,31(4):363-368.

[14] LIU Qiang,WANG Chen-gen.Pipe-assembly approach for aero-engines by modified particle swarm optimization[J].Assembly Automation,2010,30(4):365-377.

[15] LIU Qiang,WANG Chen-gen.Multi-terminal pipe routing by Steiner minimal tree and particle swarm optimization[J].Enterprise Information Systems,2012,6 (3):315-327.

[16] KIM S H,RUY W,JANG B S.The development of a practical pipe auto-routing system in a shipbuilding CAD environment using network optimization[J].International Journal of Naval Architecture and Ocean Engineering,2013,5(3):468-477.
[1] 李琴,贾英崎,黄玉峰,李刚,叶闯. 一种工业机器人多目标轨迹优化算法[J]. 工程设计学报, 2022, 29(2): 187-195.
[2] 丁述勇, 张征, 丁文洁, 林勇. 多巷道式立体车库优化设计与车辆存取策略研究[J]. 工程设计学报, 2021, 28(4): 443-449.
[3] 张帅, 韩军, 涂群章, 杨小强, 杨旋. 基于GA-NLP的剪刀式折叠桥梁展桥机构多目标优化设计[J]. 工程设计学报, 2020, 27(1): 67-75.
[4] 刘春青, 王文汉. 基于人工神经网络-遗传算法的展成法球面精密磨削参数优化[J]. 工程设计学报, 2019, 26(4): 395-402.
[5] 马天兵, 王孝东, 杜菲, 王鑫泉. 基于GA-SVM的刚性罐道故障诊断[J]. 工程设计学报, 2019, 26(2): 170-176.
[6] 邓星, 于兰峰, 雷聪, 徐江平, 肖泽平. 基于响应面法的无轨伸缩式门式起重机轻量化设计[J]. 工程设计学报, 2018, 25(3): 288-294.
[7] 唐维, 谢延敏, 黄仁勇, 张飞, 潘贝贝. 基于自适应SVR-ELM混合近似模型的镁合金差温成形本构参数反求[J]. 工程设计学报, 2017, 24(5): 536-544.
[8] 程兵, 于兰峰, 吴永明, 符康. 基于响应面法的地坑式架车机轻量化研究[J]. 工程设计学报, 2016, 23(6): 606-611.
[9] 邱瑞斌, 雷飞, 陈园, 王琼. 基于权重比的车架多工况拓扑优化方法研究[J]. 工程设计学报, 2016, 23(5): 444-452.
[10] 李晓豁, 史尚伟, 翁正洋, 钱亚森, 李岩, 杨梓嘉. 基于BP-GA的冲击破岩掘进机工作机构动态优化[J]. 工程设计学报, 2016, 23(4): 358-363.
[11] 苏建宁, 陈肖, 张书涛, 张新新. 基于进化算法的产品造型创新设计方法研究[J]. 工程设计学报, 2016, 23(2): 136-142.
[12] 王辉, 朱龙彪, 朱天成, 陈红艳, 邵小江, 朱志慧. 基于粒子群遗传算法的泊车系统路径规划研究[J]. 工程设计学报, 2016, 23(2): 195-200.
[13] 陈 鹏，吕 健，潘伟杰. 基于色彩方案重用的产品配色感性设计[J]. 工程设计学报, 2015, 22(6): 546-551.
[14] 王桂兰，成亚云，朱龙彪，朱志松. 满足“一刀切”要求的木工板排样优化研究[J]. 工程设计学报, 2014, 21(3): 212-216.
[15] 张超, 李慧, 田恺. 基于Plant Simulation的航空综合机加厂房布局仿真研究[J]. 工程设计学报, 2013, 20(3): 199-207.