The pipelines and cable trays location problem in naval design

Ocean Engineering 286 (2023) 115525 Available online 10 August 2023 0029-8018/© 2023 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/). Contents lists available at ScienceDirect Ocean Engineering journal homepage: www.elsevier.com/locate/oceaneng The pipelines and cable trays location problem in naval design Víctor Blanco a,b,1, Gabriel González a,c,1, Yolanda Hinojosa c,d,1, Diego Ponce c,e,∗,1, Miguel A. Pozo c,e,1, Justo Puerto c,e,1 aInstitute of Mathematics (IMAG), Universidad de Granada, Spain bDpt. Quant. Methods for Economics & Business, Universidad de Granada, Spain cInstitute of Mathematics (IMUS), Universidad de Sevilla, Spain dDpt. Applied Economics I, Universidad de Sevilla, Spain eDpt. Stats & OR, Universidad de Sevilla, Spain ARTICLE INFO MSC: 46N10 65K05 90B10 90C35 Keywords: Pipeline routing Cable trays location Network design Matheuristics Naval engineering ABSTRACT This paper deals with the determination of optimal locations for pipelines and cable trays in naval design. The problem consists of finding the number and types of cable tray routes to be created between various devices in order to minimize a user defined cost function. We reduce the problem to an ad hoc min-cost multicommodity flow problem with additional constraints imposed by technical requirements. This problem is solved for small-sized instances by using off-the-shelf optimization solvers. We also develop an exact relax-and- cut strategy that allows to handle medium-sized instances. For larger instances, we propose a family of heuristic algorithms consisting on the combination of two phases: (I) Construction of initial cable trays paths; and (II) Transformation to feasible cable trays verifying the technical requirements. For each of them, we also propose different strategies which give rise to several algorithms. These algorithms are compared on a computational experience using two types of instances: the first one based on random instances of different sizes and the second one based on instances with well-defined corridors to asses the availability of our methodology to enforce the creation of cable trays. Finally, we also analyze a real size case study provided by our industrial partner, Ghenova, a leading Naval Engineering company, validating our proposal to find solutions for this problem. 1. Introduction 1.1. Motivation Routing pipelines or cables optimally is a recurrent problem in naval design and the electrical industry since it is the most important activity during the detail-design phase. Actually, it takes over 50% of the total detail-design person-hours and all other activities of detail design depend on it (Park and Storch,2002). Designers face the demanding task of strategically placing multiple elements while ensuring obstacle avoidance, providing adequate machinery space, and meeting technical requirements for compatibility and manufacturability. These objectives must be accomplished within a confined space, leaving little room for maneuvering. Certain elements, such as water pipes and electrical circuits, require separation, while others, like power, phone, or optical fiber cables, can be consolidated using cable trays. These trays effectively reduce ∗Corresponding author at: Institute of Mathematics (IMUS), Universidad de Sevilla, Spain. E-mail addresses: [email protected] (V. Blanco), [email protected] (G. González), [email protected] (Y. Hinojosa), [email protected] (D. Ponce), [email protected] (M.A. Pozo), [email protected] (J. Puerto). 1Evenly contributed to all aspect of the research and writing of the manuscript. the spatial footprint by grouping elements of the same type together. Although software tools exist to aid engineers in visualizing pipe placement and identifying overlaps or interferences, achieving an optimal pipe and cable layout still heavily relies on experienced designers, who often command higher salaries, leading to increased expenses. By automating the design process for pipelines and cable trays, costs are reduced as the need for a specialized designer dedicated to this task is eliminated. This automation holds the potential for achieving a better, or even optimal, design in a more cost-effective manner. Additionally, it would significantly decrease the time required to complete this task and ultimately result in safer designs. The Pipelines and Cable Trays Location Problem (PCTLP) consists of finding the overall number and types of pipeline and cable tray paths to be created between various devices and equipment in a reduced space (building, ship, etc.) under constructability constraints in order to minimize a user defined cost function. This function usually depends https://doi.org/10.1016/j.oceaneng.2023.115525 Received 23 May 2023; Received in revised form 12 July 2023; Accepted 30 July 2023 Ocean Engineering 286 (2023) 115525 2 V. Blanco et al. on the total length and on the number of changes of direction (elbows) in the path followed by the pipes and cable trays. Although initially these paths must be traced in a continuous three-dimensional region, a discretization of the entire space is desirable in order to mathematically address the problem. One of the possible options is to discretize the space by means of a graph structure. Thus, in case no further additional constructability constraints are required and a single pipeline or cable tray is to be routed, this problem is equivalent to finding an optimal path between two nodes in a graph, and solutions can be found in polynomial time using Dijkstra’s algorithm (Dijkstra,1959). However, in these types of problems many pipelines and cable trays must be routed together, and specific constructability constraints are also required. For instance, the length of the cable that can be accommodated when laying lines (wiring tray) should be upper bounded, a minimum distance between consecutive elbows of the same cable tray, and between different cable trays and pipelines, must be assured, obstacles must be avoided, some zones are preferable, etc., making the problem extremely hard to solve. Therefore, the PCTLP poses a significant mathematical and computational challenge. In this paper, we propose a suitable mathematical optimizationbased tool for the PCTLP in naval design, considering not only the joint arrangement of several elements of the same type through cable trays but also the technical feasibility requirements of the design. 1.2. Literature review The pipeline location problem in naval design has been widely considered in the literature since it is a fundamental and challenging problem in the design of large ships. The main contribution of most proposals for this problem is the development of metaheuristic algorithms for determining the optimal routes of multiple pipelines in an intricate and obstructed three-dimensional (3D) space. There are two elements that are shared among the different works on this topic. Firstly, most of the works agree that the most efficient way to handle this problem in a continuous region (the 3D ship layout) is by appropriately discretizing the solution space. Thus, the first phase is to derive a suitable discrete space to represent the feasible solutions for the problem. Secondly, most of the approaches are based on decomposing the multiple pipeline routing problem into single pipeline problems and applying a shortest-path-like algorithm to solve them. Concerning the discretization of the space, different strategies have been proposed. In Lee (1961), the author develops a method based on partitioning the region into square cells and removing cells containing obstacles. Then, paths are constructed in the remaining continuous regions. This technique has been applied to the pipeline routing problem for several authors (see, e.g., Ando and Kimura,2011;Asmara,2013; Asmara and Nienhuis,2006;Kim et al.,2013). On this domain, one can apply several strategies to construct pipeline paths, as a maze algorithm (Lee,1961;Rourke,1975), or an escape algorithm (Hightower, 1969). On the other hand, Guirardello and Swaney (2005) propose a network-based discretization scheme to reduce the dimension of the solution space, where each vertex in the network models a junction of a feasible piperack structure. In this space, routing a single pipeline reduces to finding the shortest path between its source and its target. In Park and Storch (2002), the authors propose a mixture of the above two methods, where a network-based cell-generation method is developed. Jiang et al. (2015) propose an ant colony optimization heuristic for the pipeline routing problem. In Dong et al. (2022), a multiobjective framework for the pipe route design is considered. More recently, Blanco et al. (2022) address the problem of routing multiple pipelines using an adapted min-cost flow formulation and propose different matheuristic algorithms. In most of the previous works, the pipelines are routed while avoiding overlapping. However, in realistic situations, it is allowed to jointly route similar elements through cable trays. These devices help reduce the total cost and required space. As a result, they have been recognized as a common and advisable practice, not only in naval design (Park et al.,2020) but also in building constructions (Pogorelskiy and Kocsis, 2022). Nevertheless, the literature on the PCTLP is scarce. Once the clusters of cables/pipelines to be routed through the same cable tray are determined, one can apply any of the available approaches for the pipeline routing problem. Castorani et al. (2018) propose a two-phase approach for this problem. In the first phase, the arrangement of the cables within the trays is decided, and in the second phase, the routing of the cable trays is determined using a genetic algorithm. This strategy may provide suboptimal solutions since the determination of the routes and the decisions on the contents of the trays are computed separately. In this paper, we analyze the PCTLP in a single mathematical optimization model for the first time and provide efficient strategies to obtain high-quality solutions. This model extends the one proposed in Blanco et al. (2022) by incorporating cable trays. The inclusion of cable trays in the design of pipeline routes significantly increases the complexity of the problem. This complexity arises from the need to determine not only the routes of the pipelines but also the placement of the trays and the allocation of pipelines or cables to each tray, considering the technical requirements of both the pipelines and the trays. All these decisions are optimally made by minimizing the overall space occupied by the pipelines and the cable trays. 1.3. Contributions The main contributions of this work are: •A mathematical programming formulation for the PCTLP as a generalized Minimum Cost Multicommodity Network Flow Problem incorporating several technical requirements. •The design of an exact ad hoc relax-and-cut procedure for solving the problem by relaxing some of the difficult technical constraints. •A novel family of math-heuristic approaches for the problem based on two phases: search of potential pipeline and cable trays routes and transformation of these initial routes into feasible pipeline and cable trays routes verifying the technical requirements. Different strategies are proposed for each of the phases that can be adequately combined to derive different heuristic methods suitable to obtain good quality feasible solutions in reasonable CPU time. •Extensive computational experiments in synthetic instances in order to compare the different solution approaches. •The validation of our proposals on a real instance provided by our industrial partner. 1.4. Organization The paper is organized as follows: Section 2describes the main elements involved in the PCTLP and their mathematical representation. Section 3presents the mathematical programming model for the PCTLP in naval design, as well as the relax-and-cut method proposed for solving the problem optimally. Several matheuristic algorithms are provided in Section 4, which can be combined to solve large-sized instances. In Section 5, we report the results of computational experiments. Additionally, a case study built from a real scenario provided by our industrial partner is included. Finally, in Section 6, we present the conclusions drawn from this work and outline future research directions. 2. Main elements of the PCTLP In the PCTLP, the objective is to route multiple pipelines and cable trays (services) optimally through a complex and obstructed space (solution space), while minimizing certain design costs. In this section, we will describe the key elements of the PCTLP and establish the notation that will be used throughout the rest of the document. Ocean Engineering 286 (2023) 115525 3 V. Blanco et al. Fig. 1. A depiction of nodes exploited and virtual edges. 2.1. Services In naval design, PCTLP involves connecting several devices or equipment by means of pipelines and cables giving rise to a finite set of services of different nature (gas pipes, water pipes, drainage pipes, optical fiber cables, power cables, air conditioning pipes, etc.) that are to be located. Each of these services is classified into a type from a finite set , so that, for a given 𝑡∈, services of type 𝑡are allowed to be jointly routed through the same tray. On the other hand, services of different types must ensure certain distance-based requirements. For instance, services such as power, phone, or fiber optic cables are considered to belong to the same type 𝑡and it is reasonable to assume that they can be traced jointly in the same tray. In contrast, services such as water pipes and power cables clearly belong to different types of services and must be conveniently separated in the design. We assume that each service of type 𝑡∈is characterized by a finite set of sources, each of them with a given integer amount of outflow, and a finite set of sinks, each of them with a given integer amount of in-flow, such that the overall out-flow coincides with the overall inflow. For each type 𝑡∈, this flow represents the number of services of type 𝑡to be routed. We will denote by {𝑠𝑡 1,…, 𝑠𝑡 𝑝𝑡}the set of sources, by {𝑑𝑡 1,…, 𝑑𝑡 𝑞𝑡}the set of sinks, by 𝑔𝑠𝑡 𝑖for 𝑖= 1,…, 𝑝𝑡, the number of services of type 𝑡sent from origin 𝑠𝑡 𝑖(out-flow at source 𝑠𝑡 𝑖) and by 𝑔𝑑𝑡 𝑗, for 𝑗= 1,…, 𝑞𝑡, the number of services of type 𝑡sent to destination 𝑑𝑡 𝑗(in-flow at sink 𝑑𝑡 𝑗) assuming that, ∑𝑝𝑡 𝑖=1 𝑔𝑠𝑡 𝑖=∑𝑞𝑡 𝑗=1 𝑔𝑑𝑡 𝑗∀𝑡∈. 2.2. Solution space Designing the routing of pipelines and cable trays in a naval structure requires us to consider as solution space a 3D region that is obtained by removing a set of polyhedral obstacles from a cuboid (representing a cabin in the ship). As usual in the literature (see, e.g., Ando and Kimura,2011;Asmara,2013;Lee,1961), we discretize that continuous space by creating a 3D grid containing the set of sources {𝑠𝑡 1,…, 𝑠𝑡 𝑝𝑡}and the set of destinations {𝑑𝑡 1,…, 𝑑𝑡 𝑞𝑡}for each type 𝑡∈ . They are nodes of the grid, together with other nodes and links connecting them. The pipeline and cable tray routes will be created by constructing in the grid paths linking sources and destinations of the services of each type 𝑡∈. To take into account costs derived from direction changes (elbows) happening in these paths, we modify the original grid by transforming each physical node, 𝑣, into three virtual nodes (𝑣𝑋,𝑣𝑌,𝑣𝑍), with the same 3D coordinates, representing the three possible directions to take. These virtual nodes associated to the same physical node are linked between them through new links, that we call virtual links, with lengths equal to zero. The links in the original grid keep their length but now they only connect virtual nodes representing the same direction (links parallel to the 𝑋-axis connect 𝑣𝑋nodes, links parallel to the 𝑌-axis connect 𝑣𝑌nodes and links parallel to the 𝑍-axis connect 𝑣𝑍nodes). Fig. 1 shows (on the left) a central node with six other nodes connected to it, and three exploited nodes that originate from the central node (on the right). Each of the virtual nodes is only connected to two neighboring nodes sharing edges parallel to a particular axis and two other virtual nodes that correspond to the same physical node. Fig. 2 demonstrates how the graph can simulate different types of turns along a path. The left image shows a path that requires no elbows and only involves one exploited node, while the center and right images require traversing virtual edges, resulting in additional costs for using elbows. Let  𝐺= (𝑉 , 𝐸)be the undirected graph obtained after modifying the original grid described above, where 𝑉represents the set of virtual nodes and 𝐸represents the set of edges linking them. As already mentioned, the set 𝐸includes the virtual edges used to model elbows, denoted by 𝐸𝑣, as well as the replicas of the physical edges that now connect adjacent virtual nodes in the same direction. Given a virtual edge 𝑒∈𝐸𝑣, we denote by 𝑅𝐸(𝑒) = {𝑒 ∈ 𝐸𝑣∶𝑒 has the same coordinates as 𝑒}, namely the set of edges linking virtual nodes associated to the same physical node as the one linked by 𝑒. We also denote by 𝑑𝑒𝑒′the minimum Euclidean distance between the edges 𝑒, 𝑒′∈𝐸and by 𝐺= (𝑉 , 𝐴)the directed version of the graph  𝐺, i.e., 𝐴= {(𝑖, 𝑗)∪(𝑗, 𝑖) ∶ 𝑒= {𝑖, 𝑗} ∈ 𝐸}is the arc set induced by 𝐸. 2.3. Cost structure Different costs are considered in the design of the routes of the pipelines and trays (as the length of the pipelines/trays, the number of elbows, the height of the pipelines in the cabin, etc.). These costs are incorporated to the graph structure described above in different layers, for each of the types to be routed. For each 𝑒∈𝐸and each 𝑡∈, we denote by 𝑐𝑡 𝑒the cost of using edge 𝑒to route a service of type 𝑡. If 𝑒∈𝐸𝑣is a virtual edge, this cost includes a positive cost for elbow use but not a length cost, i.e., routes using virtual edges only imply that a change of direction occurred and an extra cost for elbow use is incurred. On the contrary, for the replicas of the physical edges, 𝑒∈𝐸⧵𝐸𝑣, this cost includes a positive length cost, but not an elbow utilization cost. 2.4. The pipelines and cable trays location problem The PCTLP in a ship that we analyze here, consists of routing the different types of services, by determining the location of the possible trays concentrating the flow of the services of the same type in part of the route, and the different connections between the pipelines/cables and the trays by minimizing the overall design cost, as well as verifying the technical constructability requirement. Specifically, a minimum distance between consecutive elbows of a pipeline/tray and a minimum security distance between services of different types are required. We denote by 𝐷𝑡the minimum allowed distance between consecutive elbows on a pipeline/cable tray of services of type 𝑡∈, by Ocean Engineering 286 (2023) 115525 4 V. Blanco et al. Fig. 2. A visual representation showcasing how nodes exploited and virtual edges can be employed to simulate various forms of turns in a path connecting node 𝑎and node 𝑏. Fig. 3. Feasible solution for a small instance of the PCTLP: as a union of edges in the graph (left) and its 3D actual representation (right). 𝑅𝑡the width of the pipeline/cable of a single service of type 𝑡, by 𝛥𝑡 the minimum distance between services of type 𝑡and services of any other type, and by 𝛥𝑡𝑡′∶= max{𝛥𝑡, 𝛥𝑡′}the minimum distance between services of type 𝑡and 𝑡′. In Fig. 3, we show a feasible PCTLP solution for a small example. There, we assume that services of two types are to be routed (services of color blue and green). Services of type blue have four different origins (each of them with out-flow 1) and two sinks (each of them with in-flow 2) available to route flows, while services of type green have two origins and two sinks (two sources with out-flow of 2and 1each, and two sinks with in-flow 1and 2separately). In the left picture, the origins and sinks are depicted as squares (□) and crosses (×), respectively. As can be observed in the picture, the services of the same type are jointly routed in a tray in part of their paths from the origins to the sinks. This solution is drawn (left) as a union of edges (a path) in the graph, but they represent dimensional pipelines or trays in the cabin of the ship. This might cause incompatibilities between the different types represented in each edge if the minimum safety distance between services of different types is not met. In Fig. 3 (right), we show the 3D representation of the solution once we have adapted the volume of the pipelines/trays to their actual size. 3. A mathematical programming model for the PCTLP In this section, we describe the mathematical programming model that we propose for the PCTLP described in the previous section. We model the problem as an adapted Minimum Cost Multicommodity Network Flow Problem (MCMNFP) with additional constraints, that include, among other features, the pipelines/cable trays layout. The goal of MCMNFP is to simultaneously route all the types of services from sources to sinks, through a network at minimum cost. This model has been widely studied in the literature and has been applied to different industrial problems (Garg and Smith,2008;Guimarães and Prata, 2022). The interested reader is referred to Salimifard and Bigharaz (2022) and the references therein for further details on the MCMNFP. In our model, (integer) flow variables, 𝑓𝑡 𝑖𝑗 are defined for each type 𝑡∈and each arc (𝑖, 𝑗) ∈ 𝐴. We assume that a single unit of flow is to be routed for each service of type 𝑡∈and thus, these variables indicate the number of services of type 𝑡∈routed through the arc (𝑖, 𝑗) ∈ 𝐴. We denote by 𝐹𝑡the maximum flow of type 𝑡∈allowed to be routed along any edge of the graph, i.e., the maximum number of services of type 𝑡∈that can be jointly routed in the same cable tray. Flow variables together with the following binary variables, also used in our model, allow us to detect the routes of each of the pipelines/cable trays in the solution. 𝑥𝑡 𝑒={1if edge 𝑒is used by the route of services of type 𝑡, 0otherwise. ∀𝑒∈𝐸, ∀𝑡∈. Let 𝑉′⊂ 𝑉 be the subset of vertices in the graph which are neither sources nor sinks and let 𝐷𝑡𝑡′>2𝑅𝑡𝐹𝑡+2𝑅𝑡′𝐹𝑡′+𝛥𝑡𝑡′be an upper bound on the width occupied by two pipelines/cable trays, one of them of type 𝑡and the other one of type 𝑡′. Table 1 summarizes the main elements and variables used in our model. Once these elements are set up, we can formulate the PCTLP as Ocean Engineering 286 (2023) 115525 5 V. Blanco et al. Table 1 Parameters and variables used for formulating PCTLP. Parameters 𝑉set of virtual nodes. 𝐸set of total edges. 𝐸𝜐set of virtual edges. 𝑅𝐸(𝑒) {𝑒 ∈𝐸𝑣∶𝑒 has the same coordinates as 𝑒∈𝐸𝑣}. 𝐴arc set induced by 𝐸. set of possibles service types. {𝑠𝑡 1,…, 𝑠𝑡 𝑝𝑡}set of sources for services of type 𝑡∈ {𝑑𝑡 1,…, 𝑑𝑡 𝑞𝑡}set of sinks for services of type 𝑡∈ 𝑉′⊂ 𝑉 subset of vertices which are neither sources nor sinks. 𝑔𝑠𝑡 𝑖number of services of type 𝑡sent from source 𝑠𝑡 𝑖(out-flow at 𝑠𝑡 𝑖). 𝑔𝑑𝑡 𝑗number of services of type 𝑡sent to sink 𝑑𝑡 𝑖(in-flow at 𝑑𝑡 𝑗) . 𝑐𝑡 𝑒cost of using edge 𝑒by a service of type 𝑡. 𝑅𝑡width of the pipeline/cable of a single service of type 𝑡. 𝐷𝑡𝑡′upper bound on the width occupied by two pipelines of type 𝑡and 𝑡′. 𝐷𝑡minimum allowed distance between consecutive elbows on a pipeline of type 𝑡. 𝛥𝑡minimum allowed distance between services of type 𝑡and services of any other type. 𝛥𝑡𝑡′minimum allowed distance between services of type t and 𝑡′. 𝑑𝑒𝑒′minimum Euclidean distance between the edges 𝑒, 𝑒′∈𝐸 𝐹𝑡maximum allowed number of services of type 𝑡jointly routed in the same cable tray. Variables 𝑥𝑡 𝑒{1if edge 𝑒is used by the route of services of type 𝑡, 0otherwise. 𝑓𝑡 𝑖𝑗 amount of flow of pipeline of type 𝑡routed through arc (𝑖, 𝑗). the following Mixed Integer Linear Programming (MILP): min ∑ 𝑒∈𝐸∑ 𝑡∈ 𝑐𝑡 𝑒𝑥𝑡 𝑒(1) s.t. ∑ 𝑗∈𝑉′∶ (𝑖,𝑗)∈𝐴 𝑓𝑡 𝑖𝑗 −∑ 𝑗∈𝑉′∶ (𝑖,𝑗)∈𝐴 𝑓𝑡 𝑗𝑖 = 0,∀𝑡∈,∀𝑖∈𝑉′,(2) ∑ 𝑗∈𝑉∶ (𝑠𝑡 𝑖,𝑗)∈𝐴 𝑓𝑡 𝑠𝑡 𝑖𝑗−∑ 𝑗∈𝑉∶ (𝑗,𝑠𝑡 𝑖)∈𝐴 𝑓𝑡 𝑗𝑠𝑡 𝑖 =𝑔𝑠𝑡 𝑖,∀𝑡∈, 𝑖 = 1,…, 𝑝𝑡,(3) ∑ 𝑖∈𝑉∶ (𝑖,𝑑𝑡 𝑗)∈𝐴 𝑓𝑡 𝑖𝑑𝑡 𝑗 −∑ 𝑖∈𝑉∶ (𝑑𝑡 𝑗,𝑖)∈𝐴 𝑓𝑡 𝑑𝑡 𝑗𝑖=𝑔𝑑𝑡 𝑗,∀𝑡∈, 𝑗 =⋯, 𝑞𝑡,(4) (𝑓𝑡 𝑖𝑗 +𝑓𝑡 𝑗𝑖)𝑅𝑡+ (𝑓𝑡′ 𝑖′𝑗′+𝑓𝑡′ 𝑗′𝑖′)𝑅𝑡′+𝛥𝑡𝑡′≤𝑑𝑒𝑒′+𝐷𝑡𝑡′(2 − 𝑥𝑡 𝑒−𝑥𝑡′ 𝑒′), ∀𝑒= {𝑖, 𝑗}, 𝑒′= {𝑖′, 𝑗′} ∈ 𝐸, ∀𝑡, 𝑡′∈,(5) ∑ 𝑒∈𝑅𝐸(𝑒) 𝑥𝑡 𝑒 +∑ 𝑒∈𝑅𝐸(𝑒′) 𝑥𝑡 𝑒 ≤1, ∀𝑒, 𝑒′∈𝐸𝑣∶ 0 < 𝑑𝑒𝑒′≤𝐷𝑡, 𝑒 ≠𝑒′,∀𝑡∈,(6) 𝑥𝑡 𝑒≤𝑓𝑡 𝑖𝑗 +𝑓𝑡 𝑗𝑖 ≤𝐹𝑡𝑥𝑡 𝑒,∀𝑡∈,∀𝑒= {𝑖, 𝑗} ∈ 𝐸, (7) 𝑥𝑡 𝑒∈ {0,1},∀𝑒∈𝐸, ∀𝑡∈.(8) Objective function (1) minimizes the overall cost of the routes. Note that this objective function benefits the creation of cable trays since the cost of using an edge does not depend on the number of services using this edge (edge flow) but only if it is used or not. Constraints (2),(3), and (4) are the flow conservation constraints ensuring the adequate construction of paths for the services. Constraints (5) ensure that in a feasible solution to the problem, the minimum allowed distances between services of a different type are kept considering the pipelines/cable tray width, which depends on the flow. The expression 𝑅𝑡(𝑓𝑡 𝑖𝑗 +𝑓𝑡 𝑗𝑖) + 𝑅𝑡′(𝑓𝑡′ 𝑖′𝑗′+𝑓𝑡′ 𝑗′𝑖′) + 𝛥𝑡𝑡′for a pair of edges 𝑒= {𝑖, 𝑗}and 𝑒′= {𝑖′, 𝑗′}and types 𝑡, 𝑡′∈, models the width of the space occupied by the two pipelines/cable trays (plus the safety distance 𝛥𝑡𝑡′). If both 𝑒and 𝑒′are used to route services of type 𝑡and 𝑡′, respectively, this amount cannot exceed the minimum Euclidean distance between the edges, since otherwise, the edges are not far enough to fit the two pipelines/cable trays. Constraints (6) assure that in case two elbows of the same pipelines/ cable trays are closer than the minimum allowed distance (𝐷𝑡), only one of them can be activated in the solution (elbow test). Clearly, given two edges 𝑒, 𝑒′∈𝐸𝑣, if 𝑑𝑒𝑒′≤𝐷𝑡, all the edges in 𝑅𝐸(𝑒)and 𝑅𝐸(𝑒′) are incompatible and then cannot take simultaneously a value of 1. Finally, constraints (7) (together with constraints (5)) impose that, if edge 𝑒= {𝑖, 𝑗}is used by the route of a service of a given type 𝑡∈ then, only services of type 𝑡∈can be routed through the arcs (𝑖, 𝑗) and (𝑗, 𝑖). They also force to activate edge 𝑒= {𝑖, 𝑗}for routing services of type 𝑡if there exists a service of type 𝑡routed through the edge and limit the number of services of type 𝑡routed through the edge to be at most 𝐹𝑡. The solution of the PCTLP is a set of paths connecting sources with destinations where services of different type do not overlap on the graph 𝐺(nor in the 3D representation of the pipelines/cable trays). Ideally, in this solution, several services of the same type should join and go together through various edges to eventually separate and finish on their sinks. 3.1. An exact relax-and-cut procedure for solving PCTLP Note that the number of constraints in families (5) and (6) is too large to make it possible to include them all into a MILP solver for medium/large-sized instances. To overcome this issue, we start by solving a relaxed formulation without these constraints and, to avoid the infeasibility of the solutions, we proceed by incorporating them as needed in a relax-and-cut procedure. More precisely, the solution of the relaxed problem may not meet the requirements of constraints (5) and/or (6). To make sure each solution is valid, we check for feasibility by using an enumerative procedure. If a constraint is found to be violated, it is separated and added to the constraint pool. Then, we solve again the relaxed formulation of the problem obtained after adding the constraints in the pool. The procedure terminates when a solution is found verifying all the constraints. To check if constraints (5) are met, we measure the minimum distance between edges belonging to different cable trays. If this distance is smaller than the sum of the width of the involved cable trays and the required security distance, we consider the constraint to be violated and add it to the constraint pool. To verify the validity of constraints (6), we first arrange the virtual edges in the path of a pipeline/cable tray and then measure the minimum distance between consecutive virtual edges. If this distance is smaller than or equal to the minimum required distance between elbows for the pipelines/cable tray type, the constraint is considered Ocean Engineering 286 (2023) 115525 6 V. Blanco et al. violated and it is introduced as a feasibility cut to the set of constraints pool. Note that the size of the activated edges (by 𝑥) and flows (𝑓) in a relaxed solution of the problem for a given type 𝑡is much smaller than the number of edges and arcs in the original graph, and thus, the separation process can be efficiently solved in practice. Furthermore, we embed this procedure, into a branch-and-cut scheme using callbacks, which are available in most of the commercial off-the-shelf software, such as Gurobi, CPLEX, or FICO. 4. A general heuristic approach Although the relax-and-cut procedure mentioned in the previous section alleviates the problem solving caused by the difficulty of the technical constraints, the number of variables and constraints of the model is still huge even for medium-sized instances. In this section, we develop a family of heuristic approaches designed to provide feasible solutions in lower computation times than the exact relax-and-cut procedure. The different heuristic approaches that we propose are based on the following two main phases: Phase I: Construction of initial paths and cable trays. In this first step, the goal is to construct promising paths in the graph not necessarily feasible connecting the sources and sinks of the services of each type and encouraging services of the same type to share edges using the overall less costly edges. Phase II: Transformation to feasible paths and cable trays. Given a partial solution obtained in Phase I, the aim of this stage is to check for feasibility (and to provide feasible solutions if necessary) of the PCTLP by correcting the technical requirements, i.e., the minimum distance between services and the elbow test. In what follows, we describe the different strategies that we propose to deal with the different phases above. 4.1. Strategies for phase I For this phase, we propose two different approaches to enforcing or encouraging the construction of cable trays. In the first strategy, the so-called Constructive Algorithm (H1) locates certain points (called supernodes) that will define the beginning- and end-nodes of the pipelines/cable trays. Then, both supernodes of each cable tray are connected by a path, constructed by an adapted shortest path algorithm. Finally, connections (not necessarily verifying the technical requirements) between sources, sinks, and trays are established. The second strategy, the so-called Decomposition Algorithm (H2), is based on solving separately for each type of service the Minimum Cost Multicommodity Network Flow Problems (MCMNFP) which is solvable in polynomial time by a primal network simplex algorithm (see, e.g., Orlin,1997). The different types of services are independently routed, and the construction of cable trays is encouraged by increasing the costs of certain edges in the underlying graph. The two approaches are independently performed for each type 𝑡∈and are detailed as follows: Constructive Algorithm (H1). For each type 𝑡∈: •H1.1 (Supernodes location). In order to find the supernodes (among the set of sinks and sources) which are the end-nodes of the 𝑞cable trays that are constructed, we solve a mathematical programming model for each service type based on a 𝑝-median location problem. We use the following set of binary variables: 𝑦𝑙 𝑗={1if node 𝑗is selected as the 𝑙th supernode, 0otherwise, where 𝑙∈𝐿= {1,…,2𝑞},𝑞=⌈𝜙𝑡∕𝐹𝑡⌉and 𝜙𝑡is the total flow that type 𝑡services transport through them (number of services of type 𝑡). Also, we consider the following set of binary variables: 𝑧𝑙 𝑖𝑗 =⎧ ⎪ ⎨ ⎪ ⎩ 1if source/sink 𝑖is assigned to the 𝑙th supernode located at node 𝑗, 0otherwise. Let 𝑆𝑇 = {𝑠𝑡 1,…, 𝑠𝑡 𝑝𝑡}⋃{𝑑𝑡 1,…, 𝑑𝑡 𝑞𝑡}be the total set of sources and sinks for service type 𝑡. The model is formulated as: min ∑ 𝑙∈𝐿∑ 𝑗∈𝑉∑ 𝑖∈𝑆𝑇 |ℎ𝑖|𝑑𝑖𝑗 𝑧𝑙 𝑖𝑗 (9) s.t. ∑ 𝑙∈𝐿∑ 𝑗∈𝑉 𝑧𝑙 𝑖𝑗 = 1,∀𝑖∈𝑆𝑇 , (10) 𝑧𝑙 𝑖𝑗 ≤𝑦𝑙 𝑗,∀𝑙∈𝐿, ∀𝑖∈𝑆𝑇 , ∀𝑗∈𝑉 , (11) ∑ 𝑙∈𝐿 𝑦𝑙 𝑗≤1,∀𝑗∈𝑉 , (12) ∑ 𝑗∈𝑉 𝑦𝑙 𝑗= 1,∀𝑙∈𝐿, (13) ∑ 𝑙∈𝐿∑ 𝑗∈𝑉 𝑦𝑙 𝑗= 2𝑞, (14) ∑ 𝑙∈𝐿∑ 𝑖∈𝑆𝑇 ℎ𝑖𝑧𝑙 𝑖𝑗 ≤𝐹𝑡𝑦𝑙 𝑗,∀𝑗∈𝑉 , (15) ∑ 𝑖∈𝑆𝑇 ∑ 𝑗∈𝑉 ℎ𝑖𝑧𝑙 𝑖𝑗 = − ∑ 𝑖∈𝑆𝑇 ∑ 𝑗∈𝑉 ℎ𝑖𝑧𝑙+1 𝑖𝑗 ,∀𝑙∈𝐿∶𝑙is odd,(16) 𝑦𝑙 𝑗∈ {0,1},∀𝑙∈𝐿, ∀𝑗∈𝑉 , (17) 𝑧𝑙 𝑖𝑗 ∈ {0,1},∀𝑙∈𝐿, ∀𝑖∈𝑆𝑇 , ∀𝑗∈𝑉 . (18) We show in Table 2 a summary of the parameters and variables used in our formulation. The objective function (9) minimizes the flow per path length between sources/sinks and supernodes, where ℎ𝑖is the flow of the source/sink 𝑖and 𝑑𝑖𝑗 is the shortest path distance from source/sink 𝑖to supernode 𝑗. Constraints (10) force each source/sink to be assigned to one supernode. Constraints (11) ensure sources/sinks can only be assigned to an activated supernode. Constraints (12) guarantee there cannot be more than one supernode with the same label. Constraints (13) assign each label 𝑙∈𝐿to a single supernode. Constraint (14) ensures there is a total of 2𝑞supernodes. Constraints (15) guarantee that the total flow that reaches a supernode must be less than its capacity 𝐹𝑡. Constraints (16) match supernodes so they have the same flow of opposite sign. If 𝐹𝑡is large enough, then only one tray of type 𝑡is formed. In this case, 𝐿= {1},𝑞= 1 and constraints (11),(12),(14), (15) are ignored. •H1.2 (Supernodes connection). To connect supernodes of each service type through feasible cable trays we use an adapted shortest path-based method similar to the one proposed in Blanco et al. (2022). This approach ensures that the pipelines/cable trays verify all the technical requirement imposed in our problem (elbow-test and minimum distance between different types). •H1.3 (Linking sources/sinks to trays). Every source/sink is connected to its corresponding tray using the shortest path, which is also considered as part of the cable tray and can be used to connect other sources/sinks to it. This process is repeated until all the sources/sinks are connected to Ocean Engineering 286 (2023) 115525 7 V. Blanco et al. Table 2 Parameters and variables of formulation (9)-(18). Parameters ℎ𝑖flow of the source/sink 𝑖. 𝑑𝑖𝑗 minimum distance between edges 𝑖and 𝑗. 𝜙𝑡number of services of type 𝑡. 𝐹𝑡maximum number of services of type 𝑡∈that can be jointly routed in the same cable tray. 𝑞⌈𝜙𝑡∕𝐹𝑡⌉. 𝐿{1,…,2𝑞}. 𝑉vertices in the graph. 𝑆𝑇 total set of sources and sinks for service type 𝑡. Variables 𝑧𝑙 𝑖𝑗 {1if source/sink 𝑖is assigned to the 𝑙th supernode located at node 𝑗, 0otherwise. 𝑦𝑙 𝑗{1if node 𝑗is selected as the 𝑙th supernode, 0otherwise. a tray. We denote by 𝐸𝑏𝑒𝑠𝑡 𝑡the list of edges obtained at the end of the procedure. Note that these connections may not verify the technical requirement imposed in the PCTLP. Decomposition-based algorithm (H2). For each type 𝑡∈: •H2.1. A MCMNFP is solved only for type 𝑡. We denote by 𝐸𝑡the list of edges induced by the solution (arcs with a positive flow). Observe that since the remainder types are not considered in the problem, the technical constraints are not guaranteed. •H2.2. For each connected component of 𝐸𝑡, we increase the cost of all the edges that do not belong to the selected connected component and we solve again the MCMNFP for this type of service 𝑡. This boosts all the services to use the same set of edges (those in the selected connected component). Once it is repeated for each connected component, the best solution (based on the objective value of the PCTLP), 𝐸𝑏𝑒𝑠𝑡 𝑡, is kept. This strategy allows to concentrate the flow in the overall less costly set of edges. 4.2. Strategies for phase II For this phase, we propose two different iterative approaches in order to construct feasible PCTLP solutions, verifying all the technical requirements. Both approaches use as starting solution the one obtained in Phase I, i.e., 𝐸𝑏𝑒𝑠𝑡 𝑡. The first algorithm, the so-called Graph trimming, is based on solving the PCTLP on a trimmed graph of the original one, and so with a smaller number of variables and constraints. The second approach, the so-called Increasing Cost, consists of increasing the costs of the edges not verifying the technical constraints to avoid their use, and repeating the process until they are fulfilled. Graph Trimming (GT). Once the initial heuristic solution is obtained from any of the strategies described in Phase I, constraints (5) and (6) are evaluated. If they are verified, the initial heuristic solution is feasible for the PCTLP. Otherwise, we propose an iterative procedure that begins with the initial heuristic solution. Then, for each service type, a cylindrical region of a given initial width is considered around each edge of the union of edges that take part of the initial solution. Instead of solving the entire PCTLP in the graph, we solve it in a reduced space, the union of these regions by fixing the variables indicating arcs outside of these regions to zero. If the problem is feasible, it provides a feasible solution, otherwise, the width of the regions is increased and the process is repeated until feasibility is achieved. Note that as the number of iterations increases the dimension of the trimmed graph becomes larger, and then, the problem requires more computational time to be solved. Although in the worst-case scenario, the algorithm requires solving the original instance of the problem (the whole graph), in practice, this strategy significantly reduces the number of variables needed to solve the problem. Increasing Cost (IC). This strategy consists of guiding the solutions obtained by the MCMNFP to verify all the requirements in the PCTLP by increasing the cost of the non-desired edges in the design (to the maximum cost value). The algorithm considers a maximum number of iterations to be performed, MaxIt, and for each iteration 𝑖𝑡 ∈ {1,…, 𝑀𝑎𝑥𝐼𝑡}a sorted list of all the commodities (types), 𝑇sort (𝑖𝑡). A multistart approach is then applied by testing different sorted lists and choosing the best of them. Some of the sorted lists are based on the decision maker’s preferences and others are obtained randomly. This approach, for iteration 𝑖𝑡 ∈ {1,…, 𝑀𝑎𝑥𝐼𝑡}and for type 𝑡∈𝑇sort (𝑖𝑡), consists of the following iterative procedures: •Elbow-Test. The elbow constraints (6) are checked for the obtained solution. If any of them is violated one of the two elbows not verifying the test is chosen and its cost is increased to avoid its use in later elbow-test iterations. The MCMNFP is again solved with the new costs and 𝐸𝑏𝑒𝑠𝑡 𝑡 is updated accordingly. This step is repeated until the elbow test is verified or a maximum number of elbowtest iterations is reached (in whose case the solution in iteration 𝑖𝑡 is not valid). •Minimum Distance. The distance requirements (5) are tested by checking overlapping edges with respect to each of the previously processed types 𝑡′∈ {1,…, 𝑡 − 1}, if any. If edge 𝑒used in type 𝑡with flow 𝑓𝑡 𝑒overlaps edge 𝑒′used in any type 𝑡′∈ {1,…, 𝑡 − 1} with flow 𝑓𝑡′ 𝑒′, this stage is addressed by increasing, for type 𝑡, the cost of the edges in conflict, that is, the edges at a distance lower than or equal to 𝑓𝑡 𝑒𝑅𝑡+𝑓𝑡′ 𝑒′𝑅𝑡′+𝛥𝑡𝑡′from the edges used in 𝐸𝑏𝑒𝑠𝑡 𝑡′and then, go to Phase I to construct a new list of edges for type 𝑡,𝐸𝑏𝑒𝑠𝑡 𝑡(updated). This procedure is repeated until there are no conflicts or a maximum number of overlapping iterations (MaxOverIt) is reached (in whose case the solution, in iteration 𝑖𝑡, is not valid). Once no conflicts appear, to prevent overlapping for the next types in the sorted list, the cost for types 𝑡+ 1,…, 𝑇 is increased for the edges in 𝐸𝑏𝑒𝑠𝑡 𝑡. Once all iterations are solved we keep the solution of the best iteration (based on the objective value of the PCTLP). Note that the strategies described above for the two different phases of the heuristic can be combined in different ways. In Fig. 4, we illustrate Ocean Engineering 286 (2023) 115525 8 V. Blanco et al. Fig. 4. Flowchart of the heuristic combination of H2 for Phase I and Increasing Cost for Phase II. a possible choice in which H2 is applied for Phase I and Increasing Cost for Phase II. Note that since in Phase II, the types of services are sorted, the sequence in which the types are processed in Phase I follows the same order. 5. Computational experience In this section, we report the results of our computational study aimed at evaluating the effectiveness of our proposed methods for solving the PCTLP. Our computational experience is organized into three parts. First, we examine the computational performance of our algorithms on a battery of randomly generated instances. Second, we assess the performance of the algorithms on instances that we have specifically designed for the PCTLP, the so-called ‘‘corridor instances’’. These instances are publicly available at https://github.com/ anticiclon/Dataset-Trays-Location-Problem. Finally, we apply our methodology to a real-world case study provided by our industrial partner. We use Gurobi v7.7 optimizer to solve all instances on a Windows 10 platform, powered by an Intel(R) Core(TM)i7 CPU 2.93 GHz processor and 16 GB RAM. We use the default settings for all Gurobi solver parameters and set a CPU time limit of 4h. 5.1. Random instances In our first study, we consider a set of random instances, that have been already used in the literature, to validate our proposal. Each instance consists of a cube of length 128 units containing a number of obstacles and different services that must be routed between a set of sources and sinks (see Table 3). More specifically, for each instance an orthogonal 3D grid is built on such a cube with a density 𝑑∈ {17,33}, with fixed distances between nodes, i.e., each axis is divided into 16 or 32 equally sized parts, and the grid is constructed. Five groups of 𝑜∈ {5,10,15} 10-units cubic obstacles are randomly generated. Five groups of 𝑠∈ {5,8,12} services are also generated each of them classified into one of two types of service (A or B), such that type 𝐴 will have services enumerated with an odd number whereas 𝐵has those services enumerated with an even number. The generated grid is constructed such that it has enough capacity to gather all services of the same type. In scenarios with 5 services, the width of a service in both types is 𝑅𝑡= 0.33. Analogously, in scenarios with 8 or 12 services widths are 𝑅𝑡= 0.25 and 𝑅𝑡= 0.17, respectively. We take into consideration several factors when calculating the cost function, which include physical distance, the number of bends or Table 3 Summary of the types of random instances. Density (𝑑) #Services (𝑠)/Radii (𝑅) Obstacles (𝑜) 17, 33 5/0.33 8/0.25 5, 10, 15 12/0.17 elbows in the path, and changes in height. More precisely, we define the cost of an edge 𝑒belonging to type 𝑡as follows: 𝑐𝑡 𝑒=𝛼𝑡 1(𝑑𝑒+ 10𝐸𝑙𝑒+ 2𝐶ℎ𝑒), where 𝛼𝑡 1is a random integer ranging in [1,9],𝑑𝑒is the length of edge 𝑒,𝐸𝑙𝑒is equal to 1 if edge 𝑒has an elbow, and 0 otherwise, and 𝐶ℎ𝑒is equal to 1 if edge 𝑒is a vertical edge along the 𝑍-axis, and 0 otherwise. In total, 90 benchmark instances are generated based on the combination of distances, services, and obstacles. Table 3 summarizes the types of instances used in this study. The size of each instance can be described by the number of edges in the resulting graph. For a given density 𝑑, this graph has 3(𝑑− 1)𝑑2 physical and 3𝑑3virtual edges. Finally, we recall that for each case, the obstacles generated within the grid remove some edges. Since there is one binary variable and two flow variables for each edge and each type, the final average number of edges can also be obtained by dividing column #Vars by six. The proposed general heuristic approach described in Section 4is very flexible and can be parameterized in many different ways. Among all possible combinations of strategies for Phases I and II, we have run two of them and, additionally, a mixing strategy to compare their performance against the exact relax-and-cut (EX) namely: H2+IC: We test the decomposition-based algorithm (H2) improving the results with the increasing cost method in order to guarantee the elbow-test and minimum distances between services. H12+GT: We trim the graph around the solutions provided by H1 and H2 and solve the PCTLP in the trimmed graph with a time limit of 900 s. This time limit is extended if required until a feasible solution is found. GT+IS: In order to improve previous solutions, we trim the graph again 32 units around the H2+IC and H12+GT solutions and solve the PCTLP with a time limit of 14400-𝑡1−𝑡2seconds, where 𝑡1and 𝑡2stand for the time consumed by H2+IC and H12+GT, Ocean Engineering 286 (2023) 115525 9 V. Blanco et al. Table 4 Computational results for random instances. 𝑑 𝑠 𝑜 #Vars #Ctrs MIPGAP Dev_UB CPU Time EX EX H2+IC H12+GT GT+IS EX H2+IC H12+GT GT+IS 17 5 5 171174 143535 25.0 0.2 1.5 3.7 0.0 TL 42.6 949.1 TL 10 170565 143055 27.3 0.0 1.6 7.2 0.0 TL 47.7 947.6 TL 15 170052 142650 26.8 0.0 1.6 10.2 0.4 TL 42.8 946.8 TL 8 5 171174 143535 26.7 0.7 6.5 15.2 0.9 TL 65.5 970.3 TL 10 170565 143055 27.0 2.6 5.8 12.9 0.3 TL 64.0 970.0 TL 15 170052 142650 27.0 0.7 5.3 15.1 1.5 TL 63.5 971.4 TL 12 5 171174 143535 27.1 1.7 6.9 15.8 0.0 TL 94.2 930.2 TL 10 170565 143055 26.9 2.7 7.0 11.7 0.2 TL 105.3 1018.3 TL 15 170052 142650 27.0 4.0 7.7 10.0 0.0 TL 92.7 1013.9 TL 17 170597 143080 26.8 1.4 4.9 11.3 0.4 TL 68.7 968.6 TL 33 5 5 1270624 1062214 37.7 6.4 0.5 15.2 0.0 TL 1956.0 1617.0 TL 10 1266961 1059258 36.9 4.9 0.4 10.4 0.0 TL 1068.6 1614.9 TL 15 1263660 1056593 36.9 4.9 0.7 12.6 0.0 TL 3030.2 1618.6 TL 8 5 1270624 1062214 36.9 14.2 2.2 18.0 0.0 TL 1312.4 1947.2 TL 10 1266961 1059258 36.7 13.4 2.2 20.7 0.0 TL 1073.6 1963.1 TL 15 1263660 1056593 36.6 11.5 1.0 17.7 0.0 TL 1206.4 2041.3 TL 12 5 1270624 1062214 36.6 8.8 2.1 24.2 0.0 TL 1620.8 2636.0 TL 10 1266961 1059258 36.7 10.6 3.7 22.4 0.0 TL 1565.2 2556.4 TL 15 1263660 1056593 36.6 7.0 3.0 20.6 0.4 TL 1864.5 2748.0 TL 33 1267082 1059355 36.9 9.1 1.8 18.0 0.0 TL 1633.1 2082.5 TL Total 718839 601217 31.8 5.2 3.3 14.6 0.2 TL 850.9 1525.6 TL respectively. Here we adopt as initial solution (IS) the best result from both H2+IC and H12+GT methods. A time limit of 4h (14400 s) was fixed for solving each instance with the exact approach (EX). In Table 4, we report the average results of this first battery of computational experiments. The first three columns indicate the parameters identifying the instances, 𝑑(density), 𝑠(number of services), and 𝑜 (number of obstacles). For each of the combinations of these parameters five instances were generated and we report the average results of the five instances. Column #Vars indicates the number of variables of the (MCMNFP) problem and column #Ctrs the number of constraints. Column MIPGAP indicates the relative MIP gap obtained at the end of the time limit for the exact method (EX). In the block of columns denoted by Dev_UB, we report, for each one of the procedures, the relative percent deviation of the obtained solution with that procedure (upper bound), 𝑧ub, with respect the best solution among the two approaches, exact and GT+IS, 𝑧best , that is: 𝙳𝚎𝚟_𝚄𝙱 =𝑧ub −𝑧best 𝑧best × 100. Finally, in the block of columns CPU Time, we report the CPU time, in seconds, required by each one of the approaches. The flag TL indicates that the time limit was reached in all the instances averaged in that row. A first analysis of the results shows that the exact approach was not able to solve, up to optimality, any of the instances within the time limit, being the MIPGAP significantly large. In addition, the average number of explored nodes in the branch-and-bound tree was below 10 for 𝑑= 17 and equal to 1 for 𝑑= 33 which implies that the MIPGAP is close to the gap with respect to the linear relaxation for those instances. This behavior was expected given the already known big size of the formulations in terms of variables and constraints. Regarding columns Dev_UB for EX and GT+IS, we can compare the results obtained by the exact method with the results obtained by matheuristic GT+IS in the same computational time (14400 s). We observe that the best solution (deviation from the best solution = 0.0) is obtained by GT+IS approach in most of the tested instances, especially for 𝑑= 33. Therefore, we can assert that matheuristic GT+IS outperforms the exact method. On the other hand, the results on the deviations obtained by the heuristic approaches H2+IC and H12+GT show that H2+IC obtains better solutions in less computational time, being in many instances better than the solution obtained by the exact procedure, especially for 𝑑= 33. H12+GT also provides good results in small running times which also benefits significantly the results obtained with GT+IS. Fig. 5 shows an example of a random instance (𝑑, 𝑠, 𝑜) = (33,12,15) together with the best obtained solution obtained with the mathheuristic GT+IS. There, the squares (□) represent the sources, the crosses (×) the sinks, the obstacles are the light blue cubes, and the services are highlighted in blue (type A) and in green (type B). As can be observed, the solution shows that there are seven trays that combine four green and three blue services simplifying the design of twelve one-by-one single pipelines. 5.2. Corridor instances In our second battery of experiments, we generate new instances encouraging the formation of cable trays in real situations. The set of random instances used in Section 5.1 are cubes containing random obstacles that may not favor the trays’ formation. In order to force services to be grouped in trays, we have designed a specific set of instances with elongated shapes and specific obstacles layout. This collection of corridor instances is generated as follows. The domain of this new set of instances is the 3D box [0,128] × [0,128] × [0,1024]. An orthogonal 3D grid of 𝑑1×𝑑2×𝑑3physical nodes, with (𝑑1, 𝑑2, 𝑑3) ∈ {(9,9,65),(17,17,129)} is built on this box, being the distance between adjacent nodes fixed to 128 𝑑1−1 in 𝑋-axis, 128 𝑑2−1 in 𝑌-axis and 1024 𝑑3−1 in 𝑍-axis. This means a spacing of 16 and 8 units for 𝑑= (𝑑1, 𝑑2, 𝑑3) = (9,9,65) and 𝑑= (𝑑1, 𝑑2, 𝑑3) = (17,17,129), respectively. Here, 𝑑represents, again, the density of the grid. The graph for a corridor instance with density 𝑑= (𝑑1, 𝑑2, 𝑑3)has 𝑑1𝑑2(𝑑3− 1) + 𝑑1(𝑑2− 1)𝑑3+ (𝑑1− 1)𝑑2𝑑3physical edges and 3𝑑1𝑑2𝑑3virtual edges. We consider a total of thirteen services partitioned into two types of services. There are eight services of type A that have to be sent from four sources, each one with an outgoing flow of two to four sinks, two of them with an in-flow of three, and another two with an in-flow of one. The remaining five services are of type B and depart from two sources with an outgoing flow of two and three, respectively to five sinks, each one with an in-flow of one. Two different scenarios, 𝑆1and 𝑆2, are generated with these characteristics by randomly distributing sources