The Internet Shopping Optimization Problem with Multiple Item Units (ISHOP-U): Formulation, Instances, NP-Completeness, and Evolutionary Optimization

Fernando Ornelas, Alejandro Santiago, Salvador Ibarra Martínez, Mirna Patricia Ponce-Flores, Jesús David Terán-Villanueva, Fausto Balderas, José Antonio Castán Rocha, Alejandro H. García, Julio Laria-Menchaca and Mayra Guadalupe Treviño-Berrones
Additional contact information
Fernando Ornelas: Faculty of Engineering “Arturo Narro Siller”, Autonomous University of Tamaulipas, Centro Universitario Tampico-Madero, Tampico 89339, Tamaulipas, Mexico
Alejandro Santiago: Faculty of Engineering “Arturo Narro Siller”, Autonomous University of Tamaulipas, Centro Universitario Tampico-Madero, Tampico 89339, Tamaulipas, Mexico
Salvador Ibarra Martínez: Faculty of Engineering “Arturo Narro Siller”, Autonomous University of Tamaulipas, Centro Universitario Tampico-Madero, Tampico 89339, Tamaulipas, Mexico
Mirna Patricia Ponce-Flores: Faculty of Engineering “Arturo Narro Siller”, Autonomous University of Tamaulipas, Centro Universitario Tampico-Madero, Tampico 89339, Tamaulipas, Mexico
Jesús David Terán-Villanueva: Faculty of Engineering “Arturo Narro Siller”, Autonomous University of Tamaulipas, Centro Universitario Tampico-Madero, Tampico 89339, Tamaulipas, Mexico
Fausto Balderas: Tecnológico Nacional de México, Instituto Tecnológico de Ciudad Madero, División de Estudios de Posgrado e Investigación, Juventino Rosas S/N, Cd. Madero C.P. 89440, Mexico
José Antonio Castán Rocha: Faculty of Engineering “Arturo Narro Siller”, Autonomous University of Tamaulipas, Centro Universitario Tampico-Madero, Tampico 89339, Tamaulipas, Mexico
Alejandro H. García: Faculty of Engineering “Arturo Narro Siller”, Autonomous University of Tamaulipas, Centro Universitario Tampico-Madero, Tampico 89339, Tamaulipas, Mexico
Julio Laria-Menchaca: Faculty of Engineering “Arturo Narro Siller”, Autonomous University of Tamaulipas, Centro Universitario Tampico-Madero, Tampico 89339, Tamaulipas, Mexico
Mayra Guadalupe Treviño-Berrones: Faculty of Engineering “Arturo Narro Siller”, Autonomous University of Tamaulipas, Centro Universitario Tampico-Madero, Tampico 89339, Tamaulipas, Mexico

Mathematics, 2022, vol. 10, issue 14, 1-19

Abstract: In this work, we investigate the variant of the Internet Shopping Optimization Problem (ISHOP) that considers different item units. This variant is more challenging than the original problem. The original ISHOP is already known as a combinatorial NP-hard problem. In this work, we present a formal proof that the ISHOP variant considering different item units belongs to the NP-Hard complexity class. The abovementioned variant is familiar to companies and consumers who need to purchase more than one unit of a specific product to satisfy their requirements. For example, companies buy different quantities of construction materials, medical equipment, office supplies, or chemical components. We propose two new evolutionary operators (crossover and mutation) and an unfeasible solution repair method for the studied ISHOP variant. Furthermore, we produce a new benchmark of 15 synthetic instances where item prices follow a random uniform distribution. Finally, to assess our evolutionary operators, we implemented two Evolutionary Algorithms, a Genetic Algorithm (GA) and a Cellular Genetic Algorithm (CGA), and an experimental evaluation against a Water Cycle Algorithm (WCA) from the state-of-the-art. Experimental results show that our proposed GA performs well with statistical significance.

Keywords: internet shopping optimization problem (ISHOP); internet shopping optimization problem with units (ISHOP-U); e-commerce; evolutionary algorithms (EAs); NP-complete; NP-hard (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/14/2513/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/14/2513/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:14:p:2513-:d:866345

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().