This repository contains implementations of various metaheuristic algorithms to solve the bin packing problem. The bin packing problem involves efficiently packing a set of items of varying sizes into a finite number of bins, minimizing the number of bins used. This problem is NP-hard and has significant practical applications in logistics, manufacturing, and resource allocation.
The bin packing problem can be formally defined as follows: given a set of items, each with a specific size, and a set of bins, each with a fixed capacity, the goal is to pack all the items into the minimum number of bins without exceeding the capacity of any bin.
These algorithms focus on solving the one-dimensional bin packing problem by iteratively improving a single candidate solution.
Simulated Annealing is inspired by the physical process of heating a material and then slowly lowering the temperature to decrease defects, thus finding a minimum energy state. The algorithm starts with a random solution and makes random changes, accepting worse solutions with a probability that decreases over time.
Tabu Search uses a memory structure called a tabu list to store previously visited solutions to avoid cycles. It iteratively moves from one solution to another, seeking to improve while avoiding solutions on the tabu list.
GRASP is a multi-start or iterative process where each iteration consists of two phases: construction and local search. The construction phase builds a feasible solution, and the local search attempts to improve it.
These algorithms are designed to solve the two-dimensional bin packing problem by evolving a population of solutions.
Genetic Algorithms are inspired by the process of natural selection. They use techniques such as selection, crossover, and mutation to evolve solutions to problems. The population of solutions evolves over generations.
ACO is inspired by the behavior of ants searching for food. Ants deposit pheromones on paths they travel, and these pheromones guide subsequent ants towards promising solutions.
PSO is inspired by the social behavior of birds flocking or fish schooling. It optimizes a problem by iteratively improving a candidate solution with regard to a given measure of quality.
The algorithms were executed on a system with the following specifications:
- Processor: Intel(R) Core(TM) i7-7500U CPU @ 2.70GHz
- Memory: 8 GB RAM
The performance of each algorithm was evaluated based on solution quality and computational time. Detailed results and comparisons are available in the report included in this repository.