2D Bin Packing Solver

A Python-based solver for the 2D irregular bin packing problem using BRKGA (Biased Random-Key Genetic Algorithm) with bottom-left placement heuristic.

Overview

This project solves the irregular bin packing problem where convex and non-convex polygons must be packed into rectangular containers while minimizing the number of bins used. The solver uses No-Fit Polygons (NFPs) for efficient collision detection and geometric operations.

Features

• BRKGA Optimization: Evolutionary algorithm for finding near-optimal packing sequences
• Bottom-Left Placement: Fast placement heuristic for positioning polygons
• NFP Caching: Pre-computed No-Fit Polygons for efficient collision detection
• Multi-bin Support: Handles instances requiring multiple containers
• Rotation Support: Configurable rotation angles for each polygon type
• Parallel Processing: Multi-core evaluation for faster convergence
• Visualization Tools: Plot solutions, convergence curves, and solution history

Project Structure

geometry/          # Polygon representation, NFP operations, container definitions
placement/         # Bottom-left placer and solution management
solvers/           # BRKGA optimizer implementation
datasets/          # Benchmark instances (Terashima, Dighe)
*_results/         # Output results and plots

Supported Datasets

• Terashima2: 480 irregular test instances with known optimal solutions
• Dighe: Additional benchmark instances

Usage

Basic usage example:

from extract import load_dataset_instance
from geometry.polygon import create_instances_from_types
from geometry.nfp_cache import create_nfp_cache
from solvers.brkga import BRKGAOptimizer

# Load dataset
polygon_types, container = load_dataset_instance("dighe", "dighe2")

# Create instances and NFP cache
instances = create_instances_from_types(polygon_types)
nfp_cache = create_nfp_cache(polygon_types)

# Run optimizer
optimizer = BRKGAOptimizer(
    instances=instances,
    container=container,
    nfp_cache=nfp_cache,
    pop_size=100,
    max_bins=10
)

solution = optimizer.run(generations=1000, verbose=True, parallel=True)
print(f"Bins used: {solution.get_statistics()['bins_used']}")

Batch Testing

Run multiple instances and collect statistics:

python batch_testing.py

Results are saved to CSV files with plots generated for each solution.

Requirements

• Python 3.x
• NumPy
• Matplotlib
• PyClipper
• pyparsing

Algorithm

The solver combines:

1. BRKGA for evolving packing sequences (order and rotation)
2. Bottom-left heuristic for deterministic placement
3. NFP-based collision detection using integer arithmetic
4. Falkenauer fitness function for multi-bin optimization

License

For academic and research purposes.