1. add insertion_procedure、 local_search_procedure in Ant class

2. add new_active_ant in VrptwAco class

1 files changed, 53 insertions, 26 deletions

diff --git a/main.py b/main.py
index 4008dac..db5b34a 100644
--- a/main.py
+++ b/main.py
@@ -50,24 +50,24 @@ class VrptwAco:
         for iter in range(self.max_iter):
 
             # 为每只蚂蚁设置当前车辆负载，当前旅行距离，当前时间
-            ants = list(Ant(self.graph.node_num) for _ in range(self.ants_num))
+            ants = list(Ant(self.graph) for _ in range(self.ants_num))
             for k in range(self.ants_num):
 
                 # 蚂蚁需要访问完所有的客户
                 while not ants[k].index_to_visit_empty():
                     next_index = self.select_next_index(ants[k])
                     # 判断加入该位置后，是否还满足约束条件, 如果不满足，则再选择一次，然后再进行判断
-                    if not self.check_condition(ants[k], next_index):
+                    if not ants[k].check_condition(next_index):
                         next_index = self.select_next_index(ants[k])
-                        if not self.check_condition(ants[k], next_index):
+                        if not ants[k].check_condition(next_index):
                             next_index = 0
 
                     # 更新蚂蚁路径
-                    ants[k].move_to_next_index(self.graph, next_index)
+                    ants[k].move_to_next_index(next_index)
                     self.local_update_pheromone(ants[k].current_index, next_index)
 
                 # 最终回到0位置
-                ants[k].move_to_next_index(self.graph, 0)
+                ants[k].move_to_next_index(0)
                 self.local_update_pheromone(ants[k].current_index, 0)
 
             # 计算所有蚂蚁的路径长度
@@ -111,27 +111,6 @@ class VrptwAco:
             next_index = self.stochastic_accept(index_to_visit, transition_prob)
         return next_index
 
-    def check_condition(self, ant: Ant, next_index) -> bool:
-        """
-        检查移动到下一个点是否满足约束条件
-        :param ant:
-        :param next_index:
-        :return:
-        """
-        current_index = ant.current_index
-        if ant.vehicle_load + self.graph.nodes[next_index].demand > self.max_load:
-            return False
-
-        # 检查访问某一个旅客之后，能否回到服务店
-        if ant.vehicle_travel_time + self.graph.node_dist_mat[current_index][next_index] + self.graph.node_dist_mat[next_index][0] > self.graph.nodes[0].due_time:
-            return False
-
-        # 不可以服务due time之外的旅客
-        if ant.vehicle_travel_time + self.graph.node_dist_mat[current_index][next_index] > self.graph.nodes[next_index].due_time:
-            return False
-
-        return True
-
     def local_update_pheromone(self, start_ind, end_ind):
         self.pheromone_mat[start_ind][end_ind] = (1-self.rho) * self.pheromone_mat[start_ind][end_ind] + \
                                                  self.rho * self.init_pheromone_val
@@ -169,6 +148,54 @@ class VrptwAco:
             if random.random() <= norm_transition_prob[ind]:
                 return index_to_visit[ind]
 
+    def new_active_ant(self, k: int, local_search: bool, IN):
+        # 对graph中的depot复制k-1，使得depot数量等于k
+        new_graph = self.graph.construct_graph_with_duplicated_depot(k)
+
+        # 从任意一个depot开始
+        start_index = random.randint(0, k-1)
+        ant = Ant(new_graph, start_index)
+
+        # 计算从当前位置可以达到的下一个位置
+        next_index_meet_constrains = ant.cal_next_index_meet_constrains()
+        while len(next_index_meet_constrains) > 0:
+            index_num = len(next_index_meet_constrains)
+            ready_time = np.zeros(index_num)
+            due_time = np.zeros(index_num)
+            for i in range(index_num):
+                ready_time[i] = new_graph.nodes[next_index_meet_constrains[i]].ready_time
+                due_time[i] = new_graph.nodes[next_index_meet_constrains[i]].due_time
+
+            delivery_time = np.max(ant.vehicle_travel_time + new_graph.node_dist_mat[ant.current_index][next_index_meet_constrains], ready_time)
+            delat_time = delivery_time - ant.vehicle_travel_time
+            distance = delat_time * (due_time - ant.vehicle_travel_time)
+            distance = np.max(1.0, distance-IN)
+
+            closeness = 1/distance
+
+            # 按照概率选择下一个点next_index
+            if np.random.rand() < self.q0:
+                max_prob_index = np.argmax(closeness)
+                next_index = next_index_meet_constrains[max_prob_index]
+            else:
+                # 使用轮盘赌算法
+                next_index = self.stochastic_accept(next_index_meet_constrains, closeness)
+            ant.move_to_next_index(next_index)
+
+            # 更新信息素矩阵
+
+            # 重新计算可选的下一个点
+            next_index_meet_constrains = ant.cal_next_index_meet_constrains()
+
+        ant.insertion_procedure()
+
+        # ant.index_to_visit_empty()==True就是feasible的意思
+        if local_search is True and ant.index_to_visit_empty():
+            new_path = ant.local_search_procedure()
+            if new_path is not None:
+                pass
+            print('fuck')
+
 
 if __name__ == '__main__':
     file_path = './solomon-100/c101.txt'