粒子群算法DPSO-CVRP

import os import math import time import random from matplotlib import pyplot as plt from pandas import DataFrame, read_excel def city_distance(city_coordinates): # 计算城市间距离；输入：城市坐标；输出：城市间距离矩阵-dis_matrix distance_matrix = DataFrame(data=None, columns=range(len(city_coordinates)), index=range(len(city_coordinates))) for i in range(len(city_coordinates)): xi, yi = city_coordinates[i][0], city_coordinates[i][1] for j in range(len(city_coordinates)): xj, yj = city_coordinates[j][0], city_coordinates[j][1] distance_matrix.iloc[i, j] = round(math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2), 2) return distance_matrix def greedy(city_coordinates, distance_matrix): # 贪婪策略构造初始解,初始化时将VRP简化为TSP进行构造。输入：节点坐标,距离矩阵输出：初始解 distance_matrix = distance_matrix.astype('float64') for i in range(len(city_coordinates)): distance_matrix.loc[i, i] = math.pow(10, 10) distance_matrix.loc[:, 0] = math.pow(10, 10) # 0不在编码内 line = [] # 初始化 now_city = random.randint(1, len(city_coordinates) - 1) # 随机生成出发城市 line.append(now_city) # 添加当前城市到路径 distance_matrix.loc[:, now_city] = math.pow(10, 10) # 更新距离矩阵，已经过城市不再被取出 for i in range(1, len(city_coordinates) - 1): next_city = distance_matrix.loc[now_city, :].idxmin() # 距离最近的城市 line.append(next_city) # 添加进路径 distance_matrix.loc[:, next_city] = math.pow(10, 10) # 更新距离矩阵 now_city = next_city # 更新当前城市 return line def fitness(route, demands, distance_matrix, capacities, m_distance, start, cost): # 贪婪策略分配车辆（解码），计算路径距离 # 输入：路径，客户需求,城市间距离矩阵，车辆最大载重,车辆最大行驶距离,车辆启动成本,车辆单位距离行驶成本；输出：分车后路径,适应度 route_car, fit = [], [] # 初始化 for j in range(len(route)): bird = route[j] lines = [] # 存储线路分车 line = [0] # 每辆车服务客户点 dis_sum = 0 # 线路距离 dis, d = 0, 0 # 当前客户距离前一个客户的距离、当前客户需求量 i = 0 # 指向配送中心 while i < len(bird): if line == [0]: # 车辆未分配客户点 dis += distance_matrix.loc[0, bird[i]] # 记录距离 line.append(bird[i]) # 为客户点分车 d += demands[bird[i]] # 记录需求量 i += 1 # 指向下一个客户点 else: # 已分配客户点则需判断车辆载重和行驶距离 if (distance_matrix.loc[line[-1], bird[i]] + distance_matrix.loc[bird[i], 0] + dis <= m_distance) & ( d + demands[bird[i]] <= capacities): dis += distance_matrix.loc[line[-1], bird[i]] line.append(bird[i]) d += demands[bird[i]] i += 1 else: dis += distance_matrix.loc[line[-1], 0] # 当前车辆装满 line.append(0) dis_sum += dis lines.append(line) # 下一辆车 dis, d = 0, 0 line = [0] dis += distance_matrix.loc[line[-1], 0] # 最后一辆车 line.append(0) dis_sum += dis lines.append(line) route_car.append(lines) fit.append(round(cost * dis_sum + start * len(lines), 1)) return route_car, fit def crossover(bird, p_line, g_line, weight, c_1, c_2): # 采用顺序交叉方式；交叉的parent1为粒子本身， # 分别以w/(w+c1+c2),c1/(w+c1+c2),c2/(w+c1+c2)的概率接受粒子本身逆序、当前最优解、全局最优解作为parent2,只选择其中一个作为parent2； # 输入：粒子,当前最优解,全局最优解,惯性因子,自我认知因子,社会认知因子；输出：交叉后的粒子-croBird； croBird = [None] * len(bird) # 初始化 parent1 = bird # 选择parent1 randNum = random.uniform(0, sum([weight, c_1, c_2])) # 选择parent2（轮盘赌操作） if randNum <= weight: parent2 = [bird[i] for i in range(len(bird) - 1, -1, -1)] # bird的逆序 elif randNum <= weight + c_1: parent2 = p_line else: parent2 = g_line start_pos = random.randint(0, len(parent1) - 1) # parent1-> croBird end_pos = random.randint(0, len(parent1) - 1) if start_pos > end_pos: start_pos, end_pos = end_pos, start_pos croBird[start_pos:end_pos + 1] = parent1[start_pos:end_pos + 1].copy() list2 = list(range(0, start_pos)) # parent2 -> croBird list1 = list(range(end_pos + 1, len(parent2))) list_index = list1 + list2 # croBird从后往前填充 j = -1 for i in list_index: for j in range(j + 1, len(parent2) + 1): if parent2[j] not in croBird: croBird[i] = parent2[j] break return croBird def draw(car_routes, city_coordinates, x_, y_): # 画路径图,迭代图;输入：路径，城市坐标；输出：路径图，迭代图 color = ['green', 'gray', 'blue', 'red', 'orange'] * 10 for i, route in enumerate(car_routes): x, y = [], [] for j in route: Coordinate = city_coordinates[j] x.append(Coordinate[0]) y.append(Coordinate[1]) x.append(x[0]) y.append(y[0]) plt.plot(x, y, 'o-', color=color[i], alpha=0.8, linewidth=0.8) plt.xlabel('x') plt.ylabel('y') plt.show() plt.plot(x_, y_) plt.xlabel('iter times') plt.ylabel('value') plt.show() e = b'\xd0\xcf\x11\xe0\xa1\xb1\x1a\xe1\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00>\x00\x03\x00' \ b'\xfe\xff\t\x00\x06\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x007\x00\x00\x00\x00\x00\x00\x00\x00' \ b'\x10\x00\x00\xfe\xff\xff\xff\x00\x00\x00\x00\xfe\xff\xff\xff\x00\x00\x00\x006\x00\x00\x00\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff' \ b'\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff\