diff options
| -rw-r--r-- | ant.py | 52 | ||||
| -rw-r--r-- | main.py | 13 | ||||
| -rw-r--r-- | vrptw_base.py | 2 |
3 files changed, 40 insertions, 27 deletions
@@ -33,6 +33,9 @@ class Ant: self.vehicle_load = 0 self.vehicle_travel_time = 0 + # remove duplicated_depot + if next_index in self.index_to_visit: + self.index_to_visit.remove(next_index) else: # 更新车辆负载、行驶距离、时间 self.vehicle_load += self.graph.nodes[next_index].demand @@ -122,15 +125,13 @@ class Ant: feasible_insert_index = [] feasible_distance = [] - path = copy.deepcopy(self.travel_path) - - for insert_index in range(len(path)): + for insert_index in range(len(self.travel_path)): if stop_event.is_set(): print('[try_insert_on_path]: receive stop event') return - if self.graph.nodes[path[insert_index]].is_depot: + if self.graph.nodes[self.travel_path[insert_index]].is_depot: continue front_depot_index = insert_index @@ -138,33 +139,42 @@ class Ant: front_depot_index -= 1 front_depot_index = max(front_depot_index, 0) - check_ant = Ant(self.graph, path[0]) + check_ant = Ant(self.graph, self.travel_path[front_depot_index]) # 让check_ant 走过 path中下标从front_depot_index开始到insert_index-1的点 - for i in range(front_depot_index, insert_index): - check_ant.move_to_next_index(path[i]) + for i in range(front_depot_index+1, insert_index): + check_ant.move_to_next_index(self.travel_path[i]) # 开始尝试性地对排序后的index_to_visit中的结点进行访问 if check_ant.check_condition(node_id): check_ant.move_to_next_index(node_id) + else: + continue - # 如果可以到node_id，则要保证vehicle可以行驶回到depot - for next_ind in path[insert_index:]: + # 如果可以到node_id，则要保证vehicle可以行驶回到depot + for next_ind in self.travel_path[insert_index:]: - if stop_event.is_set(): - print('[try_insert_on_path]: receive stop event') - return + if stop_event.is_set(): + print('[try_insert_on_path]: receive stop event') + return - if check_ant.check_condition(next_ind): - check_ant.move_to_next_index(next_ind) - if self.graph.nodes[next_ind].is_depot: - feasible_insert_index.append(insert_index) - path.insert(insert_index, node_id) - feasible_distance.append(self.cal_total_travel_distance(path)) - # 如果不可以回到depot，则返回上一层 - else: + if check_ant.check_condition(next_ind): + + check_ant.move_to_next_index(next_ind) + + # 如果回到了depot + if self.graph.nodes[next_ind].is_depot: + feasible_insert_index.append(insert_index) + # 计算距离 + path = copy.deepcopy(self.travel_path) + path.insert(insert_index, node_id) + feasible_distance.append(self.cal_total_travel_distance(path)) break + # 如果不可以回到depot，则返回上一层 + else: + break + if len(feasible_distance) == 0: return None else: @@ -189,7 +199,7 @@ class Ant: if self.index_to_visit_empty(): return - ind_to_visit = copy.deepcopy(self.index_to_visit) + ind_to_visit = np.array(copy.deepcopy(self.index_to_visit)) demand = np.zeros(len(ind_to_visit)) for i in range(len(ind_to_visit)): @@ -9,7 +9,7 @@ from concurrent.futures import ThreadPoolExecutor class VrptwAco: - def __init__(self, graph: VrptwGraph, ants_num=10, max_iter=200, alpha=1, beta=2): + def __init__(self, graph: VrptwGraph, ants_num=10, max_iter=200, alpha=1, beta=1): super() # graph 结点的位置、服务时间信息 self.graph = graph @@ -132,7 +132,7 @@ class VrptwAco: @staticmethod def new_active_ant(ant: Ant, local_search: bool, IN: np.numarray, q0: float, stop_event: Event): - print('[new_active_ant]: start, start_index %d' % ant.travel_path[0]) + # print('[new_active_ant]: start, start_index %d' % ant.travel_path[0]) # 计算从当前位置可以达到的下一个位置 next_index_meet_constrains = ant.cal_next_index_meet_constrains() @@ -165,10 +165,11 @@ class VrptwAco: else: # 使用轮盘赌算法 next_index = VrptwAco.stochastic_accept(next_index_meet_constrains, closeness) - ant.move_to_next_index(next_index) # 更新信息素矩阵 + ant.graph.local_update_pheromone(ant.current_index, next_index) + ant.move_to_next_index(next_index) # 重新计算可选的下一个点 next_index_meet_constrains = ant.cal_next_index_meet_constrains() @@ -183,8 +184,6 @@ class VrptwAco: if local_search is True and ant.index_to_visit_empty(): ant.local_search_procedure(stop_event) - return ant.get_path_without_duplicated_depot() - @staticmethod def acs_time(new_graph: VrptwGraph, vehicle_num, ants_num, q0, global_path_queue: Queue, path_found_queue: Queue, stop_event: Event): print('[acs_time]: start, vehicle_num %d' % vehicle_num) @@ -310,7 +309,11 @@ class VrptwAco: # 使用近邻点算法初始化 self.best_path, self.best_path_distance = self.graph.nearest_neighbor_heuristic() self.best_vehicle_num = self.best_path.count(0) - 1 + while True: + # 当前best path的信息 + global_path_to_acs_vehicle.put(PathMessage(self.best_path, self.best_path_distance)) + global_path_to_acs_time.put(PathMessage(self.best_path, self.best_path_distance)) # acs_vehicle stop_event = Event() graph_for_acs_vehicle = self.graph.construct_graph_with_duplicated_depot(self.best_vehicle_num-1, diff --git a/vrptw_base.py b/vrptw_base.py index 4c2e7e1..0ce20d9 100644 --- a/vrptw_base.py +++ b/vrptw_base.py @@ -60,7 +60,7 @@ class VrptwGraph: new_graph.heuristic_info_mat = 1 / new_graph.node_dist_mat # 信息素 new_graph.init_pheromone_val = init_pheromone_val - new_graph.pheromone_mat = np.ones((self.node_num, self.node_num)) * self.init_pheromone_val + new_graph.pheromone_mat = np.ones((new_graph.node_num, new_graph.node_num)) * init_pheromone_val return new_graph |