一类多商品设施选址问题的基于线性松弛解的启发式方法

doi:10.15960/j.cnki.issn.1007-6093.2019.03.002

Abstract

Abstract: 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.

Key words: multi-product facility location problem, heuristic, linear programming, integer programming, compact problem, localsearch

CLC Number:

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.

References

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

Linear relaxation solution based heuristics for a class of multi-product facility location problems

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	SHEN Yindong, QIAN Zhuang, LI Yuanyuan. A survey on driver scheduling in public transportation [J]. Operations Research Transactions, 2021, 25(1): 1-16.
[2]	ZHAO Dan, GAO Yuelin. Non-parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2020, 24(4): 63-73.
[3]	ZHENG Yujun, WU Chenxin, CHEN Enfu, LU Xueqin, ZHANG Minxia. An optimization method for production resumption planning under COVID-19 Epidemic [J]. Operations Research Transactions, 2020, 24(3): 43-56.
[4]	LU Shuxiang, Lü Changhong, QIN Tao. An algorithm based on makespan lower bound for quay crane schedule problem in container terminals [J]. Operations Research Transactions, 2020, 24(3): 67-76.
[5]	HUANG Peihuang, ZHU Wenxing. Algorithms for Max-Value Path Sweep Coverage in Mobile Sensor Networks [J]. Operations Research Transactions, 2019, 23(4): 155-164.
[6]	ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates [J]. Operations Research Transactions, 2019, 23(2): 67-74.
[7]	CAI Shuang, YANG Ke, LIU Ke. Model and algorithms of the distributed permutation flow shop scheduling problem with machine eligibility constraints [J]. Operations Research Transactions, 2018, 22(4): 17-30.
[8]	ZHU Zhenglu, LU Xiwen. Minimizing makespan on two parallel machines with learning effects [J]. Operations Research Transactions, 2018, 22(1): 55-66.
[9]	WU Peipei, GAO Yuelin. A new single parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2017, 21(3): 111-118.
[10]	HUANG Yakui, LI Bo, KANG Yang, DAI Yuhong, LIU Jianjun. A mixed integer model and an algorithm for steady-state gas network optimization [J]. Operations Research Transactions, 2017, 21(2): 13-23.
[11]	LIAN Shujun, DU Aihua, TANG Jiahui. A new class of simple smooth exact penalty functions for equality constrained optimization problems [J]. Operations Research Transactions, 2017, 21(1): 33-43.
[12]	SHI Litang, CHEN Wei. A filled-filter function algorithm for solving unconstrained nonlinear optimization [J]. Operations Research Transactions, 2017, 21(1): 55-64.
[13]	DONG Zhenyu, FENG Enmin, YIN Hongchao, ZHANG Yuduo. International crude prices forecast of double random integer programming model,algorithm and application [J]. Operations Research Transactions, 2015, 19(3): 18-25.
[14]	PAN Pingqi. On “An efficient implementation of the face algorithm for linear programming” [J]. Operations Research Transactions, 2015, 19(3): 78-84.
[15]	HE Shengxue. Determining optimal routes for transit vehicles in no-notice emergency evacuation [J]. Operations Research Transactions, 2014, 18(3): 47-59.