Network Flow based approaches for the
Pipelines Routing Problem in Naval Design

The design and construction of ships is a complex procedure that starts with a concept design phase. In the concept design, all the necessary ship construction requirements are determined, in order to meet the client needs. Next, in the basic design phase of the ship structure, piping and electrical circuits are defined and all the different equipment are adequately selected. In this phase, one of the most difficult tasks is to determine the pipeline route design in which one has to determine the paths of the different services attending to a series of technical requirements. Pipeline routing requires the coordination of different elements of the ship, as the routing of electrical circuits, water pipes and optical fiber, the prevention of traversing forbidden obstacles, the assuredness of the adequate space for handling the machinery, among many others, all of them having to guarantee the compatibility and the manufacturability technical requirements. Although there are some available tools to help the designers on this task, the difficulty of the problem makes that an expert is still necessary to guide the design to a desired final product. Usually, there are some specifications regarding the number of main lines, branches to be connected to the main lines, valves, etcetera that have to be considered (see e.g. [Cuervas et al., 2017]). Once the initial technical requirements are determined, the pipeline routing problem must be solved following these specifications. The main limitations of the pipeline routing problem on a ship can be classified in three types (see [Ando and Kimura, 2011, Park, 2002, Qian et al., 2008]):

Physical Constraints::

The path followed by the pipelines must avoid physical obstacles and connect with the adequate equipment.

Operational Constraints::

The routes must consider accessibility for handling equipment and valves slackness for security. In addition, some zones in the decision space are more desirable than others, as bottom spaces in a cabin that may be used for storing other types of materials.

Economic Constraints::

There is a limited budget both for the material and workforce cost. Thus, it is necessary to reduce the pipe lengths, as well as the use of elbows in the design.

Some of the above mentioned requirements must be imposed to design feasible routes, while others can be quantified and reflected in a cost function in order to evaluate the different feasible alternatives and decide the most favorable. Nevertheless, defining adequately such a function implies including elements of different nature as material and workforce costs, use of elbows, routes passing through preference zones and holes, etc.

There exist a few software tools (as AVEVA, FORAN or SMART3D, among others) that may help industrial designers for the development of this work. However, even those tools that incorporate some automatic routing functionality are still limited to consider all the technical requirements of this real-world problem being them more adequate for industrial plants. Furthermore, the underlying algorithms of these modules do not allow to incorporate the different specificities for the design of a ship, and then, in most cases the solution is not valid for the naval designer. In other cases, the decision aid tools are extremely specialized, not being flexible enough for the design of networks of different characteristics.

The goal of this paper is to derive an efficient mathematical programming based methodology for the automatic design of pipeline routes that take into account the different technical specificities of a naval design, but still flexible enough to be adapted to different situations and constructibility criteria that appear in real-world situations as the one that motivated this study.

Automatic pipeline routing has been already addressed in the literature (see for instance, [Guiradello and Swaney, 2005, Kimura, 2011, Min et al., 2020, Park and Storch, 2002, Singh and Cheng, 2021]). One of the most crucial steps in this problem is the description of the set of feasible routes for the pipes. Although the problem is initially stated in a continuous framework, with routes that are allowed to be traced in a continuous three-dimensional region, the mathematical problem is intractable in this form (one would need to locate a set of complex three-dimensional paths on a continuous space). Thus, a discretization of the whole space into a finite set of feasible routes is needed also because the tractability of the problem and the simplicity of the obtained routes. One of the possible options is to discretize the space by cell decomposition. In [Lee, 1961] the author proposed to subdivide the region into squared cells and those containing obstacles are removed. Several authors have used that scheme to derive algorithms for solving shortest path problems in continuous regions [Hightower, 1969, Mitsuta et al., 1986, Rourke, 1975, Schmidt-Traub et al., 1999]. This approach has been also adapted to solve the pipeline routing problem [Ando and Kimura, 2011, Asmara, 2013, Asmara and Nienhuis, 2006, Kim et al., 2013, Zhu and Latombe, 1991]. However, this method requires a high number of cells in the subdivision to get accurate solutions of the problem. To overcome this situation, one may also discretize the space by means of a graph structure [Guiradello and Swaney, 2005, Newell, 1973, Shing and Hu, 1986]. Both approaches, cell subdivision and graph generation can be also adequately combined to derive efficient approaches in pipeline routing [Park and Storch, 2002].

Once the space is adequately discretized, there are several heuristic approaches that have been proposed to solve the pipeline routing problem. Most of them are genetic algorithms [Ikehira et al., 2005, Ito, 1999, Kimura, 2011] or ant colony algorithms [Xiaoning et al., 2006, Xiaoning et al., 2007].

In this paper we will consider a graph-based discretization of the space that allows us to use Combinatorial Optimization tools for efficiently solving the problem. The graph is generated taking into account the shape of the region and obstacles, the positions of the source and destination points of the pipes, the size of the pipelines, the preferred zones and penetrable zones (holes through which some obstacles can be traversed), and other characteristics of the pipes to route. Firstly, we generate the nodes of the graph using highlighted points (source and destination points, corners, holes, …) and also intermediate points by means of a grid with a desired width. Secondly, we define the edges of the graph by linking the close-enough nodes. Finally, each edge is provided with a set of weights (one for each pipeline to route) representing the different costs of using it in a path.

On the basis of this idea our main contributions are:

1. (1)

   We discretize the continuous three-dimensional space by using a graph-based framework that allows searching for pipeline routes taking into account the obstacles and the use of elbows in the routes.

2. (2)

   We propose a multicommodity network flow based model for the problem that incorporates the different physical and operational limitations of the routing. In particular, the minimum allowed distances between consecutive elbows and separation between services. We provide a particular branch-and-cut approach for the problem.

3. (3)

   We propose a flexible assessment function to evaluate feasible routes that take into account the different specificities that appear in real-world naval design: length of the paths, preference zones, closeness to ceilings/floors, use of elbows, crossing penetrable zones, etc.

4. (4)

   We develop different matheuristic algorithms able to solve realistic instances of the problem in reasonable CPU times.

To present our contribution we have organized the paper in six sections. Section 2 describes the main elements involved in the pipeline routing problem and their mathematical representation. Section 3 is devoted to present the mathematical programming model that we propose for solving the pipeline routing problem imposing naval design technical requirements. In Section 3.1 a branch-and-cut method is proposed in order to incorporate complicating constraints as they are required, instead of considering, initially, all of them. Two families of matheuristic algorithms are provided in Section 4 to solve large-sized instances. In Section 5 we report the results of our computational experiments. There, we also include a case study based on real data provided by our industrial partner. Finally, we derive some conclusions and future lines of research is Section 6. We have included an Appendix to gather all the pseudocodes that describe the details of our algorithms.

The goal of this paper is to model and solve the problem of how to route different pipelines on a ship competing for a reduced space taking into account the adequate technical requirements. In what follows we describe the main elements of the problem: input data, feasible actions and assessment of a particular solution.

We assume that the underlined region where the pipelines are to be routed is represented by a bounded polyhedron, $\mathcal{P}_{0}$, in $\mathbb{R}^{3}$. In real-world situations, the polyhedron is usually a cuboid in the form $\mathcal{P}_{0}=[a_{1},a_{2}]\times[b_{1},b_{2}]\times[c_{1},c_{2}]$, representing a cabin in the ship. We are also given a finite set of regions $O_{1},\ldots,O_{o}\subseteq\mathcal{P}_{0}$ that represents $o$ obstacles that cannot be traversed by a pipeline route. For the sake of simplicity, these regions will be also identified with cuboids. Thus, the three-dimensional region where the pipelines are allowed to be traced is $\mathcal{P}=\mathcal{P}_{0}\backslash\cup_{\ell=1}^{o}O_{\ell}$. In addition, we are given a finite set of services (cylindrical pipelines) each of them represented by the coordinates of a source and a destination point (both in $\mathcal{P}$), a radius (of the cylindrical pipeline), and a safety minimum allowed distance with respect to other services. Our approach can be easily adapted to other shapes of pipelines, as parallelepipeds (with rectangular sections).

The main decision to be taken in this problem is to determine the set of (dimensional) paths in $\mathcal{P}$ that each one of the services must follow. Initially, a feasible path for a service will be a continuous union of segments in $\mathcal{P}$ starting off from its source point and reaching its destination point. In addition, a minimum required distance must be ensured between two consecutive breakpoints (elbows) by constructibility reasons. Furthermore, once a feasible path for each service is traced, and once a dimensional pipeline is traced around the path, one has to ensure that a minimum required distance between the different services is respected. In particular, the pipelines are not allowed to cross or to overlap in a solution.

The quality of a suitable solution of the problem, given by a set of feasible paths, is evaluated with respect to different criteria. Apart from the length, which is proportional to costs, one also looks for paths with small number of elbows, close to the ceiling of the region or traversing pre-specified preference zones.

In what follows we describe the mathematical representation of the elements involved in the Pipeline Routing Problem in a Ship (PRPS) that we analyze.

In order to discretize the continuous space $\mathcal{P}$, first, an orthogonal 3D grid is built on the big parallelepiped $\mathcal{P}_{0}$, assuring that source and destination points of each service are nodes of the grid and that they are connected with other nodes of the grid. This grid defines a baseline undirected graph to which nodes and edges intersecting regions $O_{\ell}$, for $\ell=1,\ldots,o$, are removed. In Example 1 we show a simple instace for the problem.

However, when tracing a path in such a graph, one is not able to detect or penalize the use of elbows. Elbows in a pipeline must be adequately identified in its route both because constructibility and also because routes with a smaller number of elbows are preferred. The goal is to obtain a mathematical programming model for the problem that avoids non-linearities. In order to consider elbows in a linear objective function in our model, we modify the initial graph by exploiting the nodes of the graph as follows:

1. (1)

   Each physical node $v$ in the initial graph is replaced by an exploited node, i.e., a set of three virtual nodes, $v_{X},v_{Y},v_{Z}$ with the same 3D coordinates than $v$, one for each direction of the canonical basis of $\mathbb{R}^{3}$ (X, Y and Z).

2. (2)

   Virtual nodes associated to the same physical node are linked through the so-called virtual edges. Their lengths are zero (since they link nodes with the same coordinates), but they will have a positive cost representing the usage of an elbow in the route.

3. (3)

   Each physical edge in the initial graph is replaced by another edge with the same length as the physical one, where instead of joining two physical nodes, it connects two virtual nodes (associated to the same physical end nodes of the original edge). Specifically, each edge is linked to the virtual nodes identified with its direction. In this way, edges parallel to the X-axis link $X$-virtual nodes, edges parallel to the Y-axis link $Y$-virtual nodes, and edges parallel to the Z-axis link $Z$-virtual nodes.

In Figure 2 we show an illustration of this explosion of nodes. In the left picture we show a crossing node, $v$, which is linked in the graph to other six nodes. In the right picture we show the three exploited nodes, $v_{X}$, $v_{Y}$ and $v_{Z}$, of node $v$. Node $v_{X}$ (resp. $v_{Y}$, $v_{Z}$) is linked only to the two adjacent nodes which are linked with edges parallel to the $X$-axis (resp. $Y$-axis, $Z$-axis) and with the others two virtual nodes associated with the same physical node. As we can see, the three virtual edges linking $v_{X}$ with $v_{Y}$, $v_{X}$ with $v_{Z}$ and $v_{Y}$ with $v_{Z}$ are drawn with dashed lines in this picture.

In Figure 3 we illustrate the use of this graph to model different types of turns in a path. In the left picture, to go from $a$ to $b$ no elbows are used and a single exploited node ($v_{Y}$) is used. On the other hand, in the center (resp. right) picture, turning from an edge parallel to $Y$-axis towards an edge parallel to $Z$-axis (resp. $X$-axis) requires traversing the virtual edge $(v_{Y},v_{Z})$ (resp. $(v_{Y},v_{X})$) incurring in a cost for using that elbow. The result is a graph representing the feasible space where routing the pipelines.

We denote by $\widetilde{G}=(V,E)$ the graph constructed as described above where $V$ is the set of (virtual) nodes and $E$ the set of edges. Set $E$ includes the set of virtual edges, denoted by $E^{v}$, and the replicas of the physical initial edges. Since $\widetilde{G}$ is embedded in $\mathbb{R}^{3}$, each node $v\in V$ is also identified with its $3D$ coordinates, $(x_{v},y_{v},z_{v})\in\mathbb{R}^{3}$. We denote by $d_{vv^{\prime}}=d((x_{v},y_{v},z_{v}),(x_{v^{\prime}},y_{v^{\prime}},z_{v^{\prime}}))$ the Euclidean distance between nodes $v,{v^{\prime}}\in V$ and by $d_{ee^{\prime}}$ the Euclidean distance between the edges $e,e^{\prime}\in E$ (representing either, a point in $\mathbb{R}^{3}$ if $e\in E^{v}$ or a segment in $\mathbb{R}^{3}$ if $e\in E\setminus E^{v}$).

We assume that we are given a finite set of commodities, $K$, each of them requiring its own pipeline to determine the design of its route. Each commodity $k\in K$ is defined by a pair $(s^{k},t^{k})$ where $s^{k}\in V$ is the source of the commodity and $t^{k}\in V$ is the destination of the commodity. Depending on the commodity $k\in K$, a cost structure, $c_{e}^{k}\geq 0$ for each $e\in E$, is defined over the edges of the graph. These costs depend on many factors as for instance, the length of the edges, the elbow costs, the preferences of the designer when routing the pipelines, etc. A detailed cost structure will be described in Section 5.2 for the case study we deal with in this work.

In this section we describe the mathematical programming model that we propose for solving the PRPS imposing naval design technical requirements. In a first approximation, one can model the problem as a minimum cost multicommodity network flow problem (MCMNFP, for short). Let us denote by $G=(V,A)$ (where $A=\{(i,j)\cup(j,i):\ e=\{i,j\}\in E\}$ is the arc set) the directed version of the graph $\widetilde{G}$ described in the previous section. Similar to the non-directed version, we assume that set $A$ includes the set of virtual arcs, denoted by $A^{v}$, and the replicas of the physical arcs. We also denote by $d_{aa^{\prime}}$ the Euclidean distance between the arcs $a,a^{\prime}\in A$ (notice that $d_{aa^{\prime}}=0$ if $a$ and $a^{\prime}$ are the arcs corresponding to the two opposite directions of the same edge). In addition, we assume that, for each commodity $k\in K$, the cost of each arc $(i,j)\in A$ is $c_{ij}^{k}=c_{ji}^{k}=c_{e}^{k}$, where $e=\{i,j\}$.

The goal of MCMNFP is to route jointly all the commodities in $K$ from their respective sources, $s^{k}$, to their destinations, $t^{k}$, through the network $G$ at minimum cost. This model has been widely studied in the literature (the interested reader is referred to [Salimifard and Bigharaz, 2020] and the references therein for further details on the MCMNFP).

In order to describe the mathematical programming model for the MCMNFP, we use the following set of binary decision variables:

With this set of variables, the overall cost of routing the commodities through the network can be expressed as:

The following set of linear constraints ensures the correct representation of the problem:

where (${\rm MCMNFP}_{1}$) assures that only one commodity is routed through a node and in particular, through an arc, (${\rm MCMNFP}_{2}$)-(${\rm MCMNFP}_{4}$) are the flow conservation constraints and (${\rm MCMNFP}_{5}$) is the domain of the variables.

The solution of MCMNFP is a set of paths (one for each commodity) connecting sources with destinations that do not overlap on the graph $G$. The reader may observe that in the graph $G$ each physical node has been replaced by three virtual nodes on the same coordinates. This explains that in Figure 4 (left) some paths occupy the same space although they do not actually overlap on $G$.

This problem is known to be $\mathcal{NP}$-hard, even for the case of two commodities (see [Even et al., 1975]). Additionally, in pipeline routing there are two main technical requirement that must be considered in order to construct feasible designs: a minimum distance between the pipelines and a minimum distance between consecutive elbows in a single pipeline. The first requirement allows to adequately separate the different services to be used by the pipelines (and such that, when they are enlarged to represent dimensional pipes, they fit on the space) as well as to keep space for the manipulation of machinery in the ship cabins. The second one, is a physical limitation of pipeline routing since there is not enough space for a pipe to turn twice in case consecutive elbows are positioned too close. Note that solutions consists of segments in $\mathbb{R}^{3}$ with no dimensionality and therefore, these considerations are not taken into account in the MCMNFP. Thus, to impose those technical requirements the following constraints must be added to the problem in order to adequately model the PRPS:

1. (1)

   Distance between Services:

   Given an (non-virtual) active edge for a service $k$, a minimum distance with respect to other services is required. Let $R^{k}$ be the radius of the cylinder of pipeline $k\in K$ and let $\Delta^{k}$ be the minimum security distance from $k$ to any other element. Then, the minimum distance allowed between services $k$ and $k^{\prime}$ is $R^{kk^{\prime}}=R^{k}+R^{k^{\prime}}+\max\{\Delta^{k},\Delta^{k^{\prime}}\}$.

   This requirement is assured imposing the following set of constraints:

   $\displaystyle\sum_{k^{\prime}\in K:k^{\prime}\neq k}\sum_{\begin{subarray}{c}a^{\prime}\in A\\ d_{aa^{\prime}}<R^{kk^{\prime}}\end{subarray}}x_{a^{\prime}}^{k^{\prime}}\leq M_{a}^{k}(1-x_{a}^{k}),$

   $\displaystyle\forall a\in A\setminus A^{v},k\in K,$

   (${\rm Dist}$)

   that is, if $a$ is an active arc in the path of service $k$, then, no arc in the path of any other service $k^{\prime}\neq k$ can be activated at a distance smaller than the minimum required. Here, fixed $a\in A\setminus A^{v}$ and $k\in K$, $M_{a}^{k}$ is a big enough constant (greater than $2(|K|-1)$ times the number of the grid edges contained in the cuboid centered at midpoint of arc $a$ and with edge length $length(a)+\,2\max_{k^{\prime}\neq k}R^{kk^{\prime}}$).

2. (2)

   Elbow Test:

   A feasible path for a service, $k\in K$, is required to verify a minimum distance between consecutive elbows, $D^{k}\geq 0$, of this single service. Since elbows are identified in the non-directed graph with virtual edges and then, with virtual arcs in the directed graph, this requirement can be incorporated to the model as follows:

   $\displaystyle x_{a}^{k}+x_{a^{\prime}}^{k}\leq 1,$

   $\displaystyle\forall a,a^{\prime}\in A^{v}:d_{aa^{\prime}}\leq D^{k},a\neq a^{\prime},k\in K,$

   (${\rm Elbow}$)

   that is, if two different virtual arcs (elbows) of the same service $k\in K$ are at a distance smaller than or equal to $D^{k}$, then only one of them is allowed to be active.

   Example 2 shows the effects of considering constraints (${\rm Dist}$) and (${\rm Elbow}$).

   Example 2 (Example 1 - continuation).

   Let $(N,E)$ be the grid depicted in Figure 1 (right). Grid $(N,E)$ is a simplification of the actual graph $G=(V,A)$ used to solve the problem because in the final graph a directed version is considered and each of the nodes in the grid is replaced by its explosion as explained in Section 2.

   We have solved the Example 1 scenario with the multicommodity model with and without the additional modelling constraints (${\rm Dist}$) and (${\rm Elbow}$). Observe that the paths without additional modelling constraints do not respect the conditions about distances and thus a much shorter solution is provided (see Figure 4 (left)) than in the case in which the technical requirements imposed by means of constraints (${\rm Dist}$) and (${\rm Elbow}$) have to be fulfilled (see Figure 4 (right)).

   Figure 5 shows the final solution with dimensional pipelines of the given pre-specified radii.

   

   Note that constraints (${\rm Elbow}$) can be reinforced as follows. Given a virtual arc $a\in A^{v}$, we denote by $RE(a)=\{\tilde{a}\in A^{v}:\tilde{a}\mbox{ has the same coordinates as }a\}$, namely the set of arcs linking virtual nodes associated to the same physical node as the one linked by $a$. Clearly, if $d_{aa^{\prime}}\leq D^{k}$, all the arcs in $RE(a)$ and $RE(a^{\prime})$ are incompatible and then cannot take simultaneously a value of $1$. Thus,

   $\displaystyle\sum_{\tilde{a}\in RE(a)}x_{\tilde{a}}^{k}+\sum_{\bar{a}\in RE(a^{\prime})}x_{\bar{a}}^{k}\leq 1,$

   $\displaystyle\forall a,a^{\prime}\in A^{v}:d_{aa^{\prime}}\leq D^{k},a\neq a^{\prime},k\in K.$

   (${\rm Elbow-R}$)

With the above considerations, the PRPS can be formulated as:

Problem (${\rm PRPS}$) is a minimum cost multicommodity network flow problem with additional constraints that enforce the fulfillment of the technical requirements for the pipelines in the solution. Although the problem is modeled as an Integer Linear Programming Problem, in real-world situations it has a large number of variables ($\mathcal{O}(|A||K|)$) and a large number of constraints. In particular, the technical constraints (${\rm Dist}$) and (${\rm Elbow-R}$) place a considerable load on the model ($\mathcal{O}(|A|^{2}|K|)$).

In order to solve the pipeline routing model ${\rm PRPS}$ presented in Section 3 one has to solve a MILP problem. However, in most cases of real-world situations, due to their large number of variables and constraints, the corresponding problem cannot be solved by a commercial solver (and in many cases it cannot be even loaded). For this reason, we provide in this section two families of matheuristic algorithms for the problem based on two different paradigms: reducing the dimension of the MILP model and decomposing the problem into simpler problems. The pseudocode of both algorithms is included in A.

Next, we report on the results of some computational experiments that we have run, in order to compare empirically the proposed exact and heuristic approaches.

This paper develops a general methodology for the optimal automatic network design of different commodities incorporating real-world constructability conditions. This methodology was originated by an actual problem consisting of the design of spatial pipelines with ships cabins motivated by a recent collaboration with the company Ghenova, a leading naval engineering company. Our proposal is to adapt an ‘ad hoc’ minimum cost multicommodity network flow model to the problem that includes all the technical requirements of feasible pipelines routing. The large number of variables and constraints of real-sized instances makes it inappropriate (impossible in real-world instances) to load into the solver the complete model so that we implemented a branch-and-cut algorithm, where, initially only the standard multicommodity flow model is considered and additional technical constraints are separated within the branch-and-bound tree as lazy constraints. On top of that, we also develop two heuristic algorithms that provide rather good feasible solutions. The first one is a matheuristic based on solving trimmed instances and the second one is a decomposition heuristic that iteratively solves shortest path problems with modified edges weights. Our computational results on randomly generated instances are rather promising showing that we can solve to optimality medium-sized instances. We also report a case study based on a realistic naval instance of a ship cabin provided by our partner company to our research group to test the methodology.

Future work on this topic includes the consideration of more general underline networks including non-orthogonal designs which are conceptually easy to handle once the admissible solutions graphs are generated whereas the generation of these graphs is still a challenging question that will be the focus of a follow up paper.

We will also explore the use of Machine Learning tools to determine, in advance, the parameters of the cost function, that are assumed in this paper to be given by the designer. The study of the subregions of $\alpha$-parameters inducing the same routes will allow us to provide the designers different options of reasonable parameters to explore in the decision making process.

The authors of this research acknowledge financial support by the Spanish Ministerio de Ciencia y Tecnologia, Agencia Estatal de Investigacion and Fondos Europeos de Desarrollo Regional (FEDER) via project PID2020-114594GB-C21. The authors also acknowledge partial support from projects FEDER-US-1256951, Junta de Andalucía P18-FR-422, CEI-3-FQM331, NetmeetData: Ayudas Fundación BBVA a equipos de investigación científica 2019, and Contratación de Personal Investigador Doctor (Convocatoria 2019) 43 Contratos Capital Humano Línea 2. Paidi 2020, supported by the European Social Fund and Junta de Andalucía.