CODEWITHSUNDEEP
algorithm
Trần Kim Dự
Trần Kim Dự

Reputation: 6102

Simulated Annealing Algorithm to solve Bin Packing

I'm researching about Bin Packing Problem. I currently have implemented this problem in Genetic Programming way. But when I research Simulated Annealing Algorithm for this problem, I don't understand it very well.

Is there any good link or code / psuedocode for this problem.

Upvotes: 1

Views: 2835

Answers (1)

edgarmtze
edgarmtze

Reputation: 25038

First let us define the problem

Pack a set of N = {1, 2, …, n} items, each with size t_i, i =1, 2,…, n, into identical bins, each with capacity C Minimize the number of bins without violating the capacity constraints

So main Outline of Annealing Algorithm will consist on:

  • Construct an initial solution using first-fit decreasing procedure
  • Compute and assign weights to items to distort sizes according to the packing solutions of individual bins
  • Perform local search by swapping items betweenall pairs of bins
  • Carry out re-weighting based on the result of the previous optimization run
  • Reduce weight distortion according to a cooling schedule

Now it is important to do a Neighborhood Search for Bin Packing Problem:

  • From a current solution, obtain the next solution by swapping items between bins with the following objective function (Fleszar and Hindi 2002)

enter image description here

  • Swap schemes Swap items between two bins, then Carry out Swap (1,0), Swap (1,1), Swap (1,2), Swap (2,2) for all pairs of bins.
  • Swap (1,0)

enter image description here - then evaluate only the change in the objective function value

  • Swap (1,1), then Swap (1,2) like: enter image description here

That should give you a start.

Upvotes: 6

Related Questions