基于时间满意的集覆盖问题及若干贪婪算法应用研究

传统的选址问题过于简单地考量时间这一对企业竞争力影响重大的因素。针对这一特点，对时间满意度函数进行了定义，从顾客角度考虑覆盖半径，从企业角度考虑覆盖比例，提出比传统集覆盖问题更一般的基于时间满意的覆盖选址问题。在给定的网络G（V，A）中，以最小化总的建站成本为目标建立这一问题的整数规划模型，并应用3种被证明为在覆盖选址问题中计算效果很好的贪婪算法对不同规模的问题进行求解计算。

Time-satisfaction-based Set Covering Location Problem and Applications of Greedy Algorithms

The classical facility location problems give little consideration to time,which,in fact,is a critical issue for a company to gain its competitive advantage.In the light of this,the paper defines the time satisfaction function and presents the time-satisfaction-based set covering location problem(TSBSCLP),which is more general than the classical set covering location problem.The customer interest coverage level is analyzed,and the percentage of demand to be covered on behalf of the enterprise is considered.Given a discrete network G(V,A),the authors have constructed an integer programming model of TSBSCLP under the goal of minimizing the total cost of facility construction,and then provided three greedy algorithms which have been proven to be the best in solving set covering location problems for problems of various scale.