关键词: 过道布置问题, 设施布局, 分散搜索算法, 模拟退火操作

Abstract: According to the solving complexity of the Corridor Allocation Problem（CAP）, a hybrid scatter search algorithm with simulated annealing is proposed. In the hybrid algorithm, simulated annealing operation is introduced to further optimize the solutions in the reference set and improve the probability of obtaining global optimal solution. According to the features of the CAP, the 2-tier reference set involving high quality and diverse solutions is designed to expand the search scope and avoid local optimum. Meanwhile, the dynamic reference set update method is adopted and the relatively poor solutions are replaced timely, which accelerates the algorithm convergence speed. And the reduplicated solution in the improved subset generation method is not allowed which helps to increase the efficiency. Finally, 24 test problems with different sizes are conducted. The results show that the proposed approach outperforms the basic simulated annealing algorithm and scatter search algorithm in terms of solution quality and solving stability, and surpasses the other 4 methods.

Key words: Corridor Allocation Problem（CAP）, facility layout, scatter search algorithm, simulated annealing operation