Routing Multiple Branched Pipes using Multi-Terminal Pipe Router and Conflict-Based Search

In pipe routing, a designer designs the routes of pipes in a physical space in applications such as ship or plant design. The goal is to find a routing plan that conforms to physical restrictions as well as any application specific constraints while optimizing the cost of the construction. This may be done fully manually or be assisted with automated routing by a computer program. This thesis includes a literature review on the algorithmic pipe routing problem as well the more general shortest path problem. Pipe routing usually involves multiple pipes with branches that are to be routed in the same search space. This leads to a computational problem so complex that finding the optimal solution may not be feasible in practical applications. Many have taken the approach of approximating the optimum with optimization-based approaches. In this thesis I define a specific variation of the pipe routing problem as well as a process consisting of a set of algorithms used to solve it. Multiple pipes with branches are to be routed in a shared search space that is a weighted graph. The problem is deconstructed into a low-level and a high-level search problem. In the low-level problem individual branched pipes are routed with the new Multi-Terminal Pipe Router algorithm. The high-level problem is to perform the low-level searches and find a globally optimized solution free of conflicts. This is achieved by applying the Conflict-Based Search algorithm into the pipe routing problem