优化local_search的计算

2 files changed, 40 insertions, 39 deletions

diff --git a/ant.py b/ant.py
index fe224f4..829c068 100644
--- a/ant.py
+++ b/ant.py
@@ -36,9 +36,6 @@ 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
@@ -240,9 +237,11 @@ class Ant:
 
                 position = []
                 for start_a in range(depot_ind[i-1]+1, depot_ind[i]):
-                    for end_a in range(start_a, min(depot_ind[i], start_a+7)):
+                    for end_a in range(start_a, min(depot_ind[i], start_a+6)):
                         for start_b in range(depot_ind[j-1]+1, depot_ind[j]):
-                            for end_b in range(start_b, min(depot_ind[j], start_b+7)):
+                            for end_b in range(start_b, min(depot_ind[j], start_b+6)):
+                                if start_a == end_a and start_b == end_b:
+                                    continue
                                 position.append([start_a, end_a, start_b, end_b])
 
                 for posi in position:
@@ -254,18 +253,11 @@ class Ant:
                     path.extend(self.travel_path[start_a:end_a])
                     path.extend(self.travel_path[end_b+1:])
 
-                    for k in range(1, len(path)):
-                        if path[i-1] == 0 and path[i] == 0:
-                            path.remove(i)
-                            break
-
-                    depot_before_start_a = start_a
-                    while not self.graph.nodes[path[depot_before_start_a]].is_depot:
-                        depot_before_start_a -= 1
+                    depot_before_start_a = depot_ind[i-1]
 
-                    depot_before_start_b = start_b
-                    while not self.graph.nodes[path[depot_before_start_b]].is_depot:
-                        depot_before_start_b -= 1
+                    depot_before_start_b = depot_ind[j-1] + (end_b-start_b) - (end_a-start_a) + 1
+                    if not self.graph.nodes[path[depot_before_start_b]].is_depot:
+                        raise RuntimeError('error')
 
                     # 判断发生改变的route a是否是feasible的
                     success_route_a = False
@@ -278,6 +270,7 @@ class Ant:
                                 break
                         else:
                             break
+
                     check_ant.clear()
                     del check_ant
 
@@ -305,7 +298,12 @@ class Ant:
                     else:
                         path.clear()
 
-        # 找出新生成的path中，路程最小的
+        # 判断new_path中是否存在连个连续的depot
+        for i in range(1, len(new_path)):
+            if self.graph.nodes[new_path[i]].is_depot and self.graph.nodes[new_path[i-1]].is_depot:
+                new_path.pop(i)
+                break
+
         self.travel_path = new_path
         self.total_travel_distance = new_path_travel_distance
         print('[local_search_procedure]: local search finished')
\ No newline at end of file
diff --git a/multiple_ant_colony_system.py b/multiple_ant_colony_system.py
index ea500b5..3e9b0f3 100644
--- a/multiple_ant_colony_system.py
+++ b/multiple_ant_colony_system.py
@@ -88,25 +88,23 @@ class MultipleAntColonySystem:
                 continue
 
             # 开始计算满足限制的下一个结点，选择各个结点的概率
-            index_num = len(next_index_meet_constrains)
-            ready_time = np.zeros(index_num)
-            due_time = np.zeros(index_num)
+            length = len(next_index_meet_constrains)
+            ready_time = np.zeros(length)
+            due_time = np.zeros(length)
 
-            for i in range(index_num):
+            for i in range(length):
                 ready_time[i] = ant.graph.nodes[next_index_meet_constrains[i]].ready_time
                 due_time[i] = ant.graph.nodes[next_index_meet_constrains[i]].due_time
 
-            delivery_time = np.array([max(i, j) for i, j in zip(ant.vehicle_travel_time + ant.graph.node_dist_mat[ant.current_index][next_index_meet_constrains], ready_time)])
-
+            delivery_time = np.maximum(ant.vehicle_travel_time + ant.graph.node_dist_mat[ant.current_index][next_index_meet_constrains], ready_time)
             delta_time = delivery_time - ant.vehicle_travel_time
             distance = delta_time * (due_time - ant.vehicle_travel_time)
 
-            distance = np.array([max(1.0, j) for j in distance-IN[next_index_meet_constrains]])
+            distance = np.maximum(1.0, distance-IN[next_index_meet_constrains])
             closeness = 1/distance
 
             transition_prob = ant.graph.pheromone_mat[ant.current_index][next_index_meet_constrains] * \
                               np.power(closeness, beta)
-
             transition_prob = transition_prob / np.sum(transition_prob)
 
             # 按照概率直接选择closeness最大的结点
@@ -168,7 +166,6 @@ class MultipleAntColonySystem:
                 ant = Ant(new_graph, 0)
                 thread = ants_pool.submit(MultipleAntColonySystem.new_active_ant, ant, vehicle_num, True,
                                           np.zeros(new_graph.node_num), q0, beta, stop_event)
-
                 ants_thread.append(thread)
                 ants.append(ant)
 
@@ -176,14 +173,6 @@ class MultipleAntColonySystem:
             for thread in ants_thread:
                 thread.result()
 
-            # 获取当前的best path
-            if not global_path_queue.empty():
-                info = global_path_queue.get()
-                while not global_path_queue.empty():
-                    info = global_path_queue.get()
-                print('[acs_time]: receive global path info')
-                global_best_path, global_best_distance, global_used_vehicle_num = info.get_path_info()
-
             # 判断蚂蚁找出来的路径是否是feasible的，并且比全局的路径要好
             for ant in ants:
 
@@ -191,6 +180,14 @@ class MultipleAntColonySystem:
                     print('[acs_time]: receive stop event')
                     return
 
+                # 获取当前的best path
+                if not global_path_queue.empty():
+                    info = global_path_queue.get()
+                    while not global_path_queue.empty():
+                        info = global_path_queue.get()
+                    print('[acs_time]: receive global path info')
+                    global_best_path, global_best_distance, global_used_vehicle_num = info.get_path_info()
+
                 # 如果比全局的路径要好，则要将该路径发送到macs中
                 if ant.index_to_visit_empty() and ant.total_travel_distance < global_best_distance:
                     print('[acs_time]: ant found a improved feasible path, send path info to macs')
@@ -262,13 +259,12 @@ class MultipleAntColonySystem:
                     print('[acs_vehicle]: receive stop event')
                     return
 
-                index_to_visit = copy.deepcopy(ant.index_to_visit)
-                IN[index_to_visit] = IN[index_to_visit]+1
+                IN[ant.index_to_visit] = IN[ant.index_to_visit]+1
 
                 # 蚂蚁找出来的路径与current_path进行比较，是否能使用vehicle_num辆车访问到更多的结点
-                if len(index_to_visit) < len(current_index_to_visit):
+                if len(ant.index_to_visit) < len(current_index_to_visit):
                     current_path = copy.deepcopy(ant.travel_path)
-                    current_index_to_visit = index_to_visit
+                    current_index_to_visit = copy.deepcopy(ant.index_to_visit)
                     current_path_distance = ant.total_travel_distance
                     # 并且将IN设置为0
                     IN = np.zeros(new_graph.node_num)
@@ -380,6 +376,14 @@ class MultipleAntColonySystem:
                 path_info = path_found_queue.get()
                 print('[macs]: receive found path info')
                 found_path, found_path_distance, found_path_used_vehicle_num = path_info.get_path_info()
+                while not path_found_queue.empty():
+                    path, distance, vehicle_num = path_found_queue.get().get_path_info()
+
+                    if distance < found_path_distance:
+                        found_path, found_path_distance, found_path_used_vehicle_num = path, distance, vehicle_num
+
+                    if vehicle_num < found_path_used_vehicle_num:
+                        found_path, found_path_distance, found_path_used_vehicle_num = path, distance, vehicle_num
 
                 # 如果找到的路径（which is feasible）的距离更短，则更新当前的最佳path的信息
                 if found_path_distance < self.best_path_distance:
@@ -409,7 +413,6 @@ class MultipleAntColonySystem:
 
                     # 搜索到更好的结果，更新start_time
                     start_time_found_improved_solution = time.time()
-
                     print('*' * 50)
                     print('[macs]: vehicle num of found path (%d) better than best path\'s (%d), found path distance is %f'
                           % (found_path_used_vehicle_num, best_vehicle_num, found_path_distance))