logo móvil
Contáctanos

El problema de optimización de compras en Internet con múltiples unidades de artículo (ISHOP-U): formulación, instancias, NP-completitud y optimización evolutiva

Autores: Ornelas, Fernando; Santiago, Alejandro; Martínez, Salvador Ibarra; Ponce-Flores, Mirna Patricia; Terán-Villanueva, Jesús David; Balderas, Fausto; Rocha, José Antonio Castán; García, Alejandro H.; Laria-Menchaca, Julio; Treviño-Berrones, Mayra Guadalupe

Idioma: Inglés

Editor: MDPI

Año: 2022

Descargar PDF

Acceso abierto

Artículo científico
2022

El problema de optimización de compras en Internet con múltiples unidades de artículo (ISHOP-U): formulación, instancias, NP-completitud y optimización evolutiva


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Trabajo
Problema de Optimización de Compras en Internet
Variante
Unidades de artículo
Clase de complejidad NP-Hard
Algoritmos Evolutivos

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 22

Citaciones: Sin citaciones


Descripción
En este trabajo, investigamos la variante del Problema de Optimización de Compras en Internet (ISHOP) que considera diferentes unidades de artículo. Esta variante es más desafiante que el problema original. El ISHOP original ya es conocido como un problema NP-duro combinatorio. En este trabajo, presentamos una prueba formal de que la variante de ISHOP que considera diferentes unidades de artículo pertenece a la clase de complejidad NP-Duro. La variante mencionada es familiar para empresas y consumidores que necesitan comprar más de una unidad de un producto específico para satisfacer sus requerimientos. Por ejemplo, las empresas compran diferentes cantidades de materiales de construcción, equipos médicos, suministros de oficina o componentes químicos. Proponemos dos nuevos operadores evolutivos (cruce y mutación) y un método de reparación de soluciones inviables para la variante de ISHOP estudiada. Además, producimos un nuevo conjunto de pruebas de 15 instancias sintéticas donde los precios de los artículos siguen una distribución uniforme aleatoria. Finalmente, para evaluar nuestros operadores evolutivos, implementamos dos Algoritmos Evolutivos, un Algoritmo Genético (GA) y un Algoritmo Genético Celular (CGA), y una evaluación experimental contra un Algoritmo del Ciclo del Agua (WCA) del estado del arte. Los resultados experimentales muestran que nuestro GA propuesto tiene un buen rendimiento con significancia estadística.

Otros recursos que podrían interesarte

Temas Virtualpro