Optimization by Ant Colony Hybryde for the Bin-Packing Problem

The problem of bin-packing in two dimensions (2BP) consists in placing a given set of rectangular items in a minimum number of rectangular and identical containers, called bins. This article treats the case of objects with a free orientation of 90Ôùª. We propose an approach of resolution combining optimization by colony of ants (ACO) and the heuristic method IMA to resolve this NP-Hard problem.

• Ben Mohamed Ahemed Mohamed
• Yassine Adnan

• Ant colony algorithm
• bin-packing problem
• heuristics methods.

[1] Berkey & Wang 1987BERKEY J.O. AND WANG P.Y., Two dimensional
finite bin-packing algorithms, Journal of Operational Research Society,
38(5), 1987, pp 423-429.
[2] [Garey & Johnson 1982]CHUNG F., GAREY M. AND JOHNSON D., On
packing two-dimensional bins, SIAM Journal on Algebraic and Discrete
Methods, 1982, 3, pp 66-76.
[3] DORIGO M.,MANIEZZO V. AND COLORNI A., The ant system : Optimization
by a colony of cooperating agents, IEEE T Syst Man Cy B,
26, 1996, pp 29-71
[4] H. DYCKHOFF A typology of cutting and packing problems, European
Journal Of Operational Research, 44, 1990, pp 145-159.
[5] HOPPER, E., TURTON, B.C.H.,An empirical investigation of metaheuristic
and heuristic algorithms for a 2d packing problem. European
Journal of Operational Research 128 (1), 3457.
[6] JKOBS, S.,On genetic algorithms for the packing of polygons., European
Journal of Operational Research 88, 165181.
[7] J. LEVINE AND F. DUCATELLE , An Ant Colony optimization and
local search for bin packing and cutting stock problems, Journal of
Operational Research Society, vol. 55, 2004, pp 705-716
[8] J. EL HAYEK, A. MOUKRIM, ET S. NEGRE., New resolution algorithm
and pretreatments for the two-dimensional bin-packing problem, Computers
and Operations Research , 2006.
[9] Lesh, N., Marks, J., McMahon, A., Mitzenmacher, M., Exhaustive
approaches to 2d rectangular perfect packings. Information Processing
Letters 90 (1), 714.
[10] Leung, T.W., Chan, C.K., Troutt, M.D., Application of a mixed simulated
annealing-genetic algorithm heuristic for the two-dimensional orthogonal
packing problem. European Journal of Operational Research 145 (3),
530542.
[11] [Lodi, Martello & Vigo 2002]LODI A., MARTELLO S. AND VIGO D.,
Recent advances on two-dimensional bin packing problems, Discrete
applied mathematics, 123, 2002a, pp 379-396.
[12] Lodi A, Martello S, Vigo D., Heuristic and metaheuristic approaches for
a class of two-dimensional bin packing problems. INFORMS Journal on
Computing 1999;11:34557.
[13] S. MARTELLO, I.H. OSMAN, C. ROUCAIROL (EDS.), Metaheuristics
: Advances and Trends in Local Search Paradigms for Optimization,
Kluwer academic Publishers, Boston, 1998, pp 125-139.
[14] S. MARTELLO ET D. VIGO.,Exact solution of the two-dimensional finite
bin packing problem., Management Sci., 44 :388-399, 1998.
[15] WASCHE, G., HAUSSNER, H., SCHUMANN, H.,An improved typology
of cutting and packing problems, European Journal of Operational
Research, this issue, doi:10.1016/j.ejor.2005.12.047.