1. delete: calculate_all_path_cost

2. add: local_update_pheromone, global_update_pheromone, NearestNeighborHeuristic

1 files changed, 54 insertions, 6 deletions

diff --git a/vrptw_base.py b/vrptw_base.py
index 8de14ce..a4c92a1 100644
--- a/vrptw_base.py
+++ b/vrptw_base.py
@@ -13,7 +13,7 @@ class Node:
         self.service_time = service_time
 
 
-class VPRTW_Graph:
+class VrptwGraph:
     def __init__(self, file_path):
         super()
         # node_num 结点个数
@@ -45,7 +45,7 @@ class VPRTW_Graph:
             node_dist_mat[i][i] = np.inf
             for j in range(i+1, node_num):
                 node_b = nodes[j]
-                node_dist_mat[i][j] = VPRTW_Graph.calculate_dist(node_a, node_b)
+                node_dist_mat[i][j] = VrptwGraph.calculate_dist(node_a, node_b)
                 node_dist_mat[j][i] = node_dist_mat[i][j]
 
         return node_num, nodes, node_dist_mat, vehicle_num, vehicle_capacity
@@ -60,7 +60,7 @@ class Ant:
         super()
         self.current_index = 0
         self.vehicle_load = 0
-        self.vehicle_travel_distance = 0
+        self.vehicle_travel_time = 0
         self.travel_path = [0]
         self.arrival_time = [0]
         self.index_to_visit = list(range(1, node_num))
@@ -69,21 +69,69 @@ class Ant:
     def move_to_next_index(self, graph, next_index):
         # 更新蚂蚁路径
         self.travel_path.append(next_index)
-        self.arrival_time.append(self.vehicle_travel_distance)
         self.total_travel_distance += graph.node_dist_mat[self.current_index][next_index]
 
+        dist = graph.node_dist_mat[self.current_index][next_index]
+        self.arrival_time.append(self.vehicle_travel_time + dist)
+
         if next_index == 0:
             # 如果一下个位置为服务器点，则要将车辆负载等清空
             self.vehicle_load = 0
-            self.vehicle_travel_distance = 0
+            self.vehicle_travel_time = 0
 
         else:
             # 更新车辆负载、行驶距离、时间
             self.vehicle_load += graph.nodes[next_index].demand
-            self.vehicle_travel_distance += graph.node_dist_mat[self.current_index][next_index] + graph.nodes[next_index].service_time
+            # 如果早于客户要求的时间窗(ready_time)，则需要等待
+
+            self.vehicle_travel_time += dist + max(graph.nodes[next_index].ready_time - self.vehicle_travel_time - dist, 0) + graph.nodes[next_index].service_time
             self.index_to_visit.remove(next_index)
 
         self.current_index = next_index
 
     def index_to_visit_empty(self):
         return len(self.index_to_visit) == 0
+
+
+class NearestNeighborHeuristic:
+    def __init__(self, graph: VrptwGraph):
+        self.graph = graph
+        self.ant = Ant(graph.node_num)
+
+    def cal_init_pheromone_val(self):
+        while not self.ant.index_to_visit_empty():
+            customers_meet_constrains = self.cal_customers_meet_constrains()
+            if len(customers_meet_constrains) == 0:
+                next_index = 0
+            else:
+                next_index = self.cal_nearest_customer(customers_meet_constrains)
+
+            self.ant.move_to_next_index(self.graph, next_index)
+        self.ant.move_to_next_index(self.graph, 0)
+
+        init_pheromone = (1 / (self.graph.node_num * self.ant.total_travel_distance))
+        return init_pheromone
+
+    def cal_customers_meet_constrains(self):
+        customers_meet_constrains = []
+        current_ind = self.ant.current_index
+        for next_ind in self.ant.index_to_visit:
+            condition1 = self.ant.vehicle_travel_time + self.graph.node_dist_mat[current_ind][next_ind] <= self.graph.nodes[next_ind].due_time
+            condition2 = self.ant.vehicle_load + self.graph.nodes[next_ind].demand <= self.graph.vehicle_capacity
+            if condition1 and condition2:
+                customers_meet_constrains.append(next_ind)
+        return customers_meet_constrains
+
+    def cal_nearest_customer(self, customers):
+        current_ind = self.ant.current_index
+
+        nearest_ind = customers[0]
+        min_dist = self.graph.node_dist_mat[current_ind][customers[0]]
+
+        for next_ind in customers[1:]:
+            dist = self.graph.node_dist_mat[current_ind][next_ind]
+            if dist < min_dist:
+                min_dist = dist
+                nearest_ind = next_ind
+
+        return nearest_ind