多配送中心VRP建模与求解 |
您所在的位置：网站首页 › 路径优化代码 › 多配送中心VRP建模与求解 |
多配送中心VRP建模与求解
|
多配送中心VRP建模与求解—基于粒子群算法
1 多配送中心VRP
多配送中心的车辆路径问题是 经典VRP 的扩展，它研究的是有多个车场同时对若干个客户进行服务，每个客户都有一定的货物需求。所要确定的是客户点由哪个配送中心服务，并对服务时的车辆路径进行优化，以便达到成本最低、时间最短等目标。 2 课题场景设计 2.1 场景单向：纯取货/纯送货； 多配送中心：存在多个配送中心/车场； 单车型：只考虑一种车型， 需求不可拆分：客户需求只能有一辆车满足； 车辆封闭：完成配送任务的车辆需回到配送中心； 车辆充足：不限制车辆数量，即配送车辆需求均能满足； 非满载：任意客户点的需求量小于车辆最大载重； 2.2 要求优化目标：最小化车辆启动成本和车辆行驶成本之和； 约束条件：车辆行驶距离约束，重量约束； 已知信息：配送中心位置、客户点位置、客户点需求、车辆最大载重、车辆最大行驶距离、车辆启动成本、车辆单位距离行驶成本； 3 数学模型 3.1 符号说明
多配送中心VRP问题的求解，要比CVRP难度大得多，目前对于该问题的求解大多拆分为两个阶段进行：①首先先将客户点分配给配送中心，转化为单配送中心问题；②在对每一个配送中心的路径进行优化。 本文也采用两阶段方法进行求解： ①将客户点分配给最近的配送中心； ②在对分配好的客户点配送中心集合进行路线优化。 粒子群算法相关设计见【CVRP建模与求解-基于粒子群算法（python实现）】，本算法在它的基础上进行修改以适应新场景的求解。 4.2 python程序设计 # -*- coding: utf-8 -*- import math import random import pandas as pd import matplotlib.pyplot as plt from matplotlib.pylab import mpl mpl.rcParams['font.sans-serif'] = ['SimHei'] # 添加这条可以让图形显示中文 def calDistance(CityCoordinates): ''' 计算城市间距离 输入：CityCoordinates-城市坐标； 输出：城市间距离矩阵-dis_matrix ''' dis_matrix = pd.DataFrame(data=None,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates))) for i in range(len(CityCoordinates)): xi,yi = CityCoordinates[i][0],CityCoordinates[i][1] for j in range(len(CityCoordinates)): xj,yj = CityCoordinates[j][0],CityCoordinates[j][1] dis_matrix.iloc[i,j] = round(math.sqrt((xi-xj)**2+(yi-yj)**2),2) return dis_matrix def assign_distribution_center(dis_matrix,DC,C): ''' Parameters: dis_matrix : 距离矩阵 DC : 配送中心个数 C : 客户点个数 Returns: d-存储分配给配送中心的客户点，list最后嵌套list ''' d = [[] for i in range(DC)]#存储分配的列表 for i in range(DC,DC+C): d_i = [dis_matrix.loc[i,j] for j in range(DC)]#取出当前客户分别距离配送中心的距离 min_dis_index = d_i.index(min(d_i))#取出最近的配送中心 d[min_dis_index].append(i)#将客户点分配给配送中心 return d def greedy(CityCoordinates,dis_matrix,DC,certer_number): ''' 贪婪策略构造初始解 输入：CityCoordinates-节点坐标,dis_matrix-距离矩阵 输出：初始解-line ''' #修改dis_matrix以适应求解需要 dis_matrix = dis_matrix.iloc[[certer_number]+CityCoordinates,[certer_number]+CityCoordinates].astype('float64')#只取当前需要的配送中心和客户点 for i in CityCoordinates:dis_matrix.loc[i,i]=math.pow(10,10) dis_matrix.loc[:,certer_number]=math.pow(10,10)#配送中心不在编码内 line = []#初始化 now_cus = random.sample(CityCoordinates,1)[0]#随机生成出发点 line.append(now_cus)#添加当前城市到路径 dis_matrix.loc[:,now_cus] = math.pow(10,10)#更新距离矩阵，已经过客户点不再被取出 for i in range(1,len(CityCoordinates)): next_cus = dis_matrix.loc[now_cus,:].idxmin()#距离最近的城市 line.append(next_cus)#添加进路径 dis_matrix.loc[:,next_cus] = math.pow(10,10)#更新距离矩阵 now_cus = next_cus#更新当前城市 return line def calFitness(birdPop,certer_number,Demand,dis_matrix,CAPACITY,DISTABCE,C0,C1): ''' 贪婪策略分配车辆（解码），计算路径距离（评价函数） 输入：birdPop-路径，Demand-客户需求,dis_matrix-城市间距离矩阵，CAPACITY-车辆最大载重,DISTABCE-车辆最大行驶距离,C0-车辆启动成本,C1-车辆单位距离行驶成本； 输出：birdPop_car-分车后路径,fits-适应度 ''' birdPop_car,fits = [],[]#初始化 for j in range(len(birdPop)): bird = birdPop[j] lines = []#存储线路分车 line = [certer_number]#每辆车服务客户点，起点是配送中心 dis_sum = 0#线路距离 dis,d = 0,0#当前客户距离前一个客户的距离、当前客户需求量 i = 0#指向配送中心 while i |
【本文地址】
今日新闻 |
推荐新闻 |