Optimal Ship Pipe Route Design: A MOA*-Based Software Approach

For the ship pipe routing design (SPRD) problem, previous studies have mainly employed bio-inspired algorithms such as multi-objective ant colony optimization (MOACO), non-dominated sorting genetic algorithm II (NSGA-II), and multi-objective particle swarm optimization (MOPSO). This paper proposes a novel approach based on the multi-objective A* (MOA*) algorithm to solve the SPRD. First, the optimization objectives and constraints of the SPRD problem are defined, and then an MOA*-based routing framework is developed. The time and space complexities of the approach are analyzed, and key components such as the cost functions, the solution dominance relationship, dynamic probability-based pruning, and neighbor node exploration strategy are designed to enhance solution diversity and search efficiency. Additionally, a space cascade expansion method is proposed to improve the computational efficiency of the MOA* in large-scale grid spaces. Comparative studies with MOACO, NSGA-II, GA-A*, and gray wolf optimization (GWO) on simulated cases of varying complexities and practical piping scenarios demonstrate the effectiveness of the MOA*. Furthermore, the applicability of the MOA* is validated against practical piping requirements, including the rapid generation of sub-optimal solutions, non-orthogonal routing, and partitioned pipe layouts. Experimental results, supported by a C++/OpenGL-based prototype software, show that the MOA* requires no extensive parameter tuning, exhibits stable computational efficiency and optimization capability, and demonstrates competitive performance in Pareto-optimal diversity compared with other algorithms.