Mathematics (Jul 2022)

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,
  • Mayra Guadalupe Treviño-Berrones

DOI
https://doi.org/10.3390/math10142513
Journal volume & issue
Vol. 10, no. 14
p. 2513

Abstract

Read online

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