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

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

International Journal of Applied Mathematics and Computer Science, Tome 26 (2016), p. 391-406 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 2016-01-01
EUDML-ID : urn:eudml:doc:280108

Bibliographie

[000] 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. | Zbl 1315.90064

[001] 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. | Zbl 1297.90183

[002] 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. | Zbl 0810.90062

[003] 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.

[004] 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. | Zbl 1230.90207

[005] 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.

[006] 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. | Zbl 1154.90417

[007] 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. | Zbl 1102.90377

[008] 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.

[009] 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.

[010] 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.

[011] 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.

[012] Eiselt, H. and Sandblom, C.-L. (2004). Decision Analysis, Location Models, and Scheduling Problems, Springer-Verlag, Berlin. | Zbl 1140.90032

[013] 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.

[014] Garey, M. and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., San Francisco, CA. | Zbl 0411.68039

[015] 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. | Zbl 1107.90043

[016] 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.

[017] Iyigun, C. and Ben-Israel, A. (2010). A generalized Weiszfeld method for the multi-facility location problem, Operations Research Letters 38(3): 207-214. | Zbl 1188.90148

[018] Krarup, J., Pisinger, D. and Plastria, F. (2002). Discrete location problems with push-pull objectives, Discrete Applied Mathematics 123(1): 363-378. | Zbl 1012.90028

[019] 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.

[020] 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. | Zbl 1292.90151

[021] Marszalkowski, J. and Musial, J. (2011). Database scheme optimization for online applications, Foundations of Computing and Decision Sciences 36(2): 121-129.

[022] 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. | Zbl 1163.90341

[023] 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. | Zbl 1179.90015

[024] 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. | Zbl 1175.90030

[025] Musial, J. (2012). Applications of Combinatorial Optimization for Online Shopping, NAKOM, Poznań.

[026] 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.

[027] 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.

[028] 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.

[029] 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.

[030] 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. | Zbl 1141.90025

[031] 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.

[032] 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.

[033] 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. | Zbl 1306.91132

[034] Simpson, T. (1750). The Doctrine and Application of Fluxions, Nourse, London.

[035] Sipper, M. (1999). The emergence of cellular computing, Computer 32(7): 18-26.

[036] Sterna, M. (2007). Late work minimization in a small flexible manufacturing system, Computers & Industrial Engineering 52(2): 210-228.

[037] 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. | Zbl 1337.90055

[038] Weber, A. (1929). The Theory of the Location of Industries, Chicago University Press, Chicago.

[039] Wojciechowski, A. and Musial, J. (2009). A customer assistance system: Optimizing basket cost, Foundations of Computing and Decision Sciences 34(1): 59-69.

[040] 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.