Modeling and Optimization Method of Constrained Corridor Allocation Problem
-
摘要:
为了研究过道布置问题中设施关系对布局的影响,首先,考虑定位约束与排序约束,构建过道布置问题混合整数规划模型,并提出一种求解该问题的自适应混合克隆选择算法,在克隆操作之前新增符合受约束过道布置问题特性的2-opt操作,随后对所产生种群中最优个体进行禁忌搜索操作,对其他个体进行变异操作并设置自适应变异概率;然后,对模型进行精确求解以验证模型的正确性且求解结果为算法提供了理论依据;最后,应用所提算法分别对受约束过道布置问题与基本过道布置问题的42 ~ 49规模实例进行测试,并将求解结果与克隆选择算法、遗传算法、分散搜索算法、花授粉算法以及烟花算法进行对比,结果表明:混合克隆选择算法可以达到当前先进算法的求解效果且在算例sko-42-04与算例sko49-03上表现更优.
-
关键词:
- 设施布局 /
- 受约束的过道布置问题 /
- 克隆选择算法 /
- 禁忌搜索操作 /
- 自适应变异
Abstract:In order to study the influence of facility relationship on layout in corridor allocation problem, An integer programming model considering location and relationship constraints is constructed, and a hybrid clonal selection algorithm based on clonal selection algorithm is proposed to solve the problem. Before clonal operation, a new 2-opt operation based on problem characteristics is added. Then, tabu search operation is carried out for the optimal individuals in the generated population, mutation operation is carried out for other individuals and adaptive mutation probability is set. The model is accurately solved to verify the correctness of the model and the solution results provide a theoretical basis for the algorithm. Applying the proposed algorithm to test 42−49 scale examples of constrained corridor allocation problem and basic corridor allocation problem respectively. The results are compared with clonal selection algorithm, genetic Algorithm, Scatter Search, flower pollination algorithm and fireworks algorithm. The results show that the hybrid clone selection algorithm can achieve the solution effect of the current advanced algorithm and perform better in the examples sko-42-04 and sko-49-03.
-
表 1 参数名称与定义
Table 1. Parameter names and definition
变量 意义 n 问题规模,即布置的设施数目 I 所有设施的集合,I={1, 2, 3, …, n} i, j, h, k 设施编号,i, j, h∈ I cij 设施 i 与设施 j 之间的物流成本,$\forall $i∈{1,2,…, n−1},$\forall $j∈ {1,2,…,n−1} dij 设施 i, j 之间物流交互点在 X 轴方向的距离 li 设施 i 沿 X 轴边线的长度 w 通道宽度 αij 二进制变量,i, j 分配在同一行,且设施 i 被放置在设施 j 的左侧 αij= 1,否则 αij= 0 qij 二进制决策变量,若设施 i 与设施 j 被布置于同一行,则 qij= 1,否则 qij= 0 βhi 二进制决策变量,若设施 h 的物料搬运点在设施 i 的左侧,则 βhi= 1,否则 βhi= 0 f 设施间的总物流成本 表 2 CSA与ACSATS算法求解CCAP与CAP的参数
Table 2. Algorithm parameters of CSA and ACSATS in solving CCAP and CAP
问题 算法 n N Itermax_1 G α S/个 搜索次数/次 CCAP ACSATS 9~15 200 200 0.01 1 20 200 25 400 600 0.01 1.2 40 400 30 600 800 0.02 1.6 80 800 36 800 1000 0.02 1.6 80 800 CSA 42~49 1000 1000 0.02 1.6 100 800 9~15 200 200 0.01 1 — — 9~15 200 200 0.01 0.8 20 200 CAP ACSATS 30 600 800 0.02 1.6 80 600 36 800 1000 0.02 1.6 80 600 42 1000 1000 0.02 1.6 100 800 49 1000 1200 0.02 1.8 110 800 表 3 LINGO精确解与ACSATS算法的计算结果
Table 3. LINGO exact solution and solving results of ACSATS
问题 n LINGO ACSATS F0 t/s Fmin t/s gap1 S9 9 1372.5 900 1372.5 1.34 0 S9H 9 2946.5 900 2946.5 1.42 0 S10 10 1642.5 900 1642.5 1.77 0 S11 11 4812.5 900 4268.5 2.06 −11.30 Am12 a 12 2269.0 900 1919.0 2.38 −15.43 Am12 b 12 2400.5 900 2101.5 2.45 −12.46 Am13 a 13 3401.5 900 2968.5 2.61 −12.73 Am13 b 13 4291.0 900 3439.0 3.11 −19.86 Am15 15 5146.0 900 3989.0 3.05 −22.48 N-25-05 25 — 900 8408.0 44.78 — ste-36-05 36 — 900 50210.5 798.67 — sko-42-05 42 — 900 125647.5 1355.99 — 注:下划线表示LINGO与算法ACSATS的求解结果较优的一方. 表 4 CSA算法与ACSATS算法对CCAP的求解结果
Table 4. Solving results of CSA and ACSATS for CCAP
问题 CSA ACSATS FCSA 标准偏差 FACSATS 标准偏差 S9 1372.5 6.49 1372.5 0 S9H 2946.5 2.63 2946.5 0 S10 1642.5 11.60 1642.5 0 S11 4268.5 22.97 4268.5 0 Am12 a 1919.0 9.51 1919.0 0 Am12 b 2101.5 13.11 2101.5 0 Am13 a 2968.5 15.40 2968.5 0 Am13 b 3457.0 20.29 3439.0 10.68 Am15 3989.0 37.57 3989.0 3.81 表 5 SS、GA、IDFPA、IFWA与ACSATS在42与49规模问题下测试CAP的求解结果
Table 5. Results of solving CAP with SS, GA, IDFPA, IFWA and ACSATS in 42 and 49 scale instances
算例 SS[4] GA[4] IDFPA[11] IFWA[9] ACSATS f t/s f t/s f t/s f t/s f t/s 42-1 12731.0 1249.04 12731.0 7174.64 12731.0 279.37 12731.0 321.29 12731.0 322.38 42-2 108020.5 1249.04 108049.5 6815.77 108006.5 681.43 108020.5 604.61 108006.5 489.94 42-3 86667.5 956.28 86667.5 6854.25 86644.5 427.61 86655.5 621.45 86644.5 497.01 42-4 68733.0 1141.34 68769.0 6509.35 68708.0 493.77 68722.0 867.15 68701.0 517.67 42-5 124058.5 1236.47 124099.5 7052.59 124017.5 546.72 124017.5 554.07 124017.5 519.47 49-1 20479.0 2683.93 20472.0 14934.38 20470.0 515.02 20470.0 542.13 20470.0 598.67 49-2 208081.0 2733.87 208270.0 14338.86 208068.0 760.20 208078.0 1009.45 208068.0 1007.99 49-3 162196.0 2877.19 162267.0 14351.91 162187.0 822.33 162187.0 1173.59 162183.0 1006.58 49-4 118264.5 3716.16 118311.5 14290.03 118260.5 1809.86 118260.5 1193.88 118260.5 843.93 49-5 332855.0 2596.39 332990.0 14913.18 332836.0 821.67 332811.0 989.91 332836.0 799.05 -
[1] ANJOS M F, VIEIRA M V C. Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions[J]. European Journal of Operational Research, 2017, 261(1): 1-16. doi: 10.1016/j.ejor.2017.01.049 [2] HOSSEINI-NASAB H, FEREIDOUNI S, FATEMI GHOMI S M T, et al. Classification of facility layout problems: a review study[J]. The International Journal of Advanced Manufacturing Technology, 2018, 94(1/2/3/4): 957-977. [3] AMARAL A R S. The corridor allocation problem[J]. Computers and Operations Research, 2012, 39(12): 3325-3330. [4] GHOSH D, KOTHARI R. Population heuristics for the corridor allocation problem[J]. Iima Working Papers, 2012, 98(2): 33-40. [5] 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. doi: 10.1016/j.ejor.2013.07.010 [6] 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. [7] KALITA Z, DATTA D, PALUBECKIS G. Bi-objective corridor allocation problem using a permutation-based genetic algorithm hybridized with a local search technique[J]. Soft Computing, 2019, 23(3): 961-986. doi: 10.1007/s00500-017-2807-0 [8] ZHANG Z Q, MAO L L, GUAN C, et al. An improved scatter search algorithm for the corridor allocation problem considering corridor width[J]. Soft Computing, 2020, 24(1): 461-481. doi: 10.1007/s00500-019-03925-4 [9] 刘思璐,张则强,管超,等. 考虑设施深度的过道布置问题及改进烟花算法求解方法[J]. 控制与决策,2020,35(1): 45-54. doi: 10.13195/j.kzyjc.2018.0720LIU 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. doi: 10.13195/j.kzyjc.2018.0720 [10] 管超,张则强,毛丽丽,等. 双层过道布置问题的混合整数规划模型及启发式求解方法[J]. 计算机集成制造系统,2018,24(8): 1972-1982. doi: 10.13196/j.cims.2018.08.009GUAN Chao, ZHANG Zeqiang, MAO Lili, et al. Mixed integer programming model and heuristic method for double-layer corridor allocation problem[J]. Computer Integrated Manufacturing Systems, 2018, 24(8): 1972-1982. doi: 10.13196/j.cims.2018.08.009 [11] GUAN C, ZHANG Z Q, LI Y P. A flower pollination algorithm for the double-floor corridor allocation problem[J]. International Journal of Production Research, 2019, 57(20): 6506-6527. doi: 10.1080/00207543.2019.1566673 [12] 管超,张则强,朱立夏,等. 双层过道布置问题的混合整数非线性规划模型及两阶段改进模拟退火算法[J]. 中国机械工程,2019,30(8): 975-983. doi: 10.3969/j.issn.1004-132X.2019.08.014GUAN Chao, ZHANG Zeqiang, ZHU Lixia, et al. A MINLP model and improved simulated annealing algorithm for double-layer corridor allocation problem[J]. China Mechanical Engineering, 2019, 30(8): 975-983. doi: 10.3969/j.issn.1004-132X.2019.08.014 [13] 刘俊琦,张则强,管超,等. 基于多纵向传输通道的双层过道布置问题建模与优化[J]. 计算机集成制造系统,2022,28(2): 481-494. doi: 10.13196/j.cims.2022.02.013LIU 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, 2022, 28(2): 481-494. doi: 10.13196/j.cims.2022.02.013 [14] 王沙沙,张则强,刘俊琦,等. 多路径交互环形过道布置问题建模及改进蚁狮算法优化[J]. 计算机集成制造系统,2021,27(8): 2237-2247. doi: 10.13196/j.cims.2021.08.007WANG Shasha, ZHANG Zeqiang, LIU Junqi, et al. Modeling of multi-path interactive annular corridor allocation problem and optimization of improved ant-lion algorithm[J]. Computer Integrated Manufacturing Systems, 2021, 27(8): 2237-2247. doi: 10.13196/j.cims.2021.08.007 [15] 陈凤, 张则强, 刘俊琦. 考虑设施方向的双目标过道布置问题建模与优化[J]. 计算机集成制造系统, 2022, 28(6): 1717-1734. 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, 2022, 28(6): 1717-1734. [16] KALITA Z, DATTA D. Corridor allocation as a constrained optimization problem using a permutation-based multi-objective genetic algorithm[J]. Nature-Inspired Methods for Metaheuristics Optimization: Algorithms and Applications in Science and Engineering, 2020, 16: 335-358. [17] LIU J Q, ZHANG Z Q, CHEN F, et al. A novel hybrid immune clonal selection algorithm for the constrained corridor allocation problem[J]. Journal of Intelligent Manufacturing, 2020, 33(4): 953-972. [18] GUO Y W, MILEHAM A R, OWEN G W, et al. Operation sequencing optimization using a particle swarm optimization approach[J]. Proceedings of the Institution of Mechanical Engineers, Part B:Journal of Engineering Manufacture, 2006, 220(12): 1945-1958. doi: 10.1243/09544054JEM647 [19] 张则强,汪开普,朱立夏,等. 多目标U型拆卸线平衡问题的Pareto蚁群遗传算法[J]. 西南交通大学学报,2018,53(3): 628-637,660. doi: 10.3969/j.issn.0258-2724.2018.03.026ZHANG Zeqiang, WANG Kaipu, ZHU Lixia, et al. Pareto hybrid ant colony and genetic algorithm for multi-objective U-shaped disassembly line balancing problem[J]. Journal of Southwest Jiaotong University, 2018, 53(3): 628-637,660. doi: 10.3969/j.issn.0258-2724.2018.03.026 [20] KALITA Z, DATTA D. A constrained single-row facility layout problem[J]. The International Journal of Advanced Manufacturing Technology, 2018, 98(5/6/7/8): 2173-2184. [21] LIU S L, ZHANG Z Q, GUAN C, et al. An improved fireworks algorithm for the constrained single-row facility layout problem[J]. International Journal of Production Research, 2021, 59(8): 2309-2327. doi: 10.1080/00207543.2020.1730465 [22] 高锋阳,李昭君,袁成,等. 含特殊负荷的配电网分层故障定位方法[J]. 西南交通大学学报,2020,55(3): 570-580.GAO Fengyang, LI Zhaojun, YUAN Cheng, et al. Hierarchical fault location method for distribution network with special load[J]. Journal of Southwest Jiaotong University, 2020, 55(3): 570-580. [23] 徐长安,倪少权,陈钉均. 基于两阶段算法的运行图与天窗协同优化[J]. 西南交通大学学报,2020,55(4): 882-888.XU Changan, NI Shaoquan, CHEN Dingjun. Collaborative optimization for timetable and maintenance window based on two-stage algorithm[J]. Journal of Southwest Jiaotong University, 2020, 55(4): 882-888. [24] XIA Y K, FU Z. An adaptive tabu search algorithm for the open vehicle routing problem with split deliveries by order[J]. Wireless Personal Communications, 2018, 103(1): 595-609. doi: 10.1007/s11277-018-5464-4 [25] ZHOU B H, WU Q. An improved immune clonal selection algorithm for bi-objective robotic assemble line balancing problems considering time and space constraints[J]. Engineering Computations, 2019, 36(6): 1868-1892. doi: 10.1108/EC-11-2018-0512 [26] 左兴权,王春露,赵新超. 一种结合多目标免疫算法和线性规划的双行设备布局方法[J]. 自动化学报,2015,41(3): 528-540.ZUO Xingquan, WANG Chunlu, ZHAO Xinchao. Combining multi-objective immune algorithm and linear programming for double row layout problem[J]. Acta Automatica Sinica, 2015, 41(3): 528-540. [27] 贾林,张则强,李六柯,等. 考虑面积成本的双目标环形过道布置建模及改进禁忌搜索优化[J]. 信息与控制,2019,48(4): 477-485.JIA Lin, ZHANG Zeqiang, LI Liuke, et al. Modeling and improved tabu search optimization for double objective annular corridor allocation considering area cost[J]. Information and Control, 2019, 48(4): 477-485. [28] 任子武,伞冶. 自适应遗传算法的改进及在系统辨识中应用研究[J]. 系统仿真学报,2006,18(1): 41-43,66. doi: 10.3969/j.issn.1004-731X.2006.01.011REN Ziwu, SAN Ye. Improved adaptive genetic algorithm and its application research in parameter identification[J]. Journal of System Simulation, 2006, 18(1): 41-43,66. doi: 10.3969/j.issn.1004-731X.2006.01.011 [29] 徐岩,郅静. 基于改进自适应遗传算法的PMU优化配置[J]. 电力系统保护与控制,2015,43(2): 55-62. doi: 10.7667/j.issn.1674-3415.2015.02.009XU Yan, ZHI Jing. Optimal PMU configuration based on improved adaptive genetic algorithm[J]. Power System Protection and Control, 2015, 43(2): 55-62. doi: 10.7667/j.issn.1674-3415.2015.02.009 [30] 耿敬,覃天意,李明伟,等. 基于进化ANSYS的防波堤结构智能优化方法[J]. 华中科技大学学报(自然科学版),2020,48(10): 86-91.GENG Jing, QIN Tianyi, LI Mingwei, et al. Intelligent optimization method of breakwater structure based on evolutionary ANSYS[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2020, 48(10): 86-91. [31] LIU J Q, ZHANG Z Q, ZENG Y Q. Modeling and optimization of double floor corridor allocation problem considering double channel unidirectional elevator[C]//Conference Proceedings of the 8th International Symposium on Project Management, China (ISPM2020). Beijing: [s.n.], 2020: 482-493. [32] 魏彤辉,左文杰,郑宏伟,等. 基于降维算法的车身可靠性优化[J]. 汽车工程,2020,42(7): 941-948.WEI Tonghui, ZUO Wenjie, ZHENG Hongwei, et al. Reliability-based design optimization of car BodyBased on dimension reduction method[J]. Automotive Engineering, 2020, 42(7): 941-948.