软容量限制设施选址问题的竞争决策算法

软容量设施选址问题是NP-Hard问题之一,具有广泛的应用价值。为了求解软容量设施选址问题,提出一种基于数学性质的竞争决策算法。首先研究该问题的数学性质,运用这些数学性质不仅可以确定某些设施必定开设或关闭,还可以确定部分顾客由哪个设施提供服务,从而缩小问题的规模,加快求解速度。在此基础上设计了求解该问题的竞争决策算法,最后经过一个小规模的算例测试并与精确算法的结果比较,得出了最优解;针对大规模的问题快速地求出了可行解,得到了令人满意的结果。

Competitive Decision Algorithm for Soft-Capacitated Facility Location Problem

The soft-capacitated facility location problem is one of NP-Hard problems, which has wide application value in various fields. To solve the soft-capacitated facility location problem, a competitive decision algorithm based on mathematical properties is proposed. The present paper firstly provides new observations of the SCFLP model. These mathematical properties not only can be used to decide some facilities should be open or closed, but also can be used to determine which facilities are provided by some of the customers. Therefore, the size of the original problem can be reduced, and the solution speed can be accelerated by utilizing the new observations in the paper. Given the fact, a new competitive decision algorithm based on mathematical properties is designed to solve the SCFLP. Finally, after a small scale test and comparison with the exact algorithm, the optimal solution is obtained. For the large scale problem, a feasible solution is obtained quickly, and the result is satisfied.