Un algoritmo de búsqueda local iterada como solución al problema de la mochila

Autores/as

  • Yainier Labrada-Nueva Departamento de Biometría, Centro de Identificación y Seguridad Digital (Cised), Universidad de las Ciencias Informáticas (UCI). Carretera a San Antonio de los Baños km 2.5, Reparto Torrens, Boyeros. La Habana, Cuba. CP 19370
  • Juana Enriquez-Urbano Departamento de Biometría, Centro de Identificación y Seguridad Digital (Cised), Universidad de las Ciencias Informáticas (UCI). Carretera a San Antonio de los Baños km 2.5, Reparto Torrens, Boyeros. La Habana, Cuba. CP 19370
  • Yadían García-Ojito Departamento de Biometría, Centro de Identificación y Seguridad Digital (Cised), Universidad de las Ciencias Informáticas (UCI). Carretera a San Antonio de los Baños km 2.5, Reparto Torrens, Boyeros. La Habana, Cuba. CP 19370

DOI:

https://doi.org/10.30973/progmat/2014.6.2/8

Palabras clave:

optimización combinatoria, heurística, búsqueda local iterada, problema de la mochila

Resumen

El problema de la mochila se clasifica como un problema de optimización combinatoria y, desde el punto de vista computacional, entra en la categoría de los problemas NP-completos [1]. En este artículo se soluciona el problema de la mochila aplicando un algoritmo de búsqueda local iterada en el contexto de la distribución de productos almacenados en bodegas y a su distribución en tiendas. En los resultados obtenidos se observa la convergencia del algoritmo implementado.

Biografía del autor/a

Yainier Labrada-Nueva, Departamento de Biometría, Centro de Identificación y Seguridad Digital (Cised), Universidad de las Ciencias Informáticas (UCI). Carretera a San Antonio de los Baños km 2.5, Reparto Torrens, Boyeros. La Habana, Cuba. CP 19370

Yainier Labrada-Nueva es Ingeniero en Ciencias Informáticas por la Universidad de las Ciencias Informáticas (uci) en la Habana, Cuba. Actualmente trabaja en el Centro de Identificación y Seguridad Digital (Cised), perteneciente a la Facultad 1. Es profesor docente en el Departamento de Ciencias Básicas de la misma facultad. Ha impartido clases de Matemáticas, Física y Programación web como asignatura optativa.

Juana Enriquez-Urbano, Departamento de Biometría, Centro de Identificación y Seguridad Digital (Cised), Universidad de las Ciencias Informáticas (UCI). Carretera a San Antonio de los Baños km 2.5, Reparto Torrens, Boyeros. La Habana, Cuba. CP 19370

Juana Enríquez-Urbano es Ingeniera Mecánica por el Instituto Tecnológico de Orizaba y Maestra en Ciencias en Ingeniería Mecánica con especialidad en Sistemas Térmicos por el Centro Nacional de Desarrollo Tecnológico (Cenidet).

Yadían García-Ojito, Departamento de Biometría, Centro de Identificación y Seguridad Digital (Cised), Universidad de las Ciencias Informáticas (UCI). Carretera a San Antonio de los Baños km 2.5, Reparto Torrens, Boyeros. La Habana, Cuba. CP 19370

Yadián García-Ojito es Ingeniero en Ciencias Informáticas por la Universidad de las Ciencias Informáticas (uci) en la Habana, Cuba. Actualmente trabaja en el Departamento de Tecnología, perteneciente a la Facultad 1. Es profesor docente en el Departamento de Programación de la misma facultad. Ha impartido clases de Ingeniería de Software, Gestión de Software y Programación web.

Citas

Papadimitriou, C. H., Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity. New York: Englewood Cliffs, 1998.

Soares-Vianna, D., Dianin-Vianna, M. F. Local search-based heuristics for the multiobjective multidimensional knapsack problem. Producao. 2013, 23 (3), 478-487. https://doi.org/10.1590/S0103-65132012005000081

Hristakeva, M., Shrestha, D. Solving the 0-1 Knapsack Problem with Genetic Algorithms. Midwest Instruction and Computing Symposium. 2004.

Lourenco, H. R., Martin, O. C., Stutzle, T. Iterated local search, en Glover, F., Kochenberger, G. (eds.). Handbook of Metaheuristics. Norwell: Kluwer Academic Publishers, 2002, 321-353.

Khebbache, S., Prins, C., Yalaoui, A. Iterated local search algorithm for the constrained two-dimensional non-guillotine cutting problem. Journal of Industrial and Systems Engineering. 2008, 2 (3), 164-179.

Michaelewicz, Z., Fogel, D. B. How to Solve it: Modern Heuristics. Berlín: Springer-Verlag, 2004.

Cruz-Chávez, M. A., Martínez-Oropeza, A., SernaBarquera, S. A. Neighborhood hybrid structure for discrete optimization problems. En: Electronics, Robotics and Automotive Mechanics Conference, CERMA2010. México: IEEE-Computer Society, 2010, 108-113. https://doi.org/10.1109/CERMA.2010.24

Joyanes, A. L., Zahonero, M. I. Programación en C: Metodología, algoritmos y estructura de datos. México: McGraw-Hill, 2000.

Descargas

Publicado

30-06-2014

Cómo citar

Labrada-Nueva, Y., Enriquez-Urbano, J., & García-Ojito, Y. (2014). Un algoritmo de búsqueda local iterada como solución al problema de la mochila. Programación matemática Y Software, 6(2), 57–64. https://doi.org/10.30973/progmat/2014.6.2/8

Número

Vol. 6 Núm. 2 (2014): Junio de 2014

Sección

Artículos

Licencia

Derechos de autor 2014 Programación Matemática y Software

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.