Automatic pipeline routing is studied in this project. One of the most crucial steps in this problem is the description of the set of feasible routes for the pipes. We will consider a graph-based discretization of the space that allows us to use Path searching 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, and so on.
The crucial ingredient is A* search algorithm and the main reference is this paper.
Pipe wiring before optimization
Pipe wiring after optimization
This project relies on the visualization software mayavi.
pip install PyQt5
pip install mayavi
pip install vtk| Directory | Description |
|---|---|
model |
basic implementation of A* and multi pipe routing. |
plotting |
plotting module for 2D or 3D instance |
refdemo |
some old code |
Some effective test codes can be found in test_case/test.py. The gif blow shows the visualization of A* searching.
- Some hard constraints can be replaced by soft constrains by increasing the cost of conflict path.
- conflict of overlapping with obstacles.
- minimum required distance between consecutive elbows in the paths
- Customized written code using C++ to speed the running.
- Consider more economics and physical constrains.
- 建筑物离散化，对每条管道分别找到最短路
Ship Pipe Route Design Using Improved A∗ Algorithm and Genetic Algorithm
A Distance-Field-Based Pipe-Routing Method
- 蚁群算法（多条管道全局最优）
- 分别计算每条管道满足约束下的最优路径，再建立二叉树解决冲突
From Multi-Agent Pathfinding to 3D Pipe Routing
Conflict-based search for optimal multi-agent pathfinding
- MIP
Optimal Pipe Routing Techniques in an Obstacle-Free 3D Space
Optimization of Cable Harness Routing Mathematical Modelling, Lagrangian Relaxation, and Subgra-dient Optimization