Combining Metaheuristics and Integer Linear Programming: A Hybrid Methodology Applied to the Container Loading Problem

• Napoleão V. Nepomuceno UNIFOR
• Plácido R. Pinheiro UNIFOR
• André L. V. Coelho UNIFOR

Abstract

This paper presents a hybrid framework for coping with hard combinatorial optimization problems, which is based upon a methodology combining heuristic and exact methods. In this framework, a metaheuristic engine works as a generator of reduced instances for the problem, which are formulated as mathematical programming models. These instances, in turn, are solved by an exact optimization technique, and the performance measures accomplished by the respective models are interpreted as score values by the metaheuristic, thus guiding its search process. As a means to assess the potentialities behind the novel approach, we provide an instantiation of the framework to deal specifically with the container loading problem.

References

Bischoff, E. and Ratcliff, M. (1995). “Issues in the Development of Approaches to Container Loading,” Omega 23, p. 377-390.

Blesa, M.J. et al. (2005). “Hybrid Metaheuristics.” In: 2nd International Hybrid Metaheuristics Workshop, LNCS 3636, p. VI-VII.

Morabito, R. and Arenales, S. (1997). “Abordagens para o Problema do Carregamento de Contêineres,” Pesquisa Operacional 17, p. 29-56.

Nepomuceno, N.V. (2006). “Combinação de Metaheurísticas e Programação Linear Inteira: uma Metodologia Híbrida Aplicada ao Problema de Carregamento de Contêineres.” M.Sc. Dissertation, UNIFOR, Available at [link].

Nepomuceno, N.V., Pinheiro, P.R. and Coelho, A.L.V. (2006). “Aplicação de uma Metodologia Híbrida ao Problema de Carregamento de Contêineres.” In: XXXVIII Simpósio Brasileiro de Pesquisa Operacional, p. 1596-1603.

Nepomuceno, N.V., Pinheiro, P.R. and Coelho, A.L.V. (2006). “Metaheurística e Programação Linear Inteira: Um Algoritmo Híbrido para o Problema de Carregamento de Contêineres.” In: XIII Congreso Latino-Iberoamericano de Investigación Operativa.

Nepomuceno, N.V., Pinheiro, P.R. and Coelho, A.L.V. (2007). “Tackling the Container Loading Problem: A Hybrid Approach Based on Integer Linear Programming and Genetic Algorithms.” In: 7th European Conference on Evolutionary Computation in Combinatorial Optimization, LNCS 4446, p. 154-165.

Nepomuceno, N.V., Pinheiro, P.R. and Coelho, A.L.V. "The 'Generate-and-Solve' Hybrid Framework: Combining Heuristic and Exact Methods for Tackling Cutting and Packing Problems." (Invitation to submit a full version for a special issue of Journal of Heuristics devoted to selected works from CLAIO XIII).

Raidl, G.R. (2006). “A Unified View on Hybrid Metaheuristics.” In: 3rd International Hybrid Metaheuristics Workshop, LNCS 4030, p. 1-12.