E-Commerce Evaluation – Multi-Item Internet Shopping. Optimization and Heuristic Algorithms

Report [11] states that 32% of EU customers make purchases in Internet stores. By 2013, almost half of Europeans are expected to make a purchase online, up from 21% in 2006. On-line shopping is one of key business activities offered over the Internet. However a high number of Internet shops makes it difficult for a customer to review manually all the available offers and select optimal outlets for shopping, especially if a customer wants to buy more than one product. A partial solution of this problem has been supported by software agents so-called price comparison sites. Unfortunately price comparison works only on a single product and if the customer’s basket is composed of several products complete shopping list optimization needs to be done manually. Our present work is to define the problem (multiple-item shopping list over several shopping locations) in a formal way. The objective is to have all the shopping done at the minimum total expense. One should notice that dividing the original shopping list into several sub lists whose items will be delivered by different providers increases delivery costs. In the following sections a formal definition of the problem is given. Moreover a prove that problem is NP-hard in the strong sense was provided. It is also proven that it is not approx-imable in polynomial time. In the following section we demonstrate that shopping multiple items problem is solvable in polynomial time if the number of products to buy, n, or the number of shops, m, is a given constant.