考虑周转箱的托盘配载优化研究

苌道方，徐振宇，罗天，高银萍



考虑周转箱的托盘配载优化研究

苌道方，徐振宇，罗天，高银萍

(上海海事大学 物流科学与工程研究院，上海 201306)

托盘是为配合高效物流而诞生的一种单元化物流器具，是贯穿现代供应链中各个环节的连接点。但由于实际应用中使用方式落后以及配载方案不当，导致不能完全发挥托盘的优势。针对托盘配载问题提出使用周转箱的配载模式，以提高周转箱和托盘利用率为目标，建立2阶段混合整数线性规划模型，第1阶段为周转箱装箱，第2阶段为托盘配载。通过算例验证了模型的有效性和准确性。研究结果表明：当产品箱的数量为24时，在使用周转箱的托盘配载模式中，托盘利用率为100%，周转箱利用率为81.64%；而不使用周转箱时的托盘利用率则为40.82%。与传统模式相比，使用周转箱的托盘配载模式可显著提高托盘利用率，降低物流成本。

托盘配载；周转箱；三维装箱问题；整数规划

托盘作为现代物流中基本的集装器具，广泛应用于生产和流通领域，可实现供应链中产品的无缝和高效运输，对物流一体化运作具有牵一发而动全身的作用。但是托盘在运输过程中又有其不可避免的缺点。一方面，使用托盘运输时，产品箱(本文将产品和带包装的产品统称为产品箱)通常会直接暴露于外部环境，因此在酸碱、潮湿、油污等恶劣条件下不能对产品形成有效的保护；另一方面，托盘难以高效地承载具有易碎特性的产品，如玻璃制品、陶瓷制品、精密电子电器等，这些产品在运输过程中不能积压放置，且往往对摆放方向有特殊的要求，因此只能在托盘上有限制的装载一层，严重影响托盘的利用率，而周转箱可有效消除这些弊端。周转箱也称物流箱，是一类物流集装器具，能耐酸碱、耐油污，无毒无味，具有材质坚硬、便捷周转、整齐堆砌、便于管理的特点。随着物流集装容器由多样化向系列化、标准化转变[1]，周转箱配合标准托盘的使用能提高物流标准化协同能力，保证高水平运输效率。因此，在产品运输中使用周转箱的托盘配载模式得到了越来越多的应用，也受到了政府的广泛推广。在实际物流运输中，不当的配载方案可能导致大量的空间资源浪费，从而增加供应链中物流运输的成本。因此，本文在使用周转箱的托盘配载模式下，以寻求产品箱最佳的配载方案为研究主体。作为复杂的组合优化问题，国内外诸多学者从不同角度对此类装箱问题进行了研究。蔡其琛等[2]基于一维装箱问题建立混合整数规划模型，设计基于分支定界方法的精确算法。Alonso等[3]在一维的层面上，针对托盘装载问题构建一个逐步扩展的整数线性规划模型。Ahn等[4]从二维的层面研究单托盘配载问题，并针对该问题设计改进的分支定界算法。姜丽等[5]利用重构思想建立二维装箱问题的整数线性规划模型，运用小规模算例验证了模型的有效性。颜瑞等[6]研究包含时间窗、多车场因素的二维装箱车辆路径问题，建立数学模型并提出相应的混合求解算法。CHEN等[7−9]针对三维单容器和多容器配载问题构建混合整数规划模型，考虑货物不重叠和正交放置等几何约束。HUANG等[10]将单容器三维装箱问题建模为0-1混合整数线性规划，并提出一种简单的启发式算法进行求解。Junqueira等[11−15]研究单阶段单容器配载问题，考虑产品的几何约束以及稳定性、承载强度等实际应用约束。Paquay等[14]研究航空货运中的三维多容器配载问题，构建的模型考虑了一些实际应用中的约束以及特殊形状的容器。综上所述，以往的研究主要集中于单阶段单容器、单阶段多容器配载问题，对多阶段多容器配载的研究较少；本文在三维层面上，针对使用周转箱模式下的多阶段多托盘配载问题，结合实际，考虑产品箱几何约束以及易碎性、摆放方向限制约束，以使用最少的资源装载完给定的产品箱为目标，建立2阶段混合整数线性规划模型。

1 问题描述

首先考虑使用周转箱的托盘配载过程，假设将一组尺寸不一的长方体产品箱，全部装载至托盘上。配载过程分为2个阶段，第1阶段为周转箱装箱阶段，即把产品箱全部装进给定数量且规格一致的周转箱内；装箱过程中需满足实际应用中的一些约束，包括各产品箱互不重叠、产品箱正交放置(即产品箱的物理边平行或垂直于周转箱的物理边)、周转箱装载不得超过承重限制、产品箱的易碎性和摆放方向限制；第一阶段的目标是找到最佳的装箱方案，使周转箱的利用率最大，该过程可以看作是三维装箱问题的一个变种问题[15]。第2阶段是托盘配载阶段，将第1阶段所有已使用的周转箱，装载至给定数量且规格一致的托盘上，同时考虑每个托盘的承重限制、容纳空间限制等；该阶段实质是一个一维装箱问题，旨在最小化托盘的使用数量。其次，考虑不使用周转箱的配载过程。不使用周装箱时，产品箱被直接装载到托盘上，同时考虑与上述周转箱装箱阶段类同的约束。该过程以托盘使用数量最少为目标，寻求最佳的装载方案。2种模式下的托盘配载过程如图1所示。

2 模型建立

2.1 基本假设

1) 产品箱正交装载；

2) 涉及的所有参数都是整数；

3) 忽略周转箱自身的箱体体积；

4) 给定足够数量的托盘和周转箱以供使用；

5) 产品箱、周转箱以及托盘承载空间的形状都是长方体；

6) 所有的产品箱都能装进周转箱内或托盘上，即周转箱和托盘的尺寸大于产品箱。

图1 2种模式下的托盘配载过程

2.2 符号定义

符号定义见表1~2。

表1 集合和参数定义

表2 变量定义

本文建模所用三维坐标系如图2所示，以周转箱或托盘承载空间的长、宽和高边所在直线分别为轴、轴和轴，其左−后−下角所在的点为坐标原点，各边所在的方向为正方向(左手法则)。

2.3 周转箱装箱阶段优化模型

2.3.1 目标函数

其中：表示被使用周转箱的全部可用空间，为产品箱的总体积，式(1)即表示被使用周转箱的总未利用空间最小，即空间利用率最大。

2.3.2 约束条件

1) 几何约束

2) 特定约束

此时，易碎性约束表示为式(26)~(27)，即在一个周转箱内，若产品箱是易碎的，则要保证其上方不再放置其他产品箱。

2.4 托盘配载阶段优化模型

2.4.1决策变量

2.4.2 目标函数

式(28)表示目标为最小化托盘的使用数量。

2.4.3 约束条件

式(29)保证每个周转箱都被装载且只能被装载到一个托盘上；式(30)表示每个托盘上装载周转箱的最大数量限制；式(31)表示托盘的承重量限制；式(32)给定托盘的使用索引顺序。

2.5 不使用周转箱的托盘配载优化模型

不使用周转箱的托盘配载过程与2.3中的周转箱装箱过程一致，但该模式下的目标函数为托盘使用数量最少，如式(33)所示，约束条件类同于式(2)~(22)。

3 算例及结果分析

3.1 算例

设定某厂商有24个产品箱需要装载至托盘上进行运输，配载模式可选择使用周转箱或不使用周转箱，24个产品箱有5种不同的类型，其中有14个为易碎箱，6个产品箱对摆放方向有特定要求。产品箱的具体参数如表3所示。

标准化是未来物流发展的一个必然趋势，因此本文算例中选用国家推荐标准尺寸下的托盘和周转箱(GB/T 31150，GB/T 2934)，二者的具体参数设置如表4所示。

托盘承载周转箱的平面布局如图3所示，每层可最多放置5个周转箱。在当前设置的尺寸下，托盘可放置3层周转箱，故单个托盘最多可承载15个周转箱。

3.2 结果分析

本文中所有的实验都运用ILOG CPLEX 12.8求解器进行求解，运行环境为Windows10，IntelCorei5，2.6 GHz，8 GB内存。求得2种配载模式下的结果如表5所示，其中器具利用率的计算方式为器具直接承载的物品总体积除以器具总容积。

表3 产品箱参数

表4 周转箱和托盘参数

图3 周转箱放置平面布局图

表5 2种配载模式结果统计

从表5中可以看出，使用周转箱时仅需要1个托盘即可完成装载，托盘利用率为100%，周转箱利用率为81.64%；而不使用周转箱时则需要2个托盘才能完成装载任务，托盘利用率为40.82%。这是由于周转箱可以代替部分易碎性产品箱承受来自外部的压力，使得托盘可以装载更多的易碎性产品箱，进而提高了托盘的利用率。因此，与传统模式相比，使用周转箱时的托盘利用率较高，具有一定的经济效益。

由结果可知，产品箱的易碎性是影响托盘配载效率的关键因素，因此有必要分析易碎性产品箱的数量对模型产生的影响。另外，2种配载模式下模型求解时间都相对较长，为了考量模型适用性，需要改变算例规模来进一步验证其对模型的影响。

3.2.1 易碎性约束对模型的影响

设定一组新的产品箱集合，数量为10个，使用周转箱进行托盘配载，尺寸如表6所示。在只考虑几何约束的前提下，这10个产品箱使用1个周转箱即可完成配载，且周转箱的利用率为100%。将每个产品箱的易碎性概率分别设置为10%，20%，30%和50%，每种概率下分别进行5次实验，结果如表7所示。

表6 产品箱尺寸

表7 不同易碎性概率下的实验结果

由表7可知，当产品箱易碎性概率由10%增长到50%时，使用的周转箱数量由1个增长到2个，平均求解时间由4.80 s增长到31.28 s。也就是说，随着易碎性产品箱数量的增多，完成装载任务需使用的周转箱数量可能增多，相应的平均求解时间也会增加。这是由于当使用的周转箱数量增多时，产品箱的装载方案会随之增多，因此求解时需要更多的时间来搜索可行解。

另外，即使是易碎性产品箱的数量相同，模型求解时间可能也会有差异，如表7中当易碎性概率为50%时，第1次实验完成用时43.98 s，而第3次则仅用了9.12 s。这说明模型求解时，即使易碎性产品箱数量相同，但由于各产品箱尺寸不同，构成可行解的组合规模也会不同，因此造成了计算时间的不同。

3.2.2 算例规模对模型的影响

为了说明产品箱数量对求解时间的影响，将表3中的5类产品箱组合成4个配载任务。其中，任务1需装载类型1和2中所有的产品箱；任务2需装载类型1，2和3中所有的产品箱；任务3需装载类型1，2，3和4中所有的产品箱；任务4需装载表3中所有的产品箱。即4个任务中产品箱的数量分别为10，16，20和24个。将4个配载任务分别代入2种托盘配载模型中进行计算，求解时间结果如图4所示。

图4 2种配载模式下任务1-4的求解时间

从图4中可以看出，使用周转箱的托盘配载模式比传统模式求解时间长，说明使用周转箱时可行解的数量比传统模式更多；当产品箱数量为10个时，2种模式求解时间都在1 s之内，因为计算机的性能和速度能快速迭代出最优解。同时，使用周转箱的托盘配载模式下，任务2相比任务1增加了6个产品箱，求解时间增加约5 s；而任务4仅比任务3多了4个产品箱，求解时间却增加了约6 216 s。可以看出，随着问题规模的增加，求解时间会呈指数增长，因此，可判断托盘配载问题是NP-Hard问题，模型适用于中小规模算例，但求得的最优解可作为对比样本，用于评价未来其他适用大规模实例的算法。

4 结论

1) “托盘+周转箱”的配载模式能带动供应链上下游各项配套措施的衔接流畅，在农业供应链、快消品、药品和汽车零部件等领域运输中有着越来越广泛的应用。本文针对考虑周转箱的托盘配载问题，建立2阶段托盘配载优化模型，运用ILOG CPLEX 12.8求解得出最佳的产品装载方案，并与不使用周转箱的托盘配载模式进行对比。

2) 实验结果表明，使用周转箱进行托盘配载能有效提高托盘利用率，进而能降低运输成本，提高运输效率。另外，随着易碎性产品箱数量的增加，求解时间也会相应增加。

3) 在求解过程中发现，托盘配载问题属于NP-Hard问题，求解时容易出现“组合爆炸”的情况，未来将开发能适应大规模实例且求解速度快的算法。另外，在下一步探究算法的同时，可考虑不规则形状的产品箱与装载稳定性等实际情况，为实际运输中的货物配载提出建设性方案。

[1] 张文杰, 李正军. 多尺寸塑料周转箱优化汽车零部件物流研究[J]. 物流科技, 2016, 39(3): 49−52. ZHANG Wenjie, LI Zhengjun. Research on multi-size plastic returnable container optimizes auto parts logistics[J]. Logistics Sci-Tech, 2016, 39(3): 49−52.

[2] 蔡其琛, 陈峰. 带装载组合约束的汽车出厂物流组合装箱问题的模型和分支定界算法研究[J]. 工业工程与管理, 2017, 22(6): 57−62. CAI Qichen, CHEN Feng. Research on models and algorithms of bin packing problem with patten constraints on outbound logistics[J]. Industrial Engineering and Management, 2017, 22(6): 57−62.

[3] Alonso M T, Alvarez-Valdes R, Iori M, et al. Mathematical models for multicontainer loading problems[J]. Omega, 2017, 66: 106−117.

[4] Ahn S, Park C, Yoon K. An improved best-first branch and bound algorithm for the pallet-loading problem using a staircase structure[J]. Expert Systems with Applications, 2015, 42(21): 7676−7683.

[5] 姜丽, 亓晓莹, 郭天娇. 二维矩形条带装箱问题的重构模型[J]. 武汉理工大学学报, 2017, 39(1): 85−92. JIANG Li, QI Xiaoying, GUO Tianjiao. Reconstruction model of 2D rectangular strip packing problem[J]. Journal of Wuhan University of Technology, 2017, 39(1): 85−92.

[6] 颜瑞, 朱晓宁, 张群, 等. 考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J]. 中国管理科学, 2017, 25(7): 67−77. YAN Rui, ZHU Xiaoning, ZHANG Qun, et al. Research of the model and algorithm for two-dimensional multi-depots capacitated vehicle routing problem with time window constrain[J]. Chinese Journal of Management Science, 2017, 25(7): 67−77.

[7] CHEN C S, Lee S M, SHEN Q S. An analytical model for the container loading problem[J]. European Journal of Operational Research, 1995, 80(1): 68−76.

[8] Tsai J F, LI Hanlin. A global optimization method for packing problems[J]. Engineering Optimization, 2006, 38(6): 687−700.

[9] Tsai J F, WANG Peichun, LIN Minghua. A global optimization approach for solving three-dimensional open dimension rectangular packing problems[J]. Optimization, 2014, 64(12): 2601−2618.

[10] HUANG Yaohui, Hwang F J, LU Haochun. An effective placement method for the single container loading problem[J]. Computers & Industrial Engineering, 2016(97): 212−221.

[11] Junqueira L, Morabito R, Yamashita D S. Three- dimensional container loading models with cargo stability and load bearing constraints[J]. Computers and Operations Research, 2010, 39(1): 74−85.

[12] 李孙寸, 施心陵, 张松海, 等. 基于多元优化算法的三维装箱问题的研究[J]. 自动化学报, 2018, 44(1): 106−115. LI Suncun, SHI Xinling, ZHANG Songhai, et al. Multi-variant optimization algorithm fot three dimensional container loading problem[J]. Acta Automatica Sinica, 2018, 44(1): 106−115.

[13] Lim A, MA Hong, QIU Chaoyang, et al. The single container loading problem with axle weight constraints[J]. International Journal of Production Economics, 2013, 144(1): 358−369.

[14] Paquay C, Schyns M, Limbourg S. A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application[J]. International Transactions in Operational Research, 2016, 23(1−2): 187–213.

[15] Wäscher G, Haußner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3): 1109− 1130.

(编辑 阳丽霞)

Research on optimization of pallet loading considering turnover box

CHANG Daofang, XU Zhenyu, LUO Tian, GAO Yinping

(Academy of Logistics Science and Engineering, Shanghai Maritime University, Shanghai 201306, China)

Pallet is a unitized logistics equipment invented for the cooperation with high-efficiency logistics. It is the connection point between every link in the modern supply chain. However, people cannot make full use of its advantage because the use-pattern lags behind in practical application and the improper loading scheme. This paper proposed the usage of turnover box loading mode to solve pallet loading problems. Moreover, this paper established a two-stage mixed integer linear programming model to improve the utilization rate of turnover boxes and pallets: the first stage was the turnover box packing; the second stage was the pallet loading. The validity and accuracy of the model have been verified by example analysis experiment. The results indicate that given 24 product boxes, in the pallet loading mode of using the turnover box, the pallet utilization rate is 100% and the turnover box utilization rate is 81.64%; however, without the turnover box, the rate of pallet utilization is 40.82%. Therefore, compared with the traditional model, the pallet loading mode using the turnover box can significantly improve the utilization rate of the pallet and reduce the logistics cost.

pallet loading; turnover box; three-dimensional bin packing problem; integer programming

10.19713/j.cnki.43−1423/u.2019.05.031

U169.72

A

1672 − 7029(2019)05 − 1343 − 08

2018−07−03

上海市科委科研资助项目(16040501500，17595810300)

苌道方(1978−)，男，河南封丘人，教授，博士，从事供应链设计与运营、物流系统运作与优化等研究；E−mail：dfchang@shmtu.edu.cn