Accelerating the convergence in the single-source and multi-source Weber problems

作者：Jiang Jian lin^*; Cheng Kun; Wang Can Can; Wang Li ping

来源：Applied Mathematics and Computation, 2012, 218(12): 6814-6824.

DOI：10.1016/j.amc.2011.12.050

• Single-source Weber problem
• Modified Weiszfeld method
• Newton method
• Multi-source Weber problem
• Location-allocation heuristic

The modified Weiszfeld method [Y. Vardi, C. H. Zhang, A modified Weiszfeld algorithm for the Fermat-Weber location problem, Mathematical Programming 90 (2001) 559-566] is perhaps the most widely-used algorithm for the single-source Weber problem (SWP). In this paper, in order to accelerate the efficiency for solving SWP, a new numerical method, called Weiszfeld-Newton method, is developed by combining the modified Weiszfeld method with the well-known Newton method. Global convergence of the new Weiszfeld-Newton method is proved under mild assumptions. For the multi-source Weber problem (MWP), a new location-allocation heuristic, Cooper-Weiszfeld-Newton method, is presented in the spirit of Cooper algorithm [L. Cooper, Heuristic methods for location-allocation problems, SIAM Review 6 (1964) 37-53], using the new Weiszfeld-Newton method in the location phase to locate facilities and adopting the nearest center reclassification algorithm (NCRA) in the allocation phase to allocate the customers. Preliminary numerical results are reported to verify the evident effectiveness of Weiszfeld-Newton method for SWP and Cooper-Weiszfeld-Newton method for MWP.

• 出版日期2012-2-15
• 单位南京大学