基于反向扩散灾变和精英增强进化的自适应蝴蝶算法求解MFCAP问题

doi:10.3969/j.issn.1007-7375.2022.06.009

摘要/Abstract

摘要： 针对工业实际中设施物流交互点与其靠过道边线中点存在不重合的情况，提出一种考虑设施左右镜像情况的过道布置问题 (MFCAP) ，建立该问题的整数规划模型，并提出一种适用于MFCAP的改进离散蝴蝶优化算法。该算法在标准蝴蝶优化算法的基础上对编码方法和相关操作进行离散化构造，通过自适应模式切换概率提高算法的搜索速度，采用精英增强进化、反向扩散灾变等方法提高算法的搜索精度。为验证所提模型的正确性，采用分支定界法和改进离散蝴蝶优化算法对小规模MFCAP算例进行精确求解。为验证所提算法的有效性，将改进离散蝴蝶优化算法与其他启发式算法在较大规模算例中的求解结果进行对比。结果表明，所提改进离散蝴蝶优化算法在应用于MFCAP时具有较高的寻优质量和寻优效率，是求解MFCAP问题的一种有效方法。

关键词: 过道布置问题 (CAP), 蝴蝶优化算法, 整数规划模型, 可镜像设施 (MF)

Abstract: In view of the fact that the logistics interaction point of the facility in the industrial design does not overlap with the midpoint of the aisle sideline, an aisle layout problem that considers the left and right mirror images of the facility is proposed. The integer programming model of the problem is established, and an improved discrete butterfly optimization algorithm suitable for MFCAP is proposed. Based on the standard butterfly optimization algorithm, the algorithm discretizes the encoding method and related operations, improves the search speed of the algorithm through adaptive mode switching probability, and uses methods such as elite enhanced evolution and reverse diffusion catastrophe to improve the search accuracy of the algorithm. In order to verify the correctness of the proposed model, branch and bound algorithm and improved discrete butterfly optimization algorithm are used to accurately solve small-scale MFCAP examples. In order to verify the effectiveness of the proposed algorithm, the improved discrete butterfly optimization algorithm is compared with other heuristic algorithms in medium and large-scale calculation examples. The results show that the proposed improved discrete butterfly optimization algorithm has high quality and efficiency when applied to MFCAP, and it is an effective method to solve the MFCAP problem.

Key words: corridor allocation problem (CAP), butterfly optimization algorithm, integer programming model, mirrorable facility (MF)

中图分类号:

TP18

高帅, 管兴胤, 郝帅, 叶洋. 基于反向扩散灾变和精英增强进化的自适应蝴蝶算法求解MFCAP问题[J]. 工业工程, 2022, 25(6): 71-81.

GAO Shuai, GUAN Xingyin, HAO Shuai, YE Yang. An Adaptive Butterfly Optimization Algorithm Based on Reverse Diffusion Catastrophe and Elite Enhanced Evolution for Mirrorable Facility Corridor Allocation Problem[J]. Industrial Engineering Journal, 2022, 25(6): 71-81.

参考文献

[1] MADHUSUDANAN P, IRAPPA B H, KRISHNA K. Design of robust layout for dynamic plant layout problem[J]. Computers & Industrial Engineering, 2011, 61(3): 813-823
[2] AMARAL A R S. The corridoral location problem[J]. Computers & Operations Research, 2012, 39(12): 3325-3330
[3] GHOSH D, KOTHARI R. Population heuristics for the corridor allocation problem[DB/OL]. (2012-09-02). https://econpapers.repec.org/paper/iimiimawp/11453.htm.
[4] 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
[5] 陈凤, 张则强, 刘俊琦, 等. 考虑设施方向的双目标过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 27-35
CHEN Feng, ZHANG Zeqiang, LIU Junqi, et al. Modeling and optimization of bi-objective corridor layout problem considering facility orientation[J]. Computer Integrated Manufacturing Systems, 2021, 27(4): 27-35
[6] 刘俊琦, 张则强, 管超, 等. 基于多纵向传输通道的双层过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(3): 92-105
LIU Junqi, ZHANG Zeqiang, GUAN Chao, et al. Modeling and optimization of double floor corridor allocation problem based on multi longitudinal transmission channels[J]. Computer Integrated Manufacturing Systems, 2021, 27(3): 92-105
[7] 管超, 张则强, 朱立夏, 等. 双层过道布置问题的混合整数非线性规划模型及两阶段改进模拟退火算法[J]. 中国机械工程, 2019, 30(8): 978-983
GUAN Chao, ZHANG Zeqiang, ZHU Lixia, et al. A MINLP model and improved simulated annealing algorithm gor double-layer corridor allocation problem[J]. China Mechanical Engineering, 2019, 30(8): 978-983
[8] 刘思璐, 张则强, 管超, 等. 考虑设施深度的过道布置问题及改进烟花算法求解方法[J]. 控制与决策, 2020, 35(1): 45-54
LIU Silu, ZHANG Zeqiang, GUAN Chao, et al. Improved fireworks algorithm for the corridor allocation problem with facility depth[J]. Control and Decision, 2020, 35(1): 45-54
[9] ARORA S, SINGH S. Butterfly optimization algorithm: a novel approach for global optimization[J]. Soft Computing, 2018, 23(3): 715-734
[10] 谢聪. 求解TSP问题的改进离散蝴蝶优化算法[J]. 数学的实践与认知, 2020, 50 (1) : 173-182.
XIE Cong. An improved discreate butterfly optimization algorithm for solving TSP Problem[J]. Mathematics in Practice and Theory, 2020, 50 (1) : 173-182.
[11] KUNDU S, ROY P K, MANDAL B. Renewable energy-based economic load dispatch using two-step biogeography-based optimization and butterfly optimization algorithm[J]. International Journal of Swarm Intelligence Research, 2020, 11(4): 24-60
[12] PARAMBIL R K. Economic load dispatch problem using butterfly optimization algorithm[J]. European Journal of Molecular & Clinical Medicine, 2020, 7(4): 2773-2778
[13] DEY P P, DAS D C, LATIF A, et al. Active power management of virtual power plant under penetration of central receiver solar thermal-wind using butterfly optimization technique[J]. Sustainability, 2020, 12(17): 69-79
[14] QI X, YUASN Z, HAN X, et al. A discrete butterfly-inspired optimization algorithm for solving permutation flow-shop scheduling problems[J]. Neural Network World, 2020, 30(4): 211-229
[15] LI G, SHUANG F, ZHAO P, et al. An improved butterfly optimization algorithm for engineering design problems using the cross-entropy method[J]. Symmetry, 2019, 11(8): 1049-1050
[16] ARAVINDAN T E, SESHASAYANAN R. Denoising brain images with the aid of discrete wavelet transform and monarch butterfly optimization with different noises[J]. Journal of medical systems, 2018, 42(11): 1-13