A Three-Dimensional Pipe Routing Problem in Semiconductor Fabrication Industry

In this paper, we propose a three-dimensional shortest path problem for exhaust pipe routing in the semiconductor fabrication industry, involving a single origin and multiple candidate destinations. While previous studies have addressed variations of the shortest path problem, this study extends it into a three-dimensional space in semiconductor fabrication factory, incorporating calculations for pressure loss due to pipe length and multiple types of bend angles, obstacle avoidance, and relevant safety standards for industrial applications. Given the increasing complexity and frequent layout changes in modern semiconductor fabrication facilities, efficient and automated pipe routing has become a crucial task to reduce rework, installation time, and safety risks. To solve this problem, we developed a mixed-integer linear programming (MILP) model. Given its computational complexity, we propose a Pressure-based A* algorithm with a Divide-and-Conquer strategy (PA*-DC), which iteratively applies the 3D Pipe Routing A* (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3DP_A</i>*) algorithm. We validated the algorithms through computational experiments using a real-world dataset provided by Samsung Electronics and compared the results with current industry de facto standards for pipe design in actual fabrication facilities. Experimental results confirm that the proposed PA*-DC algorithm achieves high-quality routes and improves pressure efficiency by up to 53.20%, demonstrating its practicality for real-world applications.