Path relinking for single row facility layout

Abstract

The single row facility layout problem is the problem of arranging facilities with given lengths on a line, while minimizing the weighted sum of the distances between all pairs of facilities. The problem is NP-hard. In this paper we present path relinking algorithms to solve large sized instances of the problem. We use three di erent metaheuristics to generate sets of good quality initial solutions and subject the solutions in these sets to path relinking. We present our computational experience on 43 benchmark instances with up to 110 facilities.