A heuristic algorithm combining Pareto optimization and niche technology for multi-objective unequal area facility layout problem

摘要

The unequal area facility layout problem (UA-FLP) is the problem of placing departments with different areas in a facility so that departments satisfy some given objectives and constraints. In this paper, two objectives including the material handling cost and the closeness rating are optimized. Based on the quasi-physical strategy, we introduce an extrusive elastic potential energy based on the overlapping distance between departments into the layout system. After a novel handling approach of the non-overlapping constraint formed by executing the gradient method with an adaptive step length and subsequent department deformation strategy is developed to deal with the interference among departments and between any department and the facility, the problem is first converted into an optimization problem without the non-overlapping constraint. Then, we use a new heuristic algorithm that combines the local search based on the Pareto optimization and the global optimum search based on the niche technology to obtain Pareto-optimal solutions of the problem. In the proposed heuristic algorithm, in order to overcome the shortcomings of low efficient search toward the diversity of solutions in classical Pareto optimization method, we propose a heuristic layout updating strategy and a niche technology. To improve the convergence of the algorithm to the Pareto front, a mechanism of evolution of population named a feasible layout bank in the algorithm based on the local search and global optimum search is proposed. Two sets of representative instances from the literature with the size of the problem up to 62 departments are tested. The experimental results show that the proposed heuristic algorithm is an effective method for solving the multi-objective UA-FLP.