混合模拟退火及分散搜索优化过道布置问题
|
摘要
针对过道布置问题的求解复杂性,提出了一种混合模拟退火及分散搜索算法。该算法通过引入模拟退火操作进一步优化参考集中的解,以提高获得全局最优解的概率。设计了包含高质量和多样性解的双层参考集,扩大了搜索范围,避免算法陷入局部最优。同时采用动态参考集更新方法,及时替换参考集中质量或多样性较差的解,加快算法的收敛速度,并改进子集产生方法,避免产生重复的解,从而提高算法的求解效率。应用所提算法对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.
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.
引文
[1]Drira A,Pierreval H,Hajri-Gabouj S.Facility layout problems:A survey[J].Annual Reviews in Control,2007,31(2):255-267.
[2]Anjos M F,Hungerl?nder P.A semidefinite optimization approach to space-free multi-row facility layout[J].Zhurnal Mikrobiologii Epidemiologii I Immunobiologii,2012(5):74-85.
[3]Nordin N N,Zainuddin Z M,Salim S,et al.Mathematical modeling and hybrid heuristic for unequal size facility layout problem[J].Journal of Fundamental Sciences,2009,5(1):79-87.
[4]张则强,程文明.双行布局问题的分解策略及启发式求解方法[J].计算机集成制造系统,2014,20(3):559-568.
[5]Izadinia N,Eshghi K.A robust mathematical model and ACO solution for multi-floor discrete layout problem with uncertain locations and demands[J].Computers&Industrial Engineering,2016,96:237-248.
[6]Lin Q,Liu H,Wang D,et al.Integrating systematic layout planning with fuzzy constraint theory to design and optimize the facility layout for operating theatre in hospitals[J].Journal of Intelligent Manufacturing,2015,26(1):87-95.
[7]Amaral A R S.The corridor allocation problem[J].Computers&Operations Research,2012,39(12):3325-3330.
[8]Ghosh D,Kothari R.Population heuristics for the corridor allocation problem[J].Tetrahedron Letters,2012,98(2):33-40.
[9]Ahonen H,De Alvarenga A G,Amaral A R S.Simulated annealing and tabu search approaches for the corridor allocation problem[J].European Journal of Operational Research,2014,232(1):221-233.
[10]白杰,杨根科,潘常春,等.基于改进分散搜索算法的无人机路径规划[J].上海交通大学学报,2011,45(2):173-178.
[11]Guo X,Liu S,Zhou M,et al.Disassembly sequence optimization for large-scale products with multiresource constraints using scatter search and petri nets[J].IEEETransactions on Cybernetics,2015.
[12]González M,Vela C,Varela R.Scatter search with path relinking for the flexible job shop scheduling problem[J].European Journal of Operational Research,2015,245(1):35-45.
[13]Grazielle B D P S,Sanches Mantovani J R,Cossi A M.Planning medium-voltage electric power distribution systems through a scatter search algorithm[J].IEEELatin America Transactions,2015,13(8):2637-2645.
[14]范志强.供应链订单分配优化模型及其模拟退火算法[J].计算机工程与应用,2012,48(25):28-33.
[15]Kothari R,Ghosh D.A scatter search algorithm for the single row facility layout problem[J].Journal of Heuristics,2014,20(2):125-142.
[16]MartíR,Laguna M,Glover F.Principles of scatter search[J].European Journal of Operational Research,2006,169(2):359-372.
[17]Simmons D M.One-dimensional space allocation:An ordering algorithm[J].Operations Research,1969,17(5):812-826.
[18]Amaral A R S.An exact approach to the one-dimensional facility layout problem[J].Operations Research,2008,56(4):1026-1033.
[19]Anjos M F,Vannelli A.Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes[J].Informs Journal on Computing,2008,20(4):611-617.
[20]Anjos M F,Yen G.Provably near-optimal solutions for very large single-row facility layout problems[J].Optimization Methods&Software,2009,24(4/5):805-817.
[2]Anjos M F,Hungerl?nder P.A semidefinite optimization approach to space-free multi-row facility layout[J].Zhurnal Mikrobiologii Epidemiologii I Immunobiologii,2012(5):74-85.
[3]Nordin N N,Zainuddin Z M,Salim S,et al.Mathematical modeling and hybrid heuristic for unequal size facility layout problem[J].Journal of Fundamental Sciences,2009,5(1):79-87.
[4]张则强,程文明.双行布局问题的分解策略及启发式求解方法[J].计算机集成制造系统,2014,20(3):559-568.
[5]Izadinia N,Eshghi K.A robust mathematical model and ACO solution for multi-floor discrete layout problem with uncertain locations and demands[J].Computers&Industrial Engineering,2016,96:237-248.
[6]Lin Q,Liu H,Wang D,et al.Integrating systematic layout planning with fuzzy constraint theory to design and optimize the facility layout for operating theatre in hospitals[J].Journal of Intelligent Manufacturing,2015,26(1):87-95.
[7]Amaral A R S.The corridor allocation problem[J].Computers&Operations Research,2012,39(12):3325-3330.
[8]Ghosh D,Kothari R.Population heuristics for the corridor allocation problem[J].Tetrahedron Letters,2012,98(2):33-40.
[9]Ahonen H,De Alvarenga A G,Amaral A R S.Simulated annealing and tabu search approaches for the corridor allocation problem[J].European Journal of Operational Research,2014,232(1):221-233.
[10]白杰,杨根科,潘常春,等.基于改进分散搜索算法的无人机路径规划[J].上海交通大学学报,2011,45(2):173-178.
[11]Guo X,Liu S,Zhou M,et al.Disassembly sequence optimization for large-scale products with multiresource constraints using scatter search and petri nets[J].IEEETransactions on Cybernetics,2015.
[12]González M,Vela C,Varela R.Scatter search with path relinking for the flexible job shop scheduling problem[J].European Journal of Operational Research,2015,245(1):35-45.
[13]Grazielle B D P S,Sanches Mantovani J R,Cossi A M.Planning medium-voltage electric power distribution systems through a scatter search algorithm[J].IEEELatin America Transactions,2015,13(8):2637-2645.
[14]范志强.供应链订单分配优化模型及其模拟退火算法[J].计算机工程与应用,2012,48(25):28-33.
[15]Kothari R,Ghosh D.A scatter search algorithm for the single row facility layout problem[J].Journal of Heuristics,2014,20(2):125-142.
[16]MartíR,Laguna M,Glover F.Principles of scatter search[J].European Journal of Operational Research,2006,169(2):359-372.
[17]Simmons D M.One-dimensional space allocation:An ordering algorithm[J].Operations Research,1969,17(5):812-826.
[18]Amaral A R S.An exact approach to the one-dimensional facility layout problem[J].Operations Research,2008,56(4):1026-1033.
[19]Anjos M F,Vannelli A.Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes[J].Informs Journal on Computing,2008,20(4):611-617.
[20]Anjos M F,Yen G.Provably near-optimal solutions for very large single-row facility layout problems[J].Optimization Methods&Software,2009,24(4/5):805-817.