Una nueva estrategia heurística para el problema de Bin Packing

• Joaquín Pérez-Ortega ^[1] ; Hilda Castillo-Zacatelco ^[1] ; Darnes Vilariño-Ayala ^[3] ; Adriana Mexicano-Santoyo ^[4] ; José Crispín Zavala-Díaz ^[2] ; Alicia Martínez-Rebollar ^[1] ; Hugo Estrada-Esquivel ^[5]
  1. [1] Centro Nacional de Investigación y Desarrollo Tecnológico

     Centro Nacional de Investigación y Desarrollo Tecnológico

     México

     
  2. [2] Universidad Autónoma del Estado de Morelos

     Universidad Autónoma del Estado de Morelos

     México

     
  3. [3] Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación
  4. [4] Instituto Tecnológico de Cd. Victoria
  5. [5] Fondo de Información y Documentación para la Industria

  Mostrar afiliaciones +
• Localización: Ingeniería, investigación y tecnología, ISSN 1405-7743, ISSN-e 2594-0732, Vol. 17, Nº. 2, 2016
• Idioma: español
• DOI: 10.1016/j.riit.2016.06.001
• Títulos paralelos:
  • A New Heuristic Strategy for the Bin Packing Problem
• Enlaces
  • Texto completo
• Resumen
  • español

    El problema de Bin Packing (BPP) es NP-duro, por lo que un método exacto para resolver instancias del BPP requiere un gran número de variables y demasiado tiempo de ejecución. En este trabajo se propone una nueva estrategia heurística para resolver instancias del BPP en donde se garantiza la solución óptima. La estrategia propuesta incluye el uso de un nuevo modelo exacto basado en arcos de flujo. En el modelo propuesto, el número de variables se redujo asignando objetos en contenedores. Adicionalmente se incluye una heurística que mediante el preprocesado de la instancia permite reducir su tamaño y con ello el espacio de búsqueda del algoritmo de solución. Para validar el enfoque propuesto, se realizaron experimentos usando los conjuntos de prueba hard28, 53nirup, bin1data, uniform, triplets y subconjuntos de otras instancias, todos ellos conocidos en el estado del arte. Los resultados muestran que empleando nuestro enfoque es posible encontrar la solución óptima de todas las instancias de prueba. Además, el tiempo de ejecución se redujo en relación con lo reportado por el modelo basado en arcos de flujo. Las reducciones de tiempo fueron de 19.7 y 43% para los conjuntos 53nirup y hard28, respectivamente.

  • English

    The Bin Packing problem (BPP) is NP-hard, the use of exact methods for solving BPP instances require a high number of variables and therefore a high computational cost. In this paper a new heuristic strategy for solving the BPP instances, which guarantees obtain optimal solutions, is proposed. The proposed strategy includes the use of a new model based on flow arcs. In the proposed model, the number of variables was reduced by previous allocation of objects in bins. Additionally, our approach includes a heuristic that allows reducing the instance size and thereby the solution algorithm search space. To validate the proposed approach, experiments were performed using the test sets hard28, 53nirup, bin1data and falkenauer, all of them well known in the state of the art. The results show that it using our approach is possible to find the optimal solution for all test set. Also, the execution time was reduced in regard the reported time obtained by using the flow arc model. Time reductions were up to 19.7 and 43% for 53nirup and hard28 test set, respectively.

• Referencias bibliográficas
  • Álvarez, V.M.. (2006). Modelo para representar la complejidad del problema y el desempeño de algoritmos. Instituto Tecnológico de Ciudad Madero....
  • Alves, F.D.. (2012). Bin packing and related problems:pattern-based approaches. Faculdade de Ciencias, Universidade do Porto. Portugal.
  • Alvim, A.C.F.,Glover, F.,Ribeiro, C.C.,Aloise, D.J.. (2004). A hybrid improvement heuristic for the Bin Packing problem. Journal of Heuristics....
  • Balas, E.. (1979). Disjuntive programming. Annals of Discrete Mathematics. 5. 3-51
  • Burke, E.K.,Hyde, M.R.,Kendall, G.. (2010). Providing a memory mechanism to enhance the evolutionary design of heuristics. Proceedings of...
  • Cambazard, H.,O’Sullivan, B.. Propagating the bin packing constraint using linear programming, CP’10. 16international conference on Principles...
  • Cruz, L.. (2004). Clasificación de algoritmos heurísticos para la solución de problemas de Bin Packing. Centro Nacional de Investigación y...
  • Falkenauer, E.. (1996). A hybrid grouping genetic algorithm for Bin Packing. Journal of Heuristics. 2. 5-30
  • Garey, M.R.,Johnson, D.S.. (1979). Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company. Nueva...
  • Jarboui, B.,Ibrahim, S.,Rebai, A.. (2010). A new destructive bounding scheme for the bin packing problem. Annals of Operations Research. 179....
  • LINGO user’s guide. Lindo Systems INC., USA, 2008.
  • Martello, S.,Toth, P.. (1990). Knapsack problems. Algorithms and computer. Implementations. DEIS University of Bologna. Inglaterra.
  • Mexicano, A.. (2004). Caracterización de conjuntos de instancias difíciles del problema de Bin Packing orientada a la mejora de algoritmos...
  • Pérez, J.,Castillo, H.,Vilariño, D.,De-la-Rosa, R.,Mexicano, A.,Zavala, J.C.,Santaolaya, R.,Estrada, H.. (2014). Metaheuristic for selecting...
  • Schaus, P.. (2009). Solving balancing and Bin Packing problems with constraint programming.
  • Shaw, P.. (2004). A constraint for bin packing. 648-662
  • Schoenfields, J.E.. (2002). Fast, exact solution of open packing problems without linear programming. US Army Space & Missile Defense...
  • Scholl, A.,Klein, R.,Jürgens, C.. (1997). BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers...
  • Schwerin, P.,Wäscher, G.. (1999). A new lower bound for the Bin Packing problem and its integration into MTP. Pesquisa Operacional. 19. 111
  • Taha, H.A.. (2004). Investigación de operaciones y flujo en redes. 5. Alfaomega.
  • Valerio-De Carvalho, J.M.. (1999). Exact solution of bin packing problems using column generation and branch and bound. Annals of Operation...
  • Valerio-De Carvalho, J.M.. (2002). LP models for bin packing and cutting stock problems. European Journal of Operational Research. 141. 253