Solving the Steiner Tree Problem for the Design of Medical Gas System

Abstract

Modern Hospitals require large amounts of Medical Gases for assisted patient respiration as well as for the operation of medical and pneumatic equipment. These gases are delivered to the consumption sites via a Medical Gases Network; at the assigned pressures and flows. The effiCiency of such networks depends mainly on the pipe routes within the departments involved. The optimal pipe route is defined as that one, which minimizes the pipe length and maintains pressure and flow limits for every gas outlet. Finding this optimal route is the main objective of . this thesis. The routing of pipes in the Medical Gases Network is formulated as a Rectilinear Steiner Tree Problem: "given a number of gas outlets within the hospital floor, it is required to find the minimum-length interconnection between those outlets according to the rectilinear metric".

The Steiner Tree problem is first investigated. In the absence of obstacles, two classes of algorithms are incorporated: the optimal exact algorithms and the heuristic approximation algorithms. The optimal exact algorithms are discussed with emphasis on Full-set Dynamic Programming (FOP) technique as well as its improved version, which is known as the Screening .Full-set Dynamic Programming (SFDP). We introduce an additional refutation procedure to SFDP where some of the candidate subsets composed of two terminals are excluded. This refutation procedure results in reducing the search space. The results of the numerical experiments showed up to 50% saving in the processing time, when compared to the original SFDP.