大规模多设施Weber问题的改进Cooper算法
|
摘要
多设施Weber问题(multi-source Weber problem, MWP)是设施选址中的重要模型之一,而Cooper算法是求解MWP最为常用的数值方法.Cooper算法包含选址步和分配步,两步交替进行直至达到局部最优解.本文对Cooper算法的选址步和分配步分别引入改进策略,提出改进Cooper算法:选址步中将Weiszfeld算法和adaptive Barzilai-Borwein (ABB)算法结合,提出收敛速度更快的ABB-Weiszfeld算法求解选址子问题;分配步中提出贪婪簇分割策略来处理退化设施,由此进一步提出具有更好性质的贪婪混合策略.数值实验表明本文提出的改进策略有效地提高了Cooper算法的计算效率,改进算法有着更好的数值表现.
The multi-source Weber problem(MWP) is a very important model in facility location and Cooper algorithm is the most well-used method to solve MWP. Cooper algorithm consists of two steps: location step and allocation step. By doing such two steps alternately,the local optimal solution can be obtained. In this paper, we propose a modified Cooper algorithm by introducing improved strategy for both steps. For location step, we combine the Weiszfeld method with the adaptive Barzilai-Borwein(ABB) method to propose ABBWeiszfeld method, which has a faster convergence rate in solving location subproblems. For allocation step, we propose a greedy cluster splitting strategy to deal with out-of-use facilities, and then we propose a mixed greedy strategy which has better properties. Some preliminary numerical experiments are reported which have shown that the proposed strategies improve the computational efficiency of Cooper algorithm and thus result in a modified algorithm which has better performance.
The multi-source Weber problem(MWP) is a very important model in facility location and Cooper algorithm is the most well-used method to solve MWP. Cooper algorithm consists of two steps: location step and allocation step. By doing such two steps alternately,the local optimal solution can be obtained. In this paper, we propose a modified Cooper algorithm by introducing improved strategy for both steps. For location step, we combine the Weiszfeld method with the adaptive Barzilai-Borwein(ABB) method to propose ABBWeiszfeld method, which has a faster convergence rate in solving location subproblems. For allocation step, we propose a greedy cluster splitting strategy to deal with out-of-use facilities, and then we propose a mixed greedy strategy which has better properties. Some preliminary numerical experiments are reported which have shown that the proposed strategies improve the computational efficiency of Cooper algorithm and thus result in a modified algorithm which has better performance.
引文
[1] Drezner Z. Facility location:a survey of applications and methods[M]. Springer-Verlag, 1996.
[2] Drezner Z, Hamacher H. Facility location—applications and theory[M]. DBLP, 2004.
[3] Cooper L. Solutions of generalized locational equilibrium models[J]. Journal of Regional Science,1967, 7(1):1-18.
[4] Megiddo N, Supowit K J. On the complexity of some common geometric location problem[J].SIAM Journal on Computing, 2006, 13(1):182-196.
[5] Gao H, Dai Y H, Tong X J. Barzilai-Borwein-like methods for the extreme eigenvalue problem[J].Journal of Industrial&Management Optimization, 2017, 11(3):999-1019.
[6] Dai Y H, Liao L Z. R-linear convergence of the Barzilai and Borwein gradient method[J]. IMA Journal of Numerical Analysis, 2002, 22(1):1-10.
[7] Raydan M. On the Barzilai and Borwein choice of steplength for the gradient method[J]. IMA Journal of Numerical Analysis, 1993, 13(3):321-326.
[8] Raydan M. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem[M]. Society for Industrial and Applied Mathematics, 1997, 7:26-33.
[9]庄杰鹏,彭拯.一种修正的Cauchy-Barzilai-Borwein算法[J].数值计算与计算机应用,2016, 37(03):186-198.
[10] Fang X W. A direct search frame-based adaptive Barzilai-Borwein method[J]. Journal of Computational Mathematics, 2015, 33(2):179-190.
[11] Zanghirati G, Zanni L, Frassoldati G. New adaptive stepsize selections in gradient methods[J].Journal of Industrial&Management Optimization, 2017, 4(2):299-312.
[12] Brimberg J, Mladenovic N. Degeneracy in the multi-source Weber problem[J]. Mathematical Programming, 1999, 85(1):213-220.
[13] Zanjirani F R, Hekmatfar M. Facility location:concepts, models, algorithms and case studies[J].Applications and theory, 2009, 28(1):65-81.
[14] Weiszfeld E. Sur le point pour lequel la somme des distances de n points donn es est minimum[J].Faseb Journal Official Publication of the Federation of American Societies for Experimental Biology, 2006, 20(3):559-566.
[15] Vardi Y, Zhang C H. A modified Weiszfeld algorithm for the Fermat-Weber location problem[J].Mathematical Programming, 2001, 90(3):559-566.
[16] Barazilai J, Borwein J M. Two-point step size gradient methods[J]. IMA Journal of Numerical Analysis, 1988, 8(1):141-148.
[17] Fletcher R. Low storage methods for unconstrained optimization[M]. Lectures in Applied Mathematics, 1990, 26:165-179.
[18]刘亚君,刘新为.无约束最优化的信赖域BB法[J].计算数学,2016, 38(1):96-112.
[19] Andreani R, Birgin E G, Mart i nez J M, et al. Spectral projected gradient and variable metric methods for optimization with linear inequalities[J]. IMA Journal of Numerical Analysis, 2005,25(2):221-252.
[20] Lenys B, Marcos R. Preconditioned spectral projected gradient method on convex sets[J]. Journal of Computational Mathematics, 2005, 23(3):225-232.
[21] Birgin E G, Martinez J M, Raydan M. Nonmonotone spectral projected gradient methods for convex sets[J]. IMA Journal of Numerical Analysis, 2003, 23(23):539-559.
[22] Zhang H C, Hager W W. A nonmonotone line search technique and its application to unconstrained optimization[J]. SIAM Journal on Optimization, 2006, 14(4):1043-1056.
[23] Zhou B, Gao L, Dai Y H. Gradient methods with adaptive step-sizes[J]. Computational Optimization&Applications, 2006, 35(1):69-86.
[24] Kuhn H W. A note on Fermat's problem[J]. Mathematical Programming, 1973, 4(1):98-107.
[25] Jiang J L, Yuan X M. A heuristic algorithm for constrained multi-source Weber problem—The variational inequality approach[J]. European Journal of Operational Research, 2008, 187(2):357-370.
[2] Drezner Z, Hamacher H. Facility location—applications and theory[M]. DBLP, 2004.
[3] Cooper L. Solutions of generalized locational equilibrium models[J]. Journal of Regional Science,1967, 7(1):1-18.
[4] Megiddo N, Supowit K J. On the complexity of some common geometric location problem[J].SIAM Journal on Computing, 2006, 13(1):182-196.
[5] Gao H, Dai Y H, Tong X J. Barzilai-Borwein-like methods for the extreme eigenvalue problem[J].Journal of Industrial&Management Optimization, 2017, 11(3):999-1019.
[6] Dai Y H, Liao L Z. R-linear convergence of the Barzilai and Borwein gradient method[J]. IMA Journal of Numerical Analysis, 2002, 22(1):1-10.
[7] Raydan M. On the Barzilai and Borwein choice of steplength for the gradient method[J]. IMA Journal of Numerical Analysis, 1993, 13(3):321-326.
[8] Raydan M. The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem[M]. Society for Industrial and Applied Mathematics, 1997, 7:26-33.
[9]庄杰鹏,彭拯.一种修正的Cauchy-Barzilai-Borwein算法[J].数值计算与计算机应用,2016, 37(03):186-198.
[10] Fang X W. A direct search frame-based adaptive Barzilai-Borwein method[J]. Journal of Computational Mathematics, 2015, 33(2):179-190.
[11] Zanghirati G, Zanni L, Frassoldati G. New adaptive stepsize selections in gradient methods[J].Journal of Industrial&Management Optimization, 2017, 4(2):299-312.
[12] Brimberg J, Mladenovic N. Degeneracy in the multi-source Weber problem[J]. Mathematical Programming, 1999, 85(1):213-220.
[13] Zanjirani F R, Hekmatfar M. Facility location:concepts, models, algorithms and case studies[J].Applications and theory, 2009, 28(1):65-81.
[14] Weiszfeld E. Sur le point pour lequel la somme des distances de n points donn es est minimum[J].Faseb Journal Official Publication of the Federation of American Societies for Experimental Biology, 2006, 20(3):559-566.
[15] Vardi Y, Zhang C H. A modified Weiszfeld algorithm for the Fermat-Weber location problem[J].Mathematical Programming, 2001, 90(3):559-566.
[16] Barazilai J, Borwein J M. Two-point step size gradient methods[J]. IMA Journal of Numerical Analysis, 1988, 8(1):141-148.
[17] Fletcher R. Low storage methods for unconstrained optimization[M]. Lectures in Applied Mathematics, 1990, 26:165-179.
[18]刘亚君,刘新为.无约束最优化的信赖域BB法[J].计算数学,2016, 38(1):96-112.
[19] Andreani R, Birgin E G, Mart i nez J M, et al. Spectral projected gradient and variable metric methods for optimization with linear inequalities[J]. IMA Journal of Numerical Analysis, 2005,25(2):221-252.
[20] Lenys B, Marcos R. Preconditioned spectral projected gradient method on convex sets[J]. Journal of Computational Mathematics, 2005, 23(3):225-232.
[21] Birgin E G, Martinez J M, Raydan M. Nonmonotone spectral projected gradient methods for convex sets[J]. IMA Journal of Numerical Analysis, 2003, 23(23):539-559.
[22] Zhang H C, Hager W W. A nonmonotone line search technique and its application to unconstrained optimization[J]. SIAM Journal on Optimization, 2006, 14(4):1043-1056.
[23] Zhou B, Gao L, Dai Y H. Gradient methods with adaptive step-sizes[J]. Computational Optimization&Applications, 2006, 35(1):69-86.
[24] Kuhn H W. A note on Fermat's problem[J]. Mathematical Programming, 1973, 4(1):98-107.
[25] Jiang J L, Yuan X M. A heuristic algorithm for constrained multi-source Weber problem—The variational inequality approach[J]. European Journal of Operational Research, 2008, 187(2):357-370.