Branch-pipe-routing approach for ships using improved genetic algorithm

Abstract

Branch-pipe routing plays fundamental and critical roles in ship-pipe design. The branch-pipe-routing problem is a complex combinatorial optimization problem and is thus difficult to solve when depending only on human experts. A modified genetic-algorithm-based approach is proposed in this paper to solve this problem. The simplified layout space is first divided into three-dimensional (3D) grids to build its mathematical model. Branch pipes in layout space are regarded as a combination of several two-point pipes, and the pipe route between two connection points is generated using an improved maze algorithm. The coding of branch pipes is then defined, and the genetic operators are devised, especially the complete crossover strategy that greatly accelerates the convergence speed. Finally, simulation tests demonstrate the performance of proposed method.

Key words： branch pipe; ship industry; piping system; optimization algorithm

Acknowledge

This work was funded by the National Natural Science Foundation of China (Grant No. 51275340).

References

1 Park J H, Storch R L. Pipe-routing algorithm development: Case study of a ship engine room design. Expert Systems with Applications, 2002, 23(3): 299–309

2 Lee C Y. An algorithm for path connections and its applications. IRE Transactions on Electronic Computers, 1961, EC-10(3): 346–365

3 Hightower D W. A solution to line-routing problems on the continuous plane. In: Proceedings of Twenty-five years of Electronic Design Automation. New York: ACM, 1988, 11–34

4 Kai-jian S, Hong-e Z. Efficient routing algorithm. Computer Aided Design, 1987, 19(7): 375–379

5 Kim S H, Ruy W S, Jang B S. The development of a practical pipe auto-routing system in a shipbuilding CAD environment using network optimization. International Journal of Naval Architecture and Ocean Engineering, 2013, 5(3): 468–477

6 Dijkstra E W. A note on two problems in connexion with graphs. NumerischeMathematik, 1959, 1(1): 269–271

7 Ito T. A genetic algorithm approach to piping route path planning. Journal of Intelligent Manufacturing, 1999, 10(1): 103–114

8 Sandurkar S, Chen W. GAPRUS—Geneticalgorithms based pipe routing using tessellated objects. Computers in Industry, 1999, 38(3): 209–223

9 Fan X, Lin Y, Ji Z. A variable length coding genetic algorithm to ship pipe path routing optimization in 3D space. Ship Building of China, 2007, 48(1): 82–90 (in Chinese)

10 Ren T, Zhu Z, Dimirovski G M, . A new pipe routing method for aero-engines based on genetic algorithm. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 2014, 228(3): 424–434

11 Liu Q, Wang C. Pipe-assembly approach for aero-engines by modified particle swarm optimization. Assembly Automation, 2010, 30(4): 365–377

12 Liu Q, Wang C. A discrete particle swarm optimization algorithm for rectilinear branch pipe routing. Assembly Automation, 2011, 31(4): 363–368

13 Fan X, Lin Y, Ji Z. Ship pipe routing design using the ACO with iterative pheromone updating. Journal of Ship Production, 2007, 23(1): 36–45

14 Fan X, Lin Y, Ji Z. Multi ant colony cooperative coevolution for optimization of ship multi pipe parallel routing. Journal of Shanghai Jiaotong University, 2009, 43(2): 193–197 (in Chinese)

15 Jiang W, Lin Y, Chen M, . An ant colony optimization—Genetic algorithm approach for ship pipe route design. International Shipbuilding Progress, 2014, 61(3‒4): 163–183 doi:10.3233/ISP-140111

16 Jiang W, Lin Y, Chen M, . A co-evolutionary improved multi-ant colony optimization for ship multiple and branch pipe route design. Ocean Engineering, 2015, 102: 63–70

17 Asmara A. Pipe routing framework for detailed ship design. Dissertation for the Doctoral Degree. Delft: Delft University of Technology, 2013

18 Fan J, Mei M, Yang X. Research on automatic laying out for external pipeline of aeroengine. Machine Design, 2003, 20(7): 21–23 (in Chinese)

19 Asmara A, Nienhuis U. Automatic piping system in ship. In: Proceedings of5th International Conference on Computer and IT Application in the Maritime Industries (COMPIT). 2006

20 Wu J, Lin Y, Ji Z, . Optimal approach of ship branch pipe routing optimization based on co-evolutionary algorithm. Ship & Ocean Engineering, 2008, 37(4): 135–138 (in Chinese)

21 Liu Q, Wang C. Multi-terminal pipe routing by Steiner minimal tree and particle swarm optimization. Enterprise Information Systems, 2012, 6(3): 315–327