三維空間裝箱問題之最新下界值

New Lower Bounds for the Three-dimensional Orthogonal Bin Packing Problem

許嘉紘(Chia-Hung Hsu)

指導教授 ： 廖崇碩

國立清華大學/工學院/工業工程與工程管理學系/碩士(2012年)

https://doi.org/10.6843/NTHU.2012.00274

摘要

在本篇論文中，我們研究著名的裝箱問題(the bin packing problem)¬¬以及此問題的延伸-三維空間的裝箱問題。此問題在實務上有非常多的應用，能有效的幫助許多產業，像是一般物流業、運輸業和製造業管理他們的存貨成本與運輸成本。因此裝箱問題的演算法設計與分析一直被廣為研究著。
為了使許多裝箱問題的演算法設計者有一個更好的參考工具可以衡量其演算法求解品質的好壞，我們針對此問題的下界值計算方法進行文獻探討與分析，也提出了最新三維空間裝箱問題的下界值並證明我們的結果改善了目前為止在文獻中已知的最佳結果，也就是Boschetti [3] 他們在2004年所提出的結果。另一方面，我們也提出了嚴格漸佳(Strictly better)的例子說明我們的下界值表現最好的部分，並且證明了我們下界值的最壞情況下成效比(Worst case performance ratio)，也就是在最糟糕的情況下，我們的下界值與最佳解的差距可證明在一個常數倍數內。
此外，我們也研究了裝箱問題的另一種延伸模型，也就是允許物件旋轉90度的模型，其下界值的計算方式，並同時證明我們提出的下界值，改善了文獻中，有關此模型最好的下界值。

關鍵字

裝箱問題 ； 下界值 ； 最壞情況下成效比 ； 允許物件旋轉模型

並列摘要

In this thesis, we consider the three-dimensional orthogonal bin packing problem, which is a generalization of the well-known bin packing problem. The problem is useful to many practical applications, such as logistics industry, transportation industry and manufacturing industry. A better packing result can obviously reduce inventory costs and transportation costs.
In order to evaluate the quality of algorithms for the bin packing problem, we study the literatures and look into lower bounds of the problem. We present new low-er bounds for this problem and demonstrate that they improve the best previous results, the results proposed by Boschetti [3] in 2004. We also provide a strictly better example to emphasize the difference between the lower bounds. The asymptotic worst-case performance ratio, which can show that our lower bounds are bounded within a constant ratio in the worst case, is also proved.
In addition, we study an extension of this problem, the non-oriented model, which allows items to be rotated in 90 degrees. We study how to compute lower bounds for this model and demonstrate that our lower bounds improve the best previ-ous results for this model.

並列關鍵字

bin packing ； lower bound ； worst case performance ratio ； non-oriented model

參考文獻

1. N. Bansal, M. Sviridenko. New Approximability and Inapproximability results for 2-dimensional bin packing. In Proc. 15th Symposium on Discrete Algorithms (SODA 04), 196-203, 2004.

2. N. Bansal, A. Caprara, M. Sviridenko. A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing. SIAM Journal on Computing, 39(4):1256-1278, 2010.

3. M.A. Boschetti. New lower bounds for the three-dimensional finite bin packing problem. Discrete Applied Mathematics, 140:241-58, 2004.

4. JM. Bourjolly, V. Rebetez. An analysis of lower bounds procedures for the bin packing problem. Computers & Operations Research, 32:395-405, 2005.

5. J. Carlier, F. Clautiaux, A. Moukrim. New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation. Computers & Operations Research, 34:2223-2250, 2007.