This video demonstrates the running process for a 2D implementation of a greedy two-level search algorithm for the 2D rectangular packing problem - following the process outlined in Chen and Huang (2007) (see sources).
In the right pane is an overview of all the rectangles that are to be packed. The rectangles colored in blue are the boxes that have not yet been packed, and the ones colored grey have already been packed into the left pane.
The left pane is the packing area, where the goal is to fit in as many of the boxes from the right pane as possible. The algorithm is said to converge successfully if all the boxes are packed in the left pane with no gaps.
The rectangles are placed into the container one by one and each rectangle is packed at a position by a corner-occupying action so that it touches at least two items without overlapping other already packed rectangles. At the first level of the algorithm, a simple algorithm called A0 selects and packs one rectangle according to the highest degree first rule at every iteration of packing. At the second level, A0 is itself used to evaluate the benefit of a CCOA more globally.
The algorithm is implemented in python using matplotlib for visualization where the running time has been slowed for the sake of recording.
Sources:
doi.org/10.1016/j.cie.2007.04...
doi.org/10.1016/S0377-2217(99...
en.wikipedia.org/wiki/Bin_pac...
Source code:
github.com/SebastianBitsch/bi...
29 май 2022
