混合模拟退火及分散搜索优化过道布置问题

Hybrid scatter search algorithm with simulated annealing for corridor allocation problem

针对过道布置问题的求解复杂性,提出了一种混合模拟退火及分散搜索算法。该算法通过引入模拟退火操作进一步优化参考集中的解,以提高获得全局最优解的概率。设计了包含高质量和多样性解的双层参考集,扩大了搜索范围,避免算法陷入局部最优。同时采用动态参考集更新方法,及时替换参考集中质量或多样性较差的解,加快算法的收敛速度,并改进子集产生方法,避免产生重复的解,从而提高算法的求解效率。应用所提算法对24个不同规模的测试问题进行验算与对比,结果表明所提算法的求解质量与平稳性均优于基本模拟退火算法和分散搜索算法,且较已有的4种方法更具求解优势。

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.