Single row facility layout using multi-start simulated annealing

In the single row facility layout problem (SRFLP), we are given a set of n facilities, their lengths, and a flow cost matrix. The problem asks to arrange the facilities along a straight line so as to minimize the sum of the products of the flow costs and center-to-center distances between facilities. We develop a multi-start simulated annealing (MSA) algorithm for solving this problem. The algorithm employs two move types, pairwise interchanges of facilities and insertions. We propose O(n)-time procedures for computing gains of both types of moves. They make our algorithm very fast compared to the traditional approaches, which are based on a straightforward procedure for obtaining the move gain in O(n(2)) time. When the temperature during the cooling process drops to.a certain level, the computation is accelerated with the use of an additional technique which is reminiscent of a local search algorithm (it takes O(1) time to compute the move gain and O(n(2)) time to perform the required calculations when a move is accepted). We report computational results for SRFLP instances of size up to 1000 facilities. The results demonstrate the superiority of the MSA algorithm over the state-of-the-art methods. The source code implementing MSA is made publicly available as a benchmark for future comparisons. (C) 2016 Published by Elsevier Ltd.