2D Strip Packing Problem Solution using Genetic Algorithm

The 2D offline strip packing problem involves arranging rectangles of varying dimensions within a larger strip so as to minimize unused space. Our calculator uses a genetic algorithm to find an optimal solution to this problem, making it an efficient tool for those facing this challenge.

Here is the problem definition from wikipedia: given a set of axis-aligned rectangles and a strip of bounded width and infinite height, determine an overlapping-free packing of the rectangles into the strip minimizing its height. This problem is a cutting and packing problem and is classified as an Open Dimension Problem according to Wäscher et al.¹.

To use the calculator, simply enter the strip width and the rectangles to be packed. For simplicity, assuming there are number of rectangles with the same dimensions, you enter them one type per line, using width x height x quantity notation. After that you can play with genetic algorithm parameters (if you want to) - tweak the population size, the number of generations and the chance of random mutation. The genetic algorithm will then calculate the arrangement that minimizes the unused space. You can read about the genetic algorithm below the calculator.

This calculator is ideal for those in industries such as packaging, distribution, and logistics, where optimizing space utilization is crucial. The results of the calculator can also be useful for anyone seeking to solve the 2D offline strip packing problem in an efficient and effective manner.

2D Strip Packing Problem Solution using Genetic Algorithm

Strip Width

Rectangles to Pack

4x72x1 4x30x1 26x60x2 36x52x1

Width x Height x Quantity

Evolution Parameters

Population Size

Number of Generations

Mutation Chance

Calculate

Packing Height

 

Optimal Height

 

Approximation Ratio

 

Area Waste

 

Calculation precision

Digits after the decimal point: 2

The file is very large. Browser slowdown may occur during loading and creation.

Download 

 Link  Save  Widget

Genetic Algorithm

Although there are exist polynomial time approximation algorithms with proven approximation guarantee (refer to the Wikipedia article mentioned above), I decided to use genetic or evolutionary algorithm. It does not guarantee an optimal solution, or even an upper-bounded solution ("upper-bounded" is then you have guarantee that the found solution will be not worse than 2 optimal heights, for example), but it is usually able to find a solution, good enough for any practical purposes. Besides, generally speaking, it is very easy to implement, compared to other algorithms.

The basic idea of genetic algorithm is very simple: you generate the set of random solution, then you calculate the fitness score for each solution, using a fitness function. Then you use the survival of the fittest principle: only the fittest solutions (f.e. top 50%) produce the new generation, when the algorithm produces children by combining the 'genes' of their parents. Also, to prevent the algorithm from being stuck in an suboptimal solution, some randomness is introduced in the form of the gene's mutation, which gives the algorithm the chance to escape the local maximum. That's it. Simple as that. As with other heuristic algorithms, there is no guarantee that is will be able to reach the good solution, you just run it and cross your fingers. If the end result looks like it is not good enough for you, you run the algorithm again and again, may be tweaking the number of generations or the population size until you are satisfied with the result. You can even just try several times without tweaking anything, because each time the algorithm starts from the set of random solutions, and you probably will get the different result anyway.