在线约束性可变尺寸球体三维装箱
来源:用户上传
作者:
摘 要：三维装箱问题在很多领域上有广泛的应用。现阶段对于离线矩形物体的三维装箱研究比较广泛，而矩形体以外的在线三维装箱问题研究相对单一。提出了一种在线约束性可变尺寸球体三维装箱问题，并且给出了该问题的解决方案，因球体重量不同，将球体分放入不同等级大小的单元细胞中，通过让球体装入合适的菱形十二面体的方式让其组成细胞，然后进行装载;进而根据加权法可以得到在有界环境下的竞争比。解决了同一类货物不同重量的情况下在流水线上装箱问题。
关键词：三维装箱;在线装箱;球体装箱;可变尺寸
中图分类号：TH247 文献标识码：A
Abstract： The three-dimensional packing problem has been widely used in many fields.At present，the research on three-dimensional packing for offline rectangular objects is extensive.The research on online 3D packing outside the rectangular body is relatively simple.This paper proposes a three-dimensional packing problem of online constrained variable size spheres.And gives a solution to the problem，Make the cells into cells by loading them into the appropriate rhombohedral dodecahs and then loading them;Furthermore，according to the weighting method，the competition ratio in the bounded environment can be obtained.It solves the problem of packing on the assembly line with different weights of the same type of goods.
Key words： three-dimensional packing;online packing;sphere packing;variable size
三维装箱问题（Three-dinensional Loading Problem）广泛存在于港口、机场货物运输等物流行业，实现三维装箱问题的优化有利于压缩装载和物流成本，成为各企业重要竞争节点。现阶段，待装载的货物为矩形体的研究学术成果颇为广泛[1]。如果装载算法在依序处理各待装货物时，不知道任何后续货物信息，并立即给出当前货物的装箱方案，则称为在线装箱。
二维空间中 Kamali 等人[2]将等边三角形打包成正方形。球体装箱中可以考虑将球体装入正方体中，也就是折纸技术[3]或者装入圆柱体[4]再装入箱子中。
将立方体打包成单元立方体问题中，在线状态下Han等人[5]提出了一种渐进比为2.6161的算法，Christense等人[6] 最近进行的一项调查显示，在二维或三维空间中，一些装箱方式的變化采用了近似算法[10]，包括离线和在线算法[9]。只有Hokama等人[7]考虑了在线圆包装的竞争算法：在任何有界空间算法的竞争比上，给出了2.292的下界，一种渐近竞争比为2.439的算法，以及相同半径的球体包装成立方体[8]。
目前，对于待装载货物为球体的约束条件的三维装箱研究较少，且以往的研究通常是对于相同半径的球体，对其变成相对熟悉的矩形装箱，而没有对其他约束条件下的球体装箱进行研究。提出了一种重量约束下的可变尺寸球体在线三维装箱问题，该问题中待装载的球体货物，半径不同且重量也不同，通过利用重量条件因子分成不同等级球体装入相应的细胞单元（本文应用的是菱形十二面体）中再进行装箱操作，通过计算可以证明该方法可行。解决了现实生活中在线装箱中遇到不同重量不同大小球体时的实际装载问题。
4 结 论
提出了一种在线约束性可变尺寸球体三维装箱方案，在线约束性可变化球体装箱中，将待装球体的大小通过一定因子分出球体的大小范围，进而可以区分球体的大小，因而可以分配其相应的Sbin或Lbin存放位置，得出Sbin与Lbin装箱时的在线算法竞争比至少为w（S）+（1-V（S）），进一步可以得出有界空间中在线近似算法的竞争比至少为2.8809。
参考文献
[1] BANSAL N，CORREA J R，KENYON C，et al. Bin packing inmultiple dimensions： inapproximability results and approximation schemes[J]. Mathematics of Operations Research，2006，31（1）：31—49.
[2] KAMALI S，LO′PEZ-ORTIZ A，RAHMATI Z. Online packing of equilateral triangles[C]. In Proceedings of the 27th Canadian Conference on Computational Geometry （CCCG′2015），2015. [3] FLORES J J，MART?NEZ J，CALDERN F. Evolutionary computation solutions to the circle packing problem[J]. Soft Computing，2016，20（4）：1521—1535.
[4] 滕弘飞，刘义军，葛文海，等. 旋转锥体空间中圆柱体群的布局优化[J]. 计算机学报，1993（7）：519—525.
[5] HAN X，YE D S，ZHOU Y. A note on online hypercube packing[J]. Central European Journal of Operations Research，2010，18（2）：221—239.
[6] CHRISTENSEN H I，KHAN A，POKUTTA S，et al. Approximation and online algorithms for multidimensional bin packing： A survey[J]. Computer Science Review，2017，24：S1574013716301356.
[7] QUEIROZ T A D，HOKAMA P H D B，SCHOUERY R C S，et al. Two-dimensional disjunctively constrained knapsack problem： heuristic and exact approaches [J]. Computers & Industrial Engineering，2017，105（Complete）：313—328.
[8] TATAAREVIC M. On limits of dense packing of equal spheres in a cube[J]. Electronic Journal of Combinatorics，2015，22（1）：1695—1697.
[9] 陳花. 两类在线算法问题的研究[D]. 兰州：兰州理工大学，2009.
[10] 曹炬，周济. 矩形件排样优化的一种近似算法[J]. 计算机辅助设计与图形学学报，2003，28（6）：190—195.
转载注明来源:https://www.xzbu.com/8/view-15033317.htm
