集合覆盖模型

集合覆盖模型

（一）模型介绍

    在这里，将采用集合覆盖模型进行营业厅选址的计算，集合覆盖模型的基础思想是用最小数量的变压器在规定的半径范围去覆盖所有的需求点。

覆盖模型的数学模型为：

，

约束条件为：

N——区域中的变压器全集合，N={1,2,…,n}；

M——区域中所需建设营业厅的候选点集合,M={1,2,…,m}；

di——第i个营业厅的需求量；

Dj——营业厅j的服务能力；

A(j)——营业厅节点j可以覆盖的变压器点i的集合；

B(i)——可以覆盖营业厅节点i的变压器节点j的集合；

Xj为0-1变量，Xj=1,在j点建立营业厅；Xj=0，不在j点建立营业厅；j属于集合M；

Yij——变压器节点i需求中被分配给营业厅点j的部分。

（二）计算过程

第一步：初始化。令所有Yi=0,Xj=0, (已分配的营业厅)，并确定集合A(j)和集合B(i)；

第二步：选择下一个营业厅。在M中选择Xj=0，且A(j)的规模为最大的点j’为营业厅备选点，即|A(j’)|=max{|A(j)|}，令Xj’=1，并在M集合中剔除节点j’，即M=M\{j’}

第三步：确定节点j’的覆盖范围。将A(j’)中的元素按B(i)的规模从大到小的顺序指派给j’