1. 增加初始化信息素的函数

2. 增加更新rho、q0的函数
3. 修复cost的计算部分

2 files changed, 74 insertions, 35 deletions

diff --git a/main.py b/main.py
index 0ee2071..269a659 100644
--- a/main.py
+++ b/main.py
@@ -4,7 +4,7 @@ import random
 
 
 class VRPTW_ACO:
-    def __init__(self, graph: VPRTW_Graph, ants_num=50, max_iter=300, alpha=1, beta=1, rho=0.1):
+    def __init__(self, graph: VPRTW_Graph, ants_num=10, max_iter=100, alpha=1, beta=3, rho=0.1):
         super()
         # 结点的位置、服务时间信息
         self.graph = graph
@@ -15,7 +15,7 @@ class VRPTW_ACO:
         self.alpha = alpha
         self.beta = beta
         # 信息素挥发速度
-        self.rho = rho
+        self.pheromone_rho = rho
         # q0 表示直接选择概率最大的下一点的概率
         self.q0 = 0.1
         # Q 表示每辆车的最大载重
@@ -35,7 +35,7 @@ class VRPTW_ACO:
         # 车辆行驶速度
         self.vehicle_speed = 60
         # 创建信息素矩阵
-        self.pheromone_mat = np.ones((graph.node_num, graph.node_num))
+        self.pheromone_mat = self.init_pheromone_mat()
         self.eta_mat = 1 / graph.node_dist_mat
 
         # best path
@@ -49,17 +49,19 @@ class VRPTW_ACO:
         """
         # 最大迭代次数
         for iter in range(self.max_iter):
-            transition_prob = np.zeros((self.graph.node_num, self.graph.node_num))
+            self.pheromone_rho = self.calculate_pheromone_rho(iter)
+            self.q0 = self.calculate_prob_q0(iter)
+
             # 为每只蚂蚁设置当前车辆负载，当前旅行距离，当前时间
             ants = list(Ant(self.graph.node_num) 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], transition_prob)
+                    next_index = self.select_next_index(ants[k])
                     # 判断加入该位置后，是否还满足约束条件, 如果不满足，则再选择一次，然后再进行判断
                     if not self.check_condition(ants[k], next_index):
-                        next_index = self.select_next_index(ants[k], transition_prob)
+                        next_index = self.select_next_index(ants[k])
                         if not self.check_condition(ants[k], next_index):
                             next_index = 0
 
@@ -70,7 +72,7 @@ class VRPTW_ACO:
                 ants[k].move_to_next_index(self.graph, self.vehicle_speed, 0)
 
             # 计算所有蚂蚁的路径长度
-            paths_distance = self.calculate_all_path_distance(ants)
+            paths_distance = np.array([ant.calculate_path_distance(self.graph) for ant in ants])
 
             # 记录当前的最佳路径
             best_index = np.argmin(paths_distance)
@@ -81,24 +83,64 @@ class VRPTW_ACO:
             # 更新信息素表
             self.update_pheromone_mat(ants, paths_distance)
 
-    def select_next_index(self, ant: Ant, transition_prob):
+    def init_pheromone_mat(self):
+        """
+        初始化信息素矩阵
+        随机地选择蚂蚁走的下一个位置，并且下一个需要满足载重、行驶距离等要求，直到走完所有的点，然后计算行走的路程L，则信息素初始化为1/(N*L)，这里的N为结点个数
+        :return:
+        """
+        ant = Ant(self.graph.node_num)
+        while not ant.index_to_visit_empty():
+            next_index = random.choice(ant.index_to_visit)
+            if not self.check_condition(ant, next_index):
+                next_index = random.choice(ant.index_to_visit)
+                if not self.check_condition(ant, next_index):
+                    next_index = 0
+
+            ant.move_to_next_index(self.graph, self.vehicle_speed, next_index)
+        ant.move_to_next_index(self.graph, self.vehicle_speed, 0)
+        travel_distance = ant.calculate_path_distance(self.graph)
+        val = (1 / (self.graph.node_num * travel_distance))
+        return np.ones((self.graph.node_num, self.graph.node_num)) * val
+
+    def calculate_pheromone_rho(self, iter):
+        """
+        信息素挥发系数随着迭代次数进行改变
+        :param iter:
+        :return:
+        """
+        if iter <= 1/3 * self.max_iter:
+            return 0.2
+        elif 1/3 * self.max_iter < iter < 2/3 * self.max_iter:
+            return 0.5
+        else:
+            return 0.8
+
+    def calculate_prob_q0(self, iter):
+        """
+        q0着迭代次数进行改变
+        :param iter:
+        :return:
+        """
+        return 0.1+0.8 * iter/self.max_iter
+
+    def select_next_index(self, ant: Ant):
         """
         选择下一个结点
         :param ant:
-        :param transition_prob:
         :return:
         """
         current_index = ant.current_index
         index_to_visit = ant.index_to_visit
 
-        transition_prob[ant.current_index][ant.index_to_visit] = np.power(self.pheromone_mat[current_index][index_to_visit], self.alpha) * \
+        transition_prob = np.power(self.pheromone_mat[current_index][index_to_visit], self.alpha) * \
             np.power(self.eta_mat[current_index][index_to_visit], self.beta)
         if np.random.rand() < self.q0:
-            max_prob_index = np.argmax(transition_prob[current_index][index_to_visit])
+            max_prob_index = np.argmax(transition_prob)
             next_index = index_to_visit[max_prob_index]
         else:
             # 使用轮盘度
-            next_index = self.stochastic_accept(index_to_visit, transition_prob[current_index][index_to_visit])
+            next_index = self.stochastic_accept(index_to_visit, transition_prob)
         return next_index
 
     def check_condition(self, ant: Ant, next_index) -> bool:
@@ -120,7 +162,7 @@ class VRPTW_ACO:
         更新信息素矩阵
         :return:
         """
-        self.pheromone_mat = (1 - self.rho) * self.pheromone_mat
+        self.pheromone_mat = (1 - self.pheromone_rho) * self.pheromone_mat
         for k in range(self.ants_num):
             path = ants[k].travel_path
             current_index = path[0]
@@ -133,7 +175,7 @@ class VRPTW_ACO:
         :param paths:
         :return:
         """
-        # 注意路径是否是从0开始到0结束的
+        # 注意路径是否是从0开始、以0结束的
         costs = np.zeros(self.ants_num)
         for k in range(self.ants_num):
             path = ants[k].travel_path
@@ -141,29 +183,13 @@ class VRPTW_ACO:
             for index in path[1:]:
                 if index == 0:
                     costs[k] += self.car_cost + self.travel_cost * self.graph.node_dist_mat[current_index][index]
-                else:
-                    costs[k] += self.travel_cost * self.graph.node_dist_mat[current_index][index]
-                    # 这里如何计算是否是早到了，还是迟到了，我还没有记录时间
-                    costs[k] += 0
+                costs[k] += self.travel_cost * self.graph.node_dist_mat[current_index][index]
+                costs[k] += self.before_ready_time_cost * max(self.graph.nodes[index].ready_time-ants[k].arrival_time, 0) + \
+                            self.after_due_time_cost * max(ants[k].arrival_time-self.graph.nodes[index].due_time, 0)
                 current_index = index
 
         return costs
 
-    def calculate_all_path_distance(self, ants: list):
-        """
-        计算所有蚂蚁的行走路径的长度
-        :param paths:
-        :return:
-        """
-        distances = np.zeros(self.ants_num)
-        for k in range(self.ants_num):
-            path = ants[k].travel_path
-            current_index = path[0]
-            for index in path[1:]:
-                distances[k] += self.graph.node_dist_mat[current_index][index]
-                current_index = index
-        return distances
-
     def stochastic_accept(self, index_to_visit, transition_prob):
         """
         轮盘赌
@@ -190,5 +216,5 @@ if __name__ == '__main__':
     file_path = './solomon-100/c101.txt'
     graph = VPRTW_Graph(file_path)
 
-    vrptw = VRPTW_ACO(graph, ants_num=50, max_iter=300, alpha=1, beta=1, rho=0.1)
+    vrptw = VRPTW_ACO(graph)
     vrptw.run()
diff --git a/vrptw_base.py b/vrptw_base.py
index 798ffc7..2541842 100644
--- a/vrptw_base.py
+++ b/vrptw_base.py
@@ -87,4 +87,17 @@ class Ant:
         self.current_index = next_index
 
     def index_to_visit_empty(self):
-        return len(self.index_to_visit) == 0
\ No newline at end of file
+        return len(self.index_to_visit) == 0
+
+    def calculate_path_distance(self, graph: VPRTW_Graph):
+        """
+        计算所有蚂蚁的行走路径的长度
+        :param paths:
+        :return:
+        """
+        distance = 0
+        current_index = self.travel_path[0]
+        for index in self.travel_path[1:]:
+            distance += graph.node_dist_mat[current_index][index]
+            current_index = index
+        return distance