Sep.20th-22nd
ICCAS 2011, Italy

An Automatic Piping Algorithm
Including Elbows and Bends
Dept. of Marine System Engineering, Kyushu University
Hajime KimuraDept. of Marine System Engineering, Kyushu University
Yuto AndoOutline
1. Background and Purpose- Previous Research
2. Routing Algorithm Including Bends- Approach- Dijkstra’s Method- Outline of “Bends”- Experiments
3. Conclusion and Challenges

Background
Pipe Arrangement requires …
 keeping to regulationsex.
- not to set fuel oil pipelines
near to electrical lines

http://www.cadpipe.com/industrial3D.html

Background
Pipe Arrangement requires …
 keeping to regulations

 meeting demands
ex.
- to shorten the total length- to set along with the ship hull

http://www.cadpipe.com/industrial3D.html

Background
Pipe Arrangement requires …
 keeping to regulations

 meeting demands
 originality by each ship

http://www.cadpipe.com/industrial3D.html

Background
Pipe Arrangement requires …
 keeping to regulations

 meeting demands
 originality by each ship

Experiences of skilled designers
http://www.cadpipe.com/industrial3D.html

Background
Pipe Arrangement requires …
 keeping to regulations

 meeting demands
 originality by each ship

Experiences of skilled designers
http://www.cadpipe.com/industrial3D.html

Automatic Design System

Purpose
Previous Researches

Our ProposalProblems are …

We try for …

optimization of piping routes

 solving these problems

searching of piping routes

 high performance systemconstraints

 full automatic design

Previous Research
Approach by Ikehira and Kimura
 taking into account of “valve operationality”
 dividing the pipe arrangement problem
into two challenges- equipments layout problem- routing problem

solved by “pattern match method”
which joins primitive pipe parts

Disadvantages are…

 uncertainty of optimal routing
 impossibility of solving a complicated routing problems

Previous Research

Goal Point

Approach by Asmara and Nienhuis
 looking on the pipe arrangement problem asa routing problem in a directed and weighted
graph

Obstaclesolved by “Dijkstra’s method”

Disadvantage is …
 the mesh size is restricted to be larger thana pipe’s diameter
especially in large pipe’s diameter

Strong Constraint!

Start Point

ObstacleOutline
1. Background and Purpose- Previous Research
2. Routing Algorithm Including Bends- Approach- Dijkstra’s Method- Outline of “Bends”- Experiments
3. Conclusion and Challenges

Approach
Problems of Previous Researches- uncertainty of the route with minimum costs- demanding of the mesh size on the diameter

Our Approach using “Dijkstra’s method”

 improvement the routing algorithm using not only elbows but “bends”

Approach
Problems of Previous Researches- uncertainty of the route with minimum costs- demanding of the mesh size on the diameter

Our Approach using “Dijkstra’s method”

 improvement the routing algorithm using not only elbows but “bends”

Approach
Problems of Previous Researches- uncertainty of the route with minimum costs- demanding of the mesh size on the diameter

Our Approach using “Dijkstra’s method”

variable mesh size!

 improvement the routing algorithm using not only elbows but “bends”

Approach
Problems of Previous Researches- uncertainty of the route with minimum costs- demanding of the mesh size on the diameter

Our Approach using “Dijkstra’s method”

 improvement the routing algorithm using not only elbows but “bends”

Approach Design Space: box for pipe arrangement

 Start and Goal

: coordinates and vectors

 Target Pipeline: pipes not including any branches

Approach Design Space: box for pipe arrangement

 Start and Goal

: coordinates and vectors

 Target Pipeline: pipes not including any branches

Approach Design Space: box for pipe arrangement

 Start and Goal

: coordinates and vectors

 Target Pipeline: pipes not including any branches

Approach
Pipe Arrangement

Routing Problem

Equipments LayoutProblem

Subject ofthis research Design Space: box for pipe arrangement

 Start and Goal

: coordinates and vectors

 Target Pipeline: pipes not including any branches

Approach Obstacle: structures and equipments
in ships

 Aisle Space: space for passages

 Pipe-rack Area

: space for pipelines

Approach Obstacle: structures and equipments
in ships

 Aisle Space: space for passages

 Pipe-rack Area

: space for pipelines

Approach Obstacle: structures and equipments
in ships

 Aisle Space: space for passages

 Pipe-rack Area

: space for pipelines

Dijkstra’s Method
This method can …
 find the shortest path in a directed and weighted graph guarantee a path with minimum costs
Where is the path with minimum costs
between C1 and C2?
C4
7
7C2
3
5
6
5
C1C73C510
7C388C6

The answer is …

75C1

10C2

6
3C3C4

minimum costs
73

5C5
788C616C7

Design Objectives
Pipe-rack

ObstacleAisle

 to minimize the total length of pipes
 to minimize the number of elbows and bends
 to avoid passing aisles as possible
 to pass through pipe-rack areas as possible

Routing Algorithm
Goal Point
Obstacle

Start Point

Obstacle
Obstacle

Pipe’s Diameter < Mesh Size

Routing Algorithm
Obstacle

Obstacle
Obstacle

Pipe’s Diameter > Mesh Size

Searching of Straight Pipes

Pipe’s Diameter ＞ Mesh Size

Next node

Current node
Diameter：R

Searching of Straight Pipes

Step1

Temporarynode
Current node
Diameter：R

Searching of Straight Pipes

Step2

Interference Check!

Temporarynode
Current nodeSearching of Straight Pipes

Step3

Recording Costs

Next node

Current nodeSearching of Elbows

Pipe’s Diameter ＞ Mesh Size

Next node

Current nodeSearching of Elbows

Step1

Node X
dd11≧
 R/2
R

Current node

Diameter：R

Searching of Elbows

Step2

d2≧R/2

Node X

Temporary
node

dd1
1≧
 R/2
R

Current node

Diameter：R

Searching of Elbows

Step3
Interference Check!
Temporarynode

Current nodeSearching of Elbows

Step4
Recording Costs

Next node

Current nodeOutline of Bends“Bends” are …
 pipe parts to take the form of gentle S-shape connectors for gaps within the pipe’s diameterfrom “NAMURA TECHNICAL REVIEW No.13, 2010”

Outline of Bends
Goal Point

Start Point
11Total length : 19

Outline of Bends

11

Total length : 22

Outline of Bends

11

Total length : 22

18.7

Searching of Bends
System user sets a value of 1,  2, dex. 1  5,  2  0, d  R d  2  1 R 
2  1  arcsin   arcsin 22
 (2  1)  ( 2)  (2  1) 2  ( 2) 2 L  (2 1 R  sin  )  ( 2  R  cos  )L : the minimum vertical length of the bendSearching of Bends

Pipe’s Diameter ＞ Mesh Size
Next node

Current nodeSearching of Bends

Step1
L : the minimum vertical length

Temporarynoded2≧Ld1<R
Current node

Diameter：R

Searching of Bends

Step2

TemporarynodeInterference Check!

Current node

Diameter：R

Searching of Bends

Step3

Next node

Recording Costs

Current nodeExperiments
Purpose to verify the useful of the algorithm

Test Case Setting Design Area : X 16.75m, Y 3m, Z 3m
 Mesh Size: X 0.25m, Y 0.25m, Z 0.25m

 Start Point: ( 0.5m, 1.75m, 1.5m), x+ Goal Point: ( 16.5m, 1. 5m, 1.5m), x- 10 boxes as obstacles

Experiments

d1

Cost of a Straight Pipe : 1 per 1m

Experiments
d2
d1

Cost of a Elbow : d1 + d2 + 0.1

Experiments
d2
d1

Cost of a Bend : d1 + d2 + 0.3

Experiments
Design Objectives for This Test
 to minimize the total length of pipes
 to minimize the number of elbows and bends

 to avoid passing aisles as possible
 to pass through pipe-rack areas as possibleResults (R=0.2m)

Bends

○×

Num. of Elbows

99

Num. of Bends

0

Total Costs

17.9

17.9

Time[s]12851260

Results (R=0.3m)

Bends

○×

Num. of Elbows

79

Num. of Bends

1

Total Costs

19.0

19.4

Time[s]447306

Results (R=0.4m)

Bends

○×

Num. of Elbows

79

Num. of Bends

1

Total Costs

19.5

19.9

Time[s]387298

Results (R=0.5m)

Bends

○×

Num. of Elbows

89

Num. of Bends

1

Total Costs

19.6

19.9

Time[s]373288

Results (R=0.6m)

Bends

○×

Num. of Elbows

78

Num. of Bends

1

Total Costs

21.5

22.3

Time[s]8068

Results (R=0.7m)

Bends

○×

Num. of Elbows

99

Num. of Bends

0Total Costs

22.4

22.4

Time[s]6853

Results (R=0.8m)

Bends

○×

Num. of Elbows

99

Num. of Bends

0

Total Costs

22.4

22.4

Time[s]6350

Results (R=0.9m)

Bends

○×

Num. of Elbows

1415

Num. of Bends

1

Total Costs

26.7

27.5

Time[s]4544

Results

 The algorithm practical design including bends.

Results The algorithm generated optimized solutions by each case.

Discussion
Pattern A
Diameter [m]Time[s]
0.9
450.8
63
0.7
680.6
800.5
373
0.4
387
0.3
447
0.21285

 It took more time to search a routing with smaller diameter.
Why?

The decrease of diameter causes
an increase of the searching space.

Discussion
As a result in other test case…

Especially in very
narrow space An obtained route interfered with itself!

Discussion
Node3

Node2

Node4

Coordinates : same
Directions : different
Node1

Node5

Outline
1. Background and Purpose- Previous Research
2. Routing Algorithm Including Bends- Approach- Dijkstra’s Method- Outline of “Bends”- Experiments
3. Conclusion and Challenges

Conclusions
Advantages of the algorithm
 The mesh size is free.
 The algorithm generate practical designs with bends.
 The algorithm generate routes with minimum costs.

Conclusions
Advantages of the algorithm
 The mesh size is free.
 The algorithm generate practical designs with bends.
 The algorithm generate routes with minimum costs.

Conclusions
Advantages of the algorithm
 The mesh size is free.
 The algorithm generate practical designs with bends.
 The algorithm generate routes with optimum costs.
guaranteed!

Future Works
We need to …
 improve the routing algorithm consider about pipe-rack and aisle areas
 make better the interference check algorithm
 create more maintainable systemby the use of XML input / output
 associate the routing algorithm withthe equipments layout algorithm

This system will be opened for free at
http://sysplan.nams.kyushu-u.ac.jp/gen/index.html