A particle swarm optimization based approach for ship pipe route design

Abstract

Ship pipe route design (SPRD) is to search the near optimal pipe routes that meet various constraints and objectives in a constrained ship space, which is one of the most time-consuming and difficult process in ship production. This paper proposes an automatic approach for solving the SPRD problem based on the grid theory and particle swarm optimization (PSO) algorithm. The fitness functions which are used in the PSO algorithm are formulated to evaluate the engineering objectives and constraints. A fixed-length particle encoding is improved according to the characteristics of ship pipe routing in 3-D space to overcome the shortcomings of variable-length encoding. Mutation operation is combined with the computing process of PSO to avoid the problem of local optimum and to accelerate the convergence rate. Based on the proposed algorithm, the multi-swarms optimization with co-evolution mechanism is applied to solve the problem of multiple pipes and branch pipe routing. The simulations of pipe routing examples are conducted by using VC++ and OpenGL, which demonstrate the feasibility and efficiency of the proposed algorithm. Results show that our approach can route the most common variations of ship pipes automatically under certain constraints in 3-D space. Moreover, the approach can also be applied to other similar path-planning or pipe-routing problems.

Keywords

Particle swarm optimization (PSO)ship pipe route design (SPRD)multiple pipes routing branch pipe routing grid theory

1. Introduction

Pipe route design (PRD) has been a popular research topic since 1970s. The goal of PRD is to find optimal route or path between interface locations under various kinds of constraints in a 2-D or 3-D layout space. Lots of methods are studied, including: deterministic methods, e.g., maze algorithm [18], escape algorithm [10], $A^{*}$ algorithm [26], and shortest path fast algorithm (SPFA) [6]; nondeterministic methods, e.g., genetic algorithm (GA) [11], ant colony optimization (ACO) [7,8], and particle swarm optimization (PSO) [19]; other methods, e.g., expert system [13,24], and software system or package developed with several algorithms [1–4].

The design of ship piping system usually includes five successive phases: preliminary design, functional design, detail design, production engineering, and system support information. Ship pipe route design (SPRD) plays an important role in the detail design phase since it takes over 50% of the total detail design man-hours and many other activities of detail design depend on it [22]. However, it still relies on pipe engineers’ experience and CAD software. A large amount of pipes have to be routed manually in working areas according to various rules and regulations. To improve the efficiency and quality of SPRD, some automatic methods have been proposed. Kang et al. [13] developed an expert system to route pipelines automatically. Park et al. [22] described a cell-generation method to get pipes on the basis of routing patterns. Lu et al. [21] proposed a space modeling method to simplify environment for 3-D pipeline in a ship engine room. Fan et al. [7,8] and Jiang et al. [12] used several methods based on ant colony algorithm to solve the SPRD problem. Asmara and Nienhuis [1–4] provided a pipe routing framework for detailed ship design. Kimura and Ikehira [16,17] described pipe arrangement considering valve operationally and branches. Kim et al. [15] presented a pipe routing system in practical CAD environment using network optimization. In a word, lots of methods have been proposed and verified so far, among which the most complete and mature system is developed by Asmara [1].

In Asmara’s work [1], different path finding algorithms were utilized and compared, and $A^{*}$ was regarded as the most efficient one to route a pipe in the grid layout space. However, $A^{*}$ is inappropriate in some routing cases where heuristic optimization methods tend to be employed. These common cases include as follows: (1) As a kind of deterministic algorithm, $A^{*}$ generates only one candidate solution in a static layout space, while heuristic optimization could provide alternate solutions in different runs. Users could also get their preferred pipe routes by adjusting the cost weights that determine the relative emphases of the various costs with respect to the overall cost function. (2) The result of $A^{*}$ is sensitive to the routing order of multiple pipes. In the case shown in Fig. 1(a), there is no way to route pipe 1 because it is blocked by pipe 2. In this case, those two pipes should be re-routed to find the solution. In another case as shown in Fig. 1(b), if pipe 1 is optimally routed, pipe 2 is blocked, and vice versa. To solve this mutually intervening problem, heuristic optimization such as GA and PSO could be used to find the layout for two or more pipes at the same time [1].

Fig. 1.

Mutually intervening case.

In this paper, a method based on PSO algorithm is proposed to solve the SPRD problem. PSO is originally attributed to Kennedy, Eberhart, and Shi [14,23] and was first intended for simulating social behavior, as a stylized representation of the movement of organisms in a bird flock or fish school. It was observed powerful to find optimal solutions of the numerical and qualitative problems. Moreover, it is a very efficient global searching algorithm which has fewer parameters and simpler implementation. Many research studies have been carried out to solve path planning or PRD using PSO algorithms. Foo et al. [9] presented a 3-D path planning problem formulation and solution approach using PSO. Liu et al. [20] simplified the aero-engine 3-D rotational space into 2-D planes, and then modified PSO was employed to solve the pipeline arrangement in this 2-D model. Asmara [1] briefly mentioned a method to solve the PRD problem using PSO. In Asmara’s method, the space is also divided into grids. A chromosome is defined as a turning grid location of the path, in which such location indicates a pipe bend. And the number of chromosomes in a population is the same as the maximum number of turning locations.

However, the SPRD problem has its own characters compared with pipeline arrangement in 2-D space or robot path planning in a free space. Ship pipes need to be routed orthogonally in 3-D working area under various kinds of constraints. Therefore, PSO is modified and adopted to find optimal pipe routes in 3-D space, which provides a novel method to solve SPRD. Furthermore, based on the method of routing single pipe, an algorithm framework is proposed to solve the routing of multiple pipes and branched pipes, in which pipes and branches are presented by different swarms. In this paper, the potential of routing pipe with PSO algorithm is validated using the designed test cases, and the weights of constraints in fitness functions were set manually by trial. In order to apply the proposed method in real ship piping, some following researches need to be done in the future, e.g., validating the method using real CAD model data, calibrating the weights of the constraints to fit engineering requirements, etc.

The rest of the paper is organized as follows. Section 2 describes the principle of PSO algorithm. Section 3 presents the formulation of the SPRD problem. Section 4 describes the process of solving SPRD based on the modified PSO algorithm. Section 5 provides the simulations conducted and discusses the results. Finally, Section 6 concludes the paper.

2. Particle swarm optimization (PSO) algorithm

In the PSO, an initial randomly generated swarm (a set of particles) flies towards an optimal solution in the D-dimensional search space where each particle represents a potential solution to the optimization problem, and reaches the global optimum over a series of iterations. Each particle in the swarm explores the problem space based on the information provided by previous best particles and the global best particle. PSO then uses this information to generate a velocity vector indicating a search direction towards a promising solution, and updates the locations of the particle.

Each particle with index k in the swarm, $swarm = {x_{1}, \dots, x_{k}, \dots, x_{N}}$ , is represented by the following symbols:

v_{i}^{k} (t)

ith dimensional component of the velocity of particle k at time t.

x_{i}^{k} (t)

ith dimensional component of the position of particle k at time t.

p_{i}^{k} (t)

ith dimensional component of the personal best (pbest) position of particle k at time t.

p_{i}^{g} (t)

ith dimensional component of the global best (gbest) position of the swarm at time t.

At each iteration in a PSO process, velocity and position updates are performed for each dimensional component, $i \in [1, D]$ , and for each particle, $k \in [1, N]$ , as follows: $\begin{array}{l} (1) & \begin{matrix} v_{i}^{k} (t + 1) = & w \times v_{i}^{k} (t) + c 1 \times rand () \times (p_{i}^{k} (t) - x_{i}^{k} (t)) \\ + c 2 \times rand () \times (p_{i}^{g} (t) - x_{i}^{k} (t)), \end{matrix} \\ (2) & x_{i}^{k} (t + 1) = x_{i}^{k} (t) + v_{i}^{k} (t + 1), \end{array}$ w is the inertia weight, which affects the convergence and exploration-exploitation trade-off in PSO process. A review of inertia weight strategies in PSO was given by Bansal et al. [5]. $c 1$ and $c 2$ are the acceleration constants, which usually are equal to 2. $rand ()$ is a function used to generate random variable uniformly distributed in the range of $[0, 1]$ .

Each of the terms of the velocity updates equation play different roles. $w \times v_{i}^{k} (t)$ , called the inertia component, represents the contribution of the previous velocity over the current velocity. $c 1 \times rand () \times (p_{i}^{k} (t) - x_{i}^{k} (t))$ , called the cognitive component, causes the particle to move to the regions in which it has experienced good individual fitness. $c 2 \times rand () \times (p_{i}^{g} (t) - x_{i}^{k} (t))$ , called the social component, causes the particle to move to the best region that the swarm has found so far. $rand ()$ causes the components to have a stochastic influence on the velocity update. Depending on the problem to be solved, iteration process is repeated until the stopping condition is met. Some stopping conditions include: a pre-set number of iterations is exceeded, velocity updates become zero, a number of iterations is exceeded since the last update of the global best solution, or a pre-defined target fitness is achieved.

In order to prevent oscillations, velocity clamping is used to control the maximum velocity of each particle. For a search space with the range $[- x_{max}, x_{max}]$ , velocity clamping limits the velocity to the range $[- v_{max}, v_{max}]$ , where $v_{max} = e \times x_{max}$ , and e represents a clamping factor, $e \in [0.1 \sim 1.0]$ . And in case where the search space is bounded by the range $[x_{min}, x_{max}]$ , $v_{max}$ could be defined as $e \times (x_{max} - x_{min}) / 2$ .

It can be seen from the PSO algorithm that the length (dimension) of the particle encoding needs to be fixed, i.e., fixed-length encoding. An alternative to fixed-length encoding is variable-length encoding, which is commonly adopted to solve path planning problem in grid space. E.g., a pipe route can be encoded as a series of continuous grid positions or a series of direction vectors indicating the movements of an object from the starting point to the end point. But in our method, a pipe route is converted from a particle which is encoded as a series of control points in pipe path (see Section 4.1). Since the number of control points is fixed and not too much, the performance based on this fixed-length encoding is much higher than that based on the variable-length encoding used by Ito [11]. Also, the proposed encoding method significantly differs from Asmara’s method [1], in which the number of pipe bends should be specified in advance. Moreover, the fixed-length encoding mechanism designed for PSO algorithm can be adopted by other evolutionary algorithms to solve pipe routing problem. In order to meet some special constraints of SPRD as well as to fit the pipe routing in 3-D space, the PSO algorithm is also modified.

3. Problem formulation

3.1. Objectives and constraints in SPRD

There are lots of objectives and constraints in the SPRD problem. To verify our proposed algorithm, some of the general objectives and major constraints have been taken into account as follows.

Connect pipe interfaces (nozzles, endpoints).

Avoid obstacles and routed pipes.

Arrange pipe orthogonally.

Minimize the length of pipe.

Minimize the number of pipe bends (elbows).

Route pipe close to walls or devices for better supporting.

Share pipe racks if possible to reduce installation cost.

Arrange pipes to have the same height (in a layer) if possible.

Physical constraints (1)–(3) are restrictive, while economic constraints (4)–(7) and aesthetic constraint (8) are quantifiable. Therefore, pipe routing optimization seeks to find the best path from an economic point of view among the set of feasible paths restricted by the physical constraints.

It should be noted that the preferences of the constraints are different in practical pipe engineering. E.g., the physical constraints (1)–(3) should have the highest priorities; the installation costs of constraints (6) and (7) are usually more expensive than the material costs of constraints (4) and (5); the bends cost of constraint (5) is more expensive than the length cost of constraint (4) because too many bends may result in unacceptable layout even if the pipe is short. Therefore, costly constraints are usually assigned with higher weight values. To find optimal solutions for real piping cases, lots of weight adjustments need to be performed according to the relative emphases of the constraints by experiment and comparison.

3.2. Fitness function

In the SPRD problem, the workspace can be simplified to a 3-D cubic box space. The space is decomposed into grids according to the pipeline diameter and the requirement of minimum interval distance. Grid method has been applied by many studies because it not only can guarantee the pipeline to go orthogonally, but also it can present many routing constraints easily.

The single pipe route is presented by a series of grids which connect the starting grid and the end grid in the space. The structure of a pipe path can be presented as follows: $\begin{matrix} (3) & path = {{grid}_{1}, {grid}_{2}, {grid}_{3}, \dots, {grid}_{n}}, \end{matrix}$ ${grid}_{k}$ , $k \in [1, n]$ , is a data structure including: grid id, row id, column id, layer id, center point position, grid size, energy value, and the obstacle or pipe in which the grid is located.

In the proposed method, some constraints (2, 4, 5, 6, and 7) are considered as the objectives of SPRD, and can be evaluated in the fitness functions. The other constraints (1, 3, and 8) are controlled by the restrictions in the implementation of the algorithm and the space model.

To satisfy constraint (2), the penalty function $f_{P} (path)$ is introduced to count the number of grids intersected with the obstacles or pipes on a path.

To cope with constraint (4), the length function $f_{L} (path)$ is used to accumulate the number of grids on a path.

To cope with constraint (5), the bends function $f_{B} (path)$ is used to accumulate the total number of bends on a path.

To cope with constraint (6), the energy function $f_{E} (path)$ is employed to consider the energy in the grids of a path. Grids in different areas have different energy values. The grids located close to walls and some devices are endowed with lower energy values. Therefore, a pipe path with lower energy is more favorable.

Based on the above functions, the fitness function of single pipe routing is defined as Eq. (4) $\begin{array}{l} Minimize \\ (4) & f_{single} (path) = w_{1} f_{L} (path) + w_{2} f_{B} (path) + w_{3} f_{E} (path) + w_{4} f_{P} (path) \end{array}$ $w_{1}$ , $w_{2}$ , $w_{3}$ and $w_{4}$ are the positive component weights. $w_{1}$ , $w_{2}$ and $w_{3}$ are normalized between 0 and 1.0 and these three weights add up to 1.0 in total. If a weight is zero, that cost function is unimportant for a particular run. $w_{4}$ is a large constant value, which gives a big penalty if the path violates constraint (2).

The multiple pipes routing can be divided into the arrangement of several single pipes. However, when routing a single pipe, the impact produced by the other related pipes needs to be taken into account.

The overlapping among different pipes are not expected, so a function used to represent the penalty of collision is introduced by $f_{CP} ({path}_{1}, \dots, {path}_{k})$ , which is defined as Eq. (5) $\begin{matrix} (5) & f_{CP} ({path}_{1}, \dots, {path}_{k}) = CollisionPenalty \times \sum_{\begin{array}{c} i \in [1, k] \\ j \in [1, k] \\ i \neq j \end{array}} f_{Collide} ({path}_{i}, {path}_{j}) \end{matrix}$ k is the number of single pipes. CollisionPenalty is a big constant value, and $f_{Collide} ({path}_{i}, {path}_{j})$ accumulates the number of overlapping grids on both ${path}_{i}$ and ${path}_{j}$ . In case a grid is passed by more than two paths, the grid is only counted once.

In the stage of installation, pipes need to be supported by racks, and the pipes side by side are supported by the same series of racks. To reduce the cost of installation, arrangement of pipes as a group is encouraged. Therefore, the bonus function $f_{IB} ({path}_{1}, \dots, {path}_{k})$ is used to cope with constraint (7), and it is defined as Eq. (6) $\begin{array}{l} f_{IB} ({path}_{1}, \dots, {path}_{k}) \\ (6) & = InstallationBonus / (1 + \sum_{\begin{array}{c} i \in [1, k] \\ j \in [1, k] \\ i \neq j \end{array}} f_{Install} ({path}_{i}, {path}_{j})) . \end{array}$ InstallationBonus is a big constant value, and $f_{Install} ({path}_{i}, {path}_{j})$ accumulates the number of parallel pair of grids on ${path}_{i}$ and ${path}_{j}$ . The path formed by parallel pair of grids represents the shared installation path which is expected to be as long as possible. An explanation of this formula is presented in Fig. 2.

Fig. 2.

Installation path.

Based on Eqs (4), (5) and (6), the fitness function of multiple pipes routing is formulated as Eq. (7) $\begin{array}{l} Minimize \\ (7) & \begin{matrix} f_{multiple} ({path}_{1}, \dots, {path}_{k}) = & \sum_{i = 1}^{k} f_{single} ({path}_{i}) + f_{CP} ({path}_{1}, \dots, {path}_{k}) \\ + f_{IB} ({path}_{1}, \dots, {path}_{k}) . \end{matrix} \end{array}$

The branch pipe routing is also broken down into the routing of several single pipes, which has only one starting point and several end points, or has only one end point and several starting points. The purpose of routing branch pipe is to minimize the total length of all the branches. The overlapping between different branches is allowable, which is different from multiple pipes routing. But the length of the repetitive parts is only counted once.

To induce the overlapping of different branches, $f_{OB} ({path}_{1}, \dots, {path}_{k})$ is introduced as the bonus function, which is defined as Eq. (8) $\begin{matrix} (8) & f_{OB} ({path}_{1}, \dots, {path}_{k}) = OverlapBonus / \sum_{\begin{array}{c} i \in [1, k] \\ j \in [1, k] \\ i \neq j \end{array}} f_{Overlap} ({path}_{i}, {path}_{j}) \end{matrix}$ k is the number of branches. OverlapBonus is a big constant value. Similar to $f_{Collide} ({path}_{i}, {path}_{j})$ in Eq. (5), $f_{Overlap} ({path}_{i}, {path}_{j})$ also accumulates the number of overlapping grids on ${path}_{i}$ and ${path}_{j}$ . ${path}_{i}$ ( $i \in [1, k]$ ) denotes the routing path of the ith branch. To construct the branches, our method firstly selects a point from all the terminal points of the branch pipe as the target, and then constructs all the branches by finding paths from the other points to the selected point.

Based on Eqs (4) and (8), the fitness function of branch pipe routing is defined as Eq. (9) $\begin{array}{l} Minimize \\ (9) & f_{branch} ({path}_{1}, \dots, {path}_{k}) = \sum_{i = 1}^{k} f_{single} ({path}_{i}) + f_{OB} ({path}_{1}, \dots, {path}_{k}) . \end{array}$

4. Ship pipe route design (SPRD) using PSO

4.1. Particle encoding

One of the key techniques in designing a successful PSO algorithm is the encoding method which aims at creating a suitable mapping between problem solution and PSO particle. In this section, we propose a new fixed-length encoding method used for pipe routing in 3-D space. Figure 3 shows an example of a virtual routing area. $p_{0}$ is the starting point, supposing it locates on plane $I_{0}$ . $p_{m}$ is the end point, supposing it locates on plane $I_{m}$ . $I_{0}$ and $I_{m}$ are perpendicular to Z axis. The virtual routing area is defined as the space between $I_{0}$ and $I_{m}$ , and this space is divided into m sections along the direction of Z axis by $m + 1$ virtual planes. $m + 1$ is equal to the number of dimensions of a particle. Here, m is computed by a user defined value step, which brings a trade-off effect between resolution of the particle and computational efficiency. $p_{0}$ is the first dimension of a particle and $p_{m}$ is the last dimension. $p_{i}$ is a point randomly generated on plane $I_{i}$ , ( $0 < i < m$ ). Thus the encoding of a particle can be defined by a series of control points as ${p_{0}, p_{1}, \dots, p_{m - 1}, p_{m}}$ . Figure 4 shows the process of forming a path between two adjacent control points, in which $p_{i}^{'}$ is the projection of $p_{i}$ on plane $I_{i + 1}$ , $p_{i + 1}^{'}$ is the projection of $p_{i + 1}$ on plane $I_{i}$ , and $X Y Z$ , $Y X Z$ , $Z X Y$ and $Z Y X$ are four alternative patterns of connecting $p_{i}$ and $p_{i + 1}$ . Following this process, the encoding can be converted to a line path connecting $p_{0}$ and $p_{m}$ .

Fig. 3.

The encoding model.

Fig. 4.

Creation of path segment based on control points.

Because the routing space is divided into grids, this mechanism of encoding could be implemented with less effort based on the grid model. Each control point is able to find a grid corresponding to it, and each virtual plane is corresponding to a layer of grids. The minimum value of step is 1, which means each layer of grids provides a control point. In case of a large routing area, step is usually set to a value bigger than 1 to reduce the dimensions of particle. If the distance between $I_{0}$ and $I_{m}$ is not the integral multiple of step, the last step which refers to the distance between $I_{m - 1}$ and $I_{m}$ should be shorter than step. Based on these ideas, a path connecting grids from the starting point to the end point can be created, and the evaluation of this grid path is taken as the fitness value of the particle. Figure 5 shows an example of particle encoding in the grid model, where step is 4 and the control grids are highlighted.

Fig. 5.

Example of encoding in grid model.

4.2. Direction of virtual planes

During the process of routing a pipe from one point to another, the direction of virtual planes is firstly selected based on the relative positions between the starting point and the end point. In Section 4.1, the virtual routing space is divided by virtual planes which are perpendicular to the direction of Z axis. However, this encoding strategy cannot always find feasible solutions. For example, if the Z coordinates of $p_{0}$ and $p_{m}$ are very close, or the difference of their Z coordinates is smaller than the size of the intermediate obstacle, as shown in Fig. 6(a), then the path directly formed by pattern $X Y$ or pattern $Y X$ will be blocked, as shown in Fig. 6(b). In this case, in order to let the encoding be able to bypass the obstacle, it’s better to set the virtual planes in the direction that is perpendicular to X axis or Y axis. Figure 6(c) shows that the encoding along X axis can bypass the obstacle. The probability of selecting direction i is determined by Eq. (10). $\begin{matrix} (10) & Dir_Probability (i) = \frac{| i_{m} - i_{0} |}{\sum_{i \in {x, y, z}} | i_{m} - i_{0} |} . \end{matrix}$

The direction with larger probability is more likely to be tried, as illustrated in Fig. 7. If an optimal path is found by using particles encoded in a certain direction, it’s no need to try the encodings in other directions.

Fig. 6.

Direction of virtual planes.

Fig. 7.

Probability of direction based on end points.

4.3. Velocity and position updating

PSO is commonly used in solving optimization problems in continuous search space. In this paper, the routing space is divided into adjacent grids, and there is no space gap between any adjacent grids. No matter where a control point locates, it belongs to a specific grid (control grid) in this space. Therefore, the update formulas of velocity and position in standard PSO can be applied to the path optimization in the grid model. As previously described, each particle corresponds to a grid path defined by the control points. So the kth particle is defined as follows: $\begin{array}{l} {particle}^{k} = & {p_{0}^{k} (x_{0}^{k}, y_{0}^{k}, z_{0}^{k}), p_{1}^{k} (x_{1}^{k}, y_{1}^{k}, z_{1}^{k}), \dots, \\ (11) & p_{m - 1}^{k} (x_{m - 1}^{k}, y_{m - 1}^{k}, z_{m - 1}^{k}), p_{m}^{k} (x_{m}^{k}, y_{m}^{k}, z_{m}^{k})} \end{array}$ $m + 1$ is the number of dimensions (i.e., the number of virtual planes), $p_{0}^{k}$ is the starting point, $p_{m}^{k}$ is the end point, and $x_{i}^{k}$ , $y_{i}^{k}$ , $z_{i}^{k}$ are the row id, column id, layer id of the ith control grid, respectively. Based on this definition, a particle flying is considered as the movement of these control grids. Here, we take the particle whose virtual planes are perpendicular to Z axis for example. The position change of $p_{i}^{k} (x_{i}^{k}, y_{i}^{k}, z_{i}^{k})$ is restricted to plane $I_{i}$ . Only the updates of $x_{i}^{k}$ and $y_{i}^{k}$ are permitted, and $z_{i}^{k}$ can be pre-calculated by Eq. (12). $\begin{matrix} (12) & z_{i}^{k} = z_{0}^{k} + i * step, i \in [0, m], \end{matrix}$ $z_{0}^{k}$ is the layer id of the starting point, and step represents the number of grid-layers between two adjacent control grids.

The position and velocity of the kth particle are expressed as Eqs (13) and (14). $\begin{array}{l} (13) & X^{k} = [\begin{matrix} x_{0}^{k} & x_{1}^{k} & \dots & \dots & x_{m - 1}^{k} & x_{m}^{k} \\ y_{0}^{k} & y_{1}^{k} & \dots & \dots & y_{m - 1}^{k} & y_{m}^{k} \\ z_{0}^{k} & z_{1}^{k} & \dots & \dots & z_{m - 1}^{k} & z_{m}^{k} \end{matrix}], \\ (14) & V^{k} = [\begin{matrix} 0 & v x_{1}^{k} & \dots & \dots & v x_{m - 1}^{k} & 0 \\ 0 & v y_{1}^{k} & \dots & \dots & v y_{m - 1}^{k} & 0 \\ 0 & 0 & \dots & \dots & 0 & 0 \end{matrix}] . \end{array}$

In Eq. (14), zero indicates that velocity does not update in that position. The kth particle in the swarm is updated according to Eqs (15) and (16). $\begin{array}{l} (15) & \begin{matrix} V^{k} (t + 1) = & w \times V^{k} (t) + c 1 \times rand () \times (p^{k} (t) - X^{k} (t)) \\ + c 2 \times rand () \times (p^{g} (t) - X^{k} (t)), \end{matrix} \\ (16) & X^{k} (t + 1) = X^{k} (t) + V^{k} (t + 1) . \end{array}$

After each updating, the values of $v x_{i}^{k}$ and $v y_{i}^{k}$ need to be clamped by the maximum velocity defined by user (e.g. the length of 5 grids), and the values of $x_{i}^{k}$ and $y_{i}^{k}$ need to be rounded into integers which denote the row id and column id of a grid. If the new position of a control point drops into an obstacle, give up this update. If the new position jumps out of the routing space, restrict it to the boundary (e.g. if $x_{i}^{k} > max row id$ , then $x_{i}^{k} = max row id$ ; if $x_{i}^{k} < 0$ , then $x_{i}^{k} = 0$ ).

4.4. Consideration of generation method for initial particles

In order to speed up the convergence of the proposed algorithm, it’s better to produce a swarm consisting of high quality particles. Two methods are used in this paper. (1) Each control point of a particle should not locate in an obstacle. If it drops into an obstacle, let it regenerate. By this means, the probability of intersection between routing path and obstacles is greatly reduced, and the path with small or none penalty will become more promising during the process of iterations. (2) Try to encode the control points as straight as possible, which can reduce the number of bending parts. As shown in Fig. 8, when generating a new control point, it is expected to be placed in the same direction as the previous control point. Only if the new position selected by this method drops into an obstacle, other possible positions could be tried.

Fig. 8.

Particle initialization.

4.5. Combine PSO with mutation operation

The two main advantages of PSO over the other algorithms are its algorithmic simplicity and the ability to control convergence. However, it has some drawbacks including: it may prematurely converges to a stable position, which is not guaranteed for a local optimum [25], and it is also a kind of stochastic approach, which means that no specific parameter configuration can be applied to all problems. To overcome the limitations, this paper hybrids the standard PSO with mutation mechanism to increase the diversity of the swarm and the ability to avoid being trapped into a local minimum.

When the global best particle (gbest) does not update its position over some designated iterations (ThresholdNum), the mutation operation is performed on gbest particle. With this help, the stagnated global best particle is likely to fly to a better search space. The procedure of mutation can be briefly described as follows:

Initialize counter c, $c \leftarrow 0$ .

Back up the global best particle, tbest ← gbest.

Randomly select two control points $p_{i}$ and $p_{j}$ from the control points array of tbest particle, where $0 < i < j < m$ , $m + 1$ is the dimension of a particle.

Re-generate the control points from $p_{i + 1}$ to $p_{j}$ using the same method described in Fig. 8 to make the segment of the pipe as straight as possible.

Create the grid path of tbest based on the updated control points.

Evaluate the fitness of tbest, and if tbest is better than gbest, then update gbest, gbest ← tbest.

Increase counter c, $c \leftarrow c + 1$ .

If $c <$ MutationNum (MutationNum is the number of mutation operations), then go back to Step 2, otherwise use the latest gbest to update particles.

4.6. Considerations of engineering constraints

4.6.1. Direction of endpoints

In actual pipe routing work, one of the constraints is about the direction of endpoint, which is not considered in the implementation of our particle encoding. To cope with this constraint, each original endpoint is firstly moved to a new position according to its specification of direction, and then the particles are encoded based on these new endpoints. Finally, each straight pipe segment between the original endpoint and the new endpoint is added to complete the entire path of a pipeline.

4.6.2. Layered pipe arrangement

In some cases, routing pipes at a certain height or height range is favorable in practical pipe engineering. The layered pipe arrangement can make the workspace more rational and aesthetic. Our proposed method could be used to route a pipe in this condition. E.g., supposing the height direction of a workspace is along Z axis, in order to meet the height requirement, the Z coordinates of the control points are only allowed to move within a specified height range. Moreover, if the layout height is fixed, the Z coordinates of the control points do not need to be updated. In such cases, it is more likely to find good results during the computing time because the workspace has been reduced a lot.

4.7. Flowchart of a single pipe routing

The flowchart of the algorithm based on PSO for single pipe routing is shown in Fig. 9.

Fig. 9.

Flowchart for solving single pipe routing based on PSO.

4.8. Time and space complexities of the algorithm

The computational complexity of the proposed algorithm is an aspect that should be considered in practical applications. The measures of algorithm complexity are the execution time and space, which are often estimated by big O notation.

4.8.1. Time complexity

An efficient algorithm is the one whose worst case running time is bounded by a polynomial of the problem size. PSO performance is usually measured by the numbers of particle updates and evaluations, which are carried out during the course of a PSO run. Therefore, the PSO’s time complexity is measured as a function of the number of iterations, the number of particles and the problem size, where the problem size in this algorithm is related with the dimension of encoding and the evaluation of particles. The time complexity function ${TC}_{1}$ is given by Eq. (17) $\begin{array}{l} (17) & {TC}_{1} = O (Problem size \times Number of particles \times Number of iterations) . \end{array}$

If the PSO algorithm is combined with mutation operations, an additional time cost ${TC}_{2}$ should be included, and ${TC}_{2}$ is represented as Eq. (18) $\begin{array}{l} (18) & {TC}_{2} = O (Cost \times Number of mutation operations) . \end{array}$

In which Cost is the sum of a mutation cost and an evaluation cost.

4.8.2. Space complexity

Space complexity is a measure of the amount of working memory that an algorithm needs. The majority of memory used in this algorithm is for storing the grid of cells and the particles, which are allocated at the initialization stage of the algorithm and can be predicted by Eq. (19) $\begin{array}{l} SC = & O (Size of a grid structure \times Number of grids \\ (19) & + Size of a particle structure \times Number of particles) . \end{array}$

As can be seen from Eq. (19), the memory need of this algorithm is almost stable over time.

4.9. Multiple pipes routing and branch pipe routing based on multi-swarms optimization

In order to solve the routing optimization of multiple pipes and branch pipe, the cooperative idea which was proposed by the previous work can also be applied here [12]. In this algorithm, to solve single pipe routing, all the particles belong to only one swarm. But to solve multiple pipes and branch pipe routing, the particles belong to different swarms, which set up a cooperative ecological system. Each swarm is used to route a single pipeline. All the swarms take the same process of evolution in iterations, and the representative of each swarm together forms an entire layout solution. During the optimization, each swarm is under the influence of other swarms, and all the swarms will become more and more collaborative. Finally, the optimal result of the whole problem will be reached. The flowchart of multi-swarms optimization algorithm for solving multiple pipes and branch pipe routing is shown in Fig. 10.

Fig. 10.

Flowchart for solving multiple pipes and branch pipe routing based on multi-swarm optimization.

As can be seen in Fig. 10, the process of routing multiple pipes and branch pipe is almost the same. The difference only exists in the evaluation method for a solution, which has been presented in Section 3.2. Equations (5)–(7) are for the evaluation of multiple pipes routing, while Eqs (8)–(9) are for the evaluation of branch pipe routing.

5. Simulation and results

5.1. Space model

The proposed algorithm for pipe routing is compiled with Microsoft VC++ and OpenGL under Windows 7 x64. All computational experiments are carried out on a PC with Intel i3 CPU 3.30 GHz and 8.00 GB RAM.

The layout space is simplified as a box whose coordinate values of the diagonal positions are $(- 50, - 50, - 50)$ and $(50, 50, 50)$ . There are ten obstacles in the layout space whose diagonal coordinate values are listed in Table 1. The regions which locate next to the obstacles, the walls or the floor of the layout space are endowed with lower energy values.

In the following cases, the layout space is divided into grids by 20 layers × 20 columns × 20 rows, and each grid can be indexed by a position structure denoted as (layer ID, column ID, row ID), where each ID is an integer value in range $[0, 19]$ .

Due to the random computing process of the proposed algorithm, each experiment is executed 15 times, and the results of the optimal ones are selected to show here.

5.2. Simulation for single pipe routing

In this case, the terminal grids of the routing pipe are A $(15, 0, 19)$ and B $(15, 10, 0)$ . The initial parameters are listed in Table 2. The optimal layout is shown in Fig. 11(a), in which the fitness value is 105.1 and the number of bends is 7. Two sub-optimal layouts are shown in Fig. 11(b) and (c), in which the fitness value is 105.4 and the number of bends is 8. It’s easy to see that these layouts can avoid obstacles, have shortest length and less number of bends, and go orthogonally along the obstacles, floors, and walls.

Table 1
The diagonal coordinates of the obstacles

No. Coordinate value

1 $(- 45, - 50, 20) \sim (- 30, 20, 0)$

2 $(0, - 50, 30) \sim (50, 10, 10)$

3 $(0, - 50, - 10) \sim (50, 50, - 30)$

4 $(- 40, - 50, 50) \sim (- 20, 50, 30)$

5 $(- 50, - 50, - 20) \sim (- 20, 50, - 30)$

6 $(- 20, - 10, - 40) \sim (0, 0, 20)$

7 $(- 50, - 50, - 20) \sim (- 30, - 20, 0)$

8 $(- 30, - 50, - 50) \sim (10, 30, - 40)$

9 $(- 20, - 50, - 40) \sim (0, - 40, 20)$

10 $(10, - 30, - 10) \sim (40, - 15, 10)$

No.	Coordinate value
1	$(- 45, - 50, 20) \sim (- 30, 20, 0)$
2	$(0, - 50, 30) \sim (50, 10, 10)$
3	$(0, - 50, - 10) \sim (50, 50, - 30)$
4	$(- 40, - 50, 50) \sim (- 20, 50, 30)$
5	$(- 50, - 50, - 20) \sim (- 20, 50, - 30)$
6	$(- 20, - 10, - 40) \sim (0, 0, 20)$
7	$(- 50, - 50, - 20) \sim (- 30, - 20, 0)$
8	$(- 30, - 50, - 50) \sim (10, 30, - 40)$
9	$(- 20, - 50, - 40) \sim (0, - 40, 20)$
10	$(10, - 30, - 10) \sim (40, - 15, 10)$

Table 2

The parameters set for single pipe routing

Parameter	Value
Number of grids	$20 \times 20 \times 20$
$v_{max}$	length of 3 grids
step (distance between adjacent control grids)	length of 1 grid
Number of iterations	1000
Number of particles in swarm	60
w	0.7
$c 1$	2.0
$c 2$	2.0
Weights parameters in fitness function	$w_{1} = 0.3$ ; $w_{2} = 0.3$ ;
Weights parameters in fitness function	$w_{3} = 0.4$ ; $w_{4} = 2000$
ThresholdNum (Number of iterations during which gbest has no improvement)	100
MutationNum (Number of mutation operations)	500

Fig. 11.

Result of single pipe routing.

The results of the 15 runs are listed in Table 3, which shows that the simulations can obtain good solutions in a very short time frame. And the fitness value curve of the 1st simulation is shown in Fig. 12. Because the proposed algorithm is a population based stochastic optimization technique, various candidate solutions can be obtained in different runs. Although sub-optimal solutions have slightly larger fitness values, they may be more reasonable in some conditions from the view of engineering, and can be taken as important references for pipe engineers.

Table 3

The results of single pipe routing

No.	Fitness value	Iterative times	Time (s)
1	105.1	231	2.886
2	113.0	366	2.699
3	105.1	117	2.418
4	105.4	211	2.684
5	124.4	848	2.698
6	105.4	303	2.684
7	105.1	525	2.605
8	118.6	702	2.527
9	105.4	351	2.792
10	105.1	209	2.356
11	105.4	555	2.980
12	105.1	323	2.589
13	105.4	632	2.496
14	105.4	105	2.777
15	105.4	606	2.434

Fig. 12.

Fitness value curve.

5.3. Simulation for multiple pipes routing

In this case, there are two pipes to be routed. The starting and end grids of each pipe are listed as follows: P1: A (15, 1, 19)–B (13, 8, 0); P2: C (15, 0, 19)–D (15, 10, 0). The set of weights in Eq. (4) is selected as $w_{1} = 0.2$ , $w_{2} = 0.5$ , $w_{3} = 0.3$ , $w_{4} = 2000$ , CollisionPenalty in Eq. (5) is 1500, InstallationBonus in Eq. (6) is 2500, and the other parameters used are the same as Table 2.

One optimal solution is shown in Fig. 13. Each pipe is connected and there is no collision between any of the pipes and no collision with any of the obstacles. The pipes are arranged along the surface of units with low energy as much as possible, and many parts of the two pipes can share the same installation path.

Fig. 13.

Result of multiple pipes routing.

Among the 15 times of running, our method failed to find feasible solution for 4 times. The failure is due to the complexity of the routing and the weak constraint of the fitness function which cannot absolutely prevent the collision between pipes. However, as Asmara [1] noted that the non-deterministic method for parallel arrangement is suitable to solve the shortest path problem for up to 2 or 3 pipes at the same time. To reduce the probability of collision between pipes, one possible solution is to take the height of each pipe as optimization variable and arrange different pipe at different height.

5.4. Simulation for branch pipe routing

In this case, the terminal grids of the branch pipe are A (0, 0, 19), B (0, 16, 0), C (19, 14, 10), D (12, 4, 0), and E (8, 2, 10). A (0, 0, 19) is selected as the starting point. OverlapBonus used in Eq. (8) is 1000, and the other parameters used are the same as Table 2.

One optimal solution is shown in Fig. 14(a). It can be seen that the layout of this branch pipe can meet the constraints and the objectives, and the overlapping paths of different branches are as long as possible.

Fig. 14.

Result of branch pipe routing.

As mentioned in Section 4.6.2, in practical routing, it is expected that the main part of pipelines can be arranged at a specified height. Due to the reduction of space, the probability of overlapping between pipes will grow, which is favorable for branch pipe routing. E.g., when layer ID is set to 7 as the desired height, one optimal result is presented in Fig. 14(b). Compared with the result in Fig. 14(a), most part of the branch pipe in Fig. 14(b) is routed at the specified height, which makes the workspace more rational.

From the results of simulations, we see that the piping height is an important factor that affects the layout of multiple pipes and branch pipe. Therefore, how to identify an optimal height or height range for routing will be studied further in our future work.

6. Conclusions

This paper proposes a new method for solving SPRD problem based on a modified PSO algorithm. The definition of fitness functions, the encoding of particles to deal with a pipe route, the rules to update velocity and position, the method to generate initial individuals, the considerations of engineering constraints as well as the complexity of the algorithm are described. The PSO is combined with mutation operation to overcome the shortcomings of local optimum. Moreover, based on the above ideas, multi-swarm optimization and co-evolution mechanism are applied to solve the problem of multiple pipes and branch pipe routing. A prototype system has been developed to conduct SPRD using the proposed algorithms, and the simulation results show the validity of this approach.

The following work will be studied in future: optimization of the piping height to improve layout effect, parallel implementation of the algorithm to improve the performance, consideration of more objectives and constraints, and integration with existing commercial computer aided design (CAD) systems.

Footnotes

Acknowledgements

This study is supported by the National Research Program for High Technology Ship Development, China (No. MIIT 2014-498), the Science and Technology Project of Guangdong Province, China (2015B090904010 & 2016B090918092), and the Marine Renewable Energy Special Fund, China (QDME2013ZB01).

References

Asmara, Pipe routing framework for detailed ship design, Delft University of Technology, 2013.

Asmara and

Nienhuis, Automatic piping system in ship, in: Proceedings of the 5th International Conference on Computer and IT Applications in the Maritime Industries, Delft, The Netherlands, 2006, pp. 269–280.

Asmara and

Nienhuis, Automatic piping system implementation: A real case, in: Proceedings of the 6th International Conference on Computer and IT Applications in the Maritime Industries, Cortona, Italy, 2007, pp. 290–299.

Asmara and

Nienhuis, Optimum routing of piping in real ship under real constraints, in: Proceedings of the 7th International Conference on Computer and IT Applications in the Maritime Industries, Liege, Belgium, 2008, pp. 271–281.

J.C.

Bansal,

P.K.

Singh,

Saraswat,

Verma,

S.S.

Jadon and

Abraham, Inertia weight strategies in particle swarm optimization, in: Proceedings of the Third World Congress on IEEE Nature and Biologically Inspired Computing (NaBIC), Salamanca, Spain, 2011, pp. 633–640. doi:10.1109/NaBIC.2011.6089659.

Z.R.

Dong and

Lin, Automatic ship pipe routing method based on shortest path faster algorithm, Computer Integrated Manufacturing Systems 20(12) (2014), 2962–2972. doi:10.13196/j.cims.2014.12.006.

X.N.

Fan,

Lin and

Z.S.

Ji, The ant colony optimization for ship pipe route design in 3D space, in: Proceedings of the 6th World Congress on Intelligent Control and Automation, Dalian, China, 2006, pp. 3103–3108. doi:10.1109/WCICA.2006.1712938.

X.N.

Fan,

Lin and

Z.S.

Ji, Ship pipe routing design using the ACO with iterative pheromone updating, Journal of Ship Production 23(1) (2007), 36–45.

Foo,

Knutzon,

Oliver and

Winer, Three-dimensional path planning of unmanned aerial vehicles using particle swarm optimization, in: Proceedings of the 11th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, Portsmouth, Virginia, 2006, pp. 1–10. doi:10.2514/6.2006-6995.

10.

D.W.

Hightower, A solution to line-routing problems on the continuous plane, in: Proceedings of the Sixth Design Automation Workshop, IEEE, New York, USA, 1969, pp. 1–24. doi:10.1145/800260.809014.

11.

Ito, A genetic algorithm approach to piping route path planning, Journal of Intelligent Manufacturing 10 (1999), 103–114. doi:10.1023/A:1008924832167.

12.

W.Y.

Jiang,

Lin,

Chen and

Y.Y.

Yu, An ant colony optimization–genetic algorithm approach for ship pipe route design, International Shipbuilding Progress 61 (2014), 163–183. doi:10.3233/ISP-140111.

13.

Kang,

Myung and

S.H.

Han, A design expert system for auto-routing of ship pipes, Journal of Ship Production 15(1) (1999), 1–9.

14.

Kennedy and

R.C.

Eberhart, Particle swarm optimization, in: Proceedings of IEEE International Conference on Neural Networks IV, IEEE, Perth, Australia, 1995, pp. 1942–1948. doi:10.1109/ICNN.1995.488968.

15.

S.H.

Kim,

W.S.

Ruy and

B.S.

Jang, The development of a practical pipe auto-routing system in a shipbuilding CAD environment using network optimization, Int. J. Naval Archit. Ocean Eng. 5 (2013), 468–477. doi:10.3744/JNAOE.2013.5.3.468.

16.

Kimura, Automatic design system for piping and instruments arrangement including branches of pipes, in: Proceedings of the International Conference on Computer Applications in Shipbuilding 2011 (ICCAS 2011), Vol. 3, Shanghai, China, 2011, pp. 93–99.

17.

Kimura and

Ikehira, Automatic design for pipe arrangement considering valve operationality, in: Proceedings of the International Conference on Computer Applications in Shipbuilding 2009 (ICCAS 2009), Vol. 2, Shanghai, China, 2009, pp. 121–126.

18.

C.Y.

Lee, An algorithm for path connections and its applications, J. IEEE Trans. Electron. Comput. 10(2) (1961), 346–365. doi:10.1109/TEC.1961.5219222.

19.

Liu and

C.G.

Wang, A modified particle swarm optimizer for pipe route design, in: 11th IEEE International Conference on Computational Science and Engineering Workshops, IEEE, Sao Paulo, Brazil, 2008, pp. 157–161. doi:10.1109/CSEW.2008.29.

20.

Liu and

C.G.

Wang, Pipe-assembly approach for aero-engines by modified particle swarm optimization, Assembly Automation 30(4) (2010), 365–377. doi:10.1108/01445151011075825.

21.

Lu,

Sun and

Zou, Environment modeling for simulation-based pipeline design in engine room, in: Proceedings of the ICCMS 2010–2010 International Conference on Computer Modeling and Simulation, Sanya, China, 2010, pp. 318–320. doi:10.1109/ICCMS.2010.65.

22.

J.H.

Park and

R.L.

Storch, Pipe-routing algorithm development: Case study of a ship engine room design, Expert Systems with Applications 23 (2002), 299–309. doi:10.1016/S0957-4174(02)00049-0.

23.

Shi and

R.C.

Eberhart, A modified particle swarm optimizer, in: Proceedings of IEEE International Conference on Evolutionary Computation, IEEE, Alaska, USA, 1998, pp. 69–73. doi:10.1109/ICEC.1998.699146.

24.

Vakil and

M.R.

Zargham, An expert system for channel routing, in: Proceedings of the First Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, Vol. 2, New York, USA, 1988, pp. 1033–1039. doi:10.1145/55674.55721.

25.

Van den Bergh and

A.P.

Engelbrecht, A cooperative approach to particle swarm optimization, IEEE Transactions on Evolutionary Computation 8(3) (2004), 225–239. doi:10.1109/TEVC.2004.826069.

26.

Zhu and

Latombe, Pipe routing = path planning (with many constraints), in: Proceedings of the International Conference on Robotics and Automation, IEEE, Sacramento, USA, 1991, pp. 1940–1947. doi:10.1109/ROBOT.1991.131911.