数学建模.rar

#!/usr/bin/env python # coding: utf-8 # In[32]: ## 环境设定 import numpy as np import matplotlib.pyplot as plt import random from deap import base, tools, creator, algorithms params = { 'font.family': 'serif', 'figure.dpi': 300, 'savefig.dpi': 300, 'font.size': 12, 'legend.fontsize': 'small' } plt.rcParams.update(params) from copy import deepcopy # In[33]: ## 问题定义 creator.create('FitnessMin', base.Fitness, weights=(-1.0,)) # 最小化问题 # 给个体一个routes属性用来记录其表示的路线 creator.create('Individual', list, fitness=creator.FitnessMin) # In[51]: #赋值？？？ dataDict = {} # 节点坐标，节点0是配送中心的坐标 dataDict['NodeCoor'] = [] # 将配送中心的需求设置为0 dataDict['Demand'] = [0,] # 将配送中心的服务时间设置为0 dataDict['Timewindow'] = [(0,0),] dataDict['MaxLoad'] = dataDict['Velocity'] = # 车辆的平均行驶速度 fixedCost = # 一个配送员及其车辆平摊到一次配送的固定成本和折旧成本 maxPenalty = # 订单延误的最高赔偿金额 penaltyParameter = # 惩罚函数比例系数 # In[52]: #生成路径 def genInd(dataDict = dataDict): nCustomer = len(dataDict['NodeCoor']) - 1 # 本次配送共含客户数 perm = np.random.permutation(nCustomer) + 1 # 生成客户的随机排列,编号为1--n pointer = 0 # 迭代指针 lowPointer = 0 # 指针指向下界 permSlice = [] # 当指针不指向序列末尾时 while pointer < nCustomer -1: vehicleLoad = 0 # 当不超载时，继续装载 while (vehicleLoad < dataDict['MaxLoad']) and (pointer < nCustomer -1): vehicleLoad += dataDict['Demand'][perm[pointer]] pointer += 1 if lowPointer+1 < pointer: tempPointer = np.random.randint(lowPointer+1, pointer) permSlice.append(perm[lowPointer:tempPointer].tolist()) lowPointer = tempPointer pointer = tempPointer else: permSlice.append(perm[lowPointer::].tolist()) break # 将路线片段合并为染色体 ind = [0] for eachRoute in permSlice: ind = ind + eachRoute + [0] return ind # In[53]: ## 评价函数 # 染色体解码：从染色体解码回路径片段，每条路径都是以0为开头与结尾 def decodeInd(ind): indCopy = np.array(deepcopy(ind)) # 复制ind，防止直接对染色体进行改动 idxList = list(range(len(indCopy))) zeroIdx = np.asarray(idxList)[indCopy == 0] routes = [] for i,j in zip(zeroIdx[0::], zeroIdx[1::]): routes.append(ind[i:j]+[0]) return routes # In[54]: # 计算距离，根据给出的坐标pos1和pos2，返回两点之间的距离 def calDist(pos1, pos2): return np.sqrt((pos1[0] - pos2[0])*(pos1[0] - pos2[0]) + (pos1[1] - pos2[1])*(pos1[1] - pos2[1])) # In[55]: # 根据给定路径，计算到达该路径上各顾客的时间 def calcRouteServiceTime(route, dataDict = dataDict): serviceTime = [0] * (len(route) - 2) arrivalTime = calDist(dataDict['NodeCoor'][0], dataDict['NodeCoor'][route[1]])/dataDict['Velocity'] arrivalTime = max(arrivalTime, dataDict['Timewindow'][route[1]][0]) serviceTime[0] = arrivalTime for i in range(1, len(route)-2): # 计算从路径上当前节点[i]到下一个节点[i+1]的花费的时间 arrivalTime += calDist(dataDict['NodeCoor'][route[i]], dataDict['NodeCoor'][route[i+1]])/dataDict['Velocity'] arrivalTime = max(arrivalTime, dataDict['Timewindow'][route[i+1]][0]) serviceTime[i] = arrivalTime return serviceTime # In[56]: # 时间惩罚函数 def timePenalty(ind, routes): timeArrangement = timeTable(routes) # 对给定路线，计算到达每个客户的时间 # 索引给定的最迟到达时间 desiredTime = [dataDict['Timewindow'][ind[i]][1] for i in range(len(ind))] # 如果最迟到达时间大于实际到达客户的时间，则延迟为0，否则延迟设为实际到达时间与最迟到达时间之差 timeDelay = [max(timeArrangement[i]-desiredTime[i],0) for i in range(len(ind))] if timeDelay < maxPenalty: return penaltyParameter*sum(timeDelay) else: return maxPenalty # In[57]: # 返回给定路径的总长度 def calRouteLen(routes,dataDict=dataDict): totalDistance = 0 # 记录各条路线的总长度 for eachRoute in routes: # 从每条路径中抽取相邻两个节点，计算节点距离并进行累加 for i,j in zip(eachRoute[0::], eachRoute[1::]): totalDistance += calDist(dataDict['NodeCoor'][i], dataDict['NodeCoor'][j]) return totalDistance # In[58]: # 返回目标函数 def evaluate(ind): routes = decodeInd(ind) # 将个体解码为路线 totalDistance = calRouteLen(routes) return (len(routes)*fixedCost + totalDistance + timePenalty(ind,routes)) # In[59]: ## 交叉操作 # 生成子代 def genChild(ind1, ind2, nTrail=5): # 在ind1中随机选择一段子路径subroute1，将其前置 routes1 = decodeInd(ind1) # 将ind1解码成路径 numSubroute1 = len(routes1) # 子路径数量 subroute1 = routes1[np.random.randint(0, numSubroute1)] # 将subroute1中没有出现的顾客按照其在ind2中的顺序排列成一个序列 unvisited = set(ind1) - set(subroute1) # 在subroute1中没有出现访问的顾客 unvisitedPerm = [digit for digit in ind2 if digit in unvisited] # 按照在ind2中的顺序排列 # 多次重复随机打断，选取适应度最好的个体 bestRoute = None # 容器 bestFit = np.inf for _ in range(nTrail): # 将该序列随机打断为numSubroute1-1条子路径 breakPos = [0]+random.sample(range(1,len(unvisitedPerm)),numSubroute1-2) # 产生numSubroute1-2个断点 breakPos.sort() breakSubroute = [] for i,j in zip(breakPos[0::], breakPos[1::]): breakSubroute.append([0]+unvisitedPerm[i:j]+[0]) breakSubroute.append([0]+unvisitedPerm[j:]+[0]) # 更新适应度最佳的打断方式 # 将先前取出的subroute1添加入打断结果，得到完整的配送方案 breakSubroute.append(subroute1) # 评价生成的子路径 routesFit = calRouteLen(breakSubroute) + loadPenalty(breakSubroute) if routesFit < bestFit: bestRoute = breakSubroute bestFit = routesFit # 将得到的适应度最佳路径bestRoute合并为一个染色体 child = [] for eachRoute in bestRoute: child += eachRoute[:-1] return child+[0] # 交叉操作 def crossover(ind1, ind2): ind1[:], ind2[:] = genChild(ind1, ind2), genChild(ind2, ind1) return ind1, ind2 # In[60]: ## 突变操作 def opt(route,dataDict=dataDict, k=2, c1=1.0, c2=500.0): nCities = len(route) # 城市数 optimizedRoute = route # 最优路径 desiredTime = [dataDict['Timewindow'][route[i]][1] for i in range(len(route))] serviceTime = calcRouteServiceTime(route) timewindowCost = [max(serviceTime[i]-desiredTime[1:-1][i],0) for i in range(len(serviceTime))] timewindowCost = np.sum(timewindowCost)/len(timewindowCost) minCost = c1*calRouteLen([route]) + c2*timewindowCost # 最优路径代价 for i in range(1,nCities-2): for j in range(i+k, nCities): if j-i == 1: continue reversedRoute = route[:i]+route[i:j][::-1]+route[j:]# 翻转后的路径 # 代价函数中需要同时兼顾到达时间和路径长度 desiredTime = [dataDict['Timewindow'][reversedRoute[i]][1] for i in range(len(reversedRoute))] serviceTime = calcRouteServiceTime(reversedRoute) timewindowCost = [max(serviceTime[i]-desiredTime[1:-1][i],0) for i in range(len(serviceTime))] timewindowCost = np.sum(timewindowCost)/len(timewindowCost) reversedRouteCost = c1*calRouteLen([reversedRoute]) +