Paper Info
Title
E-Commerce Evaluation - Multi-Item Internet Shopping. Optimization and Heuristic Algorithms.
Abstract
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 approximable 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. We also described an heuristic algorithm we propose and try to find some connections to known and defined problems. The paper concludes with a summary of the results and suggestions for future research.
Year
DOI
Venue
2010
10.1007/978-3-642-20009-0_24
Operations Research Proceedings
Field
DocType
ISSN
Recommender system,Mathematical optimization,Heuristic,Heuristic (computer science),Simulation,Software agent,Operations research,Facility location problem,Time complexity,E-commerce,Mathematics,The Internet
Conference
0721-5924
Citations 
PageRank 
References 
9
0.63
6
Authors
2
Name
Order
Citations
PageRank
Jacek Blazewicz11064154.23
Jędrzej Musiał2687.17