• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

受约束的过道布置问题建模及优化方法

刘俊琦 张则强 龚举华 张裕

刘俊琦, 张则强, 龚举华, 张裕. 受约束的过道布置问题建模及优化方法[J]. 西南交通大学学报, 2022, 57(6): 1376-1385. doi: 10.3969/j.issn.0258-2724.20200803
引用本文: 刘俊琦, 张则强, 龚举华, 张裕. 受约束的过道布置问题建模及优化方法[J]. 西南交通大学学报, 2022, 57(6): 1376-1385. doi: 10.3969/j.issn.0258-2724.20200803
LIU Junqi, ZHANG Zeqiang, GONG Juhua, ZHANG Yu. Modeling and Optimization Method of Constrained Corridor Allocation Problem[J]. Journal of Southwest Jiaotong University, 2022, 57(6): 1376-1385. doi: 10.3969/j.issn.0258-2724.20200803
Citation: LIU Junqi, ZHANG Zeqiang, GONG Juhua, ZHANG Yu. Modeling and Optimization Method of Constrained Corridor Allocation Problem[J]. Journal of Southwest Jiaotong University, 2022, 57(6): 1376-1385. doi: 10.3969/j.issn.0258-2724.20200803

受约束的过道布置问题建模及优化方法

doi: 10.3969/j.issn.0258-2724.20200803
基金项目: 国家自然科学基金(51205328,51675450);教育部人文社会科学研究青年基金(18YJC630255);四川省科技计划(2022YFG0245)
详细信息
    作者简介:

    刘俊琦(1995—),男,博士研究生,研究方向为设施布局与智能优化,E-mail:junqi5497@163.com

    通讯作者:

    张则强(1978—),男,教授,研究方向为制造系统与智能优化,E-mail:zzq_22@163.com

  • 中图分类号: TH165;TP301.6

Modeling and Optimization Method of Constrained Corridor Allocation Problem

  • 摘要:

    为了研究过道布置问题中设施关系对布局的影响,首先,考虑定位约束与排序约束,构建过道布置问题混合整数规划模型,并提出一种求解该问题的自适应混合克隆选择算法,在克隆操作之前新增符合受约束过道布置问题特性的2-opt操作,随后对所产生种群中最优个体进行禁忌搜索操作,对其他个体进行变异操作并设置自适应变异概率;然后,对模型进行精确求解以验证模型的正确性且求解结果为算法提供了理论依据;最后,应用所提算法分别对受约束过道布置问题与基本过道布置问题的42 ~ 49规模实例进行测试,并将求解结果与克隆选择算法、遗传算法、分散搜索算法、花授粉算法以及烟花算法进行对比,结果表明:混合克隆选择算法可以达到当前先进算法的求解效果且在算例sko-42-04与算例sko49-03上表现更优.

     

  • 图 1  过道布置问题距离计算方式

    Figure 1.  Distance calculation method of CAP

    图 2  基于两种约束的2-opt操作示意

    Figure 2.  Improved 2-opt operation diagram based on two kinds of constraints

    图 3  ACSATS 流程

    Figure 3.  Flow chart of ACSATS

    图 4  CSA与ACSATS在9~15规模下问题求解结果箱线图

    Figure 4.  Box-plot of the solution results of CSA and ACATS in the scale of 9−15

    表  1  参数名称与定义

    Table  1.   Parameter names and definition

    变量意义
    n  问题规模,即布置的设施数目
    I  所有设施的集合,I={1, 2, 3, …, n}
    i, j, h, k  设施编号,i, j, hI
    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  设施间的总物流成本
    下载: 导出CSV

    表  2  CSA与ACSATS算法求解CCAP与CAP的参数

    Table  2.   Algorithm parameters of CSA and ACSATS in solving CCAP and CAP

    问题算法nNItermax_1GαS/搜索次数/次
    CCAPACSATS9~152002000.01120200
    254006000.011.240400
    306008000.021.680800
    3680010000.021.680800
    CSA42~49100010000.021.6100800
    9~152002000.011
    9~152002000.010.820200
    CAPACSATS306008000.021.680600
    3680010000.021.680600
    42100010000.021.6100800
    49100012000.021.8110800
    下载: 导出CSV

    表  3  LINGO精确解与ACSATS算法的计算结果

    Table  3.   LINGO exact solution and solving results of ACSATS

    问题nLINGOACSATS
    F0t/sFmint/sgap1
    S991372.59001372.51.340
    S9H92946.59002946.51.420
    S10101642.59001642.51.770
    S11114812.59004268.52.06−11.30
    Am12 a122269.09001919.02.38−15.43
    Am12 b122400.59002101.52.45−12.46
    Am13 a133401.59002968.52.61−12.73
    Am13 b134291.09003439.03.11−19.86
    Am15155146.09003989.03.05−22.48
    N-25-05259008408.044.78
    ste-36-053690050210.5798.67
    sko-42-0542900125647.51355.99
    注:下划线表示LINGO与算法ACSATS的求解结果较优的一方.
    下载: 导出CSV

    表  4  CSA算法与ACSATS算法对CCAP的求解结果

    Table  4.   Solving results of CSA and ACSATS for CCAP

    问题CSAACSATS
    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
    下载: 导出CSV

    表  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
    ft/sft/sft/sft/sft/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
    下载: 导出CSV
  • [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.0720

    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. doi: 10.13195/j.kzyjc.2018.0720
    [10] 管超,张则强,毛丽丽,等. 双层过道布置问题的混合整数规划模型及启发式求解方法[J]. 计算机集成制造系统,2018,24(8): 1972-1982. doi: 10.13196/j.cims.2018.08.009

    GUAN 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.014

    GUAN 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.013

    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, 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.007

    WANG 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.026

    ZHANG 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.011

    REN 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.009

    XU 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.
  • 加载中
图(4) / 表(5)
计量
  • 文章访问数:  366
  • HTML全文浏览量:  113
  • PDF下载量:  40
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-12-01
  • 修回日期:  2021-03-22
  • 网络出版日期:  2022-08-13
  • 刊出日期:  2021-03-26

目录

    /

    返回文章
    返回