1. update: update local_search_procedure

2. remove: remove local_search_procedure_for_global_path

2 files changed, 87 insertions, 118 deletions

diff --git a/ant.py b/ant.py
index ab0cc35..fe224f4 100644
--- a/ant.py
+++ b/ant.py
@@ -1,6 +1,5 @@
 import numpy as np
 import copy
-import random
 from vrptw_base import VrptwGraph
 from threading import Event
 
@@ -20,6 +19,10 @@ class Ant:
 
         self.total_travel_distance = 0
 
+    def clear(self):
+        self.travel_path.clear()
+        self.index_to_visit.clear()
+
     def move_to_next_index(self, next_index):
         # 更新蚂蚁路径
         self.travel_path.append(next_index)
@@ -225,27 +228,25 @@ class Ant:
             if self.graph.nodes[self.travel_path[ind]].is_depot:
                 depot_ind.append(ind)
 
-        new_path_travel_distance = []
-        new_path = []
+        new_path_travel_distance = self.total_travel_distance
+        new_path = self.travel_path
+
         # 将self.travel_path分成多段，每段以depot开始，以depot结束，称为route
         for i in range(1, len(depot_ind)):
             for j in range(i+1, len(depot_ind)):
-                for k in range(10):
-                    if stop_event.is_set():
-                        # print('[local_search_procedure]: receive stop event')
-                        return
-
-                    # 随机在两段route，各随机选择一段customer id，交换这两段customer id
-                    start_a = random.randint(depot_ind[i-1]+1, depot_ind[i]-1)
-                    end_a = random.randint(depot_ind[i-1]+1, depot_ind[i]-1)
-                    if end_a < start_a:
-                        start_a, end_a = end_a, start_a
-
-                    start_b = random.randint(depot_ind[j-1]+1, depot_ind[j]-1)
-                    end_b = random.randint(depot_ind[j - 1] + 1, depot_ind[j] - 1)
-                    if end_b < start_b:
-                        start_b, end_b = end_b, start_b
 
+                if stop_event.is_set():
+                    return
+
+                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 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)):
+                                position.append([start_a, end_a, start_b, end_b])
+
+                for posi in position:
+                    start_a, end_a, start_b, end_b = posi
                     path = []
                     path.extend(self.travel_path[:start_a])
                     path.extend(self.travel_path[start_b:end_b+1])
@@ -253,35 +254,58 @@ class Ant:
                     path.extend(self.travel_path[start_a:end_a])
                     path.extend(self.travel_path[end_b+1:])
 
-                    if len(path) != len(self.travel_path):
-                        raise RuntimeError('error')
+                    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_b = start_b
+                    while not self.graph.nodes[path[depot_before_start_b]].is_depot:
+                        depot_before_start_b -= 1
 
-                    # 判断新生成的path是否是可行的
-                    check_ant = Ant(self.graph, path[0])
-                    for ind in path[1:]:
+                    # 判断发生改变的route a是否是feasible的
+                    success_route_a = False
+                    check_ant = Ant(self.graph, path[depot_before_start_a])
+                    for ind in path[depot_before_start_a+1:]:
                         if check_ant.check_condition(ind):
                             check_ant.move_to_next_index(ind)
+                            if self.graph.nodes[ind].is_depot:
+                                success_route_a = True
+                                break
                         else:
                             break
-                    # 如果新生成的path是可行的
-                    if check_ant.index_to_visit_empty() and check_ant.total_travel_distance < self.total_travel_distance:
-                        # print('success to search')
-                        new_path_travel_distance.append(check_ant.total_travel_distance)
-                        new_path.append(path)
+                    check_ant.clear()
+                    del check_ant
+
+                    # 判断发生改变的route b是否是feasible的
+                    success_route_b = False
+                    check_ant = Ant(self.graph, path[depot_before_start_b])
+                    for ind in path[depot_before_start_b + 1:]:
+                        if check_ant.check_condition(ind):
+                            check_ant.move_to_next_index(ind)
+                            if self.graph.nodes[ind].is_depot:
+                                success_route_b = True
+                                break
+                        else:
+                            break
+                    check_ant.clear()
+                    del check_ant
+
+                    if success_route_a and success_route_b:
+                        total_travel_distance = self.cal_total_travel_distance(path)
+                        if total_travel_distance < new_path_travel_distance:
+                            # print('success to search')
+                            new_path_travel_distance = total_travel_distance
+                            new_path = path
+                            print('[local_search_procedure]: found a path in local search, its distance is %f' % new_path_travel_distance)
                     else:
                         path.clear()
 
         # 找出新生成的path中，路程最小的
-        if len(new_path_travel_distance) > 0:
-            new_path_travel_distance = np.array(new_path_travel_distance)
-            min_distance_ind = np.argmin(new_path_travel_distance)
-
-            self.travel_path = copy.deepcopy(new_path[int(min_distance_ind)])
-            self.index_to_visit.clear()
-
-        for i in range(len(new_path)):
-            new_path[i].clear()
-        new_path.clear()
-        del new_path_travel_distance
-
-        # print('[new_active_ant]: local search finished')
\ No newline at end of file
+        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 21e2fae..ea500b5 100644
--- a/multiple_ant_colony_system.py
+++ b/multiple_ant_colony_system.py
@@ -53,66 +53,6 @@ class MultipleAntColonySystem:
                 return index_to_visit[ind]
 
     @staticmethod
-    def local_search_procedure_for_global_path(graph: VrptwGraph, global_best_path: list, global_best_distance: float, stop_event: Event):
-        """
-        对global_path使用cross进行局部搜索
-        :return:
-        """
-        result_path = None
-        result_distance = None
-
-        new_path_travel_distance = []
-        new_path = []
-        for i in range(1, len(global_best_path)):
-
-            if graph.nodes[global_best_path[i]].is_depot:
-                continue
-
-            for j in range(i+1, len(global_best_path)):
-
-                if graph.nodes[global_best_path[j]].is_depot:
-                    continue
-
-                if stop_event.is_set():
-                    # print('[local_search_procedure_for_global_path]: receive stop event')
-                    return result_path, result_distance
-
-                path = copy.deepcopy(global_best_path)
-                path[i], path[j] = path[j], path[i]
-
-                # 判断新生成的path是否是可行的
-                check_ant = Ant(graph, path[0])
-                for ind in path[1:]:
-                    if check_ant.check_condition(ind):
-                        check_ant.move_to_next_index(ind)
-                    else:
-                        break
-
-                # 如果新生成的path是可行的
-                if check_ant.index_to_visit_empty() and check_ant.total_travel_distance < global_best_distance:
-                    # print('success to search')
-                    new_path_travel_distance.append(check_ant.total_travel_distance)
-                    new_path.append(path)
-                else:
-                    path.clear()
-
-        # 找出新生成的path中，路程最小的
-        if len(new_path_travel_distance) > 0:
-            new_path_travel_distance = np.array(new_path_travel_distance)
-            min_distance_ind = np.argmin(new_path_travel_distance)
-
-            result_path = copy.deepcopy(new_path[int(min_distance_ind)])
-            result_distance = new_path_travel_distance[int(min_distance_ind)]
-
-        for i in range(len(new_path)):
-            new_path[i].clear()
-        new_path.clear()
-        del new_path_travel_distance
-
-        # print('[]: local search for global path finished')
-        return result_path, result_distance
-
-    @staticmethod
     def new_active_ant(ant: Ant, vehicle_num: int, local_search: bool, IN: np.numarray, q0: float, beta: int, stop_event: Event):
         """
         按照指定的vehicle_num在地图上进行探索，所使用的vehicle num不能多于指定的数量，acs_time和acs_vehicle都会使用到这个方法
@@ -236,6 +176,14 @@ 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:
 
@@ -243,30 +191,20 @@ 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')
                     path_found_queue.put(PathMessage(ant.travel_path, ant.total_travel_distance))
 
-            # 为global path进行局部搜索
-            result_path, result_distance = MultipleAntColonySystem.local_search_procedure_for_global_path(new_graph, global_best_path, global_best_distance, stop_event)
-
-            if result_distance is not None:
-                print('[acs_time]: local_search_procedure_for_global_path found  a improved feasible path,'
-                      ' send path info to macs')
-                path_found_queue.put(PathMessage(result_path, result_distance))
-
             # 在这里执行信息素的全局更新
             new_graph.global_update_pheromone(global_best_path, global_best_distance)
 
+            ants_thread.clear()
+            for ant in ants:
+                ant.clear()
+                del ant
+            ants.clear()
+
     @staticmethod
     def acs_vehicle(new_graph: VrptwGraph, vehicle_num: int, ants_num: int, q0: float, beta: int,
                     global_path_queue: Queue, path_found_queue: Queue, stop_event: Event):
@@ -308,7 +246,7 @@ class MultipleAntColonySystem:
 
             for k in range(ants_num):
                 ant = Ant(new_graph, 0)
-                thread = ants_pool.submit(MultipleAntColonySystem.new_active_ant, ant, vehicle_num, True, IN, q0,
+                thread = ants_pool.submit(MultipleAntColonySystem.new_active_ant, ant, vehicle_num, False, IN, q0,
                                           beta, stop_event)
 
                 ants_thread.append(thread)
@@ -352,6 +290,12 @@ class MultipleAntColonySystem:
 
             new_graph.global_update_pheromone(global_best_path, global_best_distance)
 
+            ants_thread.clear()
+            for ant in ants:
+                ant.clear()
+                del ant
+            ants.clear()
+
     def run_multiple_ant_colony_system(self):
         """
         开启另外的线程来跑multiple_ant_colony_system， 使用主线程来绘图
@@ -388,6 +332,7 @@ class MultipleAntColonySystem:
 
         # 使用近邻点算法初始化
         self.best_path, self.best_path_distance, self.best_vehicle_num = self.graph.nearest_neighbor_heuristic()
+        path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
 
         while True:
             print('[multiple_ant_colony_system]: new iteration')