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

Yue Xie, Shenghan Zhou, Yiyong Xiao, Sadan Kulturel-Konak, Abdullah Konak

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)26-38
Number of pages13
JournalEuropean Journal of Operational Research
Issue number1
StatePublished - Feb 16 2018

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management


Dive into the research topics of 'A β-accurate linearization method of Euclidean distance for the facility layout problem with heterogeneous distance metrics'. Together they form a unique fingerprint.

Cite this