An ADMM-based location-allocation algorithm for nonconvex constrained multi-source Weber problem under gauge
An ADMM-based location-allocation algorithm for nonconvex constrained multi-source Weber problem under gauge
复制标题
基于ADMM的规范下非凸约束多源韦伯问题位置分配算法
DOI：
10.1007/s10898-019-00796-9
复制
发表时间：
2019
影响因子：
1.8
通讯作者：
Ziwei Yan
中科院分区：
文献类型：
--
作者：
Jianlin Jiang;Su Zhang;Yibing Lv;Xin Du;Ziwei Yan
多源韦伯问题（MSWP）是设施选址中的经典非凸NP难模型。解决 MSWP 的一种众所周知的方法是位置分配算法，该算法由定位新设施的定位阶段和在每次迭代时分配客户的分配阶段组成。本文考虑了更一般和更实际的 MSWP 案例，称为约束多源韦伯问题 (CMSWP)，即在考虑测量距离的仪表和新设施的位置约束的情况下定位多个设施。根据重构后所涉及的位置子问题的有利结构，乘子交替方向法（ADMM）类型的方法有助于在统一框架中解决不同距离度量下的这些子问题。然后针对CMSWP提出了一种新的基于ADMM的位置分配算法，并从理论上证明了其局部收敛性。报告了一些初步的数值结果，以验证所提出方法的有效性。
Multi-source Weber problem (MSWP) is a classical nonconvex and NP-hard model in facility location. A well-known method for solving MSWP is the location–allocation algorithm which consists of a location phase to locate new facilities and an allocation phase to allocate customers at each iteration. This paper considers the more general and practical case of MSWP called the constrained multi-source Weber problem (CMSWP), i.e., locating multiple facilities with the consideration of the gauge for measuring distances and locational constraints on new facilities. According to the favorable structure of the involved location subproblems after reformulation, an alternating direction method of multipliers (ADMM) type method is contributed to solving these subproblems under different distance measures in a uniform framework. Then a new ADMM-based location–allocation algorithm is presented for CMSWP and its local convergence is theoretically proved. Some preliminary numerical results are reported to verify the effectiveness of proposed methods.