A rectilinear pipe routing algorithm: Manhattan visibility graph

Abstract

Pipe routing can be briefly formulated as seeking the shortest collision-free pipe paths while meeting certain engineering constraints. This article presents a new rectilinear pipe routing algorithm called Manhattan visibility graph (MVG) by extending the Visibility Graph method used for finding the shortest collision-free paths in Euclidean spaces to Manhattan spaces. Subsequently, the article proves that MVG can theoretically guarantee an optimal solution. Further, the article extends MVG algorithm to surface cases to meet requirements of routing pipes in aero-engine rotational spaces. Unlike previous graph methods that commonly yield more than n nodes (where n is the total number of terminals and obstacle vertices), MVG significantly reduces computation complexity because of containing only n nodes. Finally, numerical computations on a developed pipe routing system are performed to demonstrate the effectiveness and efficiency of the proposed method.

Keywords:

• aero-engines
• pipe routing
• rectilinear paths
• visibility graph

Additional information

Funding

This project is supported by National Natural Science Foundation of China [grant number 51305192] and PhD Start-up Fund of Liaoning Province of China [grant number 20131061].