无容量限制设施选址问题的降阶回溯算法

Reduction Backtracking Algorithm for Uncapacitated Facility Location Problem

无容量限制设施选址问题(uncapacitated facility location problem,UFLP)是经典组合优化中NP-Hard问题之一,在诸多领域具有广泛的应用价值。本文首先研究UFLP的数学性质,并进行了数学证明。运用这些数学性质不仅可以确定某些设施必定开设或者关闭,还可以确定某些连接边是否在服务集中,从而缩小问题的规模,加快求解速度;在此基础上设计出一个新的基于上下界的回溯算法来求解UFLP。最后,通过一个示例进一步阐述该算法的原理,结果表明该算法具有明显的可行性和有效性。

The uncapacitated facility location problem （UFLP） is a well-known NP-Hard problem in the area of combinatorial optimization, which has wide application value in various fields. The present paper firstly provides new observations of the UFLP model and gives the proof of the new observation. These mathematical properties not only can be used to decide whether some facilities should be open or closed, but also can be used to deter- mine whether some of the connection edges are in service set. Therefore, the size of the original problem can be reduced, and the solution speed can be accelerated by utilizing the new observation in the paper. Given the fact, a new reduction backtracking algorithm based on upper and lower bounds is designed to solve the UFLP. In the end, an example is given to illustrate the principle of the algorithm, and the optimal solution of the example is obtained by utilizing the reduction backtracking algorithm in the paper . Therefore, the results show that the algorithm is feasible and effective.