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

An algorithm of iterated local search as a solution to the knapsack problem

Publicación:
Entidad Editora:
Editor Técnico:
ISSN:
Ejemplar/Número:
Cateoría:
Páginas:
Colección:
Fecha de inicio:
Periodicidad:

Programación Matemática y Software
Universidad Autónoma del Estado de Morelos
Dr.Marco Antonio Cruz Chávez
2007-3283
Volumen 6, Número 2 /Junio del 2014
Artículo de Investigación
57-64
Computación
Junio del 2014
Cuatrimestral

Yainier Labrada Nueva, Juana Enríquez Urbano, Yadián García Ojito

Departamento de Biometría, Centro de Identificación y Seguridad Digital (CISED), Facultad No. 1. Universidad de las Ciencias Informáticas (UCI), Carretera a San Antonio de los Baños km 2 ½, Reparto Torrens, Municipio Boyeros, La Habana, CP. 19370, Cuba.

Recibido: 6 marzo 2014 Aceptado: 4 junio 2014 Publicado en línea: 30 junio 2014

Resumen. El Problema de la Mochila está clasificado como un problema de Optimización Combinatoria que desde el punto de vista computacional se clasifica como un problema NP-Completo. En este artículo se soluciona este problema aplicando un algoritmo heurístico (Búsqueda Local Iterada) y esta aplicado a la a la distribución de productos almacenados en bodegas y a la distribución de estos productos en tiendas.  Por último se presentan los resultados obtenidos, en donde se observa la convergencia del algoritmo implementado.

Abstract. The Problem Knapsack is classified as a Combinatorial Optimization problem since the computational viewpoint is classified as an NP-complete [1] problem. In this paper this problem by applying a heuristic algorithm (Iterated Local Search) and is applied to the distribution of stored products in warehouses and distribution of these products in stores is solved. Finally the results, where the convergence of the implemented algorithm is observed are presented.

Keywords: Combinatorial Optimization, Metaheuristics, Iterated Local Search, Knapsack Problem