The multi-product facility location problem is an important but difficult class in facility location problems, which allows that customers have demand for different products. When solving large scale problems, commercial solvers hardly achieve high quality solutions in a reasonable time. In this paper, the general form of the uncapacitated single-source multi-product facility location problem is studied and two heuristic methods are proposed for this problem. Based on the linear relaxation optimal solution of the original problem, the two methods can provide a feasible upper bound via solving a compact problem and local search techniques, respectively. Through the theoretical analysis, it is guaranteed that these two methods can be implemented on any feasible instances. Numerical results show that the heuristic methods can significantly improve the performance of the commercial solver for solving this kind of problem.
YANG Muming, HUANG Yakui, DAI Yuhong
. Linear relaxation solution based heuristics for a class of multi-product facility location problems[J]. Operations Research Transactions, 2019
, 23(3)
: 15
-26
.
DOI: 10.15960/j.cnki.issn.1007-6093.2019.03.002
[1] Daskin M S. What you should know about location modeling[J]. Naval Research Logistics, 2008, 55:283-294.
[2] Klose A, Drexl A. Facility location models for distribution systemdesign[J]. European Journal of Operational Research, 2005,162:4-29.
[3] Conforti M, Cornuéjols G, Zambelli G. Integer Programming[M]. Berlin:Springer, 2014.
[4] Arya V, Garg N, Khandekar R, et al.Local search heuristic for k-median and facility location problems[C]//Proceedings on 33rd Annual ACM Symposium on Theory of Computing,2001, Heraklion, Crete, Greece. ACM, 2001.
[5] Korupolu M R, Plaxton C G, Rajaraman R. Analysis of a local searchheuristic for facility location problems[J]. Journal ofAlgorithms, 2000, 37:146-188.
[6] Zhang J, Chen B, Ye Y. A multiexchange local search algorithm forthe capacitated facility location problem[J]. Mathematics ofOperations Research, 2005, 30:389-403.
[7] Sun M. Solving the uncapacitated facility location problem usingtabu search[J]. Computers & Operations Research, 2006,33:2563-2589.
[8] Chudak F A, Shmoys D B. Improved approximation algorithms for theuncapacitated facility location problem[J]. SIAM Journal onComputing, 2003, 33:1-25.
[9] Huang H C, Li R. A k-product uncapacitated facility locationproblem[J]. European Journal of Operational Research, 2008,185:552-562.
[10] Mazzola J B, Neebe A W.Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type[J].European Journal of Operational Research, 1999, 115:285-299.
[11] Nezhad A M, Manzour H, Salhi S.Lagrangian relaxation heuristics for the uncapacitated single-source multi-product facility location problem[J].International Journal of Production Economics, 2013, 145:713-723.
[12] Geoffrion A M, Graves G W. Multicommodity distribution system designby Benders decomposition[J]. Management Science, 1974, 20:822-844.
[13] Lee C Y. A cross decomposition algorithm for amultiproduct-multitype facility location problem[J]. Computers & Operations Research, 1993, 20:527-540.
[14] Klincewicz J G, Luss H, Rosenberg E. Optimal and heuristicalgorithms for multiproduct uncapacitated facility location[J].European Journal of Operational Research, 1986, 26:251-258.
[15] Karkazis J, Boffey T B. The multi-commodity facilities locationproblem[J]. Journal of the Operational Research Society,1981, 32:803-814.
[16] Klincewicz J G, Luss H. A dual-based algorithm for multiproductuncapacitated facility location[J]. Transportation Science,1987, 21:198-206.
[17] Montoya A, Vélez-Gallego M C, Villegas J G. Multi-productcapacitated facility location problem with general production andbuilding costs[J]. NETNOMICS:Economic Research and ElectronicNetworking, 2016, 17:47-70.
[18] Gurobi Optimizer[EB/OL]. http://www.gurobi.com/
[19] IBM ILOG CPLEX Optimization Studio[EB/OL].https://www.ibm.com/analytics/cplex-optimizer
[20] Achterberg T. SCIP:solving constraint integer programs[J]. Mathematical Programming Computation, 2009, 1:1-41.
