A Multi-Objective Formulation for the Internet Shopping Optimization Problem with Multiple Item Units

Abstract

The Internet Shopping Optimization Problem with multiple item Units looks for the best selection of stores where to buy various or individual units in a required list of items to minimize the final purchase cost. The problem belongs to the most challenging complexity class of optimization problems (NP-Hard). This paper adds to the already complex problem a more difficult situation with a second objective conflicting with the purchase cost minimization. As far as we know, this is the first state-of-the-art proposal with conflicting objectives for the Internet Shopping Optimization Problem or its variants. The objective in conflict with the minimization of the purchase final cost is the cash-back or reward points on personal or corporate credit cards, the most common payment method for online purchases. Due to the nature of the conflicting objectives, this paper proposes using evolutionary multi-objective optimization algorithms. We perform an experimental comparison using eight algorithms from the literature. The experimental results show that NSGA-II achieves the best overall performance for the studied instances from the state of the art.