铁路同类适盘货物装载方案优化研究

秦鉴

(中铁第一勘察设计院集团有限公司，陕西 西安 710043)



【交通运输】

铁路同类适盘货物装载方案优化研究

秦鉴

(中铁第一勘察设计院集团有限公司，陕西 西安 710043)

结合铁路货物装载约束条件，构建了使用托盘的同类长方体货物铁路货车装载优化模型，首先提出了改进二维布局优化算法求解托盘在车厢底面的布局方式，再确定托盘货件在车厢内的最佳堆码层数，得到货物的装车优化方案。实例分析结果表明，该算法是一种求解铁路同类适盘货物装载问题的有效方法。

铁路运输；适盘货物；装载方案；优化

托盘运输是铁路集装化运输的重要内容，良好的货物装载方案会给铁路集装化运输带来更大的经济效益。托盘装载货物和货车装载托盘集装件均属于三维装箱问题的研究范畴，不同的是托盘一般没有侧面支撑保护，装载时需要更加注意货物堆码的稳定性。现有的三维装箱算法都是基于一定的假设进行的，这些算法在条件复杂的实际应用中会受到很大的限制。

解决三维装箱问题主要有基于启发式算法和遗传算法两类比较有代表性的方法。George等[1]首次提出了三维装箱问题的启发式算法，并引入了“层”的概念。Bischoff等[2]对多种基于“层”的算法进行了总结和比较，得出货物的种类数影响装箱结果的好坏的结论。Pisinger[3]在墙壁支撑的理论基础上提出了一种新的基于“层”的启发式算法，该算法虽然提高了装载效率，但是有时候上层货物没有足够的支撑面，货物整体结构的稳定性较差。Eley[4]提出了基于同类货物块的启发式算法，该算法的思想是首先将相同的货物组成货物块，再通过货物块组合得到完整的布局方案。刘胜等[5]提出了求解三维装箱问题的启发式正交二叉树搜索算法。张德富等[6]提出了一种求解三维装箱问题的多层启发式搜索算法。那日萨等[7]提出了一种基于“块”和“空间”的启发式搜索算法。Gehring等[8]首次将遗传算法应用到了三维装箱问题的求解当中，为后来遗传算法求解装箱问题奠定了理论基础。孙洪礼等[9]提出了基于空间分解的包含启发式规则的混合遗传算法，对弱异类货物装箱方案进行求解，启发式规则应用在遗传算法的解码过程中。朱向等[10]针对带重心平衡约束的三维装箱问题，基于框架式布局思想，设计双层混合遗传算法进行求解。陈泽爽等[11]提出了多约束三维装箱问题的混合遗传算法。Kucuk等[12]利用混合进化算法求解三维装箱问题，并实现了货物在集装箱内的可视化。孟唯娟[13]对同类货物的托盘装箱问题进行了研究，并利用VC6.0开发工具设计托盘装载优化软件。

适盘货物装车问题涉及货物在托盘上堆码和托盘集装件在货车车厢内堆码两个过程，需要综合考虑两个阶段的装载方案，比一般的同类物品三维装箱问题更加复杂，需要考虑更多的约束条件。目前，国内对铁路适盘货物装车问题的研究相对较少，缺乏成熟的算法和相应的商业软件。本文结合铁路货运中的实际约束条件，构建了同类长方体适盘货物的装车优化模型，并给出了相应的求解算法，为下一步铁路集装化装载软件的开发提供理论基础。

1 问题描述

同类长方体适盘货物铁路货车装载优化问题可以描述为：将一批数量较大的相同品类的长方体货物装载到托盘上，并将托盘集装件装车，在满足铁路货物装车约束条件下，货车载货数量最多或者载货空间利用率最大。

鉴于装载问题的复杂性，本文对该问题做出以下假设：

(1)所有货物或者货物包装均为长方体，并且具有相同的尺寸与重量；

(2)托盘和铁路货车都简化为长方体；

(3)货物或者货物包装有侧面和底面的区分，只有底面可以作为支撑面；

(4)托盘集装件放置方向与货车车厢面平行或者正交；

(5)忽略货物间的挤压变形对装载的影响；

(6)长方体货物为均质货物，重心在其几何中心；

(7)货物属于同一货主，并且到达同一目的地。

2 数学模型

2.1 目标函数

该问题是一个多变量组合优化问题，优化目标定义为：在满足铁路货物装车约束条件下，货车载货数量最多或者载货空间利用率最大。货车载货总数量与货物在托盘上的布局、托盘集装件在货车车厢内的布局、托盘集装件在车厢内的堆码层数和货物在托盘上的堆码层数有关。选择货车载货数量最大和载货空间利用率最大为优化目标的目标函数可分别表示为：

(1)

(2)

2.2 约束条件

该问题考虑的约束条件及其描述见表1。

表1 模型约束条件及描述Table 1 Model constraint conditions and description

3 算法设计

适盘货物装车问题需要确定货物在托盘上的堆码层数、托盘集装件在车厢内的堆码层数、货物在托盘平面的布局方案和托盘集装件在车厢底面的布局方案。托盘和货物最佳堆码层数与车厢高度、重车重心高、托盘货件重心高以及货车和托盘最大载重量等诸多因素有关，在设计算法时应对影响因素进行划分，分阶段进行求解。货物在托盘平面和托盘集装件在车厢底面的布局方案则利用改进的二维局部优化算法求解。

图1 货车车厢装载托盘集装件剖面图Fig.1 Section diagram of pallet racking loaded boxcar

3.1 货物和托盘堆码层数的确定

货车车厢堆码托盘集装件示意图如图1所示，当车厢高度、托盘高度和货物高度一定时，在不考虑其他装车约束条件的情况下，货物的最大堆码层数和托盘堆码层数有关，当确定托盘堆码层数之后，货物的最大堆码层数也就确定了。在车厢高度内，托盘堆码层数越多，货物可利用堆码高度就越小，所以减少托盘堆码层数有机会增加货物堆码层数。

但是托盘有最大承载能力约束和重心高约束，货车有最大载重量约束和重车重心高约束，货物有最大抗压强度的约束，这些约束条件影响着货物实际最大堆码层数，货物在托盘上的最佳堆码层数由这些约束条件综合决定。

假设车厢内堆码t(t≥1)层托盘，T表示车厢最大允许堆码托盘货件层数，首先考虑托盘的重心高约束和车厢高度约束，计算出货物在托盘上的初始堆码方案，再检验是否满足托盘最大载重量、货车最大载重量、重车重心高和货物最大堆码强度等约束条件，如不满足，调整货物堆码层数，从上往下逐层减少，直到满足约束条件为止。同理可计算出t=1,2,…，T时的货物堆码层数方案，选择货车载货数量最多的方案作为最佳方案；当货车载货数量相同时，选择使用托盘数量最少的方案作为最佳方案。算法流程详见图2。

图2 货物装载层数确定算法流程图Fig.2 Flowchart of determination algorithm of goods loading layers

3.2 货物和托盘二维布局方案的确定

货物在托盘底面放置时应尽可能地铺满托盘底面，使得托盘底面积利用率最大；托盘集装件也需要尽可能地铺满货车底面。这就是矩形的二维布局优化问题：在一个已知长和宽的大矩形中尽可能地摆放已知长和宽的相同的小矩形，确定一种摆放方案使得平面利用率最大。假设大矩形的长和宽分别为L和W，小矩形的长和宽分别为l和w，大矩形中摆放的小矩形数量为n，S为平面利用率，则该问题的目标函数可以表示为：

(3)

矩形的二维布局优化算法较多，文献[14]中提出了一种比较简洁有效的二维布局结构图，该结构图将矩形平面分成了4块进行布局，本文将这4块分别称为block1、block2、block3和block4，如图3所示。该算法将图中的a、b、d作为基础变量，从小到大进行变化，通过各块之间的结构关系计算图中其他参数值。当a、b、d的值确定以后，其他参数c、e、f、g、h的值都可以相应地计算出来，这样就可以确定整个平面的布局。

图3 文献中的二维布局结构示意图Fig.3 Illustration of two-dimensional layout structure in the literature

本文对WANG等[14]文献中的二维布局结构图进行改进，将a、b、d、e同时作为基础变量进行变化，e不再是通过关系式直接计算出来的静态值，这样扩大了二维布局问题解的空间。根据block1和block2的宽度的不同，布局结构分为两种情况：

(1)当block1的宽度小于block2的宽度时，e从⎣cw/l」到⎣L/l」进行变化。当el≤cw时，g的取值为⎣(L-cw)/w」；当el>cw时，g的取值为⎣(L-el)/w」，二维布局结构图如图4a所示。

(2)当block1的宽度大于block2的宽度时，e从0到⎣cw/l」进行变化，g的取值为⎣(L-el)/w」，二维布局结构图如图4b所示。

图4 改进的二维布局结构图Fig.4 Structure chart of improved two-dimensional layout

在改进的二维布局结构图中，矩形块block1和block4紧贴大矩形的左侧边线摆放，block2和block3则紧贴大矩形的右侧边线摆放。在参数e变化过程中，大矩形中间可能会出现矩形块block5，对于block5继续利用本算法求解布局结构，形成循环嵌套，得到最终的布局结构。为方便描述，对算法中的符号定义见表2。

表2 算法相关参数定义Table 2 Relevant parameter definition of the algorithm

改进的二维布局优化算法流程伪代码如下：

ReadL，W，l，wamax←int(L/l);bmax←int(W/w);nlast←amax*bmax;ForbFrom0tobmaxstep1h←int((W-b*w)/l);ForaFrom0toamaxstep1c←int((L-a*l)/w);FordFrom0toint(W/l)step1f←int((W-d*l)/w);Ifd*lnlastThennlast←n0;记录二维布局参数;ElseForeFromint(c*w/l)toint(L/l)step1Ifc*w>e*lTheng←int((L-c*w)/w);Elseg←int((L-e*l)/w);n1←a*b+c*d+e*f+g*h;计算L'和W';ReadL'，W'计算n2;n0←n1+n2;Ifn0>nlastThennlast←n0;记录二维布局参数;

在改进的二维布局优化算法中，当e=⎣cw/l」，并且gw≤al时，该算法的计算结果与文献[14]相同。所以，本文提出的改进的二维布局优化算法是对文献[14]中算法的一种扩展。

4 实例分析

周康等[15]提出了规则货物包装的托盘装载优化方案，并进行了实例计算。本文利用C#编程语言实现了同类直方体货物托盘装载优化算法，并与文献中结果比较，验证算法的有效性。

实例描述为：某品牌方便面，外包装尺寸为580 mm×325 mm×330 mm，重量为6 kg；托盘规格为1 200 mm×1 000 mm×150 mm，重量为15 kg；货车车型为P64，尺寸为15 500 mm×2 796 mm×2 705 mm，自重25.4 t，载重58 t，空车重心高为1 310 mm，地板面至轨面高为1 143 mm，转向架中心距为11 700 mm，容积为116 m3，设计货物的装载方案。

利用本文提出的装载算法求得的装载信息见表3，托盘装载货物的二维布局图见图5；货车装载托盘集装件二维俯视图见图6，侧视图见图7。

表3 装载计算结果信息表Table 3 Information table of loading calculation result

图6 货车装载托盘货件俯视图Fig.6 Top view of pallet loaded boxcar

图7 货车装载托盘货件侧视图Fig.7 Side view of pallet loaded boxcar

文献[15]在未考虑货物装车后重心横、纵向合理位置和重车重心等约束条件下，计算出货车最多装载货物1 080件，比本文算法的计算结果少180件，表明了本文算法在计算同类直方体货物的装载方案时能得到更优结果。同时，本文提出的装载算法具有一般性，能够很好地处理非标准尺寸包装件的装载问题，并且在计算过程中考虑了货物重心位置等约束条件，保证了装载方案的可行性。

5 结语

本文讨论了同类直方体适盘货物的装车优化问题，结合铁路货运实际约束条件，综合考虑货物在托盘上堆码和托盘集装件在车厢内堆码两个过程设计装载优化算法。在模型约束条件方面，除了本文所考虑的约束条件外，还包括其他实际运输中的约束，比如货物属于不同的货主、到达不同的目的地、有不同的卸货顺序、中途取货、使用不同类型托盘混装以及避免货车车辆集重装载等；同时，适盘货物除了包装规则的直方体货物，还会涉及到一些非规则包装的货物，装载时有时也会有货物拼装的情况。这些问题的装载优化算法有待于今后进一步研究，然后集成开发铁路托盘集装装载软件，并进行三维显示。

[1]GEORGE J A, ROBINSON D F. A heuristic for packing boxes into a container[J]. Computers & Operations Research, 1980, 7(3): 147-156.

[2]BISCHOFF EE, MARRIOTT M D. A comparative evaluation of heuristics for container loading[J]. European Journal of Operational Research, 1990, 44(2): 267-276.

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

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

[5]刘胜，朱凤华，吕宜生，等．求解三维装箱问题的启发式正交二叉树搜索算法[J]．计算机学报，2015，38(8)：1530-1542．

[6]张德富，彭煜，张丽丽．求解三维装箱问题的多层启发式搜索算法[J]．计算机学报，2012，35(12)：2553-2560．

[7]那日萨，韩琪玮，林正奎．三维多箱异构货物装载优化及其可视化[J]．运筹与管理，2015，24(4)：76-82．

[8]GEHRING H ， BORFELDT A. A genetic algorithm for solving the container loading problem[J]. International Transaction Operational Research, 1997, 4(5/6):401-418.

[9]孙洪礼，王周敬．同类货物集装箱装载问题的启发式算法[J]．计算机应用与软件，2011，28(4)：193-195．

[10]朱向，雷定猷．带平衡约束三维装箱问题的双层混合遗传算法[J]．交通运输系统工程与信息，2015，15(2)：203-209．

[11]陈泽爽，何健明，林逵．多约束三维装箱问题的混合遗传算法[J]．现代计算机(专业版)，2011 (1)：14-19．

[12]KUCUK M, ERMIS M. A new hybrid evolutionary algorithm for three-dimensional packing problems[C]// 2010 IEEE International Conference on Systerns Man and Cybernetics (SMC). IEEE, 2010: 4029-4034.DOI:10.1109/ICSMC.2010.5642203.

[13]孟唯娟．托盘装载优化系统的研究与开发[D]．天津：天津科技大学，2010．

[14]WANG Z J, LI K W. Layer-layout-based heuristics for loading homogeneous items into a single container[J]. Journal of Zhejiang University SCIENCE A, 2007, 8(12): 1944-1952.

[15]周康，何世伟，游玲君．铁路适盘货物装载方案优化研究[J]．铁道货运，2013 (9)：52-57．

Optimization of railway pallet-suited freight loading scheme

QIN Jian

(China Railway First Survey and Design Institute Group Ltd., Xi′an 710043, China)

∶We construct an optimization model for similar rectangular freights loaded freight trains with pallets based on railway freight loading constraints. We initially solve pallets layout of carriage bottom with improved two-dimensional layout optimization algorithm. We further determine optimal stacking pallet layers in a carriage, and obtain optimal loading scheme. Instance analytical results show that the model is effective for solving railway similar pallet applied freight loading problem.

∶railway transportation; pallet-suited freight; loading scheme; optimization

10.3976/j.issn.1002-4026.2016.05.017

2016-01-09

秦鉴(1990—)，男，助理工程师，研究方向为铁路勘察设计。Email：1171432853@qq.com

U294.3

A