1. show vehicle num in figure title

2. print how much time have used

4 files changed, 69 insertions, 61 deletions

diff --git a/ant.py b/ant.py
index 1c950ea..ab0cc35 100644
--- a/ant.py
+++ b/ant.py
@@ -230,45 +230,46 @@ class Ant:
         # 将self.travel_path分成多段，每段以depot开始，以depot结束，称为route
         for i in range(1, len(depot_ind)):
             for j in range(i+1, len(depot_ind)):
-                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
-
-                path = []
-                path.extend(self.travel_path[:start_a])
-                path.extend(self.travel_path[start_b:end_b+1])
-                path.extend(self.travel_path[end_a:start_b])
-                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')
-
-                # 判断新生成的path是否是可行的
-                check_ant = Ant(self.graph, path[0])
-                for ind in path[1:]:
-                    if check_ant.check_condition(ind):
-                        check_ant.move_to_next_index(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
+
+                    path = []
+                    path.extend(self.travel_path[:start_a])
+                    path.extend(self.travel_path[start_b:end_b+1])
+                    path.extend(self.travel_path[end_a:start_b])
+                    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')
+
+                    # 判断新生成的path是否是可行的
+                    check_ant = Ant(self.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 < self.total_travel_distance:
+                        # print('success to search')
+                        new_path_travel_distance.append(check_ant.total_travel_distance)
+                        new_path.append(path)
                     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)
-                else:
-                    path.clear()
+                        path.clear()
 
         # 找出新生成的path中，路程最小的
         if len(new_path_travel_distance) > 0:
diff --git a/basic_aco.py b/basic_aco.py
index b6e2d50..c841ab3 100644
--- a/basic_aco.py
+++ b/basic_aco.py
@@ -5,6 +5,7 @@ from vrptw_base import VrptwGraph, PathMessage
 from ant import Ant
 from threading import Thread
 from queue import Queue
+import time
 
 
 class BasicACO:
@@ -51,6 +52,8 @@ class BasicACO:
         最基本的蚁群算法
         :return:
         """
+        start_time_total = time.time()
+
         # 最大迭代次数
         start_iteration = 0
         for iter in range(self.max_iter):
@@ -81,33 +84,33 @@ class BasicACO:
 
             # 记录当前的最佳路径
             best_index = np.argmin(paths_distance)
-            if self.best_path is None:
+            if self.best_path is None or paths_distance[best_index] < self.best_path_distance:
                 self.best_path = ants[int(best_index)].travel_path
                 self.best_path_distance = paths_distance[best_index]
+                self.best_vehicle_num = self.best_path.count(0) - 1
                 start_iteration = iter
 
                 # 图形化展示
                 if self.whether_or_not_to_show_figure:
                     path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
 
-            elif paths_distance[best_index] < self.best_path_distance:
-                self.best_path = ants[int(best_index)].travel_path
-                self.best_path_distance = paths_distance[best_index]
-                start_iteration = iter
-                # 图形化展示
-                if self.whether_or_not_to_show_figure:
-                    path_queue_for_figure.put(PathMessage(self.best_path, self.best_path_distance))
+                print('\n')
+                print('[iteration %d]: find a improved path, its distance is %f' % (iter, self.best_path_distance))
+                print('it takes %0.3f second multiple_ant_colony_system running' % (time.time() - start_time_total))
 
-            print('[iteration %d]: best distance %f' % (iter, self.best_path_distance))
             # 更新信息素表
             self.graph.global_update_pheromone(self.best_path, self.best_path_distance)
 
             given_iteration = 100
             if iter - start_iteration > given_iteration:
-                print('iteration is up: can not find better solution in %d iteration' % given_iteration)
-                print('exit.')
+                print('\n')
+                print('iteration exit: can not find better solution in %d iteration' % given_iteration)
                 break
 
+        print('\n')
+        print('final best path distance is %f, number of vehicle is %d' % (self.best_path_distance, self.best_vehicle_num))
+        print('it takes %0.3f second multiple_ant_colony_system running' % (time.time() - start_time_total))
+
     def select_next_index(self, ant):
         """
         选择下一个结点
diff --git a/multiple_ant_colony_system.py b/multiple_ant_colony_system.py
index 5bd5e74..9f20559 100644
--- a/multiple_ant_colony_system.py
+++ b/multiple_ant_colony_system.py
@@ -377,6 +377,8 @@ class MultipleAntColonySystem:
         :param path_queue_for_figure:
         :return:
         """
+        start_time_total = time.time()
+
         # 在这里需要两个队列，time_what_to_do、vehicle_what_to_do， 用来告诉acs_time、acs_vehicle这两个线程，当前的best path是什么，或者让他们停止计算
         global_path_to_acs_time = Queue()
         global_path_to_acs_vehicle = Queue()
@@ -389,7 +391,7 @@ class MultipleAntColonySystem:
 
         while True:
             print('[multiple_ant_colony_system]: new iteration')
-            start_time = time.time()
+            start_time_found_improved_solution = time.time()
 
             # 当前best path的信息，放在queue中以通知acs_time和acs_vehicle当前的best_path是什么
             global_path_to_acs_vehicle.put(PathMessage(self.best_path, self.best_path_distance))
@@ -419,10 +421,12 @@ class MultipleAntColonySystem:
             while acs_vehicle_thread.is_alive() and acs_time_thread.is_alive():
 
                 # 如果在指定时间内没有搜索到更好的结果，则退出程序
-                end_time = time.time()
-                if end_time - start_time > 60 * 5:
+                if time.time() - start_time_found_improved_solution > 60 * 5:
                     stop_event.set()
+                    print(' * ' * 50)
                     print('time is up: cannot find a better solution in given time')
+                    print('it takes %0.3f second from multiple_ant_colony_system running' % (time.time()-start_time_total))
+                    print(' * ' * 50)
                     return
 
                 if path_found_queue.empty():
@@ -436,11 +440,12 @@ class MultipleAntColonySystem:
                 if found_path_distance < self.best_path_distance:
 
                     # 搜索到更好的结果，更新start_time
-                    start_time = time.time()
+                    start_time_found_improved_solution = time.time()
 
-                    print('-' * 50)
+                    print(' * ' * 50)
                     print('[macs]: distance of found path (%f) better than best path\'s (%f)' % (found_path_distance, self.best_path_distance))
-                    print('-' * 50)
+                    print('it takes %0.3f second from multiple_ant_colony_system running' % (time.time()-start_time_total))
+                    print(' * ' * 50)
                     self.best_path = found_path
                     self.best_vehicle_num = found_path_used_vehicle_num
                     self.best_path_distance = found_path_distance
@@ -458,13 +463,13 @@ class MultipleAntColonySystem:
                 if found_path_used_vehicle_num < best_vehicle_num:
 
                     # 搜索到更好的结果，更新start_time
-                    start_time = time.time()
+                    start_time_found_improved_solution = time.time()
 
-                    print('-' * 50)
+                    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))
-
-                    print('-' * 50)
+                    print('it takes %0.3f second multiple_ant_colony_system running' % (time.time() - start_time_total))
+                    print(' * ' * 50)
                     self.best_path = found_path
                     self.best_vehicle_num = found_path_used_vehicle_num
                     self.best_path_distance = found_path_distance
diff --git a/vprtw_aco_figure.py b/vprtw_aco_figure.py
index 9860f8e..79fab72 100644
--- a/vprtw_aco_figure.py
+++ b/vprtw_aco_figure.py
@@ -59,10 +59,9 @@ class VrptwAcoFigure:
                 for line in remove_obj:
                     self.figure_ax.lines.remove(line)
                 remove_obj.clear()
-                plt.pause(1)
 
                 # 重新绘制line
-                self.figure_ax.set_title('current path travel distance: %f' % distance)
+                self.figure_ax.set_title('travel distance: %0.2f, number of vehicles: %d ' % (distance, used_vehicle_num))
                 self._draw_line(path)
             plt.pause(1)