求解货物在线装箱问题的融合算法

张长勇, 刘佳瑜, 王艳芳

(中国民航大学电子信息与自动化学院，天津 300300)

集装箱在运输过程中以其独特的优越性，使得在物流运输和装载环节实现快速和高效作业，从根本上改变了传统运输方式的落后面貌，对于经济社会的发展具有不可忽略的重要作用。目前邮包、快件等异构型货物的集装箱装载仍采用人工方式，装载货物过程不仅劳动强度大、效率低，还会导致货物损坏、实际装载效果差等问题。因此研究强异构型货物的在线装箱优化问题，进而实现货物的自动码放，对于提高集装箱容积利用率，减少作业人员数量，提高运输行业经济效益具有重要意义。

货物的装箱优化问题属于典型的装箱问题。根据是否已知货物信息可以将装箱问题分为在线装箱问题和离线装箱问题两种。在线装箱算法在未知待码放货物相关信息并且需要在货物到来时实时计算出货物装箱方案的一种码放算法。目前在线装箱问题中研究集中在一维和二维装箱问题上。黄海等[1]提出绑定配对策略来解决未装满箱体数量问题，针对如何启动新箱体采用了间隔函数来实现；张明会等[2]对货物进行预处理实现将对应货物装载进入相对应集装箱中，获得了1.423 6渐近竞争比；赵晓凡[3]为改进整体装箱率，采取只开两个箱子的策略，其中一个装体积小货物，一个装载大小体积的混合货物；肖教燎等[4]提出一种非矩形改进A形在线装箱问题，其中只考虑货物高度和半径两个因素；陈建新[5]改进NF算法并提出最后物件置换算法和每个物件置换算法两种具有置换功能的算法；Angelopoulos等[6]通过提出简单和复杂两种算法，从而对在线算法已知上下限进行了改进；Song等[7]通过研究CPU性能，将优化主动使用服务器数量这个问题抽象成为在线装箱问题，并且针对在线装箱算法进行设计，实现与结果评估；Steven等[8]提出并验证Harmonic+1的渐近性能比至少是1.592 17。

很多学者采用元启发式算法来提高算法性能及优化装载效果。于明正等[9]提出双层遗传算法实现算法在广度和深度上的搜索，提高装载率的同时保证码放稳定性；刘胜等[10]提出基于“箱子-片-条-层-实体”多层树搜索算法满足了摆放方向约束和完全支撑约束；何庆等[11]考虑多种实际约束提出将改进遗传与模拟退火算法结合建立并求解装载模型；Brouer等[12]以班轮运输为研究背景，对搜索算法进行设计与优化。代爱民[13]提出在半在线基础上的改进遗传算法。

目前中外学者对于一维货物在线装箱问题研究较多，而对于三维在线装箱问题的研究偏少，且大多三维在线装箱问题的研究并未考虑到实际的工程环境。为此在前人研究的基础上，考虑异构型货物集装箱装载过程中存在的一些实际约束，建立以集装箱空间利用率为优化目标的数学模型，结合模拟退火算法优越的局部搜索能力以及算法可操作性强的特点，提出在线极值点(online improved extreme point,IE)算法与模拟退火(simulated annealing,SA)算法相结合的在线融合(IES)算法，实现异构型货物的在线装箱优化，并利用机场运行的自助行李托运系统采集的货物数据验证算法的有效性。

1 问题描述

将货物和集装箱约束为三维长方体质量块，因此该模型简化成为：规定集装箱尺寸为W、H、D，货物序列是长、宽、高为wi、hi、di，要求将实时到来货物进行顺序装载，使得集装箱在满足实际约束条件下求得最大空间利用率。

1.1 约束条件

研究模型是强异构在线装箱模型，任意两件货物质量和尺寸均不相同。在实际在线装箱过程中，需要考虑以下多种现实条件约束。

(1)体积和质量约束，货物总体积以及总质量不得超过集装箱所能容纳最大容积和最大承载力。

(2)货物姿态约束，考虑到货物放置稳定性在放置时将底面积较大一面平行于地面放置，货物边和面只可与集装箱底面水平或者正交放置。

(3)货物重叠约束，垛形中任意两件货物不能相互重叠嵌入。

(4)货物装载次序约束，在线装箱考虑货物到来次序，不能允许跳过。

1.2 条件假设

在实际在线装箱环境中存在许多复杂现实问题，因此假设条件提出能够降低问题复杂性，从而简化数学模型，本文假设条件主要围绕以下几点：

(1)假设货物均为规则长方体块。

(2)假设目地为单一目地，无中转。

(3)货物重心在其几何中心上。

镇机关干部职工六十多人，班子成员和副科级以上就有十九个，宿舍楼只有二十四套。在当时，能不能入住是身份地位的象征，年龄、工龄、任职年限是分房（包括选择楼层、朝向）的依据。尽管只有五套分给中层干部，但接下来还有平房的重新分配，还有享受福利分房的“半边户”（配偶是农村户口）工作人员。尽管是平房，进门就是客厅，也是水泥地面白灰墙，还有防蚊子苍蝇的纱门纱窗，顶上钉着天花板，打架的老鼠掉不下来，屋后过道设有专门的厨房。这在当时是从单一的“宿舍”朝舒适、方便居住的生活理念的一个巨大转变。住房就像是贴在机关大门口的布告昭然若揭，一看就能分别出三六九等。

(4)不同货物交错叠放时要求下层货物承载能力优于上层货物，以此保证下层货物不被损坏。

(5)货物本身挤压变形忽略不计。

1.3 模型建立

图1为货物码放效果图，以集装箱左后下角为原点，底面为XY平面，垂直底面向上为Z轴建立坐标系。

i(i∈1,2,…,n)为货物序号；mi、vi依次为第i号货物质量、体积；M、V为集装箱承载能力、容积；(xi,yi,zi)为第i号货物在集装箱中左、后、下角角点坐标；为第i号货物在集装箱中右、前、上角端点坐标图1 货物码放效果图Fig.1 Effect of cargo coding

为在集装箱内最大化货物装载数量以此达到集装箱空间利用率最大，设目标函数为

(1)

(2)

(3)

y′-y=h

(4)

(5)

p≠q

(6)

(7)

(8)

(9)

式(2)、式(3)为集装箱容积和质量约束，要求货物总体积与总质量小于集装箱最大体积，最大承载能力；式(4)、式(5)为货物姿态约束，式(4)表示只允许以货物高度进行旋转，式(5)表示货物只能保持与集装箱方向水平或者正交；式(6)～式(8)表示货物重叠约束，为了保持稳定性，任意两个货物(p、q)之间不可重叠放置；式(9)表示考虑到货物到来顺序与装载顺序约束，要求实时码放到来货物，不可发生顺序上跳跃。

2 算法设计

2.1 IE算法提出与优化

在二维、三维状态下“角点”示意图如图2所示。角点就是指可供下一件货物左、后、下角放置点。此处首个角点为坐标原点(0,0,0)，在三维装箱中，角点可以概括为在当前垛形外侧包络面内具有阶梯化形态两件货物横、纵交叉点，在实际过程中要剔除虚假角点(x,y相同时z较大点)。

图2 角点示意图Fig.2 Corner point diagram

IE在线码放算法是通过离线装箱极值点算法[14]来改进得到，通过角点序列的实时更新来寻找下一个货物码放的空间坐标。采用角点序列首角点匹配思想形成集装箱自左向右阶梯状布局在线码放形式。首先建立x-y二维坐标系并得到二维角点，其次构建三维坐标系，即在二维坐标系的基础上增加z坐标轴，使它从0开始以整数递增，递增每个整数成为层，在遍历所有三维坐标后完成三维角点的确定，完成到来货物码放之后更新存储所有可放置角点序列等待下件货物到来。

在线装箱需要对实时到来每一件货物规划一个合理位置，最大化集装箱装载率相比时间快速性更为重要，为找到每件货物最佳放置点，设置多条规则并赋予权重，规则权重比如表1所示。表1中，角点坐标为(x,y,z)，N0为角点总个数，ni为按照规则i在角点总数中排序序号。规则1保证货物按轴优先级码放，规则2、规则3为提高集装箱容积利用率，最大化旁空间利用率；规则4针对码放垛形稳定性，使得整个垛形中心向中下位置靠近；在多次实验之后根据各个规则对最终装载效果影响大小设置权重依次为0.4、0.2、0.2、0.2。在设置各种规则权重之后写出具体优化算法流程如图4所示。

图4 优化算法流程Fig.4 Optimization algorithm flow

按照表1中规则，设置优化函数为F，每个放置角点对应一个优化值，并按照降序排列优化值f，以此来更新角点序列。为了防止出现过拟合现象，加入较小随机数γ来保证规则合理性。表1规则可以简化为

表1 规则及其权重设定Table 1 Rules and weight settings

(10)

2.2 融合算法设计

货物在线码放过程中所提出优化算法易于陷入局部最优循环，而且由于集装箱空间受限，要求其数据量保持在100以内，因此在优化算法中增加模拟退火算法[15]来增加算法快速性并且寻求全局最优解，通过增加降温过程时间来保证解稳定性。

模拟退火过程中邻域选取是影响最终结果的关键部分，在实验中，其一邻域是优化值小范围更新，其二邻域是交换货物两种码放姿态。两种邻域的不同都会影响到模拟退火最终结果，在计算过程中，上述提到两种邻域被等概率选取。如图5所示即为融合算法具体流程图。其中，用c来表示角点序列，优化值用f表示，每个角点对应着唯一f，c序列首个角点为待码放货物角点坐标，最佳角点序列用cbest表示，初始温度为tS，终止温度为tE，当前温度用t表示，当前角点序列中首角点剩余空间容积为Vb，最佳角点序列中首角点最大剩余空间为Vb,best，初始邻域为L，当前邻域长度为Lt。

图5 融合算法流程图Fig.5 Flow chart of fusion algorithm

3 实例计算与结果分析

为测试上述提出的IES算法的性能，从某机场自助行李托运系统实际采集获取的真实货物数据进行验证。从大量数据中随机选取的100件货物信息作为实验数据，对算法的最终装载布局进行验证。部分货物数据在表2中列出。

表2 待码放货物信息表Table 2 Cargo information to be coded

此处使用三维在线码放问题，需要考虑很多实际约束，且针对的是实际装载中航空货物数据，所以通过比较两种分配方案，即IE和IES算法所产生整体布局方案，采用MATLAB编程将布局方案可视化，更为直观地比较算法整体布局效果。用码放平台去直观地展示在线码放每件货物过程，手动输入待码放货物信息，点击确认按钮之后，进行在线码放。第40、41件货物码放结果位置布局效果图如图6 所示，码放货物之后得出最终整体布局图，IE和IES货物布局情况如图7所示，IES算法使货物分配更合理紧凑，集装箱容积率更大。

图6 码放第40件和第41件货物效果图Fig.6 The effect of stacking the 40th and 41st cargo

图7 IE和IES整体布局图Fig.7 IE and IES overall layout

为进一步验证算法的码放效果，采用两种算法分别对5组货物进行在线装箱规划，得到的实验数据如表3所示。采用IE算法平均码放货物55件，而采用IES算法平均码放货物61件。IES的平均容积率达到89.17%，相比IE算法提高了10.34%，且IES集装箱利用率更加均衡。究其原因，IES中加入了规则权重对算法进行优化，并且结合模拟退火算法使得算法局部以及全局寻优能力提升，在较短时间内能够快速找到最优解。

表3 两种算法容积率对比Table 3 Comparison of floor area ratio of two algorithms

4 结论

(1) 在考虑实际装载过程中的现实约束下，提出了一种适用于货物装箱的在线融合算法，通过设置码放规则以及优化函数来最大化地实现集装箱容积率，为货物的在线装载问题提供了有效的解决办法。

(2)在IE算法的基础上增加了模拟退火算法避免算法出现局部最优的情况，更好地寻求全局最优解，进一步提高装载优化效果，为在线装载决策提供理论基础。

(3)采集机场自助行李托运系统实际获取的真实货物数据进行实验验证，证明所提算法对强异构货物有着较好的适应性与有效性。采用MATLAB软件中的GUI界面实现货物的可视化装载，提高三维装箱算法的工程性。