Skip to content

Steinberg algorithm with two heuristics for Strip Packing Problem

License

Notifications You must be signed in to change notification settings

yzdxdydz/strip-packing

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

28 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Steinberg Algorithm for Strip Packing Problem with two heuristics

This project implements the Steinberg algorithm for solving the strip packing problem in Python. (see A. Steinberg, 1997) We also provide two heuristics: ''removing gaps'' and ''dropping hanging rectangles''. See documentation and examples.

Installation

Clone the repository and install the dependencies:

git clone https://github.com/yzdxdydz/strip-packing.git
cd strip-packing
pip install -r requirements.txt

Usage

To execute the packing algorithm, follow these steps:

  1. Import the SteinbergPacking class from the src/steinberg module.
from src.steinberg import SteinbergPacking
  1. Create an instance of the SteinbergPacking class with the desired parameters. For example for original algorithm.
sp = SteinbergPacking(width=10, without_gaps=False, drop_hanging_element=False)
  1. Call the get_packing method, passing in the list of elements to be packed.
elements = [[1, 1], [1, 1], [10, 8], [3, 1], [9, 1], [2, 1], [1, 1], [3, 1]]
#Optimal height H_opt = 10 can be provided with the packing 
# [9, 9], [8, 9], [0, 0], [5, 9], [0, 8], [3, 9], [9, 8], [0, 9].  
sp.get_packing(elements)
  1. Calculate the height, plot the packing and save it to file.
from random import randint
colors = []
for _ in elements:
    colors.append('#%06X' % randint(0, 0xFFFFFF))
sp.plot_packing(colors, "figure-1.png")
print("Height: ", sp.max_height())
  1. Then Steinberg algorithm provides height H_1=18.25. The plot is Alt text

  2. For ''Removing gaps'' algorithm,

sp = SteinbergPacking(width=10, without_gaps=True, drop_hanging_element=False)
sp.get_packing(elements)
sp.plot_packing(colors, "figure-2.png")
print("Height: ", sp.max_height())
  1. ''Removing gaps'' algorithm provides height H_2=13.0. Alt text

  2. To ''Drop hanging elements'',

sp = SteinbergPacking(width=10, without_gaps=True, drop_hanging_element=True)
sp.get_packing(elements)
sp.plot_packing(colors, "figure-3.png")
print("Height: ", sp.max_height())
  1. ''Drop hanging elements'' algorithm provides height H_3=12.0. Alt text

Documentation

For detailed information on the algorithm, please refer to the documentation strip-packing.pdf

Releases

No releases published

Packages

No packages published

Languages