裝箱問題自提出以來，一直是組合優化問題中最基本的問題之一，由於其應用的廣泛性和實用性的重大因素，一直受到國內外學者的廣泛關注。一般的裝箱問題是指一維的裝箱問題，但隨之衍生出二維、三維和分類限制等裝箱問題，並被應用於工業生產製造、多媒體儲存系統、資源配置等方面。
在裝箱問題中，箱子的限制條件可以為重量，面積、體積或類別來限制裝入的物品數量及處理不同型態的物品。本研究即是探討箱子除容量外並加上類別數量之限制。裝箱問題是一個 NP-hard 的問題，所以分類限制裝箱問題亦是NP-hard 的問題。
有許多學者致力於探討該如何在裝箱問題中符合容量及分類限制下，使用的最少箱子數量來處理所有物品。在此類的問題的研究文獻中，大都也提出了相當多的求解策略與方式，但都以近似演算法為主，並且鮮少有考慮到箱子裝載率。因此在本論文中，利用將較大重量物品平均分配到各箱子中，減少大重量物品佔用箱子的容量，降低小重量物品在類別限制下需要使用較多箱子數，在箱子之容量和類別限制下求得兩者最大使用率來降低箱子的使用數。根據實驗的結果，平均裝載啟發式演算法和一些啟發式演算相比較，可以較少箱子數來裝載所有之物品。
蟻族最佳化演算法(Ant Colony Optimization, ACO) 最早是Marco Dorigo於1991為解決旅行銷售員問題(Traveling Salesman Problem, TSP)所提出，乃由模擬蟻群透過費洛蒙(Pheromone)覓食的合作行為而來，其已成功地應用到各種不同的組合問題上。蟻族最佳化演算法也來解裝箱問題，例如：一維、二維等裝箱問題。本論文則是第一個運用蟻族最佳化演算法來解分類限制裝箱問題。首先，以物品的重量為啟發式值，配合使用「較佳較差界限法」將螞蟻建構的解分成較佳、一般和較差三區段。其次，依照優加劣減原則對於較佳區段增加其費洛蒙量，反之，對於較差區段的費洛蒙則減少之。最後，以鄰域搜尋法改進螞蟻所建構的解以減少箱子數，其方法共包括2-2 exchange、2-1 exchange、1-1 exchange 等數種。實驗的結果顯示本論文所提出的方法在結果與效能上皆優於其他的啟發式演算法。

The Bin Packing Problem (BPP) has been one of the fundamental problems of combinatorial optimization since it was first proposed. It has received extensive attention from researchers because of its wide range of applications and its significant economic value. One-dimensional BPP was the original Bin Packing Problem; however several other versions of BPP have also been derived, such as two-dimensional BPP, three-dimensional BPP, and the Class Constrained Bin Packing Problem. These BPPs have seen application in industrial production management, multi-media storage systems and resource allocation, among other areas.
In the BPP, the limitations of a bin can be size, weight, area size, bulk or class. These factors constrain the number of different types of items which are able to be packed into bins. This study concerns the Class Constrained Bin Packing Problem (CCBP). The BPP is an NP-hard problem; the CCBP is also an NP-hard problem.
There has been considerable research into this area, which has generated extensive results about how to meet capacity class constraints for the BPP, and about the minimum number of bins used to pack items. The published literature backing up such results has proposed a number of strategies and methods. They all adopt approximation algorithms, and seldom consider the amount of occupied capacity of each bin. In this study, we separate the large size of items into small size of items and pack them into a specific number of bins averagely. It is able to put more small size of items into a bin without against the limitation of compartment constraints. The Average Loading (AL) algorithm increases not only the capacity usage of each bin but also the usage of compartments of each bin, and reduces the number of bins needed to pack all items. In comparison with other methods, our approach is more efficient at limiting the number of bins used.
Meta-heuristics is a newly-developed optimization algorithm. Its major concept is inspired by the world of nature. Ant Colony Optimization (ACO) is one of its main examples. ACO was submitted by Marco Dorigo as a method of solving the Traveling Salesman Problem (TSP) in 1991. He simulated the behavior of ants searching for food along a pheromone trail. ACO has since been applied to many kinds of combinatorial problems including BPP. There are many research papers that have used ACO to solve one-dimensional BPP, two-dimensional BPP and other Bin Packing Problems. For the CCBP, this is the first study using ACO to solve this problem. In the initial step, we take the size of items as the heuristic value and use the MAX-MIN Ant System to group the solutions constructed by ants into three segments, the superior, the normal and the inferior. Secondly, we updated the pheromone trails by adding to the superior segment and subtracting from the inferior segment. Finally, we apply the local search method to improve the solution by 2 to 2 exchange, 2 to 1 exchange, 1 to 1 exchange, etc. The experimental results for the number of bins packed shows that our algorithm is more efficient than other heuristic methods.

[1] Changra, A. K., Hirschberg, D. S. and Wong, C. K., “Bin packing with geometric constraints in computer network design”, Operation Research, Vol. 26, No. 5, pp. 760-772 (2002).
[2] Van De Vel, H. and Sun, S. J., “An application of the bin packing technique to job scheduling on uniform processors”, Operation Research, Vol. 42, No. 2, pp.169-172, 1991.
[3] Boutevin, C., Gourgand, M. and Norre, S., “Bin packing extensions for solving an industrial line balancing problem”, Proceedings of the 5th IEEE International Symposium on Assembly and Task Planning, Vol. 23, pp. 115-121 (2003).
[4] Mongeau, M. and Bes, C., “Optimization of aircraft container loading”, IEEE on Aerospace and Electronic Systems, Vol. 39, pp. 140-150 (2003).
[5] Martello, S. and Toth, P., “Knapsack Problems, Algorithms and Computer Implementations”, John Wiley and Sons Ltd: England, (1990).
[6] Falkenauer, E., “A hybrid grouping genetic algorithm for bin packing”, Journal of Heuristics, Vol. 2, No. 1, pp. 5–30 (1996).
[7] Coffman, E. G., Garey, M. R. and Johnson, D. S., “Approximation algorithms for bin-packing-an updated survey”, Algorithm Design for Computer System Design, Springer Verlag, Wien, Vol. 171, pp. 49–106 (1984).
[8] Scholl, A., Klein, R. and Jürgens, C., “BISON: A FAST HYBRID PROCEDURE FOR EXACTLY SOLVING THE ONE-DIMENSTIONAL BIN PACKING PROBLEM”, Computers Operational Research, Vol. 24, No. 7, pp. 627–645 (1997).

[9] Gupta, J. N. D. and Ho, J. C., “A new heuristic algorithm for the one-dimensional bin-packing problem”, Production Planning & Control, Vol. 10, No. 6, pp. 598–603 (1999).
[10] Fleszar, K. and Hindi, K. S., “New heuristics for one-dimensional bin-packing”, Computers & Operations Research, Vol. 29, pp. 821–839 (2002).
[11] Wäscher, Hausner, G., H. and Schumann, H., “An improved typology of cutting and packing problems”, European Journal of Operations Research, Vol. 183, pp. 1109–1130 (2007).
[12] Epstein, L. and van Stee, R., “Optimal online algorithms for multidimensional packing problems”, SIAM Journal on Computing, Vol. 35, No. 2, pp. 431–448 (2005).
[13] Liu, D. S., Tan, K. C., Huang, S. Y., Goh, C. K. and Ho, W. K., “On solving multiobjective bin packing problems using evolutionary particle swarm optimization”, European Journal of Operational Research, Vol. 190, pp. 357-382 (2008).
[14] Shachnai, H. and Tamir, T., “Polynomial time approximation schemes for class-constrained packing problems”, JOURNAL OF SCHEDULING, Vol. 4, pp. 313–338 (2001).
[15] Xavier, E. C., Miyazawa, F. K., “A one-dimensional bin packing problem with shelf divisions”, Discrete Applied Mathematics, Vol. 156, pp. 1083-1096 (2008).
[16] Shachnai, H. and Tamir, T., “On two class-constrained versions of the multiple knapsack problem”, Algorithmica, Vol. 29, No. 3, pp. 442–467 (2001).
[17] Peeters, M. and Degraeve, Z., “The co-printing problem: A packing problem with a color constraint”, Operations Research, Vol. 52, No. 4, pp. 623–638 (2004).
[18] Shachnai, H. and Tamir, T., “Multiprocessor scheduling with machine allotment and parallelism constraints”, Algorithmica, Vol. 32, No. 4, pp. 651–678 (2002).
[19] Wolf, J. L., Wu, P. S., and Shachnai, H., “Disk load balancing for video-on-demand-systems”, ACM Multimedia Systems Journal, Vol. 5, pp. 358–3706 (1997).
[20] Shachnai, H. and Tamir, T., “Tight bounds for online class-constrained packing”, Theoretical Computer Science, Vol. 321, pp. 103–123 (2004).
[21] Fleszar, K. and Charalambous, C., “Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem”, European Journal of Operational Research, Vol. 210, pp. 176–184 (2011).
[22] Bennell, J. A., Lee, L. S. and Potts, C. N., “A Genetic Algorithm for Two-Dimensional Bin Packing with Due Dates”, International Journal of Production Economics, Vol. 145, No. 2, pp. 547-560 (2013).
[23] Xavier, E. C. and Miyazawa, F. K., “The class constrained bin packing problem with applications to video-on-demand”, Theoretical Computer Science, Vol. 393, pp. 240–259, (2008).
[24] Dorigo M., Maniezzo, V. and Colorni, A., “Positive Feedback as a Search Strategy”, Technical Report 91-016, Dip. Elettronica, Politecnico di Milan, (1991).
[25] Dorigo, M. and Gambardella, L. M., “Ant Colony System: A cooperative Learning Approach to the Traveling Salesman Problem”, IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 53–66 (1997).
[26] Bullnheimer, B., Hartl, R. F. and Straus, C., “A new rank based version of the ant system: A computational study”, Working paper, University of Vienna, Austria, (1997).
[27] Taillard, E. D. and Gambardella, L. M., “Adaptive Memories for the Quadratic Assignment Problem”, Technical report IDSIA-87-97, IDSIA, Lugano, (1997).
[28] Stützle, T. and Hoos, H., “MAX MIN Ant System”, Journal of Future Generation Computer Systems, Vol. 16, pp. 889-914 (2000).
[29] Levine, J. and Ducatelle, F., “Ants Can Solve Difficult Bin Packing Problems”, Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications, Nottingham, UK, (2003).
[30] Falkenauer, E. and Dwlchambre, A., “A genetic algorithm for bin packing and line balancing”, Proceedings of the IEEE International Conference on Robotics and Automation, IEEE Press, Piscataway, NJ, USA, pp. 1186-1192 (1992).