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

李俊; 尹晶; 张煜

doi:10.3963/j.jssn.1674-4861.2023.05.013

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

doi: 10.3963/j.jssn.1674-4861.2023.05.013

李俊^{1, 2,},
尹晶³,
张煜^4, ,

1.
天津港（集团）有限公司天津 300461
2.
武汉科技大学汽车与交通工程学院武汉 430081
3.
中车齐齐哈尔车辆有限公司大连研发中心辽宁大连 116052
4.
武汉理工大学交通与物流工程学院武汉 430063

基金项目:

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

详细信息

作者简介:
李俊（1989—），博士，讲师. 研究方向：智能调度与优化算法. E-mail: lj_whut1989@163.com

通讯作者:
张煜（1974—），博士，教授. 研究方向：交通运输与物流系统优化、智慧港航等. E-mail: sanli@whut.edu.cn

中图分类号: U169.6
计量
- 文章访问数: 303
- HTML全文浏览量: 176
- PDF下载量: 11
- 被引次数: 0
出版历程
- 收稿日期: 2023-03-28
- 网络出版日期: 2024-01-18

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

LI Jun^{1, 2
,},
YIN Jing³,
ZHANG Yu^{4
, ,}

1.
Tianjin Port (Group) Co., Ltd., Tianjin 300461, China
2.
School of Automobile and Traffic Engineering, Wuhan University of Science and Technology, Wuhan 430081, China
3.
Dalian Development Center, CRRC Qiqihar Rolling Stock Co., Ltd., Dalian 116052, Liaoning, China
4.
School of Traffic and Logistics Engineering, Wuhan University of Technology, Wuhan 430063, China

摘要

摘要: 为满足汽车零部件中异形件在集装箱多式联运中的装箱运输需求，设计提出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内完成所有算例的有效求解。
- 交通规划 /
- 集装箱装载 /
- 0-1整数规划模型 /
- 快速装箱算法 /
- 装载单元划分
Abstract: To meet the packaging and loading requirements of irregular-shaped parts within automotive components in multi-modal container transport, a novel combined unit container is designed. The loading optimization model and algorithm for the proposed container are presented. This addresses challenges pertaining to internal division of the container unit, packing of irregular-shaped items, and multi-layer stacking requirements. The focus is on pallet selection for items to be packed, the positioning of loaded pallets within the container unit, and the effective alignment of goods, pallets, and the internal container space. Considering the above differences, the decision variables are redefined for pallet selection, stacking positioning for loaded pallets within the container unit, and positioning of dual pallets on the same layer. The constraints such as the selection of pallet types, the uniformity of pallet sizes within a single loading unit and its neighboring units are considered as well. A 0-1 integer programming model, Container Loading Model (CLM), is constructed to maximize the utilization of the effective space inside the container. To achieve efficient optimization, a heuristic algorithm, Fast-packing Algorithm (FPA), is presented encompassing cargo grouping, sorting, and packing. The experiments results show that both the proposed CLM and FPA provide high-quality loading solutions. The average effective space utilization rates achieved by CLM and FPA across all instances are 84.52% and 83.57%, respectively. For the instances involving packing goods selection, the average results attain 91.00% and 89.84%, respectively. Notably, the CLM requires a long solution time with an average of 473.57 s, with marginal improvements in solution quality with increased time. In contrast, the FPA exhibits the fastest solution time with an average of 0.20 s and an average deviation from upper bounds of 1.52%. Compared with the genetic algorithm and evolutionary strategy algorithm, the proposed FPA achieves best results within 1 s for all instances.
- transport planning /
- container loading /
- 0-1 integer programming model /
- fast-packing algorithm /
- loading unit division

HTML全文

图 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

算例名称	场景	货物分组	每种货物件数	货物总件数
C₁F₁L₈₀	1	1	20	80
C₂F₁L₁₂₀	2	1	30	120
C₂F₁L₁₆₀	2	1	40	160
C₂F₁L₂₀₀	2	1	50	200
C₁F₂L₆₀	1	2	10	60
C₂F₂L₁₂₀	2	2	20	120
C₂F₂L₁₈₀	2	2	30	180
C₂F₂L₂₄₀	2	2	40	240
C₂F₃L₉₀	2	3	10	90
C₂F₃L₁₈₀	2	3	20	180
C₂F₃L₂₇₀	2	3	30	270
C₂F₃L₃₆₀	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	C₁F₁L₈₀	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	C₂F₁L₁₂₀	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	C₂F₁L₁₆₀	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	C₂F₁L₂₀₀	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	C₁F₂L₆₀	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	C₂F₂L₁₂₀	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	C₂F₂L₁₈₀	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	C₂F₂L₂₄₀	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	C₂F₃L₉₀	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	C₂F₃L₁₈₀	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	C₂F₃L₂₇₀	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	C₂F₃L₃₆₀	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	Gap2
2	C₂F₁L₁₂₀	112	78.26	600	113	78.26	1 800	0
4	C₂F₁L₂₀₀	127	85.53	600	127	85.53	1 800	0
6	C₂F₂L₁₂₀	118	94.88	600	119	95.88	1 800	1.05
7	C₂F₂L₁₈₀	126	97.19	600	127	97.19	1 800	0
8	C₂F₂L₂₄₀	122	98.83	600	122	98.83	1 800	0
9	C₂F₃L₉₀	89	91.78	600	90	92.34	1 800	0.61
10	C₂F₃L₁₈₀	82	93.47	600	78	95.75	1 800	2.44
11	C₂F₃L₂₇₀	74	93.70	600	94	94.89	1 800	1.27
12	C₂F₃L₃₆₀	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（C₂F₂L₁₈₀）		算例8（C₂F₂L₂₄₀）
装载单元编号	托盘编号	货物编号（按堆放层数从下往上）	托盘编号	货物编号（按堆放层数从下往上）
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（C₂F₃L₂₇₀）		算例12（C₂F₃L₃₆₀）
装载单元编号	托盘编号	货物编号（按堆放层数从下往上）	托盘编号	货物编号（按堆放层数从下往上）
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

参考文献(20)

[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.