IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i14p2513-d866345.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • 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 & Juli, 2022. "The Internet Shopping Optimization Problem with Multiple Item Units (ISHOP-U): Formulation, Instances, NP-Completeness, and Evolutionary Optimization," Mathematics, MDPI, vol. 10(14), pages 1-19, July.
  • Handle: RePEc:gam:jmathe:v:10:y:2022:i:14:p:2513-:d:866345
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/14/2513/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/10/14/2513/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Alejandro Santiago & Mirna Ponce-Flores & J. David Terán-Villanueva & Fausto Balderas & Salvador Ibarra Martínez & José Antonio Castan Rocha & Julio Laria Menchaca & Mayra Guadalupe Treviño Berrones, 2021. "Energy Idle Aware Stochastic Lexicographic Local Searches for Precedence-Constraint Task List Scheduling on Heterogeneous Systems," Energies, MDPI, vol. 14(12), pages 1-22, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.

      Corrections

      All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:14:p:2513-:d:866345. See general information about how to correct material in RePEc.

      If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

      If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

      If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

      For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

      Please note that corrections may take a couple of weeks to filter through the various RePEc services.

      IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.