import numpy as np import copy class Node: def __init__(self, id: int, x: float, y: float, demand: float, ready_time: float, due_time: float, service_time: float): super() self.id = id if id == 0: self.is_depot = True else: self.is_depot = False self.x = x self.y = y self.demand = demand self.ready_time = ready_time self.due_time = due_time self.service_time = service_time class VrptwGraph: """VRPTW instance container class Attributes ---------- rho : float Pheromone volatilization rate nodes : list Nodes of the graph (depot + customers) node_num : float Number of nodes node_dist_mat : list Distance matrix pheromone_mat : list Pheromone matrix heuristic_info_mat : list Heuristic information matrix """ def __init__(self, file_path, rho=0.1): super() self.node_num, self.nodes, self.node_dist_mat, self.vehicle_num, self.vehicle_capacity \ = self.create_from_file(file_path) self.rho = rho self.nnh_travel_path, nnh_travel_path_dist, _ = self.nearest_neighbor_heuristic() self.init_pheromone_val = 1 / (nnh_travel_path_dist * self.node_num) self.pheromone_mat = np.ones((self.node_num, self.node_num)) * self.init_pheromone_val self.heuristic_info_mat = 1 / self.node_dist_mat def copy(self, init_pheromone_val): new_graph = copy.deepcopy(self) # 信息素 new_graph.init_pheromone_val = init_pheromone_val new_graph.pheromone_mat = np.ones((new_graph.node_num, new_graph.node_num)) * init_pheromone_val return new_graph def create_from_file(self, file_path): """Read input file. Set parameters, nodes and distance matrix. 从文件中读取服务点、客户的位置 お前はもう死んでいる。なに〜！ """ # Create nodes node_list = [] with open(file_path, 'rt') as f: count = 1 for line in f: if count == 5: vehicle_num, vehicle_capacity = line.split() vehicle_num = int(vehicle_num) vehicle_capacity = int(vehicle_capacity) elif count >= 10: node_list.append(line.split()) count += 1 node_num = len(node_list) nodes = [Node( int(item[0]), # id float(item[1]), float(item[2]), # coords. float(item[3]), # demand float(item[4]), float(item[5]), # time window float(item[6]) # service time ) for item in node_list] # Create distance matrix node_dist_mat = np.zeros((node_num, node_num)) for i in range(node_num): node_a = nodes[i] node_dist_mat[i][i] = 1e-8 for j in range(i+1, node_num): node_b = nodes[j] node_dist_mat[i][j] = VrptwGraph.calculate_dist(node_a, node_b) node_dist_mat[j][i] = node_dist_mat[i][j] return node_num, nodes, node_dist_mat, vehicle_num, vehicle_capacity @staticmethod def calculate_dist(node_a, node_b): """Euclidean distance""" return np.linalg.norm((node_a.x - node_b.x, node_a.y - node_b.y)) def local_update_pheromone(self, start_ind, end_ind): self.pheromone_mat[start_ind][end_ind] = (1-self.rho) * self.pheromone_mat[start_ind][end_ind] + \ self.rho * self.init_pheromone_val def global_update_pheromone(self, best_path, best_path_distance): """ 更新信息素矩阵 :return: """ self.pheromone_mat = (1-self.rho) * self.pheromone_mat current_ind = best_path[0] for next_ind in best_path[1:]: self.pheromone_mat[current_ind][next_ind] += self.rho/best_path_distance current_ind = next_ind def nearest_neighbor_heuristic(self, max_vehicle_num=None): """Generate route plan using Nearest Neighbor (NN) heuristic Returns ------- list route plan, travel_distance, vehicle_num """ index_to_visit = list(range(1, self.node_num)) # 0 is depot # route plan begins at depot current_index = 0 current_load = 0 current_time = 0 travel_distance = 0 travel_path = [0] if max_vehicle_num is None: max_vehicle_num = self.node_num while len(index_to_visit) > 0 and max_vehicle_num > 0: # While there are nodes left to visit, or vehicle_num reaches 1; # find NN to visit next in travel_path nn_index = self._cal_nearest_next_index(index_to_visit, current_index, current_load, current_time) if nn_index is None: # Finish current vehicle route (return to depot) travel_distance += self.node_dist_mat[current_index][0] current_load = 0 current_time = 0 # all vehicles depart at t=0 ? travel_path.append(0) current_index = 0 max_vehicle_num -= 1 else: # Add nearest neighbour node to vehicle route current_load += self.nodes[nn_index].demand dist = self.node_dist_mat[current_index][nn_index] wait_time = max(self.nodes[nn_index].ready_time - current_time - dist, 0) service_time = self.nodes[nn_index].service_time current_time += dist + wait_time + service_time index_to_visit.remove(nn_index) travel_distance += self.node_dist_mat[current_index][nn_index] travel_path.append(nn_index) current_index = nn_index # Finish route plan (final return to depot) travel_distance += self.node_dist_mat[current_index][0] travel_path.append(0) vehicle_num = travel_path.count(0) - 1 return travel_path, travel_distance, vehicle_num def _cal_nearest_next_index(self, index_to_visit, current_index, current_load, current_time): """Find nearest reachable next_index Parameters ---------- index_to_visit : list Remaining node indices to visit """ nearest_index = None nearest_distance = None for next_index in index_to_visit: if current_load + self.nodes[next_index].demand > self.vehicle_capacity: # Homogenous vehicle capacity constraint continue dist = self.node_dist_mat[current_index][next_index] wait_time = max(self.nodes[next_index].ready_time - current_time - dist, 0) service_time = self.nodes[next_index].service_time return_time = current_time + dist * 1 + wait_time + service_time \ + self.node_dist_mat[next_index][0] if return_time > self.nodes[0].due_time: # Depot time window constraint continue if current_time + dist > self.nodes[next_index].due_time: # Time window constraint continue if nearest_distance is None or dist < nearest_distance: nearest_distance = dist nearest_index = next_index return nearest_index class PathMessage: def __init__(self, path, distance): if path is not None: self.path = copy.deepcopy(path) self.distance = copy.deepcopy(distance) self.used_vehicle_num = self.path.count(0) - 1 else: self.path = None self.distance = None self.used_vehicle_num = None def get_path_info(self): return self.path, self.distance, self.used_vehicle_num