留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

汽车零部件多式联运组合式单元集装箱装载优化模型与算法

李俊 尹晶 张煜

李俊, 尹晶, 张煜. 汽车零部件多式联运组合式单元集装箱装载优化模型与算法[J]. 交通信息与安全, 2023, 41(5): 127-137. doi: 10.3963/j.jssn.1674-4861.2023.05.013
引用本文: 李俊, 尹晶, 张煜. 汽车零部件多式联运组合式单元集装箱装载优化模型与算法[J]. 交通信息与安全, 2023, 41(5): 127-137. doi: 10.3963/j.jssn.1674-4861.2023.05.013
LI Jun, YIN Jing, ZHANG Yu. An Optimization Model and Algorithms for Loading Combined Container Units Used in Multimodal Transport System with Automotive Parts[J]. Journal of Transport Information and Safety, 2023, 41(5): 127-137. doi: 10.3963/j.jssn.1674-4861.2023.05.013
Citation: LI Jun, YIN Jing, ZHANG Yu. An Optimization Model and Algorithms for Loading Combined Container Units Used in Multimodal Transport System with Automotive Parts[J]. Journal of Transport Information and Safety, 2023, 41(5): 127-137. doi: 10.3963/j.jssn.1674-4861.2023.05.013

汽车零部件多式联运组合式单元集装箱装载优化模型与算法

doi: 10.3963/j.jssn.1674-4861.2023.05.013
基金项目: 

国家重点研发计划项目 2019YFB16004

详细信息
    作者简介:

    李俊(1989—),博士,讲师. 研究方向:智能调度与优化算法. E-mail: lj_whut1989@163.com

    通讯作者:

    张煜(1974—),博士,教授. 研究方向:交通运输与物流系统优化、智慧港航等. E-mail: sanli@whut.edu.cn

  • 中图分类号: U169.6

An Optimization Model and Algorithms for Loading Combined Container Units Used in Multimodal Transport System with Automotive Parts

  • 摘要: 为满足汽车零部件中异形件在集装箱多式联运中的装箱运输需求,设计提出1种新型组合式单元集装箱,并研究其装载优化方法。考虑到箱体内部装载单元划分、异形件装箱及多层堆放的作业要求,重点解决待装箱物品的托盘选型、载货托盘在箱体内部装载单元的堆存位置选择等难题,以实现货物、托盘和箱体内部装载空间的有效适配。结合以上差异性特征,重新定义货物托盘选择、载货托盘堆放层位选择、同层双托盘位置选择的决策变量,并考虑装箱货物托盘类型、单个装载单元内部及其前后相邻装载单元内部的托盘尺寸统一等约束条件,以集装箱内部有效空间利用率最大化为目标,构建了单元集装箱装载决策问题的0-1整数规划模型(container loading model,CLM)。为实现该问题的高效寻优,设计了包含货物分组、货物排序及货物装箱的启发式算法(fast-packing algorithm,FPA)。算例结果表明:提出的CLM模型和FPA算法能求解得出高质量装载方案,所有算例中CLM模型和FPA算法的平均有效空间利用率分别为84.52%和83.57%,且针对存在装箱货物选择的算例,平均结果可达91.00%和89.84%。其中,CLM模型求解花费时间较长,平均耗时473.57 s,且求解质量随时间延长的提升并不显著;FPA算法求解速度最快,平均耗时为0.20 s,且与上界值间的平均偏差为1.52%;对比常见的遗传算法及演化策略算法,所提FPA算法耗时更短且结果更优,可在1 s内完成所有算例的有效求解。

     

  • 图  1  智能组合式单元集装箱结构

    Figure  1.  Structure of intelligent combined unit container

    图  2  快速装卸结构示意

    Figure  2.  Rapid loading and unloading structure

    图  3  集装箱内部装载单元划分示意

    Figure  3.  Internal loading unit divisions of container

    图  4  快速装箱算法流程图

    Figure  4.  Flowchart of fast-packing algorithm

    图  5  基于整数的个体编码

    Figure  5.  Individual coding based on numbering

    图  6  不同算法求解结果对比

    Figure  6.  Comparison of solutions from different algorithms

    表  1  组1运输货物信息

    Table  1.   Transport cargo information of group 1

    项目 长/mm 宽/mm 高/mm 重量/kg 分组
    货物1 1 200 1 000 200 260
    货物2 1 200 1 000 100 180
    货物3 1 100 1 100 200 320
    货物4 1 100 1 100 100 120
    下载: 导出CSV

    表  2  组2运输货物信息

    Table  2.   Transport cargo information of group 2

    项目 长/mm 宽/mm 高/mm 重量/kg 分组
    货物5 1 200 1 000 100 100
    货物6 1 200 1 000 200 200
    货物7 1 100 1 100 300 300
    货物8 1 100 1 100 100 100
    货物9 1 100 1 000 200 200
    货物10 1 100 1 000 300 300
    下载: 导出CSV

    表  3  组3运输货物信息

    Table  3.   Transport cargo information of group 3

    项目 长/mm 宽/mm 高/mm 重量/kg 分组
    货物11 1 180 990 600 360
    货物12 1 150 980 420 280
    货物13 1 120 1 000 100 110
    货物14 1 080 1 080 580 320
    货物15 1 000 1 050 320 240
    货物16 1 060 1 070 115 110
    货物17 1 080 980 300 250
    货物18 1 060 1 000 200 180
    货物19 1 100 990 120 120
    下载: 导出CSV

    表  4  算例数据

    Table  4.   Example data

    算例名称 场景 货物分组 每种货物件数 货物总件数
    C1F1L80 1 1 20 80
    C2F1L120 2 1 30 120
    C2F1L160 2 1 40 160
    C2F1L200 2 1 50 200
    C1F2L60 1 2 10 60
    C2F2L120 2 2 20 120
    C2F2L180 2 2 30 180
    C2F2L240 2 2 40 240
    C2F3L90 2 3 10 90
    C2F3L180 2 3 20 180
    C2F3L270 2 3 30 270
    C2F3L360 2 3 40 360
    下载: 导出CSV

    表  5  不同模型及算法求解算例结果

    Table  5.   Solving results of different models and algorithms

    编号 算例名称 UBM CLM FPA GA[19] ES[20]
    N F T N F Gap1 T N F Gap1 T N F Gap1 T N F Gap1 T
    1 C1F1L80 80 56.01 1.57 80 56.01 0 2.58 80 56.01 0 0.05 80 56.01 0 0.64 80 56.01 0 1.57
    2 C2F1L120 112 78.26 474.43 112 78.26 0 600 113 78.26 0 0.10 111 77.83 0.55 1.21 113 78.25 0.01 5.92
    3 C2F1L160 125 83.17 119.91 125 83.17 0 278.59 116 81.19 2.38 0.15 116 80.46 3.26 2.24 120 80.79 2.86 12.83
    4 C2F1L200 127 85.53 600 127 85.53 0 600 119 83.66 2.19 0.27 112 80.06 6.4 3.74 124 84.07 1.71 20.69
    5 C1F2L60 60 48.24 1.28 60 48.24 0 1.69 60 48.24 0 0.02 60 48.24 0 0.49 60 48.24 0 1.17
    6 C2F2L120 119 95.46 600 118 94.88 0.61 600 116 93.31 2.25 0.07 113 90.31 5.39 4.68 116 93.09 2.48 16.50
    7 C2F2L180 126 97.19 600 126 97.19 0 600 125 95.85 1.38 0.15 124 94.63 2.63 4.51 124 95.56 1.68 10.58
    8 C2F2L240 122 98.83 600 122 98.83 0 600 116 96.22 2.64 0.26 122 96.22 2.64 2.25 122 96.22 2.64 6.81
    9 C2F3L90 90 92.34 548.77 89 91.78 0.61 600 87 90.51 1.98 0.05 84 87.22 5.54 3.11 87 90.51 1.98 13.11
    10 C2F3L180 83 95.49 600 82 93.47 2.12 600 60 92.05 3.60 0.18 60 92.05 3.6 6.64 60 92.05 3.60 15.29
    11 C2F3L270 86 94.30 600 74 93.70 0.64 600 84 93.58 0.76 0.41 63 92.22 2.21 6.96 66 93.41 0.94 19.04
    12 C2F3L360 83 94.89 600 80 93.19 1.79 600 88 93.91 1.03 0.67 61 94.33 0.59 19.18 62 94.48 0.43 38.60
    平均值 101.08 84.98 445.5 99.58 84.52 0.48 473.57 97 83.57 1.52 0.20 92 82.47 2.73 4.64 94.5 83.56 1.53 13.51
    注:Gap1=100%×(F from UBM - F from CLM or FPA or GA or ES)/F from UBM
    下载: 导出CSV

    表  6  不同求解时间限制下模型求解结果

    Table  6.   Model solving results under different solving time

    编号 算例名称 CLM(600 s) CLM(1 800 s) Gap2
    N F T N F T
    2 C2F1L120 112 78.26 600 113 78.26 1 800 0
    4 C2F1L200 127 85.53 600 127 85.53 1 800 0
    6 C2F2L120 118 94.88 600 119 95.88 1 800 1.05
    7 C2F2L180 126 97.19 600 127 97.19 1 800 0
    8 C2F2L240 122 98.83 600 122 98.83 1 800 0
    9 C2F3L90 89 91.78 600 90 92.34 1 800 0.61
    10 C2F3L180 82 93.47 600 78 95.75 1 800 2.44
    11 C2F3L270 74 93.70 600 94 94.89 1 800 1.27
    12 C2F3L360 80 93.19 600 100 94.44 1 800 1.34
    注:Gap2=100%×(F from CLM(1 800 s)-F from CLM(600 s))/F from CLM(600 s)。
    下载: 导出CSV

    表  7  算例7和8的集装箱装载方案

    Table  7.   Loading plans of the container for instance 7 and 8

    装载单元编号 算例7(C2F2L180 算例8(C2F2L240
    托盘编号 货物编号(按堆放层数从下往上) 托盘编号 货物编号(按堆放层数从下往上)
    1 1 31、32、33、34、35、36、1 1 41、42、43、44、45、46、1
    2 1 37、38、39、40、41、42、2 1 47、48、49、50、51、52、2
    3 1 43、44、45、46、47、48、3 1 53、54、55、56、57、58、3
    4 1 49、50、51、52、53、54、4 1 59、60、61、62、63、64、4
    5 1 55、56、57、58、59、60、5 1 65、66、67、68、69、70、5
    6 1 6、7、8、9、10、11、12、13、14 1 71、72、73、74、75、76、6
    7 1 15、16、17、18、19、20、21、22、23 1 77、78、79、80、7、8、9
    8 1 151、24、25、26、27、28、29、30 1 10、11、12、13、14、15、16、17、18
    9 2 61、63、65、67、69(近端位置)
    62、64、66、68、70(远端位置)
    2 81、83、85、87、89(近端位置)
    82、84、86、88、90(远端位置)
    10 2 71、73、75、77、79(近端位置)
    72、74、76、78、80(远端位置)
    2 91、93、95、97、99(近端位置)
    92、94、96、98、100(远端位置)
    11 2 81、83、85、87、89(近端位置)
    82、84、86、88、90(远端位置)
    2 101、103、105、107、109(近端位置)
    102、104、106、108、110(远端位置)
    12 2 91、93、95、97、99、101、103、105、107(近端位置)
    92、94、96、98、100、102、104、106、108(远端位置)
    2 111、113、115、117、119(近端位置)
    112、114、116、118、120(远端位置)
    13 2 152、121、109、111、113、115、117、119(近端位置)
    153、122、110、112、114、116、118、120(远端位置)
    2 121、123、125、127、129、131、133、135、137(近端位置)
    122、124、126、128、130、132、134、136、138(远端位置)
    下载: 导出CSV

    表  8  算例11和12的集装箱装载方案

    Table  8.   Loading plans of the container for instance 11 and 12

    装载单元编号 算例11(C2F3L270 算例12(C2F3L360
    托盘编号 货物编号(按堆放层数从下往上) 托盘编号 货物编号(按堆放层数从下往上)
    1 1 1、2、3 1 1、2、3
    2 1 4、5、6 1 4、5、6
    3 1 7、8、9 1 7、8、9
    4 1 10、11、12 1 10、11、12
    5 1 13、14、15 1 13、14、15
    6 1 16、17、18 1 16、17、18
    7 1 19、20、21 1 19、20、21
    8 1 22、23、24 1 22、23、24
    9 1 25、27、29(近端位置)
    26、28、30(远端位置)
    1 25、27、29(近端位置)
    26、28、30(远端位置)
    10 2 151、153、155、157、159、161、163、165、167(近端位置)
    152、154、156、158、160、162、164、166、169(远端位置)
    2 201、203、205、207、209、211、213、215、217(近端位置)
    202、204、206、208、210、212、214、216、218(远端位置)
    11 2 121、241、169、171、173、175、177、179(近端位置)
    122、242、170、172、174、176、178、180(远端位置)
    2 219、221、223、225、227、229、231、233、235(近端位置)
    220、222、224、226、228、230、232、234、236(远端位置)
    12 2 181、123、125、127、129(近端位置)
    182、124、126、128、130(远端位置)
    2 161、163、165、281、237、239(近端位置)
    162、164、166、282、238、240(远端位置)
    13 2 183、131、133、135、137(近端位置)
    184、132、134、136、138(远端位置)
    2 241、167、169、171、173(近端位置)
    242、168、170、172、174(远端位置)
    下载: 导出CSV
  • [1] 王骁. 汽车零部件物流中心三维装箱问题研究[D]. 大连: 大连理工大学, 2015.

    WANG X. Research on three dimensional container loading problem of automobile parts logistics center[D]. Dalian: Dalian University of Technology, 2015. (in Chinese)
    [2] 林永昊. 汽车零部件入厂物流三维装箱问题研究[D]. 上海: 上海交通大学, 2018.

    LIN Y H. Research on three dimensional container loading problem in automobile parts inbound logistics[D]. Shanghai: Shanghai Jiao Tong University, 2018. (in Chinese)
    [3] 姜东东. 风神物流基于三维装载的循环取货路径优化研究[D]. 长沙: 长沙理工大学, 2019.

    JIANG D D. Fengshen logistics based on the three dimensional loading cycle pickup path optimization research[D]. Changsha: Changsha University of Science & technology, 2019. (in Chinese)
    [4] 徐翔斌, 任晨昊. 考虑车辆限行和装箱约束的车辆路径优化方法[J]. 交通信息与安全, 2021, 39(3): 77-84. doi: 10.3963/j.jssn.1674-4861.2021.03.010

    XU X B, REN C H. An optimization method of vehicle routing considering vehicle restrictions and two-dimensional loading constraints[J]. Journal of Transport Information and Safety, 2021, 39(3): 77-84. (in Chinese) doi: 10.3963/j.jssn.1674-4861.2021.03.010
    [5] 孙静妍. 多零件三维装箱与循环取货路径联合优化问题研究[D]. 武汉: 湖北大学, 2021.

    SUN J Y. A study on the joint optimization problem of multi-part three-dimensional packing and recycling pickup path[D]. Wuhan: Hubei University, 2021. (in Chinese)
    [6] 朱向, 雷定猷. 带平衡约束三维装箱问题的双层混合遗传算法[J]. 交通运输系统工程与信息, 2015, 15(2): 203-209. doi: 10.3969/j.issn.1009-6744.2015.02.031

    ZHU X, LEI D Y. Bi-level hybrid genetic algorithm for three-dimensional container loading problem with balancing constrains[J]. Journal of Transportation Systems Engineering and Information Technology, 2015, 15(2): 203-209. (in Chinese) doi: 10.3969/j.issn.1009-6744.2015.02.031
    [7] RAMOS A G, SILVA E, OLIVEIRA J F. A new load balance methodology for container loading problem in road transportation[J]. European Journal of Operational Research, 2018, 266(3): 1140-1152. doi: 10.1016/j.ejor.2017.10.050
    [8] LIU S, ZHAO H X, DONG X S, et al. A heuristic algorithm for container loading of pallets with infill boxes[J]. European Journal of Operational Research, 2016(3): 728-736.
    [9] HUANG Y H, HWANG F J, LU H C. An effective placement method for the single container loading problem[J]. Computers & Industrial Engineering, 2016(97): 212-221.
    [10] LIU S, SHANG X Q, CHENG C J, et al. Heuristic algorithm for the container loading problem with multiple constraints[J]. Computers & Industrial Engineering, 2017(108): 149-164.
    [11] ARAYA I, GUERRERO K, NUÑEZ E. VCS: a new heuristic function for selecting boxes in the single container loading problem[J]. Computers & Operations Research, 2017(82): 27-35.
    [12] ARAYA I, RIFF M C. A beam search approach to the container loading problem[J]. Computers & Operations Research, 2014(43): 100-107.
    [13] ARAYA I, MOYANO M, SANCHEZ C. A beam search algorithm for the biobjective container loading problem[J]. European Journal of Operational Research, 2020(2): 417-431.
    [14] RAMOS A G, SILVA E, OLIVEIRA J F. A new load balance methodology for container loading problem in road transportation[J]. European Journal of Operational Research, 2018(3): 1140-1152.
    [15] CASTELLUCCI P, TOLEDO F, COSTA A. Output maximization container loading problem with time availability constraints[J]. Operations Research Perspectives, 2019(6): 100126.
    [16] RANCK R, YANASSE H. MORABITO R, et al. A hybrid approach for a multi-compartment container loading problem[J]. Expert Systems with Applications, 2019(137): 471-492.
    [17] BAYRAKTAR T, ERSÖZ F, KUBAT C. Effects of memory and genetic operators on artificial bee colony algorithm for single container loading problem[J]. Applied Soft Computing, 2021(108): 107462.
    [18] NASCIMENTO O X, QUEIROZ T, JUNQUEIRA L. Practical constraints in the container loading problem: comprehensive formulations and exact algorithm[J]. Computers & Operations Research, 2021(128): 105186.
    [19] 白益维. 基于遗传算法的多箱型三维装箱问题的研究[D]. 天津: 天津大学, 2018.

    BAI Y W. A genetic algorithm for three-dimensional multiple bin-size bin packing problems[D]. Tianjin: Tianjin University, 2018. (in Chinese)
    [20] LI J, ZHANG Y, JI S Y, et al. Multi-stage hierarchical decomposition approach for stowage planning problem in inland container liner shipping[J]. Journal of the Operational Research Society, 2020, 71(3): 381-399.
  • 加载中
图(6) / 表(8)
计量
  • 文章访问数:  311
  • HTML全文浏览量:  178
  • PDF下载量:  12
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-03-28
  • 网络出版日期:  2024-01-18

目录

    /

    返回文章
    返回