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
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
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.
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.