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

Competitive Decision Algorithm for Soft-Capacitated Facility Location Problem

作　　者：何永梅 宁爱兵[1] 彭大江 尚春剑 张惠珍[1] HE Yongmei;NING Aibing;PENG Dajiang;SHANG Chunjian;ZHANG Huizhen(School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机工程与应用》2019年第3期50-54,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.71401106);上海市一流学科建设项目(No.S1201YLXK);高等学校博士学科点专项科研基金联合资助课题(No.20123120120005)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]