论文部分内容阅读
摘 要：装箱问题传统解法计算工作量大、不易掌握且装箱效率低，为了克服问题提出新的优化解法，该方法把装箱作业分为3大类18种具体类别，为了简化求解方法、提高求解速度和装箱效率，对最低层的2种组合不做线性规划求解，只是选择其中好的方案，以此作为基础数据，再对货箱3个维度分别规划求解，求出优化组合，给出简便快速优化装箱方法。该方法虽然优化程度略低，但方法更为简单、求解和装箱效率更高，优化程度较为理想。
关键词：单一货物；三维装箱问题；简便快速优化装箱方法；线性规划法
中图分类号：TP 391.72 文献标识码：A 文章编号：1672-7312（2017）02-0132-04
Abstract：The traditional solution of packing problem is large，difficult to master and low packing efficiency，in order to overcome the problem，a new optimization solution is proposed，which divides the packing operation into three categories of 18 specific categories.In order to simplify the solution，improve the speed and packing efficiency，the two combinations of LOWEST STATION are not linear programming，only the good scheme，as the basic data，and three dimensions of the box are solved respectively，the optimization combination，and simple and fast packing method.Although the degree of optimization is slightly lower，but the method is simpler，the solution and packing efficiency is higher，and the optimization degree is more ideal.
Key words：single goods；three dimensional packing problem；simple and rapid packing method；linear programming method
0 引 言
貨物三维摆放无约束装箱问题是NP难问题（3DBPP），如何解决这一难题，一直是人们关注的问题。自从1960年以来，许多专家、学者和实际工作者做了大量研究，解决的方法主要是搜索法[1]、启发式算法[2]和数学规划法[3]等。虽然解法很多，但具有实际应用价值的成果较少，有些方法复杂、高深、装箱效率低，不易被实际工作者掌握和运用。研究成果多数是针对多种不同货物装箱问题，单一货物装箱问题研究成果相对很少[4-11]，国内只查到10篇文献。已有线性规划解法，通常只针对一维装箱问题[12]，三维装箱问题，国内很少有文献论述，国际上虽然有些论述[13]，但三维装箱问题可供参考的文献不多。为了丰富装箱优化方法、提高装箱效率，提出简便快速优化装箱方法。
1 理论探讨
1.1 装箱问题特点与规律分析
虽然3DBPP是NP难问题，组合方案数量众多，但是因货箱以及货物各只有长、宽和高3个维度，因此，可计算出货物装箱组合种类数，一共只有18种。一方面，尽管是三维装箱问题，但货箱或货物某一维度被选用后，就只剩下其余2个维度，以此类推，根据这一规律，可把三维装箱问题转化成二维，二维转化为一维。另一方面，尽管组合方案数量众多、但是可利用线性规划求最优解，把复杂问题简单化、程序化。
装箱过程可分为3个阶段。第一阶段，装箱时首先面临选择货箱长（JC）、宽（JK）和高（JG）3个维度中哪个维度摆放货物，形成3大类，第一大类选择货箱的长，第二大类选择货箱的宽，第三大类选择货箱的高；第二阶段，在选定货箱某一维度后，需要选择把货物长（C）、宽（K）和高（G）3个维度中哪个维度与选定货箱维度平行摆放，形成3小类，第一小类选择货物的长，第二小类选择货物的宽，第二大类选择货物的高；第三阶段，在完成前2个阶段后，货箱只剩下没被优化的2个维度，货物只剩下没被选用的2个维度（假设剩余k和h维度），还可分别按货箱剩余的2个维度（假设剩余M和N维度）优化摆放货物，形成3小类下2种最底层组合种类。如果目标只是提高优化程度，还可在此运用规划求解，求出优化组合，然后再按货箱3个维度优化组合，求出优化程度极高的优化方案。这里，既想提高优化程度，又要兼顾方法简单、求解速度快、装箱效率高，因此，对这2种最底层组合种类不进行规划求解，只是选择2种摆放方案中摆放2种数量多的方案（方案1，货物k对应货箱M、货物h对应货箱N；方案2，货物k对应货箱N、货物h对应货箱M），在此基础上，再按货箱3个维度优化组合，求出优化程度较好的优化方案。因此，3个阶段一共组合种类数（N）为：N=3×3×2=18个。
1.2 装箱问题描述及相关基础数据Excel计算公式
设某单一货物需要装入一种规格矩形货箱，Xij为货物维度为i，按货箱维度j能摆放个数，i从1到3，分别代表货物长、宽和高；j从1到3，分别代表货箱长、宽和高；其他符号参见表1.Nmax为货箱最多能装货物的个数。
某个维度能摆放的个数计算公式为：D3=int（$C3/D$2），复制区域D3：F5，货箱最多能装货物的个数Nmax对应的单元格D6=int（（C3*C4*C5）/（D2*E2*F2））。 1.3 求解步骤与数学模型
1.3.1 求解步骤
第一步，分别求出3大类中的6种最低层组合方案中每组较好的摆放方案，然后再求该大类最终优化组合方案。
第二步，求装箱问题最终近似最优解，3大类中最终组合方案最大者为近似最优解方案。
第三步，给出装箱方案。根据近似最优解方案逆向寻找具体详细装箱方案。因篇幅所限，这里只给出最终近似最优解方案，具体详细装箱方案从略。
1.3.2 数学模型
最终近似最优解方案Z=max（ZJC，ZJK，ZJG）=max（2 784，2 767，2 784）=2 784，按货箱长度或按货箱高度优化均可，以按货箱长度优化为例，装箱方案为：货物长度按货箱长度平行摆放10个，且货物的宽对应货箱的宽平行摆放、货物的高对应货箱的高平行摆放；货物高度按货箱长度平行摆放3个，因此是2种摆放方法数量相等，所以货物的长对应货箱的宽平行摆放、货物的宽对应货箱的高平行摆放，或货物的长对应货箱的高平行摆放、货物的宽对应货箱的宽平行摆放均可以。
装箱优化程度≥（2 784/2 819）×100%=98.75%，优化程度较为理想。
最终优化解法为Z=max（ZJC，ZJK，ZJG）=max（2 794，2 794，2 784）=2 794，优化程度99.1%.与最低层规划求解方法优化程度只相差0.36%，装箱优化程度比较理想，方法更为简单、装箱效率更高。
3 结 论
由于货物和货箱只具有3个维度，因装箱时某一区域摆放方式是相同的，所以装箱组合数是固定，根据装箱18种组合，运用线性规划进行组合优化，借助Excel软件能在几分钟内给出易于装箱优化方案。该方法优化程度高、装箱效率高、耗时少、求解成本低。
参考文献：
[1]Jose Fernando Goncaves，Mauricio G C，Resende.A biased random key genetic algorithm for 2D and 3D bin packing problems[J].Int J Production Economics，2013，145（2）：500-510.
[2]张德富，彭 煜，张丽丽.求解三维装箱问题的多层启发式搜索算法[J].计算机学报，2012，35（12）：2 253-2 260.
[3]Hifi M，Kacem L，Negre S，et al.A linear programming approach for the threedimensional bin packing problem[J].Electronic Notes in Discrete Mathematics，2010，36：993-1 000.
[4]农健恒，崔耀东.同尺寸物品装箱的动态规划算法[J].计算机应用与软件，2014，31（7）：249-251.
[5]隋树林，邵巍，高自友.同一尺寸货物三维装箱问题的一种启发式算法[J].信息与控制，2006，34（4）：490-494.
[6]王 岩，潘卫平，陈秋莲，等.单一尺寸长方体三维装箱问题的一种求解算法[J].包装工程，2015，36（11）：96-99.
[7]姚 怡，崔耀东.一种高效的同尺寸長方体的装箱算法[J].计算机工程与科学，2012，34（10）：192-194.
[8]廖元秀，崔耀东.对Agrawal 单一矩形排样算法的改进与扩展[J].广西师范大学学报：自然科学版，2004，22（3）：49-53.
[9]徐丽丽，季 忠，夏继梅.同规格货物装箱问题的优化计算[J]. 山东大学学报，2008，38（3）：14-17.
[10]杨德荣.集装箱单一规格物体装箱的优化算法[J]. 交通运输工程与信息学报，2007，5（2）：17-23.
[11]孙洪礼，王周敬.同类货物集装箱装载问题的启发式算法[J].计算机应用与软件2011，28（4）：93-95.
[12]王桂强.运筹学上级指南原理导航用Excel工具[M].北京：格致出版社，2010.
[13]
Hifi M，Negre S，Wu L.Hybrid greedy heuristics based on linear programming for the threedimensional single binsize bin packing problem[J].International Transactions in Operational Research，2014，21（1）：59-79.
（责任编辑：许建礼）
关键词：单一货物；三维装箱问题；简便快速优化装箱方法；线性规划法
中图分类号：TP 391.72 文献标识码：A 文章编号：1672-7312（2017）02-0132-04
Abstract：The traditional solution of packing problem is large，difficult to master and low packing efficiency，in order to overcome the problem，a new optimization solution is proposed，which divides the packing operation into three categories of 18 specific categories.In order to simplify the solution，improve the speed and packing efficiency，the two combinations of LOWEST STATION are not linear programming，only the good scheme，as the basic data，and three dimensions of the box are solved respectively，the optimization combination，and simple and fast packing method.Although the degree of optimization is slightly lower，but the method is simpler，the solution and packing efficiency is higher，and the optimization degree is more ideal.
Key words：single goods；three dimensional packing problem；simple and rapid packing method；linear programming method
0 引 言
貨物三维摆放无约束装箱问题是NP难问题（3DBPP），如何解决这一难题，一直是人们关注的问题。自从1960年以来，许多专家、学者和实际工作者做了大量研究，解决的方法主要是搜索法[1]、启发式算法[2]和数学规划法[3]等。虽然解法很多，但具有实际应用价值的成果较少，有些方法复杂、高深、装箱效率低，不易被实际工作者掌握和运用。研究成果多数是针对多种不同货物装箱问题，单一货物装箱问题研究成果相对很少[4-11]，国内只查到10篇文献。已有线性规划解法，通常只针对一维装箱问题[12]，三维装箱问题，国内很少有文献论述，国际上虽然有些论述[13]，但三维装箱问题可供参考的文献不多。为了丰富装箱优化方法、提高装箱效率，提出简便快速优化装箱方法。
1 理论探讨
1.1 装箱问题特点与规律分析
虽然3DBPP是NP难问题，组合方案数量众多，但是因货箱以及货物各只有长、宽和高3个维度，因此，可计算出货物装箱组合种类数，一共只有18种。一方面，尽管是三维装箱问题，但货箱或货物某一维度被选用后，就只剩下其余2个维度，以此类推，根据这一规律，可把三维装箱问题转化成二维，二维转化为一维。另一方面，尽管组合方案数量众多、但是可利用线性规划求最优解，把复杂问题简单化、程序化。
装箱过程可分为3个阶段。第一阶段，装箱时首先面临选择货箱长（JC）、宽（JK）和高（JG）3个维度中哪个维度摆放货物，形成3大类，第一大类选择货箱的长，第二大类选择货箱的宽，第三大类选择货箱的高；第二阶段，在选定货箱某一维度后，需要选择把货物长（C）、宽（K）和高（G）3个维度中哪个维度与选定货箱维度平行摆放，形成3小类，第一小类选择货物的长，第二小类选择货物的宽，第二大类选择货物的高；第三阶段，在完成前2个阶段后，货箱只剩下没被优化的2个维度，货物只剩下没被选用的2个维度（假设剩余k和h维度），还可分别按货箱剩余的2个维度（假设剩余M和N维度）优化摆放货物，形成3小类下2种最底层组合种类。如果目标只是提高优化程度，还可在此运用规划求解，求出优化组合，然后再按货箱3个维度优化组合，求出优化程度极高的优化方案。这里，既想提高优化程度，又要兼顾方法简单、求解速度快、装箱效率高，因此，对这2种最底层组合种类不进行规划求解，只是选择2种摆放方案中摆放2种数量多的方案（方案1，货物k对应货箱M、货物h对应货箱N；方案2，货物k对应货箱N、货物h对应货箱M），在此基础上，再按货箱3个维度优化组合，求出优化程度较好的优化方案。因此，3个阶段一共组合种类数（N）为：N=3×3×2=18个。
1.2 装箱问题描述及相关基础数据Excel计算公式
设某单一货物需要装入一种规格矩形货箱，Xij为货物维度为i，按货箱维度j能摆放个数，i从1到3，分别代表货物长、宽和高；j从1到3，分别代表货箱长、宽和高；其他符号参见表1.Nmax为货箱最多能装货物的个数。
某个维度能摆放的个数计算公式为：D3=int（$C3/D$2），复制区域D3：F5，货箱最多能装货物的个数Nmax对应的单元格D6=int（（C3*C4*C5）/（D2*E2*F2））。 1.3 求解步骤与数学模型
1.3.1 求解步骤
第一步，分别求出3大类中的6种最低层组合方案中每组较好的摆放方案，然后再求该大类最终优化组合方案。
第二步，求装箱问题最终近似最优解，3大类中最终组合方案最大者为近似最优解方案。
第三步，给出装箱方案。根据近似最优解方案逆向寻找具体详细装箱方案。因篇幅所限，这里只给出最终近似最优解方案，具体详细装箱方案从略。
1.3.2 数学模型
最终近似最优解方案Z=max（ZJC，ZJK，ZJG）=max（2 784，2 767，2 784）=2 784，按货箱长度或按货箱高度优化均可，以按货箱长度优化为例，装箱方案为：货物长度按货箱长度平行摆放10个，且货物的宽对应货箱的宽平行摆放、货物的高对应货箱的高平行摆放；货物高度按货箱长度平行摆放3个，因此是2种摆放方法数量相等，所以货物的长对应货箱的宽平行摆放、货物的宽对应货箱的高平行摆放，或货物的长对应货箱的高平行摆放、货物的宽对应货箱的宽平行摆放均可以。
装箱优化程度≥（2 784/2 819）×100%=98.75%，优化程度较为理想。
最终优化解法为Z=max（ZJC，ZJK，ZJG）=max（2 794，2 794，2 784）=2 794，优化程度99.1%.与最低层规划求解方法优化程度只相差0.36%，装箱优化程度比较理想，方法更为简单、装箱效率更高。
3 结 论
由于货物和货箱只具有3个维度，因装箱时某一区域摆放方式是相同的，所以装箱组合数是固定，根据装箱18种组合，运用线性规划进行组合优化，借助Excel软件能在几分钟内给出易于装箱优化方案。该方法优化程度高、装箱效率高、耗时少、求解成本低。
参考文献：
[1]Jose Fernando Goncaves，Mauricio G C，Resende.A biased random key genetic algorithm for 2D and 3D bin packing problems[J].Int J Production Economics，2013，145（2）：500-510.
[2]张德富，彭 煜，张丽丽.求解三维装箱问题的多层启发式搜索算法[J].计算机学报，2012，35（12）：2 253-2 260.
[3]Hifi M，Kacem L，Negre S，et al.A linear programming approach for the threedimensional bin packing problem[J].Electronic Notes in Discrete Mathematics，2010，36：993-1 000.
[4]农健恒，崔耀东.同尺寸物品装箱的动态规划算法[J].计算机应用与软件，2014，31（7）：249-251.
[5]隋树林，邵巍，高自友.同一尺寸货物三维装箱问题的一种启发式算法[J].信息与控制，2006，34（4）：490-494.
[6]王 岩，潘卫平，陈秋莲，等.单一尺寸长方体三维装箱问题的一种求解算法[J].包装工程，2015，36（11）：96-99.
[7]姚 怡，崔耀东.一种高效的同尺寸長方体的装箱算法[J].计算机工程与科学，2012，34（10）：192-194.
[8]廖元秀，崔耀东.对Agrawal 单一矩形排样算法的改进与扩展[J].广西师范大学学报：自然科学版，2004，22（3）：49-53.
[9]徐丽丽，季 忠，夏继梅.同规格货物装箱问题的优化计算[J]. 山东大学学报，2008，38（3）：14-17.
[10]杨德荣.集装箱单一规格物体装箱的优化算法[J]. 交通运输工程与信息学报，2007，5（2）：17-23.
[11]孙洪礼，王周敬.同类货物集装箱装载问题的启发式算法[J].计算机应用与软件2011，28（4）：93-95.
[12]王桂强.运筹学上级指南原理导航用Excel工具[M].北京：格致出版社，2010.
[13]
Hifi M，Negre S，Wu L.Hybrid greedy heuristics based on linear programming for the threedimensional single binsize bin packing problem[J].International Transactions in Operational Research，2014，21（1）：59-79.
（责任编辑：许建礼）