汽车零部件三维装载问题研究

林永昊 姚明山 赵 磊，3 朱道立，3

（1.上海交通大学 中美物流研究院，上海 200030；2.同济大学 经济与管理学院，上海 200092；3.上海交通大学 安泰经济与管理学院，上海 200030）

1　问题描述

汽车零部件三维装载问题是指对给定一辆待配载货车以及一批待装货物，确定一个可行的装载方案使得在满足约束条件（货物不与车厢相嵌约束；货物互不相嵌约束；货物承重约束等）下，车辆装载率（装入货车的所有货物体积之和／货车车厢体积*100%）最大。

该问题满足如下假设条件：

（1）车厢及待装货物均为长方体；

（2）放入的货物完全被包含在车厢内；

（3）货物只能以棱平行（或垂直）于车厢的棱的方向放置；

（4）货物只能绕高度棱旋转，不可倾倒放置。

如图1所示，以面向车头方向车厢左前角作为坐标原点建立笛卡尔坐标系，待装货物的装载位置由其最靠近坐标原点的角点坐标值表示，则可行装载方案中各已装入货物的装载位置可用货物的角点坐标值表示。

图1　坐标系示意图

在图1所示建立坐标系下，汽车零部件三维装载问题的数学模型可表示如下：

1.1　集合

I=｛1，…，N｝：待装载货物的集合。

1.2　参数

Li：货物i的长度，i∈I；

Wi：货物i的宽度，i∈I；

Hi：货物i的高度，i∈I；

Qi：货物i的重量，i∈I；

Vi：货物i的体积，i∈I，Vi=Li×Wi×Hi；

Si：货物i的承重重量，i∈I；

CL：车厢的长度；

CW：车厢的宽度；

CH：车厢的高度；

CV：车厢的体积，CV=CL×CW×CH。

1.3　变量

连续决策变量：用于刻画装载方案的连续变量。

xi：货物i的放置位置的x轴坐标，i∈I；

yi：货物i的放置位置的y轴坐标，i∈I；

zi：货物i的放置位置的z轴坐标，i∈I；

0-1决策变量：用于刻画装载方案的0-1变量。

αi：货物i的装载在车上则αi=1，否则，αi=0，i∈I；

βi：货物i需要旋转90°，如果货物i长边平行Y轴，宽边平行X轴则βi=1，反之则βi=0；

0-1辅助决策变量：用于保证决策变量所刻画的装载方案为可行方案的变量。

lpij：货物j在货物i的X轴正方向上，则lpij=1，否则lpij=0；

wpij：货物j在货物i的Y轴正方向上，则wpij=1，否则wpij=0；

hpij：货物j在货物i的Z轴正方向上，则hpij=1，否则hpij=0。

1.4　目标函数

该问题的求解目标为车辆装载率（装入货车的所有货物体积之和／货车车厢体积*100%）最大，即如式（1）所示：

（2）货物互不嵌入约束。

（3）货物与车厢不相嵌约束，即如式（12-14）所示：

1.5　约束条件

一般三维装载问题约束。一般三维装载问题的约束主要有体积约束、装入货物互不嵌入约束和货物与车厢不相嵌约束，具体约束的数学表达如下：

（1）体积约束：装入所有货物的体积总和不超过车厢最大容积，即如式（2）所示：

（3）堆叠约束：零部件包装箱有多种类型，存在不同堆叠限制：①不允许堆叠；②仅允许同类型、同尺寸堆叠；③允许同类型，同尺寸／底面尺寸小的堆叠；④允许不同类型、同尺寸按既定顺序堆叠；⑤允许不同类型，同尺寸／底面尺寸小的堆叠（本条约束过于繁琐，本文中省略其数学模型表述）。

汽车零部件装载中特殊约束。汽车零部件装载问题中的特殊约束主要有完全支撑约束、单箱承重约束和货物堆叠约束，具体数学表达如下：

（1）完全支撑约束：货物必须得到车厢底部或其他一件货物的完全支撑，不允许悬空。

（2）单箱承重约束：货物叠放时，货物重量不得大于支撑其摆放的货物的承重能力。

2　基于装载块序列的混合模拟退火算法

由于汽车零部件三维装载问题较经典三维装箱问题在货物堆叠方面更为复杂，现存的求解经典三维装箱问题的算法很难直接应用到汽车零部件三维装载问题上。因此，本文设计了一种基于装载块装入顺序的模拟退火算法。首先，将单箱货物构造成为装载块（装载块不能在高度上堆叠），将三维装载问题降为二维装载问题。然后，利用模拟退火过程，将各装载块装入车厢。该算法以装载块的装载顺序作为编码方式，通过模拟退火过程随机调整装载序列以优化装载序列对应的装载方案，最后输出算法结束时产生的装载序列对应的装载方案。以下算法流程中的集合、参数和变量的定义沿用上一小节中定义。

2.1　整体算法框架

基于装载块序列的混合模拟退火算法流程如下：

基于装载块序列的混合模拟退火算法

输入：2.1中的待装货物集合；2.2中所有参数；降温速度η，0＜η＜1；最大迭代次数n；降温目

息βi，装载率

否则，回到Step 4。

2.2　装载块生成子算法

装载块生成子算法输入：2.1中的待装货物集合；2.2中所有参数。输出：装载块序列B_list；货物与装载块的对应关系。

Step 1：输入2.1中的待装货物集合；2.2中所有参数。

Step 2：按照底面积从大到小顺序将待装货物排序，生成待装货物列表I_list；初始化iI=1，iB=1。

Step 3：将I_list中第iI个货物放置于装载块iB，并I_list=I_list＼｛iI｝。

Step 4：选择I_list中满足堆叠、承重等约束条件可堆叠于装载块iB的货物中，底面积最大的货物jI。

Step 1：输入2.1中的待装货物集合和2.2中的所有参数；设置降温速度η，0＜η＜1；最大迭代次数n；降温目标tgoal。

Step 2：调用装载块生成子算法，生成装载块集合B。

Step 3：根据B随机生成装载块的一个排序B_list（装载序列）；设置初始温度t＞tgoal。

Step 4：设置k=1。

Step 5：调用装载方案生成子算法，计算适应度值F=f（B_list）。

Step 6：调用随机扰动产生新的装载序列B′_list；调用装载方案生成子算法，计算适应度值F′=f（B′_list）。

Step 7：判断适应度值是否改进，若F′＞F，则接受新的装载序列B_list=B′_list；否则按照Metropolis概率准则接受新的装载序列；令k=k+1。

Step 8：判断是否k＞n，若是则执行Step 9；否则回到Step 5。

Step 9：冷却退火，令t=t·η。

Step 10：判断是否t＜tgoal，若是则调用装载方案生成子算法，由B_list生成并输出装载方案，即对任意i∈I，放置位置的x轴坐标xi，y轴坐标yi，z轴坐标zi，是否装载在车上αi，是否需要旋转90°信标tgoal。

输出：装载方案，即对任意i∈I，放置位置的x轴坐标xi；y轴坐标yi；z轴坐标zi；是否装载在车上αi；是否需要旋转90°信息βi。装载率f（B_list）

Step 5：若存在jI，则将jI放置于装载块iB目前已存在货物的上一层，并I_list=I_list＼｛jI｝，回到Step 4。若不存在jI，则进入Step 6。

Step 6：判断I_list是否为空，若是，则输出结果；若不是，iB=iB+1，回到Step 3。

由此生成的装载块，块与块之间在高度方向（z轴方向）上不能相互叠放。

2.3　装载方案生成子算法

为方便表达，这里做如下定义：

定义1（格局）设某一时刻，车厢内已放入若干装载块，还有若干个装载块待放，这称为一个格局。车厢内尚未放入任何装载块时，称为初始格局。所有装载块已放入车厢，或车厢外剩余的装载块无法再放入时，称为终止格局。

定义2（可装载点）可装载点定义参考文献［3］，可装载点是在当前装载格局下车厢中装载块的可行放置点。如图2-（a）所示，初始可装载点即为原点，坐标为（0，0），当装入长为l宽为w的装载块后，可装载点更新为（1，0）、（0，w）。如图2-（b）所示，在某个装载格局下，装入3个装载块，当4号装载块装入时，新增两个可装载点。

定义3（可装载度）：可装载度表示待装载块与可装载点的匹配程度，用于指导每个装载动作中可装载点的选择对任意装载块i在给定方向下和可装载点j之间的可装载度定义为一个向量当按给定方向可装载点j装不下目标待装载块i时，令Wkij=-1＜0，k∈｛1，2，3，4｝。反之，向量中各元素计算方法如下：

图2　可装载点示意图

W1ij：新生成可装载点指标。表示放入车厢后新生成的可装载点数量，NE∈｛0，1，2｝，NE越小，表示箱子与当前空间的紧密度越高，因此，定义：

W2ij：穴度。具体定义参考文献［4］，Bl，Bw表示装入装载块的长和宽，Bd表示装入装载块与车厢边界或相邻装载块最小距离，定义：

W3ij：封闭空间面积指标。封闭空间是指装箱过程中，由装载块间或装载块与车厢四个边界围成的空白区域，面积为BA。封闭空间面积越大，说明装载空间浪费越严重，因此定义封闭空间面积指标W3ij：

贴边数。表示新装入装载块与已装入装载块或车厢边界相贴的边数

对任意装载块i和可装载点我们记Wij大于装载度如果；或和和或和装载方案生成子算法的流程如下：

装载方案生成子算法

输入：装载块序列B_list；货物与装载块的对应关系。

输出：装载方案，即对任意货物i∈I，放置位置的x轴坐标xi；y轴坐标yi；z轴坐标zi；是否装载在车上αi；是否需要旋转90°信息βi。适应度值，即装载率f（B_list）。

Step 1：输入装载块序列B_list；货物与装载块的对应关系，设置iB=1。

Step 2：选择B_list中第iB个装载块；获得当前格局下的可装载点列表EP；计算B_list中第iB个装载块对EP中各可装载点横放／竖放的可装载度值；第iB个装载块对EP中各可装载点横放／竖放的可装载度值均小于0，则进入Step 4；否则，选择可装载点列表EP中可装载度值最大的可装载点和其对应的装载方向作为第iB个装载块的装载位置和装载方向，进入Step 3。

Step 3：按照当前装入装载块，得到一个新的格局。

Step 4：iB=iB+1。

Step 5：如果iB＞length（B_list），则算法终止，输出装载方案，即对任意货物i∈I，放置位置的x轴坐标xi；y轴坐标yi；z轴坐标zi；是否装载在车上αi；是否需要旋转90°信息βi。装载率f（B_list）=否则，回到Step 2。

2.4　随机扰动

采用随机置换的方式对装载序列进行调整，即在装载序列中随机选择两个装载块位置进行交换，其他装载块排序不变。如初始装载序列为［A，B，C，D，E，F，G］，随机选择到第1位和第5位进行交换，则新的装载序列为［E，B，C，D，A，F，G］。

2.5　Metropolis准则

本文求解目标为装载率最大，设置评价函数为装载率F，若ΔF=F′-F≥0，则接受新的装载序列，若ΔF＜0，则采用Metropolis准则，生成一个（0，1）之间的随机数θ，若θ小于接受概率exp（10*ΔF／t），则同样接受新的装载序列，否则保留当前装载序列。

3　算例分析

本文选取上海某汽车物流企业的零部件入厂物流三维装载的实际运营数据，将算法优化装载方案与实际运作中人工编排装载方案进行比较，验证算法能否有效处理零部件三维装载问题，提高作业效率。

3.1　单箱装载

（1）算例数据

如表1所示，共有8类159箱待装零部件，数据包含货物编号、长、宽、高、需求箱数等，采用9.6M货车装载，车厢长宽高分别为9400cm，2300cm，2300cm。

表1　单箱装载数据

（2）算例结果

如表2所示，待装零部件全部装入车厢，装载率达93.9%，装载方案给出了零部件装入顺序、摆放方向及对应的坐标值，装载效果如图3表示。

表2　单箱装载结果

图3　单箱装载结果（单位：cm）

3.2　多箱装载-单日数据对比

为了进一步验证算法的有效性，选取该汽车物流企业一条取货路线某天的全部装箱需求数据，采用串行装箱方式即装满一车厢再装下一车厢，直至装完全部待装货物，比较装载率及车辆使用数等指标。

（1）算例数据：

共有31类1942箱待装零部件，限于篇幅未列出具体数据。采用12M货车装载，车厢长宽高分别为11800cm，2300cm和2300cm。

（2）算例结果：

如表3所示，算法平均装载率76.2%，需要使用10辆车；而实际运营中人工作业结果为安排了12辆车，平均装载率为63.5%。

表3　20170503装载算例结果

3.3　多箱装载——10日数据对比

选取该路线连续10日装箱数据，共有16950箱待装零部件，限于篇幅未列出具体数据，仅列出每天待装零部件类型、需求箱数、算法结果、人工结果以及优化效果，如表4所示。

图4　装载率对比

图5　车辆使用数对比

表4　连续10日装载结果比较

图6　运输成本对比

结果表明，本文算法能有效解决汽车零部件三维装载问题，在车辆装载率、车辆使用数等方面均优于人工编排结果。算法优化后平均使用车辆数为6.7辆，平均装载率75.5%，实际运营使用车辆数8.2辆，平均装载率62.9%。相比于人工结果，算法优化后平均车辆使用数减少1.5辆，平均装载率提升12.6%。

从成本角度而言，优化后车辆使用数减少，直接降低了运输成本、装卸成本及人力成本等。以运输成本为例，该取货路线平均运输距离为140公里，运输费用为3.4元／公里，优化后10日运输成本减少了7140元，较人工结果降低18%。

4　总结

本文针对汽车零部件入厂物流实践中的零部件三维装载问题，考虑汽车零部件堆叠规则、单箱承重等现实约束，设计了基于装载块装载序列的混合模拟退火算法。通过使用上海某汽车物流企业的实际数据进行仿真实验，并与人工操作方案进行对比，验证了本文提出的算法能有效解决汽车零部件三维装载问题。未来的研究方向为取货路径与装载的协同优化问题。

参考文献：

［1］ BOYSEN N，EMDE S，HOECK M，et al.Part logistics in the automotive industry：decision problems，literature review and research agenda［J］.European Journal of Operational Research，2015，242（1）：107-120.

［2］ 何明珂，张屹然.国内汽车零件入厂物流研究综述［J］.中国流通经济，2011，25（7）：31-36.

［3］ CRAINIC T G，PERBOLI G，TADEI R.Extreme point-based heuristics for three-dimensional bin packing［J］.Informs Journal on Computing，2008，20（3）：368-384.

［4］ 何琨，黄文奇，金燕.基于动作空间求解二维矩形Packing问题的高效算法［J］.软件学报，2012，34（5）：1037-1044.

［5］ 何琨，黄文奇.基于动作空间的三维装箱问题的确定性高效率求解算法［J］.计算机学报，2014，37（8）：1786-1793.

［6］ PARRENO F，ALVAREZ-VALDES R，OLIVEIRA J F，et al.Neighborhood structures for the container loading problem：a VNS implementation［J］.Journal of Heuristics，2010，16（1）：1-22.

［7］ FANSLAU T，BORTFELDT A.A tree search algorithm for solving the container loading problem［J］.Informs Journal on Computing，2010，22 （2）：222-235.

［8］ 张德富，彭煜，朱文兴，等.求解三维装箱问题的混合模拟退火算法［J］.计算机学报，2009，32（11）：2147-2156.

［9］ 张德富，彭煜，张丽丽.求解三维装箱问题的多层启发式搜索算法［J］.计算机学报，2012，35（12）：2553-2561.

［10］ 刘胜，朱凤华，吕宜生，等.求解三维装箱问题的启发式正交二叉树搜索算法［J］.计算机学报，2015，38（8）：1530-1543.

［11］ 靳志宏，兰辉，郭贝贝.基于现实约束的集装箱装箱优化及可视化［J］.系统工程理论与实践，2010，30（9）：1722-1728.

［12］ 张莹，刘二超，戚铭尧.考虑支撑面约束的三维装箱问题快速求解方法［J］.交通运输系统工程与信息，2014，14（2）：192-198.

［13］ 那日萨，崔雪莲，韩琪玮，等.有角件约束的集装箱装箱问题优化算法［J］.工业工程与管理，2016，21（1）：1-7.