Optimization by Ant Colony Hybryde for the Bin-Packing Problem

Authors: Ben Mohamed Ahemed Mohamed, Yassine Adnan

Abstract:

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.

Keywords: Ant colony algorithm, bin-packing problem, heuristics methods.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1072140

References:

[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.