From 453a2ae1d15f3fcb197f17974c8541216c4baded Mon Sep 17 00:00:00 2001 From: Mitsuo Tokumori Date: Sun, 24 Apr 2022 18:48:51 -0500 Subject: Add comments to vrptw_base Also add sols/ directory. MACS generated travel_paths. --- .gitignore | 4 +- example1.py | 9 +++-- sols/c208_v3_d811 | 13 ++++++ vrptw_base.py | 119 ++++++++++++++++++++++++++++++++++++------------------ 4 files changed, 102 insertions(+), 43 deletions(-) create mode 100644 sols/c208_v3_d811 diff --git a/.gitignore b/.gitignore index a047a94..c06e163 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,4 @@ .idea/ -__pycache__/ \ No newline at end of file +__pycache__/ + +*.swp diff --git a/example1.py b/example1.py index dd1a3ec..165e7ff 100644 --- a/example1.py +++ b/example1.py @@ -1,9 +1,8 @@ from vrptw_base import VrptwGraph from multiple_ant_colony_system import MultipleAntColonySystem - -if __name__ == '__main__': - file_path = './solomon-100/c101.txt' +def main(): + file_path = './solomon-100/c208.txt' ants_num = 10 beta = 2 q0 = 0.1 @@ -12,3 +11,7 @@ if __name__ == '__main__': graph = VrptwGraph(file_path) macs = MultipleAntColonySystem(graph, ants_num=ants_num, beta=beta, q0=q0, whether_or_not_to_show_figure=show_figure) macs.run_multiple_ant_colony_system() + + +if __name__ == '__main__': + main() diff --git a/sols/c208_v3_d811 b/sols/c208_v3_d811 new file mode 100644 index 0000000..0f8eac6 --- /dev/null +++ b/sols/c208_v3_d811 @@ -0,0 +1,13 @@ +solmon c208 +************************************************** +[acs_vehicle]: receive stop event +time is up: cannot find a better solution in given time(10 minutes) +it takes 607.824 second from multiple_ant_colony_system running +the best path have found is: +[0, 93, 5, 75, 2, 20, 22, 24, 30, 29, 6, 32, 33, 31, 35, 37, 38, 39, 36, 34, 28, 26, 23, 18, 19, 16, 14, 12, 15, 17, 13, 25, 9, 11, 10, 21, 0, 67, 63, 61, 62, 72, 74, 69, 66, 64, 68, 65, 55, 49, 54, 53, 56, 59, 58, 60, 57, 40, 44, 46, 45, 51, 50, 52, 47, 42, 41, 43, 48, 8, 90, 0, 27, 1, 99, 100, 97, 92, 94, 95, 98, 7, 3, 4, 89, 88, 91, 86, 84, 83, 82, 76, 71, 85, 73, 70, 79, 80, 78, 77, 87, 96, 81, 0] +best path distance is 810.973266, best vehicle_num is 3 +************************************************** + +Optimum C208.100 v=3 d=585.8 method=KLM + + 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: -- cgit v1.2.3