Exact and heuristic approaches to solve the Internet shopping optimization problem with delivery costs

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

Identyfikatory

DOI

10.1515/amcs-2016-0028

• Języki publikacji: EN

Abstrakty

EN

Internet shopping has been one of the most common online activities, carried out by millions of users every day. As the number of available offers grows, the difficulty in getting the best one among all the shops increases as well. In this paper we propose an integer linear programming (ILP) model and two heuristic solutions, the MinMin algorithm and the cellular processing algorithm, to tackle the Internet shopping optimization problem with delivery costs. The obtained results improve those achieved by the state-of-the-art heuristics, and for small real case scenarios ILP delivers exact solutions in a reasonable amount of time.

Słowa kluczowe

EN

internet shopping optimization; integer linear programming; cellular processing algorithm; heuristic algorithms; optimization in e-commerce

PL

zakupy internetowe; programowanie liniowe; algorytm heurystyczny; handel elektroniczny

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: Vol. 26, no. 2
• Strony: 391--406
• Opis fizyczny: Bibliogr. 41 poz., rys., tab., wykr.

Twórcy

autor

Lopez-Loces M. C.

• National Institute of Technology of Ciudad Madero, National Institute of Technology of Mexico, v. 1o. de Mayo esq. Sor Juana Inés de la Cruz s/n, Col. Los Mangos C.P. 89440, Cd. Madero, Tamaulipas, Mexico

autor

Musial J.

• Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland

autor

Pecero J. E.

• Computer Science and Communications Research Unit, University of Luxembourg, 6, rue Richard Coudenhove-Kalergi, L-1359 Luxembourg, Luxembourg

autor

Fraire-Huacuja H. J.

• National Institute of Technology of Ciudad Madero, National Institute of Technology of Mexico, v. 1o. de Mayo esq. Sor Juana Inés de la Cruz s/n, Col. Los Mangos C.P. 89440, Cd. Madero, Tamaulipas, Mexico

autor

Blazewicz J.

• Institute of Computing Science, Poznań University of Technology, ul. Piotrowo 2, 60-965 Poznań, Poland; Institute of Bioorganic Chemistry, Polish Academy of Sciences, ul. Z. Noskowskiego 12/14, 61-704 Poznań, Poland

autor

Bouvry P.

• Computer Science and Communications Research Unit, University of Luxembourg, 6, rue Richard Coudenhove-Kalergi, L-1359 Luxembourg, Luxembourg

Bibliografia

• [1] Blazewicz, J., Bouvry, P., Kovalyov, M.Y. and Musial, J. (2014a). Erratum to: Internet shopping with price-sensitive discounts, 4OR—A Quarterly Journal of Operations Research 12(4): 403–406.
• [2] Blazewicz, J., Bouvry, P., Kovalyov, M.Y. and Musial, J. (2014b). Internet shopping with price sensitive discounts, 4OR—A Quarterly Journal of Operations Research 12(1): 35–48.
• [3] Blazewicz, J., Burkard, R., Finke, G. and Woeginger, G. (1994). Vehicle scheduling in two-cycle flexible manufacturing systems, Mathematical and Computer Modelling 20(2): 19–31.
• [4] Blazewicz, J., Cheriere, N., Dutot, P.-F.,Musial, J. and Trystram, D. (2016). Novel dual discounting functions for the Internet shopping optimization problem: New algorithms, Journal of Scheduling 19(3): 245–255.
• [5] Błażewicz, J., Kovalyov, M., Musiał, J., Urbański, A. and Wojciechowski, A. (2010). Internet shopping optimization problem, International Journal of Applied Mathematics and Computer Science 20(2): 385–390, DOI: 10.2478/v10006-010-0028-0.
• [6] Blazewicz, J. and Musial, J. (2011). E-commerce evaluation—multi-item internet shopping. Optimization and heuristic algorithms, in B. Hu et al. (Eds.), Operations Research Proceedings 2010, Springer-Verlag, Berlin, pp. 149–154.
• [7] Blazewicz, J., Pesch, E., Sterna, M. and Werner, F. (2007). A note on the two machine job shop with the weighted late work criterion, Journal of Scheduling 10(2): 87–95.
• [8] Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P. and Schulenburg, S. (2003). Hyper-heuristics: An emerging direction in modern search technology, in F. Glover and G.A. Kochenberger (Eds.), Handbook of Metaheuristics, International Series in Operations Research & Management Science, Vol. 57, Springer-Verlag, Berlin, pp. 457–474.
• [9] Cheung, C.M., Chan, G.W. and Limayem, M. (2005). A critical review of online consumer behavior: Empirical research, Journal of Electronic Commerce in Organizations 3(4): 1–19.
• [10] Chu, W., Choi, B. and Song, M. (2005). The role of on-line retailer brand and infomediary reputation in increasing consumer purchase intention, International Journal of Electronic Commerce 9(3): 115–127.
• [11] Clay, K., Krishnan, R. and Wolff, E. (2001). Prices and price dispersion on the web: Evidence from the online book industry, Journal of Industrial Economics 49(4): 521–539.
• [12] Diaz, C.O., Pecero, J.E. and Bouvry, P. (2014). Scalable, low complexity, and fast greedy scheduling heuristics for highly heterogeneous distributed computing systems, The Journal of Supercomputing 67(3): 837–853.
• [13] Eiselt, H. and Sandblom, C.-L. (2004). Decision Analysis, Location Models, and Scheduling Problems, Springer-Verlag, Berlin.
• [14] Freund, R., Gherrity, M., Ambrosius, S., Campbell, M., Halderman, M., Hensgen, D., Keith, E., Kidd, T., Kussow, M., Lima, J., Mirabile, F., Moore, L., Rust, B. and Siegel, H. (1998). Scheduling resources in multi-user, heterogeneous, computing environments with smartnet, Proceedings of the 7th Heterogeneous Computing Workshop, Orlando, FL, USA, pp. 184–199.
• [15] Garey, M. and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., San Francisco, CA.
• [16] Goossens, D.R., Maas, A., Spieksma, F.C. and Van de Klundert, J. (2007). Exact algorithms for procurement problems under a total quantity discount structure, European Journal of Operational Research 178(2): 603–626.
• [17] Guzek,M., Gniewek, A., Bouvry, P., Musial, J. and Blazewicz, J. (2015). Cloud brokering: Current practices and upcoming challenges, IEEE Cloud Computing 2(2): 40–47.
• [18] Iyigun, C. and Ben-Israel, A. (2010). A generalized Weiszfeld method for the multi-facility location problem, Operations Research Letters 38(3): 207–214.
• [19] Krarup, J., Pisinger, D. and Plastria, F. (2002). Discrete location problems with push–pull objectives, Discrete Applied Mathematics 123(1): 363–378.
• [20] Krichen, S., Laabidi, A. and Abdelaziz, F.B. (2011). Single supplier multiple cooperative retailers inventory model with quantity discount and permissible delay in payments, Computers & Industrial Engineering 60(1): 164–172.
• [21] Marszalkowski, J., Marszalkowski, J.M. and Drozdowski, M. (2014). Empirical study of load time factor in search engine ranking, Journal of Web Engineering 13(1&2): 114–128.
• [22] Marszalkowski, J. and Musial, J. (2011). Database scheme optimization for online applications, Foundations of Computing and Decision Sciences 36(2): 121–129.
• [23] Melo, M.T., Nickel, S. and Saldanha da Gama, F. (2009). Facility location and supply chain management—A review, European Journal of Operational Research 196(2): 401–412.
• [24] Mirmohammadi, S.H., Shadrokh, S. and Kianfar, F. (2009). An efficient optimal algorithm for the quantity discount problem in material requirement planning, Computers & Operations Research 36(6): 1780–1788.
• [25] Munson, C. and Hu, J. (2010). Incorporating quantity discounts and their inventory impacts into the centralized purchasing decision, European Journal of Operational Research 201(2): 581–592.
• [26] Musial, J. (2012). Applications of Combinatorial Optimization for Online Shopping, NAKOM, Poznań.
• [27] Nesmachnow, S., Dorronsoro, B., Pecero, J.E. and Bouvry, P. (2013). Energy-aware scheduling on multicore heterogeneous grid computing systems, Journal of Grid Computing 11(4): 653–680.
• [28] Pan, X., Ratchford, B. and Shankar, V. (2003). The evolution of price dispersion in internet retail markets, in M.R. Baye (Ed.), Organizing the New Industrial Economy, Advances in Applied Microeconomics, Vol. 12, Emerald Group Publishing, Bingley, pp. 85–105.
• [29] Pathak, B. (2012). Comparison shopping agents and online price dispersion: A search cost based explanation, Journal of Theoretical and Applied Electronic Commerce Research 7(1): 64–76.
• [30] Ratchford, B., Pan, X. and Shankar, V. (2003). On the efficiency of internet markets for consumer goods, Journal of Public Policy & Marketing 22(1): 4–16.
• [31] Revelle, C., Eiselt, H. and Daskin, M. (2008). A bibliography for some fundamental problem categories in discrete location science, European Journal of Operational Research 184(3): 817–848.
• [32] Rose, S. and Dhandayudham, A. (2014). 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.
• [33] Rose, S. and Samouel, P. (2009). Internal psychological versus external market-driven determinants of the amount of consumer information search amongst online shoppers, Journal of Marketing Management 25(1–2): 171–190.
• [34] Sawik, B. (2012). Downside risk approach for multi-objective portfolio optimization, in D. Klatte et al. (Eds.), Operations Research Proceedings 2011, Springer-Verlag, Berlin, pp. 191–196.
• [35] Simpson, T. (1750). The Doctrine and Application of Fluxions, Nourse, London.
• [36] Sipper, M. (1999). The emergence of cellular computing, Computer 32(7): 18–26.
• [37] Sterna, M. (2007). Late work minimization in a small flexible manufacturing system, Computers & Industrial Engineering 52(2): 210–228.
• [38] Terán-Villanueva, J.D., Huacuja, H.J.F., Valadez, J.M.C., Rangel, R.P., Soberanes, H.J.P. and Flores, J.A.M. (2015). A heterogeneous cellular processing algorithm for minimizing the power consumption in wireless communications systems, Computational Optimization and Applications 62(3): 787–814.
• [39] Weber, A. (1929). The Theory of the Location of Industries, Chicago University Press, Chicago.
• [40] Wojciechowski, A. and Musial, J. (2009). A customer assistance system: Optimizing basket cost, Foundations of Computing and Decision Sciences 34(1): 59–69.
• [41] Wojciechowski, A. and Musial, J. (2010). Towards optimal multi-item shopping basket management: Heuristic approach, in R. Meersman et al. (Eds.), On the Move to Meaningful Internet Systems: OTM 2010 Workshops, Lecture Notes in Computer Science, Vol. 6428, Springer-Verlag, Berlin, pp. 349–357.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.