(A) graph-theoretic heuristic for minimizing total transportation distance in facilities layout planning

Abstract

In this thesis, we consider an unequal sized facility layout problem with the objective of minimizing the total transportation distance. The total transportation distance is defined as the sum of the products of flow amounts and rectilinear distance between facilities, where the flow amounts represent the number of trips per time period between facilities. In this layout problem, sizes of facilities are unequal and locations for facilities placement are unknown. Since it is difficult to solve optimally the problem with reasonable number of facilities, researchers have concentrated on suboptimal methods. In the previous methods, however, the final solution usually depends upon the initial one, and is far from the optimal one. We propose a new graph-theoretic heuristic for the problem. In the proposed heuristic, we make an initial layout by constructing a planar adjacency graph and then improve the solution by changing not the physical layout but its adjacency graph. Therefore, this algorithm does not need an initial layout in advance, and we do not need to consider sizes and locations of facilities in the improvement steps. Computational results show that the proposed algorithm tends to give better solution than CRAFT, which is the most popular algorithm for the unequal sized facility layout problem.