关键词: 过道布置问题, 设施布局, 分散搜索算法, 禁忌搜索操作

Abstract: To better reflect the actual layout situation,aiming at the problems such as corridor width was ignored and no flow entrance was set in the existing research on Corridor Allocation Problem (CAP),a mixed-integer programming model considered corridor width and flow entrance was presented.An Improved Scatter Search (ISS) algorithm was proposed to handle CAP.In ISS,tabu search operation was introduced as an improvement method to further optimize the solutions in the reference set and improve the probability of obtaining global optimal solution.Several improvement mechanisms had been applied to ISS such as designs of 2-tier reference set involved high quality and diverse solutions,dynamic reference set update method and subset generation method.The proposed approach was evaluated on test problems of different sizes (from 9 to 49 facilities).Computational results indicated that for small size test problems,the best solutions acquired were equal to the optimal solutions obtained by Lingo,and the proposed algorithm showed better performance in solving quality compared with tabu search algorithm and scatter search algorithm for large size test problems.

Key words: corridor allocation problem, facility layout, scatter search algorithm, tabu search operation