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

Lopez-Loces, Mario C.; Musial, Jedrzej; Pecero, Johnatan E.; Fraire-Huacuja, Hector J.; Blazewicz, Jacek; Bouvry, Pascal

doi:10.1515/amcs-2016-0028

Abstract

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.

References

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.10.1007/s10288-014-0271-6
Search in Google Scholar
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.10.1007/s10288-013-0230-7
Search in Google Scholar
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.10.1016/0895-7177(94)90203-8
Search in Google Scholar
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.10.1007/s10951-014-0390-0
Search in Google Scholar
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.10.2478/v10006-010-0028-0
Search in Google Scholar
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.
Search in Google Scholar
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.10.1007/s10951-006-0005-5
Search in Google Scholar
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.10.1007/0-306-48056-5_16
Search in Google Scholar
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.4018/jeco.2005100101
Search in Google Scholar
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.10.1080/10864415.2005.11044336
Search in Google Scholar
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.10.1111/1467-6451.00161
Search in Google Scholar
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.10.1007/s11227-013-1038-0
Search in Google Scholar
Eiselt, H. and Sandblom, C.-L. (2004). Decision Analysis, Location Models, and Scheduling Problems, Springer-Verlag, Berlin.10.1007/978-3-540-24722-7
Search in Google Scholar
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.
Search in Google Scholar
Garey, M. and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., San Francisco, CA.
Search in Google Scholar
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.10.1016/j.ejor.2006.03.010
Search in Google Scholar
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.10.1109/MCC.2015.32
Search in Google Scholar
Iyigun, C. and Ben-Israel, A. (2010). A generalized Weiszfeld method for the multi-facility location problem, Operations Research Letters 38(3): 207-214.10.1016/j.orl.2009.11.005
Search in Google Scholar
Krarup, J., Pisinger, D. and Plastria, F. (2002). Discrete location problems with push-pull objectives, Discrete Applied Mathematics 123(1): 363-378.10.1016/S0166-218X(01)00346-8
Search in Google Scholar
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.10.1016/j.cie.2010.10.014
Search in Google Scholar
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.
Search in Google Scholar
Marszalkowski, J. and Musial, J. (2011). Database scheme optimization for online applications, Foundations of Computing and Decision Sciences 36(2): 121-129.
Search in Google Scholar
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.10.1016/j.ejor.2008.05.007
Search in Google Scholar
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.10.1016/j.cor.2008.05.003
Search in Google Scholar
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.10.1016/j.ejor.2009.03.043
Search in Google Scholar
Musial, J. (2012). Applications of Combinatorial Optimization for Online Shopping, NAKOM, Poznań.
Search in Google Scholar
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.10.1007/s10723-013-9258-3
Search in Google Scholar
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.10.1016/S0278-0984(03)12004-4
Search in Google Scholar
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.10.4067/S0718-18762012000100006
Search in Google Scholar
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.10.1509/jppm.22.1.4.17620
Search in Google Scholar
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.10.1016/j.ejor.2006.12.044
Search in Google Scholar
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.10.1556/JBA.3.2014.003411728625215218
Search in Google Scholar
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.10.1362/026725709X410089
Search in Google Scholar
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.10.1007/978-3-642-29210-1_31
Search in Google Scholar
Simpson, T. (1750). The Doctrine and Application of Fluxions, Nourse, London.
Search in Google Scholar
Sipper, M. (1999). The emergence of cellular computing, Computer 32(7): 18-26.10.1109/2.774914
Search in Google Scholar
Sterna, M. (2007). Late work minimization in a small flexible manufacturing system, Computers & Industrial Engineering 52(2): 210-228.10.1016/j.cie.2006.12.004
Search in Google Scholar
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.10.1007/s10589-015-9754-4
Search in Google Scholar
Weber, A. (1929). The Theory of the Location of Industries, Chicago University Press, Chicago.
Search in Google Scholar
Wojciechowski, A. and Musial, J. (2009). A customer assistance system: Optimizing basket cost, Foundations of Computing and Decision Sciences 34(1): 59-69.
Search in Google Scholar
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. 10.1007/978-3-642-16961-8_54
Search in Google Scholar

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

Abstract

Paradigm

My account