Graph search approach to rectangle packing problem

• Autorzy: Korzeń M. , Klęsk P.
• Języki publikacji: EN

Abstrakty

EN

A rectangle packing problem is considered, where the goal is to suitably arrange a subset of given rectangles within a container so that the area of wastes (uncovered spaces) is the smallest. We propose a reduction of this problem to a graph search problem and show possible solving approaches by means of well known BFS, Dijkstra’s and A* algorithms. We explain the way we construct search graphs for the problem, taking under consideration two main variants: (1) with arbitrary straight-line cuts, (2) with straight-line cuts which must go along the whole length or width of the remaining container — ‘full cuts’. We also give some insights on: optimization criterion, search stopping condition and heuristics we use. Finally, we present results of experiments carried out.

Słowa kluczowe

EN

Rectangle Packing Problem; graph search algorithm; search heuristics

PL

Problem Pakowania Bloków; algorytm przeszukiwania grafu; heurystyka wyszukiwania

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2015
• Tom: Vol. 23, nr 1
• Strony: 47--62
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Korzeń M.

• West Pomeranian University of Technology, Faculty of Computer Science and Information Technology, ul. Żołnierska 49, 71-210 Szczecin, Poland

autor

Klęsk P.

• West Pomeranian University of Technology, Faculty of Computer Science and Information Technology, ul. Żołnierska 49, 71-210 Szczecin, Poland

Bibliografia

• [1] Huang, E. and Korf, R. E., Optimal Rectangle Packing: An Absolute Placement Approach, J. Artif. Intell. Res. (JAIR), Vol. 46, 2013, pp. 47–87.
• [2] Scheithauer, G. and Sommerweiss, U., 4-Block Heuristic for the Rectangle Packing Problem, European Journal of Operational Research, Vol. 108, 1996, pp. 509–526.
• [3] Korf, R., Optimal Rectangle Packing: Initial Results. In: ICAPS, edited by E. Giunchiglia, N. Muscettola, and D. S. Nau, AAAI, 2003, pp. 287–295.
• [4] Huang,W. and Chen, D., An efficient heuristic algorithm for rectangle-packing problem, Simulation Modelling Practice and Theory, Vol. 15, No. 10, 2007, pp. 1356–1365.
• [5] Hart, P., Nilsson, N., and Raphael, B., A Formal Basis for the Heuristic Determination of Minimum Cost Paths, Systems Science and Cybernetics, IEEE Transactions on, Vol. 4, No. 2, 1968, pp. 100–107.
• [6] Pearl, J., Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
• [7] Hansson, O., Mayer, A., and Yung, M., Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models, Tech. Rep. CUCS-219-85, Department of Computer Science, Columbia University, New York, USA, 1985.
• [8] Russell, S. and Norvig, P., Artificial Intelligence: A Modern Approach, Prentice Hall, 2002.
• [9] Dijkstra, E., A note on two problems in connexion with graphs, Numerische Mathematik, Vol. 1, No. 1, 1959, pp. 269–271.