陆 华 赵 琨

(北京物资学院物流学院 北京 101149)

基于复杂约束的多个集装箱配载优化问题研究

陆 华 赵 琨

(北京物资学院物流学院 北京 101149)

根据集装箱配载问题中现实存在的多个制约因素，构建了多个集装箱配载优化模型.为寻求最优解，设计了以预分配策略为原则的遗传算法和启发式算法交互进行的混合算法.通过算例验证和比较得出，该模型算法在满足集装箱重心要求、下层货物额定承重能力，以及货物混装限制等约束条件下，可得到较高集装箱容积利用率的配载方案.

多个集装箱配载；遗传算法；启发式算法；复杂约束

0 引 言

集装箱配载效率是集装箱多式联运运行的一个重要指标，是指将典型形状的货物(通常为长方体或立方体，例如，各种纸箱)如何在集装箱内部摆列实现空间利用优化的问题，也就是探寻如何优化立体货物在集装箱内部的摆放布置，实现将所有货物配载完毕后，所使用的集装箱数量最少.

配载问题根据需配装的集装箱数目的多少可以划分为单个集装箱和多个集装箱配载问题.单箱布局优化方法有启发式方法、数学规划、图论法、遗传算法、模拟退火法等方法.George 等[1]利用构造型启发式算法来研究集装箱配载问题，首次提出“层”的概念.Pisinger[2]也根据“层”的概念提出了一种启发式算法，将集装箱内部空间划分成几个垂直的列，然后将列分成几个水平的层，合适的列宽和层深利用分支定界法得到，这种设计的配装方式可以获得较高的集装箱利用率，然而货物稳定性却较低，往往上层货物得不到下层货物的全面支撑.Loe等[3]对装载的货物以“层”的状态出现，也就是从下至上实现装箱工作，为了达到平坦的“层”面，该算法根据适箱货物的高度设立装载的优先级别.姜义东等[4]采用三叉树的数据结构来构思集装箱内部空间布局的优化算法，其将体积大的货物给予优先级，依次放入集装箱，这样处理空间导致产生较为零碎的狭长部分，降低空间利用率，但算法较为简单减少复杂性.

针对集装箱多箱配装问题，Bortfeklt[5]论述了多种形状货物组合的连续性配装设计，但采用该设计常常导致体积大的物品留在最后放置，因而集装箱内部空间利用率较低.Eley[6]设计了多个集装箱同时装载方案，利用单箱装载方案解决多箱装载问题，该算法在强异类货物的装载问题得到较大改善，得到较高的集装箱内部空间利用率，在货物装载稳定性上不错.Terno等[7]采用预分配原则，在分支定界概念和启发式方法的基础上进行优化，首先采用贪婪算法得到初始解，之后逐步迭代优化.

文中将启发式算法和预分配原则的遗传算法相结合，设计一种2种算法交互进行的算法，该算法加入了现实装载中应考虑的下层货物承载能力、集装箱重心配置和不同货物混装问题.根据数值测试表明，该算法较好的解决了实际中问题，获得较好的集装箱内部空间利用率.

1 集装箱配载模型及求解算法

1.1 研究对象及约束条件

文中的研究对象是多箱配装问题，以国际标准集装箱为配装箱型，将已经界定的不同种类和不同大小的货物装入多个集装箱，通过算法设计货物的配载优化布局，使得在满足多项约束条件的前提下，使用最少的集装箱数量.

在实际的集装箱配载中，需要考虑约束条件如下：(1)在实际的装箱操作中，很多货物不能倒置，本算法要求货物不能倒置；(2)单件货物的体积不能超过集装箱的界限限制；(3)装入货物的总重量小于或等于集装箱的额定载重量；(4)货物装载必须有足够的支撑，不能悬空，必须放在其他货物的上方；(5)为了确保装卸过程的稳定性，要求配装完毕后的集装箱重心在合理的范围内；(6)考虑不同货物不能混装的问题，本算法设计了配装隔离约束，也就是限制货物的混装，例如，不同化学用品不能混装；(7)每件货物都有一定的承重能力，因此，需要考虑货物承重能力的约束，也就是上层货物的总质量不能超过下层货物的承重能力.

1.2 假设条件

由于实际问题非常复杂，为了避免不必要的复杂性，文中做出以下假设：(1)所装货物都是长方体或立方体；(2)货物的重心和其他几个中心一致；(3)货物中途不会出现掏箱问题；(4)货物装载过程中不会出现变形.

2 构建模型

2.1 符号说明

将货物和集装箱放置于笛卡尔三维坐标系中，坐标系中X轴正向方向为集装箱的长度方向，Y轴正向方向为集装箱的宽度方向，Z轴正向方向为集装箱的高度方向，集装箱左后角位于坐标系的原点上(0,0,0)见图1.

图1 集装箱坐标示意图

2.2 目标函数与现实约束条件

优化目标为最小化集装箱的使用数量，则目标函数可以表示为

(1)

约束条件：

∀i=1,2,…,n

(2)

(3)

式中：

spj=[(xbj-xaj+xbp-xap)-

(max{xbp,xaj}-min{xap,xaj})]×

[(ybj-yaj+ybp-yap)-(max{ybp,ybj}-

min{yap,yaj})]

(4)

xlp≤xlj,xbp≥xbj,yap≤yaj,

max{xbp,xbj}-min{xap,xaj}<

xbj-xaj+xbp-xap,

max{ybp,ybj}-min{yap,ybj}<

ybj-yaj+ybp-yap}

(5)

i=1,2,…,N}

(6)

[(xbj-xaj)-lj][(ybj-yaj)-wj]=0,

∀j∈{Xij=1,i=1,2,…,N}

(7)

minxaj≥0;minyaj≥0;minzaj≥0,

(8)

maxxbj≥0;maxybj≥0;maxzbj≥0,

(9)

(10)

XjkXik(1-rij)=0,

∀k∈1,2,…,N;∀j∈1,2,…,n

(11)

∀i∈1,2,…,N

(12)

∀i∈1,2,…,N

(13)

∀i∈1,2,…,N

(14)

∀j=1,2,…,n

(15)

式中：

yai≥ya2,xbi≤xbj,ybi≤ybj}

(16)

min{xaq,xaj}

max{ybq,ybj}-min{yaq,yaj}

ybq-yaq},∀k∈1,2,…,N

(17)

上述模型中，式(2)为货物都务必全部装入到集装箱；式(4)为箱内上下两层相邻货物之间的重合面积；式(5)为箱内上下两层相邻货物重合情况由完全重合和部分重合组成；式(3)～(5)组合为货物必须完全放在下一层货物的上面，不存在悬空放置的情况；式(6)为所有货物不能上下颠倒放置；式(7)为货物的放置与集装箱内部长度或宽度方向垂直或平行；式(8)～(9)为全部货物的体积小于或等于集装箱内部容积界限；式(10)为箱内货物总重小于或等于集装箱额定载重量；式(11)为不能混装的货物不能装载在一起，需要满足货物隔离限制；式(12)～(14)为装载完毕后集装箱的重心位置应在要求范围内；式(15)为集装箱内上下两层相邻货物的由完全重合和部分重合两种形式构成；式(16)～(17)为上下货物中，上层所有货物总重不能超过下层货物所能承受的最大重量.

3 混合算法设计

由于该问题实际约束较为复杂，文中结合采用遗传算法预启发式算法相结合交互式的混合算法.首先，利用遗传算法具有全局搜索能力做出集装箱配载的预分配，再使用启发式算法进行迭代，产生不同的集装箱配载方案，2个算法交替进行优化.算法设计流程见图2.

图2 遗传算法预启发式算法的交互设计流程图

该算法结合了遗传算法和启发式算法的优点，算法效率较高，可以实现较高的集装箱内部空间利用率，同时还考虑在装卸过程中集装箱的重心要求、避免货物承受过重载荷造成货损以及不同货物不能混载的要求.算法主要参数取值如下：遗传算法群体规模数为50，最大迭代代数为350，变异操作次数取100，交叉概率为0.95，变异概率为0.01.

4 算法评价

4.1 与现行研究的比较

为了对设计的遗传和启发式结合的混合式算法进行检验，文中采用OR-LIBRARY的基准测试问题来评判[8].标准算例借鉴Bischoff等[9-10]所采用的算例，共7大类，每一类有50个算例.所用集装箱为20 ft国际标准集装箱，尺寸为5.898 m×2.352 m×2.385 m.文中采用目前取得较好效果的Elay的2种算法，用EL1和EL2表示，文中设计算法用YQ表示.

现有的研究资料表明，目前对于集装箱内装载优化问题主要考虑集装箱内容积限制，对于集装箱内部货物承重限额、集装箱吊装重心要求缺乏考虑.文中设计的优化模型的优点在于，不仅考虑货物的体积，还考虑货物在集装箱内的承重限额、货物混载限制及重心稳性要求等约束条件.

关于启发式-变异算法的参数比较结果见表1～2.

表1 交互式混合算法与目前应用算法的结果比较(所需集装箱个数)

算例序号EL1EL2YQSL(3)302305302SL(6)305307303SL(7)301302301SL(9)303304303算例序号EL1EL2YQSL(11)301303301SL(14)300302301SL(19)305307304合计211721302115

注释：括号()内的数字是该算例中货物的种类数目

由表1的7个算例可知，文中算法YQ和算法EL2相比，使用集装箱数量较少，YQ与算法EL1相比，不多于EL1所使用的集装箱数量.由表2可知，YQ的前5个集装箱容积平均利用率比EL1更加平均，并且对7个算例总体来看，YQ的集装箱内部容积利用率的平均值均大于算法EL1，表明文中设计算法在充分利用集装箱内部容积上取得较好的效果.

表2 文中设计算法(YQ)与算法EL1的集装箱配载容积利用率比较

4.2 2种分配原则的比较

由于根据目前研究资料缺乏对货物承载限额、货物混装限制及集装箱重心位置要求的研究，因此无法做出这方面的比较.目前较为常用的连续性分配策略，而文中采用遗传算法进行货物装载的预分配策略，因此，对不同分配策略进行比较，结果见表3.由表3可知，预分配策略的集装箱内容容积利用率(91.60%)略高于连续性策略取得结果(91.00%).主要原因在于，采用遗传算法进行预分配，而遗传算法具有全局搜索优化能力；其次是启发式算法与遗传式算法的交互进行，也就是将单个集装箱配载的结果与多个集装箱配载的结果进行再次平衡优化.

表3 连续分配原则与预分配原则的集装箱利用率 %

5 结 束 语

研究了在实际复杂的约束限制下，多个集装箱内部配载优化问题，对集装箱重心要求、下层货物承重能力、不同货物混载限制等多个实际因素进行考虑，构建了多个集装箱配载的混合整数规划模型，在模型算法上设计了预分配原则，将遗传算法和启发式算法相结合进行交互式计算的混合算法.通过算例测试，与目前流行算法相比，文中算法取得了较好的集装箱配载效果，使的集装箱容积平均利用率较高，使用集装箱数量较少.不足之处，在于没有考虑其他典型形状的货物，例如卷盘状，桶装货物和托盘等货物，以及中途掏箱的情况也未考虑.

[1]GEORGE J A, ROBINSON D F. A heuristic for packing boxes into a container[J]. Computer and Operational Research,1980(7):147-156.

[2]PISINGER D. Heuristics for the container loading problem[J]. European Journal of Operational Research,2002,141:382-92.

[3]lOE T H, NEE A Y C. A packing algorithm for hexahedral boxes[C]. Proceeding of the Conference of Industrial Automation, Singapore,1992:115-126.

[4]姜义东，查建中，何大勇.集装箱装载矩形货物的布局研究[J].铁道学报，2000,22(6):13-18.

[5]BORTFELDT A. Heuristik fuer multiple container lade probleme[J]. Or Spektrum,2000,22(2):239-262.

[6]ELEY M. Solving container loading problems by block arrangement[J]. European Journal of Operational Research,2002,141:393-409.

[7]TERNO J, SCHEITHAUER G, SOMMERWEIU U, et al. An efficient approach for the multi-pallet loading problem[J]. European Journal of Operational Research,2000,123:372-381

[8]BEASLEY J E. OR-library: distributing test problems by electronic mail[J]. Journal of Operation Research Society,1990,41(11):1069-1072.

[9]BISCHOFF E E, RATCLI M S W. Issues in the development of approaches to container loading[J]. Omega,1995,23(4):377-390.

[10]JIN Z H, ITO T, OHNO K. The threo-dimensional bin packing problem and its practical algorithm[J]. International Journal of Japan Society of Mechanical Engineers,2003,46(1):60-66.

Optimization of the Multi-containers Loading Problems Based on Complex Constraints

LU Hua ZHAO Kun

(LogisticsSchool,BeijingWuziUniversity,Beijing101149,China)

According to the multiple constraints existing in the actual container loading problem, the paper establishes multiple containers loading optimization of mixed integer programming model. In order to obtain the optimal solution, the paper designs a hybrid algorithm based on genetic algorithm and heuristic algorithm, which is based on the principle of pre-allocation strategy. Through the example verification and comparison, the model algorithm satisfies the constraints, the focus of container goods and mixed goods bearing capacity constraints, can obtain higher utilization ratio of the volume of container stowage solution.

multiple containers loading; genetic algorithm; heuristic algorithm; complex constraints

2016-11-03

U169

10.3963/j.issn.2095-3844.2016.06.023

陆华(1977—):女，博士，主要研究领域为运输与物流