节约里程法求解CVRP问题

发布时间：2024-11-22 11:03

积极解决问题：遇到问题时，寻求解决办法而非抱怨。 #生活技巧# #心理调节技巧# #积极心态调整#

节约里程法求解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

【结果展示】序贯法倾向于使用较少的车，且最后一辆车的装载量一般是最低的。
在这里插入图片描述

一个配送中心9个客户点

在这里插入图片描述

一个配送中心31个客户点 2. 2 并列法

# -*- 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

【结果展示】并列法倾向于使用较多的车辆，且车辆装载稍微均匀一些。
在这里插入图片描述

一个配送中心9个客户点

在这里插入图片描述

一个配送中心31个客户点

3. 总结

序贯的算法写的比较冗余，在写并列算法的时候进行了一点改进。总体来说序贯法“倾向于”使用较少的车辆，相应的总里程可能长一点，而并列算法倾向于使用更多的车辆，其总里程可能稍微短一些。节约里程法可以获得一个比较优的解，但相比启发式算法（遗传算法啊、粒子群算法等），其解的质量还是差一些，不过CW算法是确定性算法，计算时间比启发式算法少的多。

网址：节约里程法求解CVRP问题 https://www.yuejiaxmz.com/news/view/190002

上一篇：节约里程法求解TSP问题

下一篇：两个例子

节约里程法求解CVRP问题