计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  重点论文 |  在线办公 | 
计算数学  2018, Vol. 40 Issue (4): 470-484    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |   
大规模多设施Weber问题的改进Cooper算法
蒋建林, 潘蕴文
南京航空航天大学理学院, 南京 210016
A MODIFIED COOPER ALGORITHM FOR LARGE-SCALE MULTI-SOURCE WEBER PROBLEM
Jiang Jianlin, Pan Yunwen
Nanjing University of Aeronautics and Astronautics, College of Science, Nanjing 210016, China
 全文: PDF (459 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 多设施Weber问题(multi-source Weber problem,MWP)是设施选址中的重要模型之一,而Cooper算法是求解MWP最为常用的数值方法.Cooper算法包含选址步和分配步,两步交替进行直至达到局部最优解.本文对Cooper算法的选址步和分配步分别引入改进策略,提出改进Cooper算法:选址步中将Weiszfeld算法和adaptive Barzilai-Borwein (ABB)算法结合,提出收敛速度更快的ABB-Weiszfeld算法求解选址子问题;分配步中提出贪婪簇分割策略来处理退化设施,由此进一步提出具有更好性质的贪婪混合策略.数值实验表明本文提出的改进策略有效地提高了Cooper算法的计算效率,改进算法有着更好的数值表现.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词多设施Weber问题   Cooper算法   ABB-Weiszfeld算法   退化   贪婪簇分割     
Abstract: 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.
Key wordsmulti-source Weber problem   Cooper algorithm   ABB-Weiszfeld   out-ofuse facilities   greedy cluster splitting   
收稿日期: 2017-11-14;
基金资助:

国家自然科学基金(11571169).

引用本文:   
. 大规模多设施Weber问题的改进Cooper算法[J]. 计算数学, 2018, 40(4): 470-484.
. A MODIFIED COOPER ALGORITHM FOR LARGE-SCALE MULTI-SOURCE WEBER PROBLEM[J]. Mathematica Numerica Sinica, 2018, 40(4): 470-484.
 
[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 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.
[1] 王同科, 樊梦. 第二类端点奇异Fredholm积分方程的分数阶退化核方法[J]. 计算数学, 2019, 41(1): 66-81.
[2] 杨建平, 刘清, 帅晓勇, 吕敬祥. 非线性系统退化数据的小波墒序列及其应用[J]. 计算数学, 2012, 33(3): 198-206.
[3] 赵海峰,  刘新为. 退化线性规划的一个新的改进的单纯形方法[J]. 计算数学, 2012, 33(2): 109-120.
[4] 陈艳萍,黄云清,沈祖和. 退化椭圆问题的最小二乘混合元逼近[J]. 计算数学, 2001, 23(1): 87-94.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10