计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (3): 50-54.DOI: 10.3778/j.issn.1002-8331.1803-0292

• 理论与研发 • 上一篇    下一篇

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

何永梅,宁爱兵,彭大江,尚春剑,张惠珍   

  1. 上海理工大学 管理学院,上海 200093
  • 出版日期:2019-02-01 发布日期:2019-01-24

Competitive Decision Algorithm for Soft-Capacitated Facility Location Problem

HE Yongmei, NING Aibing, PENG Dajiang, SHANG Chunjian, ZHANG Huizhen   

  1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2019-02-01 Published:2019-01-24

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

关键词: 软容量设施选址, 数学性质, 竞争决策算法, 竞争力函数

Abstract: 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.

Key words: soft-capacitated facility location, mathematical properties, competitive decision algorithm, competitive force function