选址问题是运筹学中经典的问题之一。选址问题在生产生活、物流、甚至军事中都有着非常广泛的应用,如工厂、仓库、急救中心、消防站、垃圾处理中心、物流中心、导弹仓库的选址等。选址问题是运筹学中非常经典的问题。该问题是指在确定选址对象,选址目标区,成本函数以及约束条件的前提下,以总物流成本最低或总服务水平最优或社会效益最大化为目标,确定物流系统中物流节点的数量,位置,从而合理规划物流网络结构。选址问题在公司实现其经营战略与目标的过程中有着重大的意义。选址的好坏直接影响到生产成本,服务时间,服务质量等等,进而影响公司的利润与其在商业市场上的竞争力,甚至决定了企业的命运。一个好的选址可以减少生产成本,节省顾客购买时间,便利顾客,而差的选址会带来物流中的不便与损失。由于选址是一项长期性投资,一旦确定下来就不能随意更改,因此规划其位置前必须进行深入的调查和周密的考虑。
方法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.遗传算法求解结果。遗传算法求解结果经纬度坐标及最小运输成本结果基本相同,可见两种方法都能解决选址问题。一个完整的选址问题需考虑的因素非常多,还要考虑道路交通情况、政策情况、该地是否有合适仓库、仓库租赁及人工费用等。实际业务中一般是离散选址的问题,先找到一些可以备选的仓库,再通过整数规划或启发式算法求解。