求解过道布置问题的一种改进分散搜索算法

Improved scatter search algorithm for corridor allocation problem

为更好地反映实际布置情况,针对现有研究在求解过道布置问题时忽略通道宽度、未设置总流量入口等不足,构建了考虑通道宽度和总流量入口的混合整数规划模型,提出一种改进分散搜索算法进行求解。该算法将禁忌搜索操作嵌入分散搜索的解改进方法中,可以进一步优化参考集中的解,提高获得全局最优解的概率。设计了包含高质量和多样性解的双层参考集、动态参考集更新方法、子集产生方法等多种改进机制。对不同规模(9~49个设施)的测试问题进行了验算与对比,结果表明:针对小规模问题,所提算法均求得了与Lingo软件相同的最优解;对大规模问题的求解质量明显优于基本分散搜索算法和禁忌搜索算法。

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 9to 49facilities）.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.