最小最大后悔准则下新增设施选址策略研究

The Study on New Facility Location Strategy under Minmax Regret Criterion

基于新增设施选址问题,考虑网络节点权重不确定性,以设施中最大负荷量最小为目标,提出最小最大后悔准则下的新增设施选址问题。在网络节点权重确定时,通过证明将网络图中无穷多个备选点离散为有限个设施候选点,设计了时间复杂度为O(mn^(2))的多项式算法;在节点权重为区间值时,通过分析最大后悔值对应的最坏情境权重结构,进而确定最大后悔值最小的选址,提出时间复杂度为O(2^(n)m^(2)n^(3))的求解算法;最后给出数值算例。

In this paper,we consider the new facility location problem in a general network with positive edge lengths and interval vertex weights.There are some facilities in the network already,and a new facility should be located so that the maximum load of all the facilities is minimized.When the vertex weights are determined,the network graph can be discretized into finite facility candidate points,and a polynomial algorithm with a time complexity of is designed.When the vertex weights are given as interval values,a particular assignment of a weight to each vertex is called a scenario.The problem requires that a point should be determined as the new facility location on the graph,such that the maximum regret of the objective function for all possible scenarios is minimized.By analyzing the structure of the worst scenarios corresponding to the maximum regret value,an algorithm with a time complexity of is proposed to solve the problem.Finally,a numerical example is given.