×

Two-phase semi-Lagrangian relaxation for solving the uncapacitated distribution centers location problem for B2C E-commerce. (English) Zbl 1420.90040

Summary: This paper develops a mixed integer programming model for determining uncapacitated distribution centers location (UDCL) for B2C E-commerce. Based on the characteristics of distribution system for B2C E-commerce firms, the impact of supply cost of multi-commodity is considered in this model. Combining with the properties of the semi-Lagrangian relaxation (SLR) dual problem in the UDCL case, a two-phase SLR algorithm with good convergency property is furthermore developed for solving the UDCL problem. For the sake of contrastive analysis, this paper has performed computational experiments on 15 UDCL instances by the mixed integer programming solver, CPLEX, and the approach obtained by combining two-phase SLR algorithm with CPLEX, respectively. The numerical results show that the two-phase SLR algorithm not only can improve the solving speed of the CPLEX solver, but also can provide better results in reasonable time for most instances.

MSC:

90C11 Mixed integer programming
90B80 Discrete location and assignment

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aardal, K., Van den Berg, P.L., Gijswijt, D., Li, S.: Approximation algorithms for hard capacitated k-facility location problems. Eur. J. Oper. Res. 242(2), 358-368 (2015) · Zbl 1341.90080 · doi:10.1016/j.ejor.2014.10.011
[2] An, Y., Zeng, B., Zhang, Y., Zhao, L.: Reliable \[p\] p-median facility location problem: two-stage robust models and algorithms. Transp. Res. Part B Methodol. 64, 54-72 (2014) · doi:10.1016/j.trb.2014.02.005
[3] Arabani, A.B., Farahani, R.Z.: Facility location dynamics: an overview of classifications and applications. Comput. Ind. Eng. 62(1), 408-420 (2012) · doi:10.1016/j.cie.2011.09.018
[4] Aydin, N., Murat, A.: A swarm intelligence based sample average approximation algorithm for the capacitated reliable facility location problem. Int. J. Prod. Econ. 145(1), 173-183 (2013) · doi:10.1016/j.ijpe.2012.10.019
[5] Beltran, C., Tadonki, C., Vial, J.-P.: Solving the p-median problem with a semi-Lagrangian relaxation. Comput. Optim. Appl. 35(2), 239-260 (2006) · Zbl 1151.90521 · doi:10.1007/s10589-006-6513-6
[6] Beltran, C., Vial, J.-P., Alonso-Ayuso, A.: Semi-lagrangian relaxation applied to the uncapacitated facility location problem. Comput. Optim. Appl. 51(1), 387-409 (2012) · Zbl 1244.90168 · doi:10.1007/s10589-010-9338-2
[7] Chen, C.-H., Ting, C.-J.: Combining lagrangian heuristic and ant colony system to solve the single source capacitated facility location problem. Transp. Res. Part E Logist. Transp. Rev. 44(6), 1099-1122 (2008) · doi:10.1016/j.tre.2007.09.001
[8] Farahani, R.Z., Hekmatfar, M., Fahimnia, B., Kazemzadeh, N.: Hierarchical facility location problem: models, classifications, techniques, and applications. Comput. Ind. Eng. 68, 104-117 (2014) · doi:10.1016/j.cie.2013.12.005
[9] Farahani, R.Z., SteadieSeifi, M., Asgari, N.: Multiple criteria facility location problems: a survey. Appl. Math. Model. 34(7), 1689-1709 (2010) · Zbl 1193.90143 · doi:10.1016/j.apm.2009.10.005
[10] Gadegaard, S.L.: Discrete Location Problems—Theory, Algorithms, and Extensions to Multiple Objectives. PhD thesis, School of Business and Social Sciences, Aarhus University (2016)
[11] Guignard, M.: A Lagrangean dual ascent algorithm for simple plant location problems. Eur. J. Oper. Res. 35(2), 193-200 (1988) · Zbl 0696.90025 · doi:10.1016/0377-2217(88)90029-X
[12] Hassanzadeh Amin, S., Zhang, G.: A multi-objective facility location model for closed-loop supply chain network under uncertain demand and return. Appl. Math. Model. 37(6), 4165-4176 (2013) · doi:10.1016/j.apm.2012.09.039
[13] Ho, S.C.: An iterated tabu search heuristic for the single source capacitated facility location problem. Appl. Soft Comput. 27, 169-178 (2015) · doi:10.1016/j.asoc.2014.11.004
[14] Hua, X., Hu, X., Yuan, W.: Research optimization on logistics distribution center location based on adaptive particle swarm algorithm. Optik 127(20), 8443-8450 (2016) · doi:10.1016/j.ijleo.2016.06.032
[15] Huang, R., Menezes, M.B.C., Kim, S.: The impact of cost uncertainty on the location of a distribution center. Eur. J. Oper. Res. 218(2), 401-407 (2012) · Zbl 1244.90035 · doi:10.1016/j.ejor.2011.11.016
[16] Jörnsten, K., Klose, A.: An improved lagrangian relaxation and dual ascent approach to facility location problems. Comput. Manag. Sci. 13(3), 317-348 (2016) · Zbl 1397.90239 · doi:10.1007/s10287-015-0244-z
[17] Karatas, M., Yakıcı, E.: An iterative solution approach to a multi-objective facility location problem. Appl. Soft Comput. 62, 272-287 (2018) · doi:10.1016/j.asoc.2017.10.035
[18] Klose, A., Drexl, A.: Facility location models for distribution system design. Eur. J. Oper. Res. 162(1), 4-29 (2005) · Zbl 1132.90345 · doi:10.1016/j.ejor.2003.10.031
[19] Klose, A., Gortz, S.: A branch-and-price algorithm for the capacitated facility location problem. Eur. J. Oper. Res. 179(3), 1109-1125 (2007) · Zbl 1163.90607 · doi:10.1016/j.ejor.2005.03.078
[20] Lau, H.C.W., Jiang, Z.-Z., Ip, W.H., Wang, D.: A credibility-based fuzzy location model with Hurwicz criteria for the design of distribution systems in B2C E-commerce. Comput. Ind. Eng. 59(4), 873-886 (2010) · doi:10.1016/j.cie.2010.08.018
[21] Li, J., Chu, F., Prins, C.: Lower and upper bounds for a capacitated plant location problem with multicommodity flow. Comput. Oper. Res. 36(11), 3019-3030 (2009) · Zbl 1162.90495 · doi:10.1016/j.cor.2009.01.012
[22] Li, J., Chu, F., Prins, C., Zhu, Z.: Lower and upper bounds for a two-stage capacitated facility location problem with handling costs. Eur. J. Oper. Res. 236(3), 957-967 (2014) · Zbl 1304.90124 · doi:10.1016/j.ejor.2013.10.047
[23] Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45-58 (2013) · Zbl 1281.68236 · doi:10.1016/j.ic.2012.01.007
[24] Melo, M.T., Nickel, S., Saldanha-da Gama, F.: Facility location and supply chain management—a review. Eur. J. Oper. Res. 196(2), 401-412 (2009) · Zbl 1163.90341 · doi:10.1016/j.ejor.2008.05.007
[25] Monabbati, E.: An application of a lagrangian-type relaxation for the uncapacitated facility location problem. Jpn. J. Ind. Appl. Math. 31(3), 483-499 (2014) · Zbl 1307.90111 · doi:10.1007/s13160-014-0149-1
[26] Nezhad, A.M., Manzour, H., Salhi, S.: Lagrangian relaxation heuristics for the uncapacitated single-source multi-product facility location problem. Int. J. Prod. Econ. 145(2), 713-723 (2013) · doi:10.1016/j.ijpe.2013.06.001
[27] Ortiz-Astorquiza, C., Contreras, I., Laporte, G.: Multi-level facility location problems. Eur. J. Oper. Res. 267(3), 791-805 (2018) · Zbl 1403.90484 · doi:10.1016/j.ejor.2017.10.019
[28] Puerto, J., Ramos, A.B., Rodriguez-Chia, A.M.: A specialized branch & bound & cut for single-allocation ordered median hub location problems. Discrete Appl. Math. 161(16-17), 2624-2646 (2013) · Zbl 1294.90034 · doi:10.1016/j.dam.2013.05.035
[29] Rahmani, A., MirHassani, S.A.: A hybrid firefly-genetic algorithm for the capacitated facility location problem. Inf. Sci. 283, 70-78 (2014) · Zbl 1355.90110 · doi:10.1016/j.ins.2014.06.002
[30] Rao, C., Goh, M., Zhao, Y., Zheng, J.: Location selection of city logistics centers under sustainability. Transp. Res. Part D Transp. Environ. 36, 29-44 (2015) · doi:10.1016/j.trd.2015.02.008
[31] Tang, X., Lehuédé, F., Péton, O.: Location of distribution centers in a multi-period collaborative distribution network. Electron. Notes Discrete Math. 52, 293-300 (2016) · Zbl 1351.90118 · doi:10.1016/j.endm.2016.03.039
[32] Yang, L., Ji, X., Gao, Z., Li, K.: Logistics distribution centers location problem and algorithm under fuzzy environment. J. Comput. Appl. Math. 208(2), 303-315 (2007) · Zbl 1119.90003 · doi:10.1016/j.cam.2006.09.015
[33] Yang, Z., Chen, H., Chu, F., Wang, N. : An effective hybrid approach to the two-stage capacitated facility location problem. Eur. J. Oper. Res. (2018). https://doi.org/10.1016/j.ejor.2018.11.062 · Zbl 1430.90387
[34] Yun, L., Qin, Y., Fan, H., Ji, C., Li, X., Jia, L.: A reliability model for facility location design under imperfect information. Transp. Res. Part B Methodol. 81(Part 2), 596-615 (2015) · doi:10.1016/j.trb.2014.10.010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.