Algorithms solving the Internet shopping optimization problem with price discounts

• Autorzy: Musial J. , Pecero J. E. , Lopez-Loces M. C. , Fraire-Huacuja H. J. , Bouvry P. , Blazewicz J.

Identyfikatory

DOI

10.1515/bpasts-2016-0056

• Języki publikacji: EN

Abstrakty

EN

The Internet shopping optimization problem arises when a customer aims to purchase a list of goods from a set of web-stores with a minimum total cost. This problem is NP-hard in the strong sense. We are interested in solving the Internet shopping optimization problem with additional delivery costs associated to the web-stores where the goods are bought. It is of interest to extend the model including price discounts of goods. The aim of this paper is to present a set of optimization algorithms to solve the problem. Our purpose is to find a compromise solution between computational time and results close to the optimum value. The performance of the set of algorithms is evaluated through simulations using real world data collected from 32 web-stores. The quality of the results provided by the set of algorithms is compared to the optimal solutions for small-size instances of the problem. The optimization algorithms are also evaluated regarding scalability when the size of the instances increases. The set of results revealed that the algorithms are able to compute good quality solutions close to the optimum in a reasonable time with very good scalability demonstrating their practicability.

Słowa kluczowe

EN

e-commerce; Internet shopping; applications of operations research; approximations; algorithms; heuristics; combinatorial optimization

PL

e-commerce; zakupy przez Internet; wnioski z badań operacyjnych; aproksymacje; algorytmy; heurystyki; optymalizacja kombinatoryczna

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2016
• Tom: Vol. 64, nr 3
• Strony: 505--516
• Opis fizyczny: Bibliogr. 37 poz., rys., wykr., tab.

Twórcy

autor

Musial J.

• Institute of Computing Science, Poznan University of Technology, 2 Piotrowo St., 60-965 Poznan, Poland

autor

Pecero J. E.

• Comp. Sci. and Commun. Res. Unit, University of Luxembourg, 6 rue Coudenhove Kalergi, L-1359 Luxembourg, Luxembourg

autor

Lopez-Loces M. C.

• Instituto Tecnológico de Ciudad Madero, Tecnológico Nacional de México, 1º de Mayo S/N, 89440, Ciudad Madero, Mexico

autor

Fraire-Huacuja H. J.

• Instituto Tecnológico de Ciudad Madero, Tecnológico Nacional de México, 1º de Mayo S/N, 89440, Ciudad Madero, Mexico

autor

Bouvry P.

• Comp. Sci. and Commun. Res. Unit, University of Luxembourg, 6 rue Coudenhove Kalergi, L-1359 Luxembourg, Luxembourg

autor

Blazewicz J.

• Institute of Bioorganic Chemistry, Polish Academy of Sciences, 12/14 Noskowskiego St., 61-704 Poznan, Poland
• Institute of Computing Science, Poznan University of Technology, 2 Piotrowo St., 60-965 Poznan, Poland

Bibliografia

• [1] K. M. Tolle and H. Chen, “Intelligent software agents for electronic commerce”, Handbook on Electronic Commerce, Springer Berlin Heidelberg, 365–382 (2000).
• [2] S. Rose and A. Dhandayudham, “Towards an understanding of Internet-based problem shopping behaviour: The concept of online shopping addiction and its proposed predictors”, Journal of Behavioral Addictions 3 (2), 83–89 (2014).
• [3] J. Blazewicz, M. Kovalyov, J. Musial, A. Urbanski and A. Wojciechowski, “Internet shopping optimization problem”, International Journal of Applied Mathematics and Computer Science 20 (2), 385–390 (2010).
• [4] J. Blazewicz and J. Musial, “E-commerce evaluation – multi-item Internet shopping. Optimization and heuristic algorithms”, Operations Research Proceedings 2010, 149–154 (2011).
• [5] J. Blazewicz, P. Bouvry, M. Y. Kovalyov and J. Musial, “Internet shopping with price sensitive discounts”, 4OR-Q J Oper Res 12 (1), 35–48 (2014).
• [6] J. Blazewicz, P. Bouvry, M. Y. Kovalyov and J. Musial, “Erratum to: Internet shopping with price-sensitive discounts”, 4OR-Q J Oper Res 12 (4), 403–406 (2014).
• [7] B. Sawik, “Downside risk approach for multi-objective portfolio optimization”, Operations Research Proceedings 2011, 191–196 (2012).
• [8] D. R. Goossens and A. J. T. Maas, “Exact algorithms for procurement problems under a total quantity discount structure”, European Journal of Operational Research 178 (2), 603–626 (2007).
• [9] A. Wojciechowski and J. Musial, “Towards optimal multi-item shopping basket management: Heuristic approach”, Lecture Notes in Computer Science (LNCS) 6428, 349–357 (2010).
• [10] A. Wojciechowski and J. Musial, “A customer assistance system: optimizing basket cost”, Foundations of Computing and Decision Sciences 34 (1), 59–69 (2009).
• [11] M. Shaw, R. Blanning, T. Strader and A. Whinston, Handbook on Electronic Commerce, International Handbooks on Information Systems, Springer, Berlin-Heidelberg (2000).
• [12] C. Revelle, H. Eiselt and M. Daskin, “A bibliography for some fundamental problem categories in discrete location science”, European Journal of Operational Research 184 (3), 817–848 (2008).
• [13] J. Krarup, D. Pisinger and F. Plastria, “Discrete location problems with push-pull objectives”, Discrete Applied Mathematics 123 (13), 363–378 (2002).
• [14] H. Eiselt and C. Sandblom, Decision Analysis, Location Models, and Scheduling Problems, Springer-Verlag, Berlin-Heidelberg-New York (2004).
• [15] M. Melo, S. Nickel and F. Saldanha-da Gama, “Facility location and supply chain management – A review”, European Journal of Operational Research 196 (2), 401–412 (2009).
• [16] C. Iyigun and A. Ben-Israel, “A generalized Weiszfeld method for the multi-facility location problem”, Operations Research Letters 38 (3), 207–214 (2010).
• [17] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, New York, Freeman (1979).
• [18] S. Krichen, A. Laabidi and F. B. Abdelaziz, “Single supplier multiple cooperative retailers inventory model with quantity discount and permissible delay in payments”, Computers & Industrial Engineering 60 (1), 164–172 (2011).
• [19] D. Manerba and R. Mansini, “An exact algorithm for the capacitated total quantity discount problem”, European Journal of Operational Research 222 (2), 287–300 (2012).
• [20] S. H. Mirmohammadi, S. Shadrokh and F. Kianfar, “An efficient optimal algorithm for the quantity discount problem in material requirement planning”, Computers & Operations Research 36 (6), 1780–1788 (2009).
• [21] C. Munson and J. Hu, “Incorporating quantity discounts and their inventory impacts into the centralized purchasing decision”, European Journal of Operational Research 201 (2), 581–592 (2010).
• [22] T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, McGraw-Hill Higher Education, 2nd edition (2001).
• [23] J. D. Terán-Villanueva, H. J. F. Huacuja, J. M. C. Valadez, R. A. Pazos Rangel, H. J. P. Soberanes and J. A. M. Flores, “Cellular processing algorithms”, Studies in Fuzziness and Soft Computing 294, 53–74 (2013).
• [24] E. Burke, G. Kendall, J. Newall, E. Hart, P. Ross and S. Schulenburg, “Hyper-heuristics: An emerging direction in modern search technology”, Handbook of Metaheuristics, Springer, 457–474 (2003).
• [25] C. O. Diaz, J. E. Pecero and P. Bouvry, “Scalable, low complexity, and fast greedy scheduling heuristics for highly heterogeneous distributed computing systems”, Journal of Supercomputing 67 (3), 837–853 (2014).
• [26] S. Nesmachnow, B. Dorronsoro, J. E. Pecero and P. Bouvry, “Energy-aware scheduling on multicore heterogeneous grid computing systems”, Journal of Grid Computing 11 (4), 653–680 (2013).
• [27] M. Wu, W. Shu and H. Zhang, “Segmented min-min: A static mapping algorithm for meta-tasks on heterogeneous computing systems”, Heterogeneous Computing Workshop IEEE, 375–385 (2000).
• [28] T. Braun, H. Siegel, N. Beck, L. Bölöni, M. Maheswaran, A. Reuther, J. Robertson, M. Theys, B. Yao, D. Hensgen et al., “A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems”, Journal of Parallel and Distributed Computing 61 (6), 810–837 (2001).
• [29] A. Land and A. Doig, “An automatic method for solving discrete programming problems”, Econometrica 28 (3), 497–520 (1960).
• [30] E. W. Karen Clay, Ramayya Krishnan, “Prices and price dispersion on the web: evidence from the online book industry”, The Journal of Industrial Economics 49 (4), 521–539 (2001).
• [31] W. Chu, B. Choi and M. Song, “The role of on-line retailer brand and infomediary reputation in increasing consumer purchase intention”, International Journal of Electronic Commerce 9 (3), 115–127 (2005).
• [32] J. Marszalkowski, J. M. Marszalkowski and M. Drozdowski, “Empirical study of load time factor in search engine ranking”, Journal of Web Engineering 13 (1&2), 114–128 (2014).
• [33] F. Pinel, B. Dorronsoro and P. Bouvry, “Solving very large instances of the scheduling of independent tasks problem on the GPU”, Journal of Parallel and Distributed Computing 73 (1), 101–110 (2013).
• [34] P. Ezzatti, M. Pedemonte and A. Martin, “An efficient implementation of the Min-Min heuristic”, Computers & Operations Research 40 (11), 2670–2676 (2013).
• [35] J. Marszalkowski, J. Marszalkowski and J. Musial, “Database scheme optimization for online applications”, Foundations of Computing and Decision Sciences 36 (2), 121–129 (2011).
• [36] J. Blazewicz, N. Cheriere, P.-F. Dutot, J. Musial and D. Trystram, “Novel dual discounting functions for the Internet shopping optimization problem: new algorithms”, Journal of Scheduling 19 (3), 245–255 (2016).
• [37] M. Guzek, A. Gniewek, P. Bouvry, J. Musial and J. Blazewicz, “Cloud brokering: current practices and upcoming challenges”, IEEE C