Accelerating the convergence in the single-source and multi-source Weber problems |
| |
Authors: | Jian-lin Jiang Kun ChengCan-Can Wang Li-ping Wang |
| |
Institution: | Department of Mathematics, College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China |
| |
Abstract: | 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. |
| |
Keywords: | Single-source Weber problem Modified Weiszfeld method Newton method Multi-source Weber problem Location-allocation heuristic |
本文献已被 ScienceDirect 等数据库收录! |
|