选址问题是运筹学中经典的问题之一。选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用，如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。选址问题是运筹学中非常经典的问题。该问题是指在确定选址对象，选址目标区，成本函数以及约束条件的前提下，以总物流成本最低或总服务水平最优或社会效益最大化为目标，确定物流系统中物流节点的数量，位置，从而合理规划物流网络结构。选址问题在公司实现其经营战略与目标的过程中有着重大的意义。选址的好坏直接影响到生产成本，服务时间，服务质量等等，进而影响公司的利润与其在商业市场上的竞争力，甚至决定了企业的命运。一个好的选址可以减少生产成本，节省顾客购买时间，便利顾客，而差的选址会带来物流中的不便与损失。由于选址是一项长期性投资，一旦确定下来就不能随意更改，因此规划其位置前必须进行深入的调查和周密的考虑。
方法1：精确重心法
重心法适用于选址区域为连续平面，以球面距离或者欧式距离为距离形式，以总运输成本最低为目标函数的选址问题。重心法选址模型来源于解析几何，其将物流网络中的需求点看作一平面内的点，把需求量作为重量，一般选取出这一平面内的需求点的重心点作为枢纽，以达到减少运输成本的目的。重心法目标函数为：
TC表示总运输成本，d表示各个网点到选址点的距离，W表示运输费率，C表示货量。可以把W和C是对距离的加权，设置成其他变量也可以。精确重心法迭代的过程。
import numpy as np import pandas as pd import math as m from math import radians, cos, sin, asin, sqrt #球面距离函数 def geodistance(lng1,lat1,lng2,lat2): #lng1,lat1,lng2,lat2 = (120.12802999999997,30.28708,115.86572000000001,28.7427) lng1, lat1, lng2, lat2 = map(radians, [float(lng1), float(lat1), float(lng2), float(lat2)]) # 经纬度转换成弧度 dlon=lng2-lng1 dlat=lat2-lat1 a=sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2 distance=2*asin(sqrt(a))*6371*1000 # 地球平均半径，6371km distance=round(distance/1000,3) return distance data = pd.read_excel("data1212.xls")#W,C是费率和货量，对距离进行加权，转换成运费成本。 #精确重心法迭代 WC = np.array(data['W']) * np.array(data['C']) WCX = (np.array(data['X_c']) * WC).sum() WCY = (np.array(data['Y_c']) * WC).sum() x0 = WCX / WC.sum()#初始等效重心 y0 = WCY / WC.sum()#初始等效重心 d_j=[] for m in range(len(np.array(data['X_c']))): d_j.append(geodistance(np.array(data['X_c'])[m],np.array(data['Y_c'])[m],x0,y0))#球面距离 #d_j.append(((np.array(data['X_c'])[m] - x0)**2 + (np.array(data['Y_c'])[m]-y0)**2)**0.5) #欧式距离 T= (WC * d_j).sum()#算总成本 print('重心法初始选点位置：（{}，{})'.format(x0,y0)) print('总费用T0：{}'.format(T)) #选址迭代 for i in range(10): WC_j = WC/d_j WCX_j = ((np.array(data['X_c']) * WC)/d_j).sum() WCY_j = ((np.array(data['Y_c']) * WC)/d_j).sum() x = WCX_j / WC_j.sum() y = WCY_j / WC_j.sum() d_j=[] for j in range(len(np.array(data['X_c']))): d_j.append(geodistance(np.array(data['X_c'])[j],np.array(data['Y_c'])[j],x,y))#球面距离 #d_j.append(((np.array(data['X_c'])[j] - x)**2 + (np.array(data['Y_c'])[j]-y)**2)**0.5) #欧式距离 T = (WC * d_j).sum() print('经{}次迭代后选址点位置：({},{})'.format(i+1,x,y)) print('总费用T{}：{}'.format(i+1,T))
输出结果：
data数据样式：
最终选址确定在经纬度：113.28,23.02 总运输成本：42557.4182
方法2：遗传算法选址
遗传算法是计算数学中用于解决最佳化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。 遗传算法是一类借鉴生物界的进化规律(适者生存，优胜劣汰遗传机制)演化而来的随机化搜索方法，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法的原理不在这里详细说明，感兴趣的可看我前面的文章。1.构造遗传算法数学模型
#搭建遗传算法问题框架，单个设施选址 import numpy as np import geatpy as ea #选址目标函数 def km1(x,y): K=0 for i in range(len(data)): K+=geodistance(x,y,data.X_c.values[i],data.Y_c.values[i])*data.W.values[i]*data.C.values[i] return K class MyProblem(ea.Problem): # 继承Problem父类 def __init__(self): name = 'MyProblem' # 初始化name（函数名称，可以随意设置） M = 1 # 初始化M（目标维数） maxormins = [1] # 初始化maxormins（目标最小最大化标记列表，1：最小化该目标；-1：最大化该目标） Dim = 2 # 初始化Dim（决策变量维数） varTypes = [0] * Dim # 初始化varTypes（决策变量的类型，元素为0表示对应的变量是连续的；1表示是离散的） lb = [100, 20] # 决策变量下界 ub = [120, 26] # 决策变量上界 lbin = [1,1] # 决策变量下边界（0表示不包含该变量的下边界，1表示包含） ubin = [1,1] # 决策变量上边界（0表示不包含该变量的上边界，1表示包含） # 调用父类构造方法完成实例化 ea.Problem.__init__(self, name, M, maxormins, Dim, varTypes, lb, ub, lbin, ubin) def evalVars(self, Vars): # 目标函数 x1 = Vars[:, [0]] x2 = Vars[:, [1]] f = km1(x1[0],x2[0]) for mm in range(1,10):#跟后面种群数相同 f=np.vstack((f,km1(x1[mm],x2[mm]))) ###设置约束范围 CV = np.hstack([x1- 130, x2 - 25]) return f, CV def calReferObjV(self): # 设定目标数参考值（本问题目标函数参考值设定为理论最优值）可不设置，对结果无影响 referenceObjV = np.array([[300000]]) return referenceObjV
2.遗传算法求解 本例是一个很简单的单设施选址问题，种群暂设置为10个，复杂的问题可设置更多种群；迭代次数设置为100次。
#遗传算法求解 if __name__ == '__main__': # 实例化问题对象 problem = MyProblem() # 构建算法 algorithm = ea.soea_DE_rand_1_bin_templet(problem, ea.Population(Encoding='RI', NIND=10), MAXGEN=100, # 最大进化代数。 logTras=10) # 表示每隔多少代记录一次日志信息，0表示不记录。 algorithm.mutOper.F = 0.5 # 差分进化中的参数F algorithm.recOper.XOVR = 0.7 # 重组概率 # 求解 res = ea.optimize(algorithm, verbose=True, drawing=1, outputMsg=True, drawLog=False, saveFlag=True) print(res)
3.遗传算法求解结果。
遗传算法求解结果经纬度坐标及最小运输成本结果基本相同，可见两种方法都能解决选址问题。一个完整的选址问题需考虑的因素非常多，还要考虑道路交通情况、政策情况、该地是否有合适仓库、仓库租赁及人工费用等。实际业务中一般是离散选址的问题，先找到一些可以备选的仓库，再通过整数规划或启发式算法求解。
