节约里程法求解CVRP问题
积极解决问题:遇到问题时,寻求解决办法而非抱怨。 #生活技巧# #心理调节技巧# #积极心态调整#
节约里程法求解CVRP问题
1. 节约里程法简介
节约里程法(CW算法)是针对VRP问题开发的一个贪婪算法,基本思想是不断优先将合并后距离节约最大的线路进行合并,节约里程法分为两种:序贯法和并列法,两者基本思想一样,区别在于计算过程中处理线路的顺序,序贯法是一辆车一辆车的装,而并列法是允许并行装车。两种方法很难评价优劣,在不同的数据集上存在不同的优劣表现。节约算法的详细介绍可以看这里。
2. C-W算法求解CVRP
用CVRP进行测试,关于CVRP的建模和启发式求解在先前的博文中总结过【CVRP建模与求解-基于粒子群算法】,以下分别使用序贯法和并列法进行对CVRP问题进行求解。
2.1 序贯法# -*- coding: utf-8 -*- import math 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 draw_path(car_routes,CityCoordinates): ''' #画路径图 输入:line-路径,CityCoordinates-城市坐标; 输出:路径图 ''' for route in car_routes: x,y= [],[] for i in route: Coordinate = CityCoordinates[i] x.append(Coordinate[0]) y.append(Coordinate[1]) x.append(x[0]) y.append(y[0]) plt.plot(x, y,'o-', alpha=0.8, linewidth=0.8) plt.xlabel('x') plt.ylabel('y') plt.show() if __name__ == '__main__': car_load = 50 #0表示配送中心,1-31表示需求点 points = [(50, 50),(96, 24),(40, 5),(49, 8),(13, 7),(29, 89),(48, 30),(84, 39),(14, 47),(2, 24),(3, 82),(65, 10),(98, 52),(84, 25),(41, 69),(1, 65), (51, 71),(75, 83),(29, 32),(83, 3),(50, 93),(80, 94),(5, 42),(62, 70),(31, 62),(19, 97),(91, 75),(27, 49),(23, 15),(20, 70),(85, 60),(98, 85)] demand = [0,16,11,6,1,7,2,6,9,6,8,4,7,10,3,2,8,9,1,4,8,2,4,8,4,5,2,10,5,2,7,9] dis_matrix = calDistance(points)#计算城市间距离 #计算合并减少的里程 dis_com = pd.DataFrame(data=None,columns=["point1","point2","save_dis"]) for i in range(1,len(points)-1): for j in range(i+1,len(points)): detal = dis_matrix.iloc[0,i] + dis_matrix.iloc[0,j] - dis_matrix.iloc[i,j] dis_com = dis_com.append({"point1":i,"point2":j,"save_dis":detal}, ignore_index=True) dis_com = dis_com.sort_values(by="save_dis" , ascending=False).reset_index(drop=True)#排序 carLine,carLines = [],[]#记录分车 finished_point = []#记录已完成车辆 carDemand,carDemands = [],[]#记录车辆装载量 #序贯 while True: for i in range(len(dis_com)): if not carLine :#列表为空时直接合并 carLine.append(int(dis_com.loc[i,'point1'])) carLine.append(int(dis_com.loc[i,'point2'])) carDemand = demand[int(dis_com.loc[i,'point1'])] + demand[int(dis_com.loc[i,'point2'])] finished_point.append(int(dis_com.loc[i,'point1']))#全局 finished_point.append(int(dis_com.loc[i,'point2'])) continue if ((int(dis_com.loc[i,'point1']) in finished_point) & (int(dis_com.loc[i,'point2']) in finished_point))\ | ((int(dis_com.loc[i,'point1']) not in carLine) & (int(dis_com.loc[i,'point2']) not in carLine)):#两点都已完成,或两点都不在当前车辆服务的点中 continue else:#一点在车上,一点不在车上, if int(dis_com.loc[i,'point1']) == carLine[0]: if carDemand + demand[int(dis_com.loc[i,'point2'])] <= car_load: carDemand += demand[int(dis_com.loc[i,'point2'])] carLine.insert(0, int(dis_com.loc[i,'point2'])) finished_point.append(int(dis_com.loc[i,'point2'])) continue else: carDemands.append(carDemand) carLine = [0] + carLine + [0] carLines.append(carLine) carLine = [] carDemand = 0 elif int(dis_com.loc[i,'point1']) == carLine[-1]: if carDemand + demand[int(dis_com.loc[i,'point2'])] <= car_load: carDemand += demand[int(dis_com.loc[i,'point2'])] carLine.append(int(dis_com.loc[i,'point2'])) finished_point.append(int(dis_com.loc[i,'point2'])) continue else: carDemands.append(carDemand) carLine = [0] + carLine + [0] carLines.append(carLine) carLine = [] carDemand = 0 elif int(dis_com.loc[i,'point2']) == carLine[0]: if carDemand + demand[int(dis_com.loc[i,'point1'])] <= car_load: carDemand += demand[int(dis_com.loc[i,'point1'])] carLine.insert(0, int(dis_com.loc[i,'point1'])) finished_point.append(int(dis_com.loc[i,'point1'])) continue else: carDemands.append(carDemand) carLine = [0] + carLine + [0] carLines.append(carLine) carLine = [] carDemand = 0 elif int(dis_com.loc[i,'point2']) == carLine[-1]: if carDemand + demand[int(dis_com.loc[i,'point1'])] <= car_load : carDemand += demand[int(dis_com.loc[i,'point1'])] carLine.append(int(dis_com.loc[i,'point1'])) finished_point.append(int(dis_com.loc[i,'point1'])) continue else: carDemands.append(carDemand) carLine = [0] + carLine + [0] carLines.append(carLine) carLine = [] carDemand = 0 else:#一点不在,一点在线路中间,无法链接 continue #更新减少里程列表 dis_com = dis_com[~(dis_com['point1'].isin(finished_point)|dis_com['point2'].isin(finished_point))].reset_index(drop=True) break#跳出for循环 if sorted(finished_point) == list(range(1,len(points))): #最后一辆车 carDemands.append(carDemand) carLine = [0] + carLine + [0] carLines.append(carLine) carDemand = 0 carLine = [] break if dis_com.empty:#打补丁,存在列表空了但节点未全部服务的情况 carLine = list(set(list(range(1,len(points)))).difference(set(sorted(finished_point)))) for i in carLine:carDemand += demand[i] carLine = [0] + carLine + [0] carLines.append(carLine) break draw_path(carLines,points)#画路径图 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158
【结果展示】序贯法倾向于使用较少的车,且最后一辆车的装载量一般是最低的。
# -*- coding: utf-8 -*- """ Created on Sun May 23 00:23:31 2021 @author: Administrator """ # -*- coding: utf-8 -*- import math 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 indexfind(point1,point2,carLines): ''' 定位链接点在哪辆车【连接点表示已在车辆上的点,比如车辆0-1-2-3-0,合并点3-4,那么这里把3称为链接点】 输入:point1和point2-合并点,carLines-所有车辆服务点 输出:连接点位置 ''' for i in range(len(carLines)): if (point1 in carLines[i]) | (point2 in carLines[i]): return i def linkfind(carline,point1,point2): ''' 返回车辆中链接点的位置,连接点,和待合并点 输入:point1和point2-合并点,carLine-车辆服务点 输出:车辆中链接点的位置,连接点,和待合并点 ''' left = carline[0] right = carline[-1] if point1 == left: return 0,point1,point2 elif point2 == left: return 0,point2,point1 elif point1 == right : return -1,point1,point2 else: return -1,point2,point1 def draw_path(car_routes,CityCoordinates): ''' #画路径图 输入:line-路径,CityCoordinates-城市坐标; 输出:路径图 ''' for route in car_routes: x,y= [],[] for i in route: Coordinate = CityCoordinates[i] x.append(Coordinate[0]) y.append(Coordinate[1]) x.append(x[0]) y.append(y[0]) plt.plot(x, y,'o-', alpha=0.8, linewidth=0.8) plt.xlabel('x') plt.ylabel('y') plt.show() if __name__ == '__main__': car_load = 50 #0表示配送中心,1-31表示需求点 points = [(50, 50),(96, 24),(40, 5),(49, 8),(13, 7),(29, 89),(48, 30),(84, 39),(14, 47),(2, 24),(3, 82),(65, 10),(98, 52),(84, 25),(41, 69),(1, 65), (51, 71),(75, 83),(29, 32),(83, 3),(50, 93),(80, 94),(5, 42),(62, 70),(31, 62),(19, 97),(91, 75),(27, 49),(23, 15),(20, 70),(85, 60),(98, 85)] demand = [0,16,11,6,1,7,2,6,9,6,8,4,7,10,3,2,8,9,1,4,8,2,4,8,4,5,2,10,5,2,7,9] dis_matrix = calDistance(points)#计算城市间距离 #计算合并减少的里程 dis_com = pd.DataFrame(data=None,columns=["point1","point2","save_dis"]) for i in range(1,len(points)-1): for j in range(i+1,len(points)): detal = dis_matrix.iloc[0,i] + dis_matrix.iloc[0,j] - dis_matrix.iloc[i,j] dis_com = dis_com.append({"point1":i,"point2":j,"save_dis":detal}, ignore_index=True) dis_com = dis_com.sort_values(by="save_dis" , ascending=False).reset_index(drop=True)#排序 carLines = [[]]#记录分车 unfinished_point = []#在车辆两端的点 finished_point = []#记录已完成车辆 carDemands = [0]#记录车辆装载量 #并列 for i in range(len(dis_com)): if not carLines[-1] :#列表为空时 carLines[0].append(int(dis_com.loc[i,'point1'])) carLines[0].append(int(dis_com.loc[i,'point2'])) carDemands[0] = demand[int(dis_com.loc[i,'point1'])] + demand[int(dis_com.loc[i,'point2'])] unfinished_point.append(int(dis_com.loc[i,'point1']))#全局 unfinished_point.append(int(dis_com.loc[i,'point2'])) continue if ((int(dis_com.loc[i,'point1']) in unfinished_point) & (int(dis_com.loc[i,'point2']) in unfinished_point))\ | (int(dis_com.loc[i,'point1']) in finished_point) | (int(dis_com.loc[i,'point2']) in finished_point): continue#两点都装车,或有一点已完成 elif ((int(dis_com.loc[i,'point1']) not in unfinished_point) & (int(dis_com.loc[i,'point2']) not in unfinished_point)):#两点都不在,新的车 carLines.append([int(dis_com.loc[i,'point1']),int(dis_com.loc[i,'point2'])]) carDemands.append(demand[int(dis_com.loc[i,'point1'])] + demand[int(dis_com.loc[i,'point2'])]) unfinished_point.append(int(dis_com.loc[i,'point1'])) unfinished_point.append(int(dis_com.loc[i,'point2'])) else:#一点已装车且允许再衔接其他点,一点未装车, car_index = indexfind(int(dis_com.loc[i,'point1']),int(dis_com.loc[i,'point2']),carLines)#查看在哪辆车 link_index,link_point,point = linkfind(carLines[car_index],int(dis_com.loc[i,'point1']),int(dis_com.loc[i,'point2']))#确定链接位置和链接点 if carDemands[car_index] + demand[point] <= car_load: carDemands[car_index] += demand[point] if link_index == 0: unfinished_point.remove(link_point) unfinished_point.append(point) finished_point.append(link_point) carLines[car_index].insert(0, point) else: unfinished_point.remove(link_point) unfinished_point.append(point) finished_point.append(link_point) carLines[car_index].append(point) continue for i in carLines: i.append(0) i.insert(0,0) draw_path(carLines,points)#画路径图 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141
【结果展示】并列法倾向于使用较多的车辆,且车辆装载稍微均匀一些。
3. 总结
序贯的算法写的比较冗余,在写并列算法的时候进行了一点改进。总体来说序贯法“倾向于”使用较少的车辆,相应的总里程可能长一点,而并列算法倾向于使用更多的车辆,其总里程可能稍微短一些。节约里程法可以获得一个比较优的解,但相比启发式算法(遗传算法啊、粒子群算法等),其解的质量还是差一些,不过CW算法是确定性算法,计算时间比启发式算法少的多。
网址:节约里程法求解CVRP问题 https://www.yuejiaxmz.com/news/view/190002
相关内容
物流配送中心的VPR问题的节约里程法课件使用蛮力法求解数字迷问题(类似ABCAB*A = DDDDDD)
如何解决房屋居住中的能源节约问题?这些问题的解决方法有哪些环保效益?
求由方程siny=ln(x+y)确定的函数求详解求由方程si 爱问知识人
3种方法来解决人生中的问题
你对家里节约开支有什么办法?
垃圾分类的现存问题及解决方法
汽车保养6个小妙招你知道几个?解决问题还能节约成本!
法官约谈是什么程序?
一级建造师工程法规知识点:节约能源法