在線約束性可變尺寸球體三維裝箱

郭曉雯　楊鼎強

摘? ?要：三維裝箱問題在很多領(lǐng)域上有廣泛的應(yīng)用?，F(xiàn)階段對于離線矩形物體的三維裝箱研究比較廣泛，而矩形體以外的在線三維裝箱問題研究相對單一。提出了一種在線約束性可變尺寸球體三維裝箱問題，并且給出了該問題的解決方案，因球體重量不同，將球體分放入不同等級大小的單元細胞中，通過讓球體裝入合適的菱形十二面體的方式讓其組成細胞，然后進行裝載;進而根據(jù)加權(quán)法可以得到在有界環(huán)境下的競爭比。解決了同一類貨物不同重量的情況下在流水線上裝箱問題。

關(guān)鍵詞：三維裝箱;在線裝箱;球體裝箱;可變尺寸

中圖分類號：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）廣泛存在于港口、機場貨物運輸?shù)任锪餍袠I(yè)，實現(xiàn)三維裝箱問題的優(yōu)化有利于壓縮裝載和物流成本，成為各企業(yè)重要競爭節(jié)點?，F(xiàn)階段，待裝載的貨物為矩形體的研究學(xué)術(shù)成果頗為廣泛[1]。如果裝載算法在依序處理各待裝貨物時，不知道任何后續(xù)貨物信息，并立即給出當前貨物的裝箱方案，則稱為在線裝箱。

二維空間中 Kamali 等人[2]將等邊三角形打包成正方形。球體裝箱中可以考慮將球體裝入正方體中，也就是折紙技術(shù)[3]或者裝入圓柱體[4]再裝入箱子中。

將立方體打包成單元立方體問題中，在線狀態(tài)下Han等人[5]提出了一種漸進比為2.6161的算法，Christense等人[6] 最近進行的一項調(diào)查顯示，在二維或三維空間中，一些裝箱方式的變化采用了近似算法[10]，包括離線和在線算法[9]。只有Hokama等人[7]考慮了在線圓包裝的競爭算法：在任何有界空間算法的競爭比上，給出了2.292的下界，一種漸近競爭比為2.439的算法，以及相同半徑的球體包裝成立方體[8]。

目前，對于待裝載貨物為球體的約束條件的三維裝箱研究較少，且以往的研究通常是對于相同半徑的球體，對其變成相對熟悉的矩形裝箱，而沒有對其他約束條件下的球體裝箱進行研究。提出了一種重量約束下的可變尺寸球體在線三維裝箱問題，該問題中待裝載的球體貨物，半徑不同且重量也不同，通過利用重量條件因子分成不同等級球體裝入相應(yīng)的細胞單元（本文應(yīng)用的是菱形十二面體）中再進行裝箱操作，通過計算可以證明該方法可行。解決了現(xiàn)實生活中在線裝箱中遇到不同重量不同大小球體時的實際裝載問題。

4? ?結(jié)? ?論

提出了一種在線約束性可變尺寸球體三維裝箱方案，在線約束性可變化球體裝箱中，將待裝球體的大小通過一定因子分出球體的大小范圍，進而可以區(qū)分球體的大小，因而可以分配其相應(yīng)的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]? ? 滕弘飛，劉義軍，葛文海，等. 旋轉(zhuǎn)錐體空間中圓柱體群的布局優(yōu)化[J]. 計算機學(xué)報，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]. 蘭州：蘭州理工大學(xué)，2009.

[10]? 曹炬，周濟. 矩形件排樣優(yōu)化的一種近似算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報，2003，28（6）：190—195.