COLLISION FREE REGION DETERMINED USING NON-REGULARIZED BOOLEAN OPERATION AND ITS APPLICATION IN THE IRREGULAR PLACEMENT PROBLEM

摘要

The strip packing problem is a special case of cutting and packing problems and is found on several industries including garment, wood and shipbuilding. When items are irregular, dealing with geometry complexity is one of the main difficulties. Collision free region concept was adopted as a geometric tool to ensure that items do not collide and do not protrude from the container. It represents all possible translations for an item to be inserted into a container with already placed items and is determined using non-regularized Boolean operations involving no-fit polygons. With a newly developed robust non-regularized Boolean operation algorithm, it is possible to detect exactly fitting and exactly sliding placements, which are represented by degenerated boundaries in the collision free region. These positions are valuable to the packing problem, as they often represent local optima placement. In conjunction with collision free region, simulated annealing was used to solve the strip packing problem. The results obtained using benchmark problems showed to be very competitive, achieving the most compact layouts in some cases.