往期优质资源

CVRP系列

遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法

MDVRP系列

遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法

VRPTW系列

遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法

HVRP系列

遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法

MDHFVRPTW系列

遗传算法
蚁群算法
禁忌搜索算法
模拟退火算法
自适应大邻域算法
粒子群算法
量子粒子群算法
差分进化算法

1. 适用场景

求解CVRP
车辆类型单一
车辆容量不小于需求节点最大需求
单一车辆基地

2. 改进效果对比

这里做了简单的参数敏感性分析，比较不同参数组合下两个版本code的最优值与求解时间的差异。具体为：1）设定信息素挥发因子为0.1,0.3三个不同等级；2）设定信息启发式因子为1,2,3,4,5不同值；3）设定期望启发式因子为1,2,3,4,5不同值，其他参数固定不变：最大迭代次数为300，车辆容量为80。

2.1实验结果

rho=0.1：
在这里插入图片描述
rho=0.3：

2.2 改进前后算法性能对比

求解时间对比（红色为改进后，蓝色为改进前）：
在这里插入图片描述
行驶距离对比（红色为改进后，蓝色为改进前）：

可以直观看出，改进后算法求解时间略有增加，平均增加3.10%，目标函数平均优化1.38%。

3. 求解结果

（1）收敛曲线
在这里插入图片描述

（2）车辆路径
在这里插入图片描述
（3）输出文件

在这里插入图片描述

4. 改进内容

本期代码在前期代码的基础上做了以下改进：

增加距离矩阵，减少代码中重复计算节点间距离代码
引入文献中基于图论的Split方法，在给定节点id序列时，可求得最优分割方案

除了以上关键改动之外，还对代码做了细小调整。

5. 部分代码

（1）数据结构

# 数据结构：解
class Sol():def __init__(self):self.node_no_seq=None # 解的编码self.obj=None # 目标函数self.action_id=None # 算子idself.route_list=None # 解的解码self.route_distance = None  # 车辆路径的长度集合
# 数据结构：网络节点
class Demand():def __init__(self):self.id = 0 # 节点idself.x_coord = 0 # 节点平面横坐标self.y_coord = 0  # 节点平面纵坐标self.demand = 0 # 节点需求
# 数据结构：全局参数
class Model():def __init__(self):self.best_sol = None # 全局最优解self.demand_dict = {}  # 需求节点集合self.demand_id_list = []self.sol_list = []  # 解的集合self.depot = None # 车场节点self.number_of_nodes = 0 # 需求节点数量self.vehicle_cap = 80 # 车辆最大容量self.distance_matrix = {}self.popsize = 100 # 种群规模self.alpha = 2 # 信息启发式因子self.beta = 3 # 期望启发式因子self.Q = 100 # 信息素总量self.rho = 0.5 # 信息素挥发因子self.tau = {} # 弧信息素集合self.vehicle_cap=0  # 车辆最大容量

（2）距离矩阵

def calDistanceMatrix(model):for i in range(len(model.demand_id_list)):f_n = model.demand_id_list[i]for j in range(i + 1, len(model.demand_id_list)):t_n = model.demand_id_list[j]dist = math.sqrt((model.demand_dict[f_n].x_coord - model.demand_dict[t_n].x_coord) ** 2+ (model.demand_dict[f_n].y_coord - model.demand_dict[t_n].y_coord) ** 2)model.distance_matrix[f_n, t_n] = distmodel.distance_matrix[t_n, f_n] = distmodel.tau[f_n, t_n] = 100model.tau[t_n, f_n] = 100dist = math.sqrt((model.demand_dict[f_n].x_coord - model.depot.x_coord) ** 2+ (model.demand_dict[f_n].y_coord - model.depot.y_coord) ** 2)model.distance_matrix[f_n, model.depot.id] = distmodel.distance_matrix[model.depot.id, f_n] = dist

（3）路径提取

def extractRoutes(node_no_seq,P,depot_id):route_list = []route = []p = P[node_no_seq[0]]for node_seq in node_no_seq:if P[node_seq] == p:route.append(node_seq)else:route.insert(0,depot_id)route.append(depot_id)route_list.append(route)route = [node_seq]p = P[node_seq]return route_list

（4）蚁群移动

# 蚂蚁移动
def movePosition(model):sol_list=[]local_sol=Sol()local_sol.obj=float('inf')for _ in range(model.popsize):#随机初始化蚂蚁为止node_no_seq=[random.randint(0,len(model.demand_id_list)-1)]all_node_no_seq=copy.deepcopy(model.demand_id_list)all_node_no_seq.remove(node_no_seq[-1])#确定下一个访问节点while len(all_node_no_seq)>0:next_node_no=searchNextNode(model,node_no_seq[-1],all_node_no_seq)node_no_seq.append(next_node_no)all_node_no_seq.remove(next_node_no)sol=Sol()sol.node_no_seq=node_no_seqsol.obj,sol.route_list,sol.route_distance=calObj(node_no_seq,model)sol_list.append(sol)if sol.obj < local_sol.obj:local_sol = copy.deepcopy(sol)model.sol_list=copy.deepcopy(sol_list)if local_sol.obj<model.best_sol.obj:model.best_sol=copy.deepcopy(local_sol)
# 搜索下一移动节点
def searchNextNode(model,current_node_no,SE_List):if len(SE_List) == 1:return SE_List[0]prob=np.zeros(len(SE_List))for i,node_no in enumerate(SE_List):eta=1/model.distance_matrix[current_node_no,node_no]tau=model.tau[current_node_no,node_no]prob[i]=((eta**model.alpha)*(tau**model.beta))#采用轮盘法选择下一个访问节点cumsumprob=(prob/sum(prob)).cumsum()cumsumprob -= np.random.rand()return SE_List[list(cumsumprob > 0).index(True)]

（5）收敛曲线

# 绘制目标函数收敛曲线
def plotObj(obj_list):plt.rcParams['font.sans-serif'] = ['SimHei']  #show chineseplt.rcParams['axes.unicode_minus'] = False  # Show minus signplt.plot(np.arange(1,len(obj_list)+1),obj_list)plt.xlabel('Iterations')plt.ylabel('Obj Value')plt.grid()plt.xlim(1,len(obj_list)+1)plt.show()

（6）车辆路径

# 绘制优化车辆路径
def plotRoutes(model):for route in model.best_sol.route_list:x_coord=[]y_coord=[]for node_no in route:x_coord.append(model.demand_dict[node_no].x_coord)y_coord.append(model.demand_dict[node_no].y_coord)plt.plot(x_coord,y_coord,marker='s',color='b',linewidth=0.5)plt.show()

（7）输出结果

# 输出结果
def outPut(model):work=xlsxwriter.Workbook('result.xlsx')worksheet=work.add_worksheet()worksheet.write(0, 0, 'id')worksheet.write(0, 1, 'route')worksheet.write(0, 2, 'distance')worksheet.write(0, 3, 'total_distance')worksheet.write(1,3,model.best_sol.obj)for id,route in enumerate(model.best_sol.route_list):r=[str(i)for i in route]worksheet.write(id + 1, 0, f'v{str(id + 1)}')worksheet.write(id + 1, 1, '-'.join(r))worksheet.write(id + 1, 2, model.best_sol.route_distance[id])work.close()