A β-accurate linearization method of Euclidean distance for the facility layout problem with heterogeneous distance metrics

Most existing research on facility layout problems (FLPs) considers a single distance metric, mainly Rectilinear distance, in the calculation of the material handling cost between departments. However, there are many industrial cases in which heterogeneous distance metrics may need to be used simultaneously to cater for different styles of material handling, such as the Euclidean distance metric for conveyor belts and the Tchebychev distance metric for overhead cranes. In this paper, we study the unequal area facility layout problem with heterogeneous distance metrics (UA-FLP-HDM), considering a hybrid use of three metrics, i.e., Rectilinear, Euclidean, and Tchebychev, as distance measures of different styles of material handling in the production system. We propose a β-accurate linearization method that uses a set of tangent planes to convert the non-linear Euclidean distance constraint into a set of linear constraints that guarantee the approximation error within a given percentage β, e.g., as small as −0.01% in our experiments, and develop linear constraints for the Tchebychev distance metric as well. Based on these contributions, we present a mixed-integer linear programming (MILP) model for the UA-FLP-HDM. Computational experiments are carried out to test the performance of the MILP model with five benchmark problems in the literature and compare the layout designs using different distance metrics. Numerical results indicate that different distance metrics may lead to significantly different solutions and a hybrid use of heterogeneous distance metrics fits better for real industrial applications.