International Conference on Computer Applications in Shipbuilding 2011 (ICCAS2011), Vol.3, pp.93—99.

AUTOMATIC DESIGNING SYSTEM FOR PIPING AND INSTRUMENTS
ARRANGEMENT INCLUDING BRANCHES OF PIPES
H Kimura, Kyushu University, JAPANSUMMARY
Automatic design of piping layout is challenging since it is composed of several numerical and/or combinational
optimization problems, e.g., routing problems of pipes including branches, and arrangement problems of equipments.
This paper presents a new approach that the branches of pipes are considered to be a variety of equipment. Accordingly,
the pipe routing problems are fairly simplified by removing the branches, and it derives a lot of efficient algorithms tosolve the pipe arrangement problems. One is a multi-objective genetic algorithm (MOGA) in which the gene represents
both the locations of the equipments and the arrangement of the pipes. And a new crossover operation which merges two
different piping layouts is proposed. To provide a fairly good initial population for the MOGA, a new heuristics making
use of self-organization techniques to arrange equipments is proposed. The efficiency of the approach is demonstrated
through two experiments, one is a designing problem including five valves, one pump, and five branches, and the otherincludes seven valves, one pump, and six branches.
2.
1.

PROBLEM FORMULATIONINTRODUCTION

Recently, pipe routing design process is reinforced bymaking use of 3D-CAD systems, so that designers caneasily verify the arrangement visually. However,automatic designing of piping layout is challenging
because it is composed of several numerical and/or
combinational optimization problems, e.g., routing
problems of pipes including branches, and arrangement
problems of equipments.
Chen (1999)[1] and Wang et al. (2006)[2] proposed path
planning algorithms based on genetic Algorithms (GA).
Park and Storch (2002)[3] proposed a pipe-routing
algorithm which divides pipes into several pipeline
groups and arranges the pipelines by selecting from finite
patterns. Ito (1999)[4] proposed a new pipe routing
approach combined with Dijkstra path planningalgorithm and GA. Asmara and Nienhuis (2006,2007)[5][6] developed Delft-Route system whicharranges pipes and branches by combining Dijkstra path
planning algorithm and an evolutional algorithm, and it isapplied to a practical ship design problem, and
AISROUTE presented by Martins and Lobo (2009)[7] isalso a similar approach.
This paper presents a new approach that the branches ofpipes are considered to be a variety of equipment.
Accordingly, the pipe routing problems are fairly
simplified by removing the branches, and it derives a lotof efficient algorithms to solve the pipe arrangement
problems. One is a multi-objective genetic algorithm(MOGA) in which the gene represents both the locationsof the equipments and the arrangement of the pipes. And
a new crossover operation which merges two different
piping layouts is proposed. To provide a fairly goodinitial population for the MOGA, a new heuristics
making use of self-organization techniques to arrange
equipments is proposed. The efficiency of the approachis demonstrated through experiments.

The following information must be given to theautomatic piping system in advance:
1) [Design Space] The range of the space to be
designed is given. It is a box-shaped.
2) [Geometric information about equipments] Valves,
pumps, T-branches, and external connection pointsof the design objective space are defined as
equipments. The equipments are expressed by thesize of boxes, and the relative location, orientation,and the diameter of the pipes connecting theequipments are given. Possible mounting directionsof the equipments are also given.
3) [Information about connection of equipments] It isnearly the piping and instruments diagram (PID),
that is, the information about whether or how thepipe connections of the equipments are connected toeach other. In this paper, all the piping branches aredefined as equipments, therefore the destination of apipe connected to one connector of an equipment isonly one.
4) [Geometric information about obstacles] Structuralcomponents and excluded equipments are considered
to be obstacles. The locations and sizes of the
obstacles are represented as a set of boxes andtriangles.
5) [Aisle region] A region used as a passage for thecrew is represented by a set of box. In this region theequipments are not placed. Placement of pipes in thisarea should be avoided as much as possible.
6) [Element placement candidate mesh points]
Elements (that is, equipments and elbows of pipes)
placement candidates are limited to mesh points.
Based on the information above, the automatic piping
arrangement system explores the following design
parameters:
1) [Locations and directions of equipments] Locationsof the predetermined equipments are selected from

International Conference on Computer Applications in Shipbuilding 2011 (ICCAS2011), Vol.3, pp.93—99.

the mesh points by the system. Variations of thedirection parameter are at most twelve. Whenmounting direction of the target equipment isconstrained, the number of the direction variations
would be less than twelve.
2) [Piping routes] Since piping branches are considered
to be a variety of equipment, a pipeline simply
connects two equipments. The start and end
locations, directions, and diameter of the pipeline are
given from the connected equipment's information.
The pipeline’s route is expressed by a list of
coordinates of elbows. Accordingly, the parameters
for routes of pipelines are subordinate to theparameters of connected equipments.

corresponding pipe in the parent A and thereafter thepipe is cut off at an arbitrary elbow. Similarly thepipeline of the B-side is also constructed by inheriting
the corresponding pipe in the parent B and the pipe is cut
off at an arbitrary elbow. Under this condition, thispipeline would be broken at the cut off points. Therefore
a new pipe is drawn between the cut off points within
three elbows. If the pipes are interfering with equipments,
obstacles, or themselves, then cut-off points in theinherited pipes from the parents are changed and a newpipe is redrawn between the cut-off points. Whenmultiple pipelines are interfering, the pipeline which haseither the largest number of interference or the largest
diameter is re-constructed first.

In this paper, all pipes are drawn parallel to the axis
direction of the rectangular design space.
The design parameters are optimized by multi-objective
algorithms specified in the following section 3.3. The
objective of the optimization here is piping cost, numberof elbows and valve operability, but it can change
arbitrary.
3. A NEW AUTOMATIC DESIGNING SYSTEM
3.1 CODING AND CROSSOVER OPERATION
3.1 (a) Gene Coding
A gene for GAs is composed of design parameters which
express locations and directions of equipments andpiping routes. Each element of the gene for equipments
consists of a set of parameters which expresses a location
and a direction of the corresponding equipment. The
gene for pipelines is variable length since the piping
routes are expressed by the position of the elbows, thenumber of which is variable.
3.1 (b) Crossover Operation
This operation generates a new gene of a child C fromgenes of parents A and B. The position and the directionof each equipment in the child C inherits from thecorresponding equipment in the parents either A or B
with probability 50%. The process above is repeated until
two conditions are satisfied: One condition is that
arranged equipments do not interfere each other. The
other is that the child C inherits at least one or moreequipments from the different parent. (That is, the child
C must have equipments from both the parent A and B.)
After the condition above is satisfied, piping routes
connecting equipments are generated as the following:
In the child C, the pipelines of which both sides areconnected to equipments from the parent A are inheritedfrom the corresponding pipelines in the parent A as it is.
Similarly, the pipelines of which both sides areconnected to equipments from the parent B are inheritedfrom the corresponding pipelines in the parent B. Whenone side of the equipment in a pipeline is coming fromthe parent A (here we term it A-side), and the other side
is coming from B (we term it B-side), then the pipelineof the A-side is constructed by inheriting the

Figure 1: An example of the crossover operation
Figure 1 shows an example of the crossover operation.
The pipes in the child C inherit the part of the parent A's
pipes which are connected to the equipments comingfrom the parent A, and also inherit the part of the parent
B's pipes which are connected to the equipments from theparent B. The broken parts of the pipelines in the child C
is redrawn as shown by the dotted lines in the Figure 1.
To avoid falling into an infinite loop of the crossover
operation, the repetition of arranging equipments islimited at most 500 times, and the repetition of redrawing
pipelines is limited at most 100 times. If the process
breaks the limitations, the crossover operation results
failure, then another pair of parents should be selected.
3.1 (c) Mutation Operation
In this operation, one equipment is randomly selected asa target, and the position and the direction of the target
equipment is changed as shown in the following: In
many cases, the random movement of the equipments
results bad arrangement, therefore the target equipment is
randomly moved to neighbour mesh points with 50%
probability, or the target equipment is moved to thecenter of all the equipments which are connected to thetarget equipment. If the modification of the target
equipment described above results interference of pipes
or equipments, then the modification is undid and theoperation is started over from selecting a target
equipment.

International Conference on Computer Applications in Shipbuilding 2011 (ICCAS2011), Vol.3, pp.93—99.

3.2 GENERATING INITIAL POPULATION FOR GA
In our system, a genetic algorithm improves candidatesof the arrangement design using the crossover operationand the mutation operation described in the previous
section. Prior to that, an initial population which iscomposed of feasible arrangement design candidates
must be provided in advance. Therefore, two types ofheuristics are introduced to generate the initial
population: One is Random Equipment Arrangement, theother is Self-organization Equipment Arrangement.
3.2 (a) Random Equipment Arrangement
Locations of all the equipments are randomly selectedfrom the mesh points, and also the directions of all theequipments are randomly determined from the possible
mounting directions. When there exist equipments whichinterfere with obstacles or the other equipments, thecorresponding equipments are re-arranged randomly until
the interference is dissolved. After all the equipments arearranged without interference, pipelines which connect
the equipments are drawn using within three elbows.
When the pipelines interfere with each other or the otherobjects, the system re-arranges equipments which areconnected the most interfered pipeline, and all the
pipelines are re-drawn within three elbows until theinterference is dissolved. Figure 2 shows examples of thesolution candidates generated by this operation.

As shown in Figure 3, an equipment is selected as atarget, and it is moved to the nearest possible meshpoint of the center of all equipments which are connectedto the target equipment. Actually, the destination point of
the center location of connected equipments is weighted
by the diameter of the corresponding pipes. Also thedirection of the target equipment is changed so that the
total length of the pipelines between the target and theother connected equipments becomes shortest. By
applying a random selection of all the movableequipment for such scheme, lean and clean layout can beformed as a whole. However, this approach cannot copewith the following case: One is that there exists many
obstacles in the design space, the other is to consider thevalve operability. For this reason, this algorithm is used
only to generate arrangements for the initial population.

Figure 4: An example of the self-organization operation
Figure 4 shows an example obtained by this algorithm.
Notice that wasteful pipeline drawing is obviously lessthan that of the random arrangements shown in Figure 2.

(a) Example 1

Figure 2:(b) Example 2

Randomly generated arrangements

3.2 (b) Self-Organization Equipment Arrangement
The random arrangement explained above tends togenerate so inefficient candidates that the pipelines run
throughout the space filling as shown in Figure 2. Here I
propose a new algorithm which arranges the equipments
to shorten the pipelines and also to avoid interference.

Figure 3: A basic concept of the self-organization

3.3 FORMULATION OF THE VALVE OPERABILITY
In this paper, the valve operability cost is given by the
total energy consumed by the crew to move to all thevalves from the aisle region going through accessible
space. We define that a valve is "accessible" in the caseof crew can move to a location where the valve can be
operated by hand. I modify the recursive fill algorithm[8] to distinguish the accessible space with standing
position from one with only squat (bending) position.
Here explains the concept of the algorithm using aschematic 2-D sample shown in Figure 5. First, thedesign space is partitioned into regular grids, and freecells are distinguished from ones occupied by obstacles.
We refer to the cells that include or interfere withobstacles (i.e., pipes, valves, or other equipments) as"obstacle segments", and the cells that are put inpathways as "aisle segments". We define "standing
worker-segment matrix" as aggregated cells imitating
shape of the standing crew (worker), and "squat workersegment matrix" as aggregated cells imitating shape ofthe squatting crew. The cells that are swept by the squat
worker-segment matrix without interfering with obstacle
segments starting from an aisle segment are recognizedas "accessible segments by squatting" (See pinksegments in Figure 5 upper). Similarly, the cells that areInternational Conference on Computer Applications in Shipbuilding 2011 (ICCAS2011), Vol.3, pp.93—99.

swept by the standing worker-segment matrix arerecognized as "accessible segments by standing" (seeblue segments in Figure 5 downward).

4.

EXPERIMENTS

4.1 SIMULATION SETTING
To confirm the effectiveness of the proposed method, it
was applied to two types of pipe arrangement design
problems: One has five valves, one pump, and fivebranches as shown in Figure 7, and the other has sevenvalves, one pump, and six branches as shown in Figure 8.
The PID in Figure 7 is the same as shown in [8], but thesize of the design space is that the width is 5 [m], thelength is 5 [m] and the height is 2 [m] which is less thanthe height 5 [m] shown in [8]. Also it has the double sizeof the diameter of the pipeline through CP0, T-000, T004, Valve-004 and CP1. That is, geometric constraint inthis paper is tighter than [8]. The PID in Figure 8 is given
by modifying the PID in Figure 7 adding two valves, one
T-branch, and one external connection.

Figure 5: Recursive fill algorithm to find accessible
space
After that, the energy to move to the valves is calculated
in the following. First, the segments where the crew
would operate the valves are identified. And a pathplanning from each segment where the crew would
operate the valve to any segments in the aisle region is
executed through the accessible space found by themodified recursive fill algorithm. Dijkstra method is used
for the path-planning. The consumed energy by the crewis estimated using RMR (relative metabolic rate). The
movement energy with squatting is larger than the one
with standing. For example, in Figure 6, right side pathneeds less energy than one of left side path, because thesquatting section is smaller. These schemes describedabove are explained only in a 2-dimensional space,however, it is executed actually in 3-dimensional space.
In the case that there exist valves which the crew cannot
access, a large amount of cost is estimated as a penalty.

Figure 7: PID of 5 valves

Figure 8: PID of 7 valves

Figure 6: Two routes to a valve

It is three-objective optimization (minimization): The
first is material cost, the second is the number of theelbows, and the third is the valve operability cost. The
material cost is estimated by multiplying the length andthe diameter of the pipes same as [8]. NSGA-II [9] isused as the multi-objective genetic algorithm that is thesame as [8]. From preliminary experiments, thepopulation size is set to 80 in the problem of five valves,and is set to 200 in the problem of seven valves.

International Conference on Computer Applications in Shipbuilding 2011 (ICCAS2011), Vol.3, pp.93—99.

4.2 RESULTS
All timings are reported on the Intel Core2 Quad
2.66GHz processor with 2GB RAM running Java ver.1.6
program codes on Microsoft Windows-XP. In the
problem of five valves in the Figure 7, the calculation
period for the evaluating solution candidates 18,880
times is about 10 days. Especially, the calculation time
for generating the only initial population with 80
individuals takes 3.5 days of the 10 days. In the problem
of seven valves in the Figure 8, the calculation period forthe evaluating solution candidates 20,000 times is about
7 days, and the calculation time for generating the initial
population with 200 individuals takes 2 days of the 7days.
On the first stage of the optimization, the proposedsystem attempt to generate the initial population partly
using Random Arrangement method. In the case that theequipments and pipelines are to be arranged into narrowdesign space, the Random Arrangement method canhardly find feasible solutions, therefore the calculation
time to generate the initial population takes too much.
Figure 9 shows a pareto solution that consists of thesmallest number (that is 13) of elbows at the 18,880th
evaluations in the problem of five valves. The yellow
transparent box is a pathway, the red box is a pump, andthe dark gray objects are obstacles. All the pareto
solutions got similar layout that arranges the equipments
connected to fat pipes in a linear to shorten the fat pipes.
However, migration paths expressed by dotted purple
lines in the Figure 9 are often formed above pipes orvalves, therefore the cost to place grating or the cost of
the crew's position to operate valves must be consideredin practice.

2.6475, number of elbows is the best 22, and the valve
operability cost is 286.0.

Figure 10: A solution in the problem of 7-valves

Figure 11: A solution in the problem of 7-valves
The valve operability of the solution in Figure 10 issuperior to one of Figure 11, however, in the sense thatthe space secured widely like as in Figure 11 is preferred.
It will need to consider in evaluation. Due to space
limitations, the specific description is omitted, but the
proposed method held a set of all the pareto solutions, somany useful solutions are generated.

Figure 9: A solution in the problem of 5-valves
Figure 10 and 11 are typical pareto solutions at the
20,000th evaluations in the problem of seven valves. In
the figures, dotted purple lines denote minimum-cost
migration paths. In the solution shown in Figure 10, thematerial cost equals 2.7975, number of elbows is 24, andthe valve operability cost is the best 270.8. In thesolution shown in Figure 11, the material cost equals

Figure 12, 13, and 14 show the best solutions in thematerial cost, number of elbows, and the valve
operability respectively along the optimization process ofthe problem of seven valves.
Since the optimization here is three objective.
It is difficult to illustrate distribution of the pareto
solutions in 2-dimensional, however, Figure 15 shows
the candidates of the solution at the initial generation,
1200th, 2400th, 4800th, 9600th, 15000th, and 20000th
generations. The horizontal axis denotes the valve
operability, and the vertical axis denotes the materials
cost. The nearer candidates to the origin are the better.
Figure 16 shows the number of pareto solutions along theprocess of the optimization.

International Conference on Computer Applications in Shipbuilding 2011 (ICCAS2011), Vol.3, pp.93—99.

Figure 12: Best solution of material cost in GA
population

Figure 15: Pareto solutions at each search stage

Figure 13: Best solution of number of elbows in GA
population

Figure 16: Number of pareto solutions
5.

Figure 14: Best solution of valve operability in GA
population
From Figure 12, 13, and 14, we notice that optimum
solutions were found at the 15000th evaluations at eachobjective function, but from Figure 16, the system found
new pareto solutions after that. That is, since the NSGAII method used in the proposed algorithm does not allow
holding duplicate solution candidates, plural different
solution candidates which have the same costs are
generated.

DISCUSSION

5.1 SEARCH PERFORMANCE
Since experimental setting is rather different fromprevious works, a direct comparison is a stretch, but thequality of obtained solutions is dramatically improved.
However, from Figure 9, 10 and 11, we notice that thesolutions can improve by changing positions of someequipments or arrangements of pipes. The crossover
operation and the mutation operation have room for
improvement.
Also, the pipe drawing method used in the Random
equipment arrangement method and Self-organizedequipment arrangement method and the mutation
operation is too primitive that draws a pipeline between
corresponding two equipments simply within 3 elbows.
For this reason, if too many obstacles are put in thedesign space, generating the initial population may be
impossible in our system. Therefore, we are planning to
make use of Dijkstra path planning method to generate
pipelines between the equipments as a future work.
5.2 SHOWING PLURAL OPTIMUM SOLUTIONS
The multi-objective genetic algorithm used in our
approach does not allow holding duplicate solutions in
the population, however the cost can be the same.
Therefore the plural different pareto-optimum solutions

International Conference on Computer Applications in Shipbuilding 2011 (ICCAS2011), Vol.3, pp.93—99.

were shown as shown in Figure 10 and 11. In real piping
arrangement design, the case would be exist that somedesign criteria are obscure, then the system which canshow plural optimum solutions is practical.
5.3 LAYOUT CONSIDERING PIPING SUPPORTS
In our approach, geometrical information of the aisle
region is given as a set of boxes in advance. Accordingly,
the system avoids putting pipes in that region making useof the cost function. To introduce the similar mechanism,
it is easy to draw pipes along walls or pipe-racks where
piping supports are easily placed. However, notice thatthe user's load would increase to give the systemgeometrical information of the pipe-rack space as a set ofboxes.
5.4 RULES EXPRESSED BY XML AND
CONNCTION WITH CAD SOFTWARE
The proposed system makes use of XML (extensive
markup language) files as the interface between the othersystems. The connection with CAD software will begood since it is easy to convert the other file format. Also
the system use file converter from plot-plan XML files to
3-D model X3D files. In real arrangement problems,possible mounting directions of the equipments are often
constrained, so in the proposed system, the conditions of
the mounting equipments are specified in the geometricalfeature of the equipments which is expressed by XML. In
the experiments, only the valves, pumps, T-branches, andconnections to outsides are expressed as the equipments.
However, any types of equipments such as concentric or
eccentric reducers, crossing branches or strainers can beeasily defined as similar equipments by using XML.
How to express the general design guide for pipearrangement or regulations by XML is a future work.
6.

8.
1.

2.

3.

4.

5.

6.

7.

8.

CONCLUSIONS
9.

This paper presents a new automatic piping arrangement
approach. First, the branches of pipes are considered to
be a variety of equipment. Accordingly, the pipe routing
problems are fairly simplified by removing the branches,
and it derives many efficient algorithms to solve the pipearrangement problems. One is a gene coding method forgenetic algorithms in which the gene represents both thelocations of the equipments and the arrangement of thepipes. And a new crossover operation which merges two
different piping layouts is proposed. To provide a fairly
good initial population for GA, a new heuristics making
use of self-organization techniques to arrange
equipments is proposed. The efficiency of the approachis demonstrated through experiments.
7.

ACKNOWLEDGEMENTS

This work was supported by Japan Society for the
Promotion of Science (JSPS) Grant-in-Aid for Scientific
Research (B) 23360388.

9.

REFERENCES
S. Sandurkar and W. Chen: 'GAPLUS-Genetic
Algorithms Based pipe Routing Using Tessellated
Objects', Journal of Computers in Industry, Volume38, Issue 3, pp.209-223, April 1999.
H. Wang, C. Zhao, W. Yan and X. Feng: 'ThreeDimensional Multi-Pipe Route Optimization Basedon Genetic Algorithms', Knowledge Enterprise:Intelligent
Strategies
in
Product
Design,Manufacturing, and Management, Springer Boston,
vol.207, pp.177-183, 2006.
J. Park and R.L. Storch: 'Pipe-routing algorithm
development: case study of a ship engine roomdesign', Expert Systems with Applications, Volume
23, Issue 3, pp. 299-309, 1 October 2002,
T. Ito: 'A genetic algorithm approach to piping route
path planning', Journal of Intelligent Manufacturing,10(1), 1999.
A. Asmara and U. Nienhuis: 'Automatic piping
system in ship', COMPIT - 5th Int. Conf. on
Computer and IT Application Mar. Ind. 2006.
A. Asmara and U. Nienhuis: 'Automatic Piping
System Implementation: A Real Case', COMPIT 6th Int. Conf. on Computer and IT Application Mar.
Ind. 2007.
P.T. Martins and V.J.A.S. Lobo: 'A tool for
automatic routing of auxiliary circuits in ships',
EPIA'09 - 14th Portuguese Conference on Artificial
Intelligence, ALEA - Artificial Life and Evolutionary
Algorithms, Aveiro Oct. 2009.
H. Kimura and S. Ikehira: Automatic Design for
Pipe Arrangement Considering Valve Operationality',
Proceedings of the International Conference on
Computer Applications in Shipbuilding 2009
(ICCAS 2009) Vol.2, pp.121--126, Shanghai, China,
1--3 Sep 2009.
K. Deb, S. Agrawal, A. Pratab and T. Meyarivan：'A fast elitist non-dominated sorting genetic
algorithms for multiobjective optimization: NSGA
II', KanGAL report 200001, Indian Institute ofTechnology, Kanpur, India, 2000.

AUTHORS’ BIOGRAPHIES

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.