Solving the Rectangular Packing Problem by a New Bottom-Left Placement Method Incorporated with a Multi-Start Local Search

• Autorzy: Wetweerapong J. , Remsungnen T.
• Języki publikacji: EN

Abstrakty

EN

This paper presents a new Bottom-Left placement method for the rectangular packing problem. It is a modified version of the Row-Column Search (RCS) placement method for a faster packing. Incorporated with some improvement heuristics and a simple local search (LS), it is found to be quite efficient in solving easy to moderate packing problems. For the difficult packing problems, a multi- start mechanism is added in order to enable the packing process to overcome getting trapped to a local optimal solution. Testing on some well-known packing instances in the literature shows results that are both satisfied and informative.

Słowa kluczowe

EN

Rectangular packing; local search; heuristics

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2010
• Tom: Vol. 35, No. 2
• Strony: 127--141
• Opis fizyczny: Bibliogr. 29 poz.

Twórcy

autor

Wetweerapong J.

autor

Remsungnen T.

Bibliografia

• [1] Alberto G., David F., Solving the packing and strip-packing problem with genetic algorithms. Lecture Notes in Computer Science: Foundations and Tools for Modeling, Springer Berlin/Heidelberg, 1606, 1999, 709-718.
• [2] Alberto G., David F., Resolution of strip-packing problems with genetic algorithms. Journal of the Operational Research Society, 51, 2000, 1289-1295.
• [3] Andreas B., A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. European Journal of Operational Research : Discrete Optimization, 17, 2006, 814-837.
• [4] Alvarez-Valdes R., Parreno F., Tamarit JM., A GRASP algorithm for constrained two-dimensional non-guillotine cutting problem. Journal of the Operational Research Society, 56, 2005, 414-425.
• [5] Alvarez-Valdes R., Parreno F., Tamarit JM., A tabu search algorithm for a two-dimensional non-guillotine cutting problem. European Journal of Operational Research, 183, 2007, 1167-1182.
• [6] Bekrar A., Kacem I., Chu C., Sadfi C., A branch and bound Algorithm for solving the 2D strip packing problem. IEEE Transactions on Computers, 2006, 1-4244-0451.
• [7] Bekrar A., Kacem I., and Chu C., A comparative study of exact algorithms for the two dimensional strip packing problem. Journal of Industrial and Systems Engineering, 1, 2, 2007, 151-170.
• [8] Bekrar A., Kacem I., A Comparison study of heuristics for solving the 2D guillotine strip and bin packing problems. IEEE Transactions on Computers, 2008, 978-1-4244-1672
• [9] Burke E., Kendall G., Whitwell G., A new placement heuristic for the orthogonal stock-cutting problem. Operations Research, 52, 4, 2004, 655-671.
• [10] Burke E., Hyde M., Kendall G., Woodward J., A genetic programming hyperheuristic approach for evolving two dimensional strip packing heuristics. ASAP research group, 2008.
• [11] Chazelle B., The bottom-left bin-packing heuristic : an efficient implementation. IEEE Transactions on Computers, 32, 1983, 697-707.
• [12] Chen D., Huang W., A novel quasi-human heuristic algorithm for two-dimensional rectangle packing problem. International Journal of Computer Science and Network Security, 6, 12, 2006, 115-120.
• [13] Chen M., Huang W., A two-level search algorithm for 2D rectangular packing problem. Computer & Industrial Engineering, 53, 2007, 123-136.
• [14] Christine L., Pearl W., Heuristic for large strip packing problem with guillotine pattern: an empirical study. MIC 2001 - 4th Metaheuristics International Conference, Portugal, July 16-20, 2001.
• [15] Dyckhoff H., A topology of cutting and packing problem. European Journal of Operational Research, 44, 1990, 145-59.
• [16] Hifi M., M'Hallah R., A hybrid algorithm for the two-dimensional layout problem: the case of regular and irregular shapes. International Federation of Operational Research Societies, Blackwell Publishing Ltd., 10, 2003, 195-216.
• [17] Hopper E., Turton B., A review of the application of meta-heuristic algorithm to 2D strip packing problems. Artificial Intelligence Review, 16, 2001, 257-300.
• [18] Hopper E., Turton B., An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research, 128, 1, 2001, 34-57.
• [19] Jakobs S., On genetic algorithms for the packing of polygons. European Journal of Operational Research, 88, 1996, 165-181.
• [20] Jiang JQ., Liang YC., Shi XH., Lee HP., A hybrid algorithm based on PSO and SA and its application for two-dimensional non-guillotine cutting stock problem. Springer-Verlag Berlin-Heidelberg, 2004, 666-669.
• [21] John E., Christine L., Developing an aCe solution for two-dimensional strip packing. Proceedings of the 18th international Parallel and Distributed Processing Symposium (IPDPS'04), IEEE, 2004.
• [22] Leung TW., Chan CK., Troutt MD., Application of a mixed simulated annealing-genetic algorithm for the two-dimensional orthogonal packing problem. Discrete Optimization, 145, 2003, 530-542.
• [23] Liu D., Teng H., An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. European Journal of Operational Research, 112, 1999, 413-420.
• [24] Pablo G., Maria R., An evolutionary hyperheuristic to solve strip-packing problems. Springer-Verlag Berlin Heidelberg, LNCS 4881, 2007, 1109-1130.
• [25] Wäscher G., Haubner H., Schumann H., An improved typology of cutting and packing problems. European Journal of Operation Research, 183, 2007, 406-415.
• [26] Wei L., Zhang D., Chen Q., A least wasted first heuristic algorithm for the rectangular packing problem. Computer & Operations Research, 36, 2009, 1608-1614.
• [27] Wu YL., Chan CK., On improved least flexibility first-heuristics superior for packing and stocking cutting problems. Springer-Verlag Berlin-Heidelberg, 2005.
• [28] Zhang D., Kang Y., Deng A., A new heuristic recursive algorithm for the strip rectangular packing problem. Computer & Operations Research, 33, 2006, 2209-2217.
• [29] Zhang D., Chen SD., Liu YJ., An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem. Acta Automatica Sinica, 33, 9, 2007, 911-916.