多车场路径优化丨遗传算法求解MDCVRP问题
python语言编写遗传算法求解多车场有载重约束的路径优化问题MDCVRP
路径优化系列文章：
- 1、路径优化历史文章
- 2、路径优化丨带时间窗和载重约束的CVRPTW问题-改进遗传算法：算例RC108
- 3、路径优化丨带时间窗和载重约束的CVRPTW问题-改进和声搜索算法：算例RC108
- 4、路径优化丨复现论文-网约拼车出行的乘客车辆匹配及路径优化
- 5、多车场路径优化丨遗传算法求解MDCVRP问题
引言
问题描述
车场车辆路径问题 （MDVRP）是基本车辆路径问题（VRP）的扩展，指的是有数个车场同时对多个用户进行服务，各用户有一定的货物需求，每个车场都可提供货物，并有车队负责执行运输任务，要求对各车场的车辆和行驶路线进行适当的安排，在保证满足各用户的需求的前提下，使总的运输成本最低。
问题满足假设：
-
1、各车场派出车辆的数目不能超过该车场所拥有的车辆数；
-
2、各车辆都是从各自的车场出发，并回到原车场；
-
3、每个用户只能被一辆车服务一次；4、车辆满足载重约束。
数学模型
数学模型：
算法数据处理
数据：
本文是数据是3个车场和100个需求量，各个车场的车辆数是20，具体车场和需求点的坐标及需求点的需求量见两个depot和demand文件，车辆载重暂时设为50。模型是一般的路径优化模型，目标函数设置为3个车场派出的所有车辆的路径总长度。
以3个车场为原点，分别和100个需求点组合，计算组合后的任意两点的距离，形成3个101×101的距离矩阵。距离矩阵计算比较简单，计算矩阵右上角的值即可，左下角的值和右上角的值对称。
距离矩阵
def distance(dep_demand): # 3个点和需求点距离矩阵计算
dis = np.zeros((len(dep_demand),len(dep_demand)))
for i in range(len(dep_demand)-1):
for j in range(i+1):
point1 = dep_demand[i]
point2 = dep_demand[j]
di = np.sqrt((point1[0]-point2[0])**2+(point1[1]-point2[1])**2)
dis[i,j], dis[j,i] = di, di # 距离关于对角线对称
return dis
编码及解码
编码
采用实数编码的方式，用1到100共100个数表示100个需求点，随机打乱即是一个可行的编码：
road = random.sample(range(1,101),100)
一个可行编码:
road = [95, 34, 71, 23, 18, 17, 80, 91, 96, 60, 50, 28, 72, 37, 30, 41, 33, 2, 15, 66, 36, 73, 38, 82, 49, 84, 31, 16, 3, 7, 43, 6, 4, 20, 13, 5, 93, 52, 70, 53, 29, 89, 67, 98, 26, 45, 100, 79, 87, 64, 59, 81, 44, 61, 63, 83, 8, 76, 92, 12, 32, 1, 9, 77, 75, 46, 65, 25, 85, 24, 69, 86, 58, 19, 22, 74, 88, 90, 94, 21, 55, 39, 42, 51, 27, 10, 48, 35, 97, 57, 11, 56, 40, 54, 62, 99, 68, 78, 14, 47]
解码
核心是遍历到某个需求点时，寻找最优车场的最优车辆。一个车场的最优车辆寻找如下：
step1:遍历该车场的所有车辆，如果至少有一辆车的剩余载重满足该需求点，计算对应车辆的最后一个点到该需求点的距离，再加上该需求点到对应回归车场的距离，转入步骤3，如果没有车辆的剩余载重满足，转入step2
step2:新增一辆车，
计算车场到该需求点的距离，再加上需求点到车场的距离，车场的最优车辆只有一个，即最优
step3:比较各个车辆对应的计算距离，最优个体是距离最短对应的车辆
3个车场的最优个体做比较，距离最短是整个系统的最优个体。这种车辆选择方式采用一种贪婪的思想，寻找使路径最短的车辆，一定程度上会加快最优路径的寻找。
核心代码如下:
def fitness(self,road):
p1, p2, p3 = [[]], [[]], [[]] # 存车场到需求点的路径
dis_p =[0, 0, 0]
d1, d2, d3 = [[]], [[]], [[]]
for w in range(len(road)):
point = road[w] # 新的点
p = [p1, p2, p3]
dis = [self.dis1, self.dis2, self.dis3] # 3个车场到需求点的距离矩阵
s = []
d = [d1, d2, d3]
location = []
for i in range(3):
p_now = p[i] # 依次从第1车场到第3车场
dis_now = dis[i]
d_now = d[i]
signal = 0
if len(p_now[-1]) > 0: # 如果最后一个车的装载情况非空
dx = []
loc = []
for j in range(len(p_now)): # 依次遍历对应车场的各个车
now_load = sum(d_now[j]) # 计算每个车的装载情况
if now_load + self.demand.iloc[point-1,-1] <= self.load: # 如果可以装
dw = dis_now[p_now[j][-1], point] + dis_now[point,0] # 计算其与上一个点的距离和回到车场的距离
dx.append(dw)
loc.append(j)
if len(dx)>0:
di = min(dx) # 挑选最小距离对应的车
idx = dx.index(min(dx))
best_idx = loc[idx]
if len(dx)==0: # 如果各个车都不能装，进入下一步
signal=1
if len(p_now[-1]) == 0 or signal==1: # 如果车场最后一个车是空车，或者上一步没装成功
now_car = len(p_now) # 现在的车场对应的车辆使用情况
if now_car + 1 <= self.car_number: # 如果使用车辆加1小于等于20辆，增加新车
if i ==0 :
p1.append([])
d1.append([])
if i ==1 :
p2.append([])
d2.append([])
if i ==2:
p3.append([])
d3.append([])
else: # 如果使用车辆加1大于20辆，距离赋予一个很大的值，对应车不能装，也没有增加新车
di = 100000
best_idx = 111111
if len(p_now[-1]) == 0: # 如果有新车
di = dis_now[0, point] + dis_now[point, 0] # 计算车场到需求点及回去的距离
best_idx = -1
s.append(di)
location.append(best_idx)
idx = s.index(min(s)) # 挑选最小距离对应的车场
idd = location[idx] # 对应车场对应的车辆选择
if idx ==0 : # 车场1对应车辆添加需求点，下面相同
p1[idd].append(point)
d1[idd].append(self.demand.iloc[point-1,-1])
if idx ==1 :
p2[idd].append(point)
d2[idd].append(self.demand.iloc[point-1,-1])
if idx ==2:
p3[idd].append(point)
d3[idd].append(self.demand.iloc[point-1,-1])
dis_p[idx] += min(s) # 各个车场对应的距离累计
return p1, p2, p3, dis_p, d1, d2, d3
遗传算法
路径交叉
采用pox的交叉方式，1到100随机生成一个数，假设生成的数是20，对于两个可行的编码road1和road2，大于20的基因不变，小于20的基因位置填入另一个体的编码：
以a=[1,3,2,4]和b=[2,4,1,3]为例，假设生成的数是3 ,a,b中的3,4基因不变，1和2位置填入对面的1,2基因，结果a1 = [2,3,1,4]，b1=[1,4,2,3]
核心代码:
def road_cross(self,road1,road2): # pox交叉
num = random.randint(1, len(road1)+1)
un1, un2 = [],[]
for i in range(len(road1)):
if road1[i] < num: # 小于num的编码
un1.append(road1[i])
road1[i] = 0 # 对应位置基因设为0
if road2[i] < num:
un2.append(road2[i])
road2[i] = 0
for j in range(len(road1)):
if road1[j] == 0:
road1[j] = un2[0] # road1对应位置填充road2小于num的基因
del un2[0] # 删除填充基因
if road2[j] == 0:
road2[j] = un1[0] # road2对应位置填充road1小于num的基因
del un1[0] # 删除填充基因
return road1, road2
路径变异
采用逆序变异的方式：随机生成两个位置对于两个位置的基因逆序。
如a=[1,3,2,4]，生成位置1和位置3，变异后的结果是a1=[2,3,1,4]
核心代码：
def road_mul(self,road): # 逆序变异
index = random.sample(range(len(road)), 2) # 随机生成两个位置
idx = list(set(index)) # 位置按先后顺序调整
d = road[idx[0]:idx[1] + 1]
d.reverse() # 逆序
road[idx[0]:idx[1] + 1] = d
return road
个体选择
采用精英策略，每次迭代选择最优的一半个体：
核心代码：
sort = np.array(answer).argsort() # 总长度从小到大的索引
Road1 = np.array(Road)[sort][:self.popsize].tolist() # 取一半
answer1 = np.array(answer)[sort][:self.popsize].tolist()
结果
主函数：
from decode import decoding
from ga import GA
parm_car = [50,20] # 载重和车场车辆数
de = decoding(parm_car) # 解码模块
parm_ga = [50,100,.8,.2] # 迭代次数，种群规模，交叉概率，变异概率
ga = GA(parm_ga,de)
road,answer,result = ga.ga_total() # 遗传寻优结果
p1, p2, p3, dis_p,d1, d2, d3 = de.fitness(road) # 各车场的路径等结果
de.draw(p1,p2,p3,dis_p) # 各车场路径
de.draw_change(result) # 路径总长度变化
运行结果展示：
路径图：
路径长度变化：
视频演示：
视频
多车场车辆路径优化丨遗传算法求解
参考文献
[1]邹彤,李宁,孙德宝等.多车场车辆路径问题的遗传算法[J].计算机工程与应用,2004(21):82-83.
完整算法+数据：
#关注 微信公众号：学长带你飞
# 主要更新方向：1、车间调度问题求解算法
# 2、学术写作技巧
# 3、读书感悟
# @Author : Jack Hao
可加微信：diligent-1618，请备注：学校-专业-昵称。
腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。
更多推荐
1
1- 0
已为社区贡献1条内容
所有评论(0)