A MINLP Model and Improved Simulated Annealing Algorithm for Double-layer Corridor Allocation Problem

Abstract

Abstract: Considering the situation that facilities were distributed into multi-layers space, a double layer corridor allocation problem was proposed, and a MINLP model was built for this problem. Concerning the problem features, an improved simulated annealing algorithm was proposed, which was improved in annealing processes and sampling processes via adopting the two-stage improvement strategy. The algorithm replaced the Markov chain search length with adaptive searching strategy, combined the memory function and the tempering operation to improve the solving quality; the double threshold was also set to improve the efficiency of the solution. 24 benchmarks were tested with the proposed algorithm and the validity was verified compared with the results of the basic simulated annealing algorithm and GUROBI exact method.

Key words: double-layer corridor allocation problem, facility layout, mixed-integer nonlinear programming(MINLP) model, simulated annealing algorithm

摘要： 结合实际布局活动中，设施在多层空间布置的实际情况，提出了双层过道布置问题，并构建了该问题的混合整数非线性规划（MINLP）模型。针对问题特征，提出了一种改进模拟退火算法，通过采用两阶段改进策略，对退火过程及抽样过程进行改进。该算法以自适应搜索策略替代马氏链搜索长度，并引入记忆功能、回火操作以提高求解质量，通过设置双阈值来提高求解效率。应用所提算法对24个基准算例进行测试，并将其与原模拟退火算法和GUROBI精确方法作对比，验证了所提算法的有效性。

关键词: 双层过道布置问题, 设施布局, 混合整数非线性规划模型, 模拟退火算法

CLC Number:

GUAN Chao;ZHANG Zeqiang;ZHU Lixia;MAO Lili. A MINLP Model and Improved Simulated Annealing Algorithm for Double-layer Corridor Allocation Problem[J]. China Mechanical Engineering.

管超;张则强;朱立夏;毛丽丽. 双层过道布置问题的混合整数非线性规划模型及两阶段改进模拟退火算法[J]. 中国机械工程.

References

[1]TOMPKINS J A, WHITE J A, BOZER Y A, et al. Facilities Planning [M]. 4th ed. New York: John Wiely & Sons, 2010.

[2]AMARAL A R S. The Corridor Allocation Problem [J]. Computers & Operations Research, 2012, 39(12): 3325-3330.
[3]张则强, 程文明. 双行布局问题的分解策略及启发式求解方法[J]. 计算机集成制造系统, 2014, 20(3): 559-568.
ZHANG Zeqiang, CHENG Wenming. Decomposition Strategies and Heuristic for Double Row Layout Problem [J]. Computer Integrated Manufacturing Systems, 2014, 20(3): 559-568.

[4]HONG D, SEO Y, XIAO Y. A Concurrent Approach for Facility Layout and AMHS Design in Semiconductor Manufacturing[J]. International Journal of Industrial Engineering, 2014, 21(4): 231-242.
[5]GHOSH D, KOTHARI R. Population Heuristics for the Corridor Allocation Problem [J]. Tetrahedron Letters, 2012, 98(2): 33-40.
[6]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.
[7]KALITA Z, DATTA D. Solving the Bi-objective Corridor Allocation Problem Using a Permutation-based Genetic Algorithm [J]. Computers & Operations Research, 2014, 52: 123-134.
[8]AHONEN H, ALVARENGAA G D, 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.
[9]韩伟, 张子成. 基于模拟退火的贯通约束不规则排样[J]. 中国机械工程, 2016, 27(24):3326-3331.
HAN Wei, ZHANG Zicheng. A Simulated Annealing Algorithm for Irregular Guillotine Packing Problems [J]. China Mechanical Engineering, 2016, 27(24):3326-3331.
[10]祝恒云, 叶文华. 模拟退火粒子群算法在动态单元布局中的应用[J]. 中国机械工程, 2009, 20(2): 181-185.
ZHU Hengyun, YE Wenhua. Application of Particle Swarm Algorithm Based on Simulated Annealing in Variable Cellular Facility Layout Problems[J]. China Mechanical Engineering, 2009, 20(2):181-185.
[11]SIMMONS D M. One-dimensional Space Allocation: an Ordering Algorithm [J]. Operations Research, 1969, 17(5): 812-826.
[12]AMARAL A R S. An Exact Approach to the One-dimensional Facility Layout Problem [J]. Operations Research, 2008, 56(4): 1026-1033.
[13]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.
[14]ANJOS M F, YENG. Provably Near-optimal Solutions for Very Large Single-row Facility Layout Problems [J]. Optimization Methods & Software, 2008, 24(4): 805-817.
[15]HERAGU S S, KUSIAK A. Efficient Models for the Facility Layout Problem[J]. European Journal of Operational Research, 1991, 53(1): 1-13.