International Conference on Computer Applications in Shipbuilding (ICCAS-2009) Shanghai, China
Vol.2, pp.121--126.

AUTOMATIC DESIGNOPERATIONALITY

FORPIPEARRANGEMENTCONSIDERINGVALVE

H Kimura, Kyushu University, JapanS Ikehira, Kyushu University, JapanSUMMARY
We propose a novel evaluation method of valve operationality for pipe-arrangement design, and multi-objective genetic
algorithms (GAs) suitable for the pipe-arrangement problems are developed. The pipe-arrangement design inshipbuilding requires not only to arrange all pipes without interference but also to make space from pathways to valves
so that crew can access the valves. For this reason, it needs sophisticated skill, and is considered that numericalevaluation for pipe-arrangement designs is difficult. To evaluate pipe-operationality, we propose a recursive-fillalgorithm to judge whether the arranged valves are accessible by crew or not. In the proposed genetic algorithms, only
the parameters of location and directions of valves are encoded, and the other parameters are generated by amodification operators that are similar to local-search algorithms. The proposed approach is demonstrated throughcomputational experiments that contain five valves, one pump and five branches in the diagram, and remarks areprovided for applying this methodology to practical pipe-arrangement design problems.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1.

INTRODUCTION

Pipe arrangement design in shipbuilding needs highlysophisticated skill, and it is considered that numericalevaluation or automatic arrangement are quite difficult.
One reason is that considered items are plural; Materialcosts, assembly costs, convenience of valve operation orpipe-maintenance, etc. The other reason is that many
considered items are ambiguous or defined without
numerical evaluation. Therefore, automatic pipearrangement will be possible by means ofz Defining numerical evaluation for all considereditems , andz Formulating the pipe-arrangement problem into a
multi-objective optimization problem.
Based on this idea, we propose a new approach to solve
the problem.
The pipe-arrangement design in shipbuilding requires not
only to arrange all pipes without interference but also tomake space from pathways to valves (or some otherequipment) so that crew can access the valves. Thisaccounts largely for requiring sophisticated design skills.
Since the designing know-how is implicit, the evaluationof the pipe-arrangement design is ambiguous and it isconsidered that numerically sound evaluation is difficult.
In our previous works, we proposed a formulation ofpipe-arrangement problems including valves and pipebranches to develop an automatic designing system thatgenerates rough arrangement of pipes and equipments for
CAD operators[1][2][3]. In this paper, we propose anovel numerical evaluation algorithm of valve
operationality, and formulate a pipes-and-valvesarrangement problem as a multi-objective optimization
problem. Since it includes not only numerical but
combinatorial optimization, we developed multiobjective genetic algorithms (GAs) suitable for the pipearrangement
problems. The proposed approach isdemonstrated through computational experiments that
contain five valves, one pump and five branches in thediagram, and remarks are provided for applying thismethodology to practical pipe-arrangement designproblems.
2.
AN EVALUATION ALGORITHM FOR
VALVE OPERATIONALITY
2.1

VALVE OPERATIONALITY

Valves are essential equipment manipulated by crew.
Since almost valves are worked by hand, the pipes andvalves must be arranged to make space from pathways tothe valves so that the crew can access and operate thevalves. Here we refer to the evaluation of the enoughspace from pathways to the valves as “valveoperationality”, and defined as below.
2.1 (a) Accessibility
We define that a valve is “accessible” in the case ofz Crew can move to a position where the valve can beoperated by hand, orz Crew can move to a position where the valve cannot
be operated by hand, but can be operated by sometools (rods, etc.).
The arrangement plan must be accessible for all valves.
2.1 (b) Possibility of Valve HandlingWe define “possibility of valve handling” as the valve
can be operated by hand. In the two cases above, it isobvious that the arrangement plan of the former issuperior than the latter because the former does not need
any tools for the valve operation.
2.2

EVALUATION ALGORITHM

In this section we describe an algorithm for calculate theaccessibility and the convenience of valve handling.

International Conference on Computer Applications in Shipbuilding (ICCAS-2009) Shanghai, China
Vol.2, pp.121--126.

2.2 (a) Overview of The Algorithm
In order to evaluate valve operationality, we need torecognize whether the space from the pathway to thevalves is enough or not for the crew. Therefore, wepartition the design space into regular grids, anddistinguish free cells from ones occupied by obstacles.
Thereafter, the accessibility and the possibility of valve
handling are checked in the cellular space as below. We
refer to the cells that include or intersect obstacles (i.e.,pipes, valves, or other equipments) as “obstaclesegments”, and the cells that are put in pathways as “aislesegment”. We define “worker-segment matrix” asaggregated cells imitating shape of the crew (worker).
The cells that are swept by the worker-segment matrix
without intersecting obstacle segments starting from anaisle segment are recognized as “accessible segments”.
Then, both the accessibility and possibility of valve
handling for an arbitrary valve are easily evaluated bycounting the grids between the cell containing thecorresponding valve and the nearest accessible segments.
Figure 1 shows an example of the calculation procedure.

1.
2.
3.
4.
5.
6.

7.

Partition the design space into grids at regularintervals of some distance k.
Find obstacle segments that include or intersect
obstacles.
Find aisle segments that are put in pathways.
Define worker-segment matrix in the size ofl×m×n.
Recognize accessible segments using Recursive
Fill algorithm.
Find minimum distance from each valve toaccessible segments that are located in thedirection of the axis of the valve’s handle orfour directions perpendicular to that axis.
Sum up the minimum distance over all valves.

Figure 2 shows the detail of the calculation procedure.
Recursive Fill algorithm shown in the step 5 is describedin the next section.
Figure 2: Valve operationality evaluation algorithm
2.2 (c) Recursive Fill Algorithm
This algorithm is used to recognize accessible segments.
It is a kind of 3D-sweeping algorithm that the workersegment matrix is swept in the design grid-space without
intersecting obstacle segments. The outline of theprocedure is described below.
Select one cellular segment where worker-segment
matrix can be put without intersecting obstacle segments
in aisle segments. Expressing the coordinate of theselected segment as ( x 0 , y 0 , z 0 ) , then execute a
method fill ( x 0 , y 0 , z 0 ) . In the method offill ( x, y, z ) , the corresponding cellular segment( x, y, z ) is checked whether it is already labelled asaccessible or not. When the segment is not labelled, it ischecked whether the worker-segment matrix can be put
without intersecting obstacle segments at this segment.
When it is possible, the method fill () is recursively

Figure 1: An example of the calculation procedure of the valve
operationality

2.2 (b) The Detailed Explanation of the Algorithm

applied to neighbour six cellular segments (up, down,back, forth, right and left). Using C like language
expression, the method fill ( x, y, z ) is described as
Figure 3. The function
WorkerSegmentMatrix_intersects_with_ObstacleSegment_at( segment[x][y][z] ) returns false when the workersegment matrix containing segment[x][y][z] can be put
without intersecting obstacle segments.

International Conference on Computer Applications in Shipbuilding (ICCAS-2009) Shanghai, China
Vol.2, pp.121--126.

fill( int x , int y , int z){if(segment[x][y][z]==NotLabeled){
if( WorkerSegmentMatrix_intersects_with_Ob
stacleSegment_at( segment[x][y][z] ) ==false ){
segment[x][y][z] = AccessibleSegment ;fill( x+1 , y , z ) ;fill( x-1 , y , z ) ;fill( x , y+1 , z ) ;fill( x , y-1 , z ) ;fill( x , y , z+1) ;fill( x , y , z-1) ;}else{
segment[x][y][z] = InaccessibleSegment ;}}else{return;}}
Figure 3: Recursive Fill algorithm: fill(x,y,z)
3.
GENERATING CANTIDATES FOR THE
SOLUTION OF THE PIPE-ARRANGEMENTPROBLEM

3.3

DESIGNING GENE CODING

In our pipe-arrangement problems, since the design
parameters are locations and directions of valves,bending patterns of path of pipes and length of thestraight parts of the pipes, it is a combination ofnumerical optimization and combinational optimization.
Therefore, conventional coding methods such as binary
coding, gray coding, real-coding, etc. cannot be applied
without modification. Putting all design parameters into amatrix as genes is the most simple approach, but it isquite wasteful because many design parameters arestrongly related each other or depend on the otherparameters. For example, if the location of valves arechanged, the parameters of the pipes that are connected
the removed valves would not be feasible any more. We
consider that the locations and directions of the valves
are dominant to ones of the pipes. For this reason, weencode only the parameters of the locations anddirections of the valves as the genes for the MOGA. Let( xi , y i , z i ) be a location of a valve i , where eachcomponent is continuous variable as shown in Figure 4,and let θ i be the direction of the handle of the valve i ,where θ i takes one of twelve discrete values as shown inFigure 5.

3.1
FORMULATION AS A MULTI-OBJECTIVE
OPTIMIZATION PROBREM
In our previous works, we proposed a formulation ofpipe-arrangement problems including valves and pipebranches as an single-objective optimization problem. In
this paper, we consider two-objective functions; One isthe valve operationality introduced in the previoussection. The other is a material cost defined as follows:

Figure 4: Location of Valvenpf _ material = ∑Wk Lk Dk , where
k =1

k ：Index of the corresponding pipe,
Wk ：Material cost per unit weight of the pipe k,Lk ：Length of the pipe k,
Dk ：Diameter of the pipe k.
In this section, we explain our optimization algorithm tosolve the pipe arrangement design problems.
3.2

NONDOMINATED SORTING GENETIC
ALGORITHM II (NSGA-II)
In multi-objective optimization, since plural objectivefunctions that have trade-off relations each other must be
considered, selection strategy for generation alternationis very important for multi-objective genetic algorithms(MOGA). Deb’s NSGA-II [4] and Zitzler’s SPEA-II [5]are representative methods in MOGA. In this paper, weadopt NSGA-II for the selection strategy.

Figure 5: Direction of ValveIn this paper, locations and directions of all valves are
expressed by the following matrix as the genome of thevalves:

International Conference on Computer Applications in Shipbuilding (ICCAS-2009) Shanghai, China
Vol.2, pp.121--126.

⎡θ1 θ 2⎢x x2
⎢ 1
⎢ y1 y 2⎢⎣ z1 z 2

L θn ⎤
L x n ⎥⎥.
L yn ⎥⎥
L zn ⎦Figure 8, and the pipeline list shown in Figure 9 specifies
the connection between the pipes and equipments.

This coding does not inhere the information of the pipes.
Pipes are arranged by the other search algorithm [3] after
the locations and directions of the valves are given.
3.4

DESIGNING CROSSOVER OPERATOR

We apply one-point crossover to the genome. It selects asingle crossover point randomly on both parent’sorganism strings, and all data beyond that point in eitherorganism string is swapped between the two-parentorganisms. The resulting organism are children as shownin Figure 6.

Figure 7: Pipe diagram in the experiments

Figure 8: Equipment arrangement list
Figure 6: One-Point Crossover

3.4

DESIGNING MUTATION OPERATOR

The mutation is applied to each generation genome atsome constant probability referred as a mutation rate.
The genome to which the mutation is applied is selected
at random following constant probability.
3.5

Figure 9: From-To list (Pipeline list)

DESIGNING MODIFICATION OPERATORIn this paper, a solution candidate of the arrangement ofvalves is regarded as infeasible when the valves interferewith each other. It is too difficult to find feasible
solutions using only naïve genetic operators because theprobability of finding feasible solutions exponentiallydecreases as the number of valves increases when thecandidates are generated at random. Therefore, theinfeasible solution candidates of the valve arrangement
are modified to feasible candidates. We refer to thisoperation as modification operator for valve (MOV).
4.

EXPERIMENTS AND RESULTS

4.1

A SAMPLE PROBLEM FORMULATION

To confirm the effectiveness of the proposed method, it
was applied to a pipe arrangement design problem thathave five valves, one pump, and five branch of pipes asshown in Figure 7. Its equipment tables are shown in

4.2

RESULTS

The proposed method was compared with a simpler
method in which a random search is substituted for thecrossover operator. It is not affected to the framework ofthe NSGA-II. Size of the population is set to 10, theparameter α of modification parameter for pipes(MOP)[3] is 10, and the rate for the mutation operator is0.1. All timings are reported for a Pentium IV 2.4GHz
processor with 512MB RAM running Java programcodes on Microsoft WindowsXP. Figure 10, 11, 12 are
the candidates of the solution at the initial generation,,
400th generations and 450th generations respectively. The
horizontal axis denotes the valve operationality(f_operationality), and the vertical axis denotes thematerials cost. The nearer candidates to the origin are thebetter. In the 400th generation, 4.0 × 10 individuals areevaluated and it takes about 60 minutes for the3calculation.

In

the450thgeneration,

4.5 × 10 3

International Conference on Computer Applications in Shipbuilding (ICCAS-2009) Shanghai, China
Vol.2, pp.121--126.

individuals are evaluated and it takes about 70 minutes.
Figure 13 and 14 show the 3-D models generated by theproposed algorithm using one-point crossover in the450th generations. The white wireframe denotes thedesign space, the transparent cuboid is a pathway, andthe black cuboid is a pump. The pipes with the samecolours means the same pipeline.

Figure 13: The result of the best design in materials cost
Figure 10: Solution candidates at initial population

Figure 11: Solution candidates at 400th generation

Figure 14: The result of the best design in the valve
operationality

5.

Figure 12: Solution candidates at 450th generation

DISCUSSIONIn Figure 10, both the one-point crossover and therandom search found good solutions with regard to thevalve operationality. In the progress of the search, thematerials cost is also improved as shown in Figure 11and 12. But comparing the one-point crossover with therandom search in the same individual, the former foundthe better solutions with regard to the materials cost. Inaddition, the one-point crossover generated more various
and better solutions than the ones of random search. TheInternational Conference on Computer Applications in Shipbuilding (ICCAS-2009) Shanghai, China
Vol.2, pp.121--126.

reason of this advantage is considered that the one-pointcrossover generates good candidates from the promising
candidates that are referred as parents. Note that thesearch is converged sufficiently at 400th generations
because the improvement of the 450th generations is little.
From Figure 13 and 14, we can see that the multiobjective optimization algorithms generate multiple
solutions that are superior in the sense of the valve
operationality or the materials cost simultaneously.

6.

CONCLUSIONSIn this paper, we proposed a criterion for valve
operationality in pipe arrangement, and we formulated
the pipe arrangement problems as a multi-objectiveoptimization problem. The criterion for valveoperationality is given by enumerating accessible valves
that is neighbouring accessible space. We also proposeda multi-objective genetic algorithm for the pipearrangement problem. We encoded only the parametersof the locations and directions of the valves as the genes
for the multi-objective genetic algorithms. In this genetic
algorithm, the children of the solution inherits only theparent’s information of valves , and arrangement of pipes
are given by the other heuristics at every new candidate.
However, it is inefficient in the search of pipearrangements. In real pipe-arrangement design, pipearrangement is determined first from the pipe diagram ,and thereafter, valves are set in the arranged pipes. It islargely different from our approaches. Finding a coding
method that inherits the arrangement of pipes is thefuture work.

8.

REFERENCES

1. S. Ikehira, H. Kimura, H. Kajiwara：’Automatic Design for
Pipe Arrangement using Multi-objective Genetic Algorithms’,
12th International Conference on Computer Applications inShipbuilding (ICCAS), Vol.2, pp.97-110, 2005.
S. Ikehira, Hajime Kimura ： ’Multi-objective Genetic
Algorithms for Pipe Arrangement Design’, Proceedings of the2006 Genetic and Evolutionary Computation Conference(GECCO 2006), pp.1869-1870, 2006.

2.

3. Satoshi Ikehira, Hajime Kimura and Hiroyuki
Kajiwara: ‘Automatic Pipe Arrangement Design
considering Operationality of Valves’, Conference
Proceedings of the Japan Society of Naval Architectures
and Ocean Engineers, Vol.4, pp.335--338 (2007) inJapanese.
4. K. Deb, S. Agrawal, A. Pratab and T. Meyarivan：’A fastelitist non-dominated sorting genetic algorithms for
multiobjective optimization: NSGA II’, KanGAL report
200001, Indian Institute of Technology, Kanpur, India, 2000.
5. E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: ‘Improving
the Performance of the Strength Pareto Evolutionary

Algorithm’, In Technical Report 103, Computer Engineeringand Communication Networks Lab (TIK), Swiss Federal
Institute of Technology (ETH) Zurich, 2001.

9.

AUTHORS BIOGRAPHY

Hajime Kimura holds the current position of Associate
Professor at Department of Marine Systems Engineering,
Kyushu University. His previous experience includes
optimization in shipbuilding, etc.
Satoshi Ikehira holds the current position of a candidateof Ph.D. degrees in Department of Maritime Engineering,
Graduate School of Engineering, Kyushu University.