文章目录

1. 设施选址集合覆盖问题2. 算法实现2.1 测试数据集 OR-Library2.2 python调用SCIP求解设施选址覆盖问题完整代码:2.3 数据结果参考文献

1. 设施选址集合覆盖问题

选址问题（Facility location problem, FLP）分为离散型和连续型两类。其中离散选址问题即设施点被选址的地点是离散的。此类问题往往设定设施点与需求点都位于在网络节点上，需求点区位确定，需求点与其 他一些节点作为设施被选点，需求点与设施被选点之间有连线相连。 离散选址问题纷繁复杂，在国外学者的研究基础上，我们认为主要的离散选址问题有：中值问题、覆盖问题、中心问题、多产品问题、动态选址问题、路径选址、多目标选址、网络中心选址问题。

集合覆盖问题(Set Covering Problem, SCP)是经典组合优化问题之一，被广泛应用到航空的人员行程安排、电路设计、运输的车辆路线安排等领域。该问题已被证明是一个NP-C问题。

设施选址集合覆盖问题被分为集覆盖问题（完全覆盖问题）、最大覆盖问题：

集覆盖问题（Location Set Covering Problem，LSCP研究满足覆盖所有需求点顾客需求点的前提下，设施的建站个数或建设费用最小的问题；数学模型

最大覆盖问题（Maximum Covering Location Problem，MCLP）研究在备选物流中心里，如何选择p个设施，使得服务的需求点数最多或需求量最大；数学模型

大白话：

1.集覆盖即要求所有的需求点都要被满足，就算为了某个需求点被覆盖满足，建立了成本很大的设施也没关系（前提假设是设施是肯定能满足所有的需求点的），所以目标是最小化成本。

2.最大覆盖问题在建造的设施数量是固定的约束下，尽可能满足足够多的需求，当然每个需求点可能有一定的权重（这个可以由需求点的人数、距离决定），所以目标是最大化满足的需求

2. 算法实现

2.1 测试数据集 OR-Library

OR-Library is a collection of test data sets for a variety of Operations Research (OR) problems.

测试算例直接使用 Set covering的测试算例，代码中给出了OR-Library数据集txt文件的解析的方式。

2.2 python调用SCIP求解设施选址覆盖问题完整代码:

import pandas as pdimport numpy as npimport pyscipopt as optclass SCP_FLP(object):def __init__(self):self.num_nodes = None # 需求点的数量self.num_facilities = None # 设施数量self.setup_cost = None # 每个设施的建造成本self.cover_matrix = 0 # cover_matrix[[i, j]], 需求点i能否被设施j是否能覆盖def prepare_data(self, filepath):# 获取数据集 OR-Library数据集数据，http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html# 获取所有的行lines = []with open(filepath, 'r') as file:for line in file:lines.append(line)# 第一行获取服务点的数量num_nodes和仓库的数量num_facilitiesline_0 = lines[0].strip().split()self.num_nodes, self.num_facilities = list(map(int, line_0))iter_lines = iter(lines)next(iter_lines)# 从第二行开始获取num_facilities个设施的建造成本self.setup_cost = np.array([])for line in iter_lines:self.setup_cost = np.append(self.setup_cost, list(map(int, line.strip('\n').split())))if len(self.setup_cost) == self.num_facilities:break# 获取需求点是否能被设施覆盖矩阵。这段逻辑比较复杂，为了不同算例的通用性。idx_point = -1count_aux = 0mark_value = 0line_of_size = Trueself.cover_matrix = np.full((self.num_nodes, self.num_facilities), 0)for line in iter_lines:if line_of_size:# 一行只有一个数据的数据值mark_value，然后取下一行开始的长度为mark_value的数据集mark_value = int(line.strip('\n').split()[0])line_of_size = Falseidx_point += 1count_aux = 0else:line_search = line.strip('\n').split()count_aux += len(line_search)# 生成覆盖关系矩阵for j in line_search:self.cover_matrix[idx_point][int(j) - 1] = 1if count_aux == mark_value:line_of_size = Truedef cover_model(self):# 创建模型model = opt.Model('LSCP')# 添加变量：是否在j处建造设施，1则建造，0则不建造select = {}for n in range(self.num_facilities):select[n] = model.addVar(vtype='B', name='select_' + str(n))# 添加约束: 每个需求点至少被一个设施服务范围所覆盖for i in range(self.num_nodes):model.addCons(opt.quicksum(self.cover_matrix[i][j] * select[j] for j in range(self.num_facilities)) >= 1)# 设置目标model.setObjective(opt.quicksum(self.setup_cost[j] * select[j] for j in range(self.num_facilities)))model.setMinimize()# model.hideOutput()# 优化求解model.optimize()# 输出解print('model_obj =', model.getObjVal())select_facility = []for i in range(self.num_facilities):if model.getVal(select[i]) > 0:select_facility.append(i)print('select facility =', select_facility)def max_cover_model(self):np.random.seed(0)# 需求点权重（可以是和距离的正比的权重、需求点的需求量等等）weight_points = np.random.randint(10, size=self.num_nodes)fixed_facilities_num = int(self.num_facilities / 2)# 创建模型model = opt.Model('MCLP')# 添加变量1：设施j是否建造，0-1变量, 1则建造，0则不建造select = {}for n in range(self.num_facilities):select[n] = model.addVar(vtype='B', name='select_' + str(n))# 添加变量2：需求点i是否被覆盖，1则被覆盖，0则不被覆盖served = {}for n in range(self.num_nodes):served[n] = model.addVar(vtype='B', name='served_' + str(n))# 添加约束1: 从备选中选择的设施 = 决策设施数量model.addCons(opt.quicksum(select[j] for j in range(self.num_facilities)) == fixed_facilities_num)# 添加约束2: 若有设施j建造（select=1）, 且覆盖需求点i，则由于目标最大化, served=1; 反之亦然for i in range(self.num_nodes):model.addCons(opt.quicksum(self.cover_matrix[i][j] * select[j] for j in range(self.num_facilities)) >= served[i])# 设置目标最大化: 在设施总数量确定的情况下，选择设施及服务点，使得需求量最大model.setObjective(opt.quicksum(weight_points[i] * served[i] for i in range(self.num_nodes)))model.setMaximize()# model.hideOutput()# 优化求解model.optimize()if __name__ == '__main__':flp = SCP_FLP()# 算例Scp41flp.prepare_data('./scp41.txt')# 集覆盖问题flp.cover_model()# 最大覆盖问题flp.max_cover_model()

2.3 数据结果

集覆盖问题结果

最大覆盖问题结果

参考文献

[1] Owen S H , Daskin M S . Strategic facility location: A review[J]. Euro.j.oper.res, 1998, 111(3):423-447.