diff options
Diffstat (limited to 'vrptw_base.py')
| -rw-r--r-- | vrptw_base.py | 119 |
1 files changed, 80 insertions, 39 deletions
diff --git a/vrptw_base.py b/vrptw_base.py index 30c20de..e7e55bd 100644 --- a/vrptw_base.py +++ b/vrptw_base.py @@ -21,22 +21,32 @@ class Node: 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() - # node_num 结点个数 - # node_dist_mat 节点之间的距离（矩阵） - # pheromone_mat 节点之间路径上的信息度浓度 self.node_num, self.nodes, self.node_dist_mat, self.vehicle_num, self.vehicle_capacity \ = self.create_from_file(file_path) - # rho 信息素挥发速度 self.rho = rho - # 创建信息素矩阵 - - self.nnh_travel_path, self.init_pheromone_val, _ = self.nearest_neighbor_heuristic() - self.init_pheromone_val = 1/(self.init_pheromone_val * self.node_num) + 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): @@ -49,7 +59,12 @@ class VrptwGraph: 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 @@ -62,9 +77,15 @@ class VrptwGraph: node_list.append(line.split()) count += 1 node_num = len(node_list) - nodes = list(Node(int(item[0]), float(item[1]), float(item[2]), float(item[3]), float(item[4]), float(item[5]), float(item[6])) for item in 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] @@ -78,6 +99,7 @@ class VrptwGraph: @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): @@ -97,7 +119,15 @@ class VrptwGraph: current_ind = next_ind def nearest_neighbor_heuristic(self, max_vehicle_num=None): - index_to_visit = list(range(1, self.node_num)) + """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 @@ -108,66 +138,77 @@ class VrptwGraph: max_vehicle_num = self.node_num while len(index_to_visit) > 0 and max_vehicle_num > 0: - nearest_next_index = self._cal_nearest_next_index(index_to_visit, current_index, current_load, current_time) + # 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 nearest_next_index is None: + 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 + current_time = 0 # all vehicles depart at t=0 ? travel_path.append(0) current_index = 0 max_vehicle_num -= 1 else: - current_load += self.nodes[nearest_next_index].demand + # Add nearest neighbour node to vehicle route + current_load += self.nodes[nn_index].demand - dist = self.node_dist_mat[current_index][nearest_next_index] - wait_time = max(self.nodes[nearest_next_index].ready_time - current_time - dist, 0) - service_time = self.nodes[nearest_next_index].service_time + 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(nearest_next_index) + index_to_visit.remove(nn_index) - travel_distance += self.node_dist_mat[current_index][nearest_next_index] - travel_path.append(nearest_next_index) - current_index = nearest_next_index - # 最后要回到depot + 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 + 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 """ - 找到最近的可达的next_index - :param index_to_visit: - :return: - """ - nearest_ind = None + 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 - # 检查访问某一个旅客之后，能否回到服务店 - if current_time + dist + wait_time + service_time + self.node_dist_mat[next_index][0] > self.nodes[0].due_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 - # 不可以服务due time之外的旅客 if current_time + dist > self.nodes[next_index].due_time: + # Time window constraint continue - if nearest_distance is None or self.node_dist_mat[current_index][next_index] < nearest_distance: - nearest_distance = self.node_dist_mat[current_index][next_index] - nearest_ind = next_index + if nearest_distance is None or dist < nearest_distance: + nearest_distance = dist + nearest_index = next_index - return nearest_ind + return nearest_index class PathMessage: |