【改进篇】Python实现VRP常见求解算法 |
您所在的位置：网站首页 › 遗传算法优化路径 › 【改进篇】Python实现VRP常见求解算法 |
【改进篇】Python实现VRP常见求解算法
|
基于python语言，实现经典遗传算法（GA）对车辆路径规划问题（CVRP）进行求解， 优化代码结构，改进Split函数 目录 往期优质资源1. 适用场景2. 改进效果对比3. 求解结果4. 改进内容5. 部分代码6. 完整代码参考 往期优质资源 python实现6种智能算法求解CVRP问题python实现7种智能算法求解MDVRP问题python实现7种智能算法求解MDVRPTW问题Python版MDHFVRPTW问题智能求解算法代码【TS算法】Python版MDHFVRPTW问题智能求解算法代码【SA算法】Python版MDHFVRPTW问题智能求解算法代码【GA算法】Python版MDHFVRPTW问题智能求解算法代码【DPSO算法】Python版MDHFVRPTW问题智能求解算法代码【DE算法】Python版MDHFVRPTW问题智能求解算法代码【ACO算法】Python版HVRP问题智能求解算法代码【GA算法】Python版HVRP问题智能求解算法代码【DPSO算法】 1. 适用场景 求解CVRP车辆类型单一车辆容量不小于需求节点最大需求单一车辆基地 2. 改进效果对比这里做了简单的参数敏感性分析，比较不同参数组合下两个版本code的最优值与求解时间的差异。具体为：依次设定交叉概率为0.7,0.8,0.9，其他参数固定不变：最大迭代次数为500，种群规模为100，选择个体为80，变异概率0.2。具体实验结果如下表： 可以看出，改进后的code，目标函数优化 3% 至 7% 不等，但牺牲了40%左右的计算时间。这里计算时间以秒为单位，所以改进后的代码运算时间还是可以接受的。 3. 求解结果（1）收敛曲线 （2）车辆路径 本期代码在前期代码的基础上做了以下改进： 增加距离矩阵，减少代码中重复计算节点间距离代码引入文献中基于图论的Split方法，在给定节点id序列时，可求得最优分割方案除了以上关键改动之外，还对代码做了细小调整。 5. 部分代码（1）数据结构 # 数据结构：解 class Sol(): def __init__(self): self.node_no_seq = None # 解的编码 self.obj_val = None # 目标函数 self.fitness = None # 适应度 self.route_list = None # 解的解码 # 数据结构：网络节点 class Demand(): def __init__(self): self.id = 0 # 节点id self.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.pc = 0.5 # 交叉概率 self.pm = 0.2 # 变异概率 self.n_select = 80 # 种群选择数量 self.popsize = 100 # 种群规模（2）距离矩阵 def cal_distance_matrix(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] = dist model.distance_matrix[t_n, f_n] = dist dist = 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] = dist model.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 plotObj(obj_list): plt.rcParams['font.sans-serif'] = ['SimHei'] #show chinese plt.rcParams['axes.unicode_minus'] = False # Show minus sign plt.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()（5）车辆路径 def plotRoutes(model): for route in model.best_sol.route_list: x_coord = [model.depot.x_coord] y_coord = [model.depot.y_coord] for node_no in route[1:-1]: x_coord.append(model.demand_dict[node_no].x_coord) y_coord.append(model.demand_dict[node_no].y_coord) x_coord.append(model.depot.x_coord) y_coord.append(model.depot.y_coord) plt.plot(x_coord, y_coord, marker='s', color='b', linewidth=0.5) plt.show()（6）主程序 def run(filepath,epochs,pc,pm,popsize,n_select,v_cap): """ :model filepath: Xlsx文件路径 :model epochs: 迭代次数 :model pc: 交叉概率 :model pm: 变异概率 :model popsize: 种群规模 :model n_select: 优秀父代保留数量 :model v_cap: 车辆容量 :model opt_type: 优化目标，0：最小化车辆数，1：最小化总行驶距离 :return: """ model=Model() model.vehicle_cap=v_cap model.pc=pc model.pm=pm model.popsize=popsize model.n_select=n_select readXlsxFile(filepath,model) cal_distance_matrix(model) genInitialSol(model) history_best_obj = [] best_sol=Sol() best_sol.obj_val=float('inf') model.best_sol=best_sol start = time.time() for ep in range(epochs): calFit(model) selectSol(model) crossSol(model) muSol(model) history_best_obj.append(model.best_sol.obj_val) print("%s/%s， best obj: %s time : %s" % (ep,epochs,model.best_sol.obj_val,time.time()-start)) plotObj(history_best_obj) plotRoutes(model) outPut(model) 6. 完整代码如有错误，欢迎交流。 有偿获取 参考 A simple and effective evolutionary algorithm for the vehicle routing problem |
【本文地址】
今日新闻 |
推荐新闻 |