Add comments to vrptw_base

Also add sols/ directory.  MACS generated travel_paths.

1 files changed, 80 insertions, 39 deletions

diff --git a/vrptw_base.py b/vrptw_base.py
index 30c20de..e7e55bd 100644
--- a/vrptw_base.py
+++ b/vrptw_base.py
@@ -21,22 +21,32 @@ class Node:
 
 
 class VrptwGraph:
+    """VRPTW instance container class
+
+    Attributes
+    ----------
+    rho : float
+        Pheromone volatilization rate
+    nodes : list
+        Nodes of the graph  (depot + customers)
+    node_num : float
+        Number of nodes
+    node_dist_mat : list
+        Distance matrix
+    pheromone_mat : list
+        Pheromone matrix
+    heuristic_info_mat : list
+        Heuristic information matrix
+    """
     def __init__(self, file_path, rho=0.1):
         super()
-        # node_num 结点个数
-        # node_dist_mat 节点之间的距离（矩阵）
-        # pheromone_mat 节点之间路径上的信息度浓度
         self.node_num, self.nodes, self.node_dist_mat, self.vehicle_num, self.vehicle_capacity \
             = self.create_from_file(file_path)
-        # rho 信息素挥发速度
         self.rho = rho
-        # 创建信息素矩阵
-
-        self.nnh_travel_path, self.init_pheromone_val, _ = self.nearest_neighbor_heuristic()
-        self.init_pheromone_val = 1/(self.init_pheromone_val * self.node_num)
 
+        self.nnh_travel_path, nnh_travel_path_dist, _ = self.nearest_neighbor_heuristic()
+        self.init_pheromone_val = 1 / (nnh_travel_path_dist * self.node_num)
         self.pheromone_mat = np.ones((self.node_num, self.node_num)) * self.init_pheromone_val
-        # 启发式信息矩阵
         self.heuristic_info_mat = 1 / self.node_dist_mat
 
     def copy(self, init_pheromone_val):
@@ -49,7 +59,12 @@ class VrptwGraph:
         return new_graph
 
     def create_from_file(self, file_path):
-        # 从文件中读取服务点、客户的位置
+        """Read input file.  Set parameters, nodes and distance matrix.
+
+        从文件中读取服务点、客户的位置
+        お前はもう死んでいる。なに〜！
+        """
+        # Create nodes
         node_list = []
         with open(file_path, 'rt') as f:
             count = 1
@@ -62,9 +77,15 @@ class VrptwGraph:
                     node_list.append(line.split())
                 count += 1
         node_num = len(node_list)
-        nodes = list(Node(int(item[0]), float(item[1]), float(item[2]), float(item[3]), float(item[4]), float(item[5]), float(item[6])) for item in node_list)
-
-        # 创建距离矩阵
+        nodes = [Node(
+            int(item[0]),                           # id
+            float(item[1]), float(item[2]),         # coords.
+            float(item[3]),                         # demand
+            float(item[4]), float(item[5]),         # time window
+            float(item[6])                          # service time
+        ) for item in node_list]
+
+        # Create distance matrix
         node_dist_mat = np.zeros((node_num, node_num))
         for i in range(node_num):
             node_a = nodes[i]
@@ -78,6 +99,7 @@ class VrptwGraph:
 
     @staticmethod
     def calculate_dist(node_a, node_b):
+        """Euclidean distance"""
         return np.linalg.norm((node_a.x - node_b.x, node_a.y - node_b.y))
 
     def local_update_pheromone(self, start_ind, end_ind):
@@ -97,7 +119,15 @@ class VrptwGraph:
             current_ind = next_ind
 
     def nearest_neighbor_heuristic(self, max_vehicle_num=None):
-        index_to_visit = list(range(1, self.node_num))
+        """Generate route plan using Nearest Neighbor (NN) heuristic
+        
+        Returns
+        -------
+        list
+            route plan, travel_distance, vehicle_num
+        """
+        index_to_visit = list(range(1, self.node_num))      # 0 is depot
+        # route plan begins at depot
         current_index = 0
         current_load = 0
         current_time = 0
@@ -108,66 +138,77 @@ class VrptwGraph:
             max_vehicle_num = self.node_num
 
         while len(index_to_visit) > 0 and max_vehicle_num > 0:
-            nearest_next_index = self._cal_nearest_next_index(index_to_visit, current_index, current_load, current_time)
+            # While there are nodes left to visit, or vehicle_num reaches 1;
+            # find NN to visit next in travel_path
+            nn_index = self._cal_nearest_next_index(index_to_visit, 
+                                        current_index, current_load, current_time)
 
-            if nearest_next_index is None:
+            if nn_index is None:
+                # Finish current vehicle route (return to depot)
                 travel_distance += self.node_dist_mat[current_index][0]
 
                 current_load = 0
-                current_time = 0
+                current_time = 0        # all vehicles depart at t=0 ?
                 travel_path.append(0)
                 current_index = 0
 
                 max_vehicle_num -= 1
             else:
-                current_load += self.nodes[nearest_next_index].demand
+                # Add nearest neighbour node to vehicle route
+                current_load += self.nodes[nn_index].demand
 
-                dist = self.node_dist_mat[current_index][nearest_next_index]
-                wait_time = max(self.nodes[nearest_next_index].ready_time - current_time - dist, 0)
-                service_time = self.nodes[nearest_next_index].service_time
+                dist = self.node_dist_mat[current_index][nn_index]
+                wait_time = max(self.nodes[nn_index].ready_time - current_time - dist, 0)
+                service_time = self.nodes[nn_index].service_time
 
                 current_time += dist + wait_time + service_time
-                index_to_visit.remove(nearest_next_index)
+                index_to_visit.remove(nn_index)
 
-                travel_distance += self.node_dist_mat[current_index][nearest_next_index]
-                travel_path.append(nearest_next_index)
-                current_index = nearest_next_index
-        # 最后要回到depot
+                travel_distance += self.node_dist_mat[current_index][nn_index]
+                travel_path.append(nn_index)
+                current_index = nn_index
+
+        # Finish route plan (final return to depot)
         travel_distance += self.node_dist_mat[current_index][0]
         travel_path.append(0)
 
-        vehicle_num = travel_path.count(0)-1
+        vehicle_num = travel_path.count(0) - 1
         return travel_path, travel_distance, vehicle_num
 
     def _cal_nearest_next_index(self, index_to_visit, current_index, current_load, current_time):
+        """Find nearest reachable next_index
+
+        Parameters
+        ----------
+        index_to_visit : list
+            Remaining node indices to visit
         """
-        找到最近的可达的next_index
-        :param index_to_visit:
-        :return:
-        """
-        nearest_ind = None
+        nearest_index = None
         nearest_distance = None
 
         for next_index in index_to_visit:
             if current_load + self.nodes[next_index].demand > self.vehicle_capacity:
+                # Homogenous vehicle capacity constraint
                 continue
 
             dist = self.node_dist_mat[current_index][next_index]
             wait_time = max(self.nodes[next_index].ready_time - current_time - dist, 0)
             service_time = self.nodes[next_index].service_time
-            # 检查访问某一个旅客之后，能否回到服务店
-            if current_time + dist + wait_time + service_time + self.node_dist_mat[next_index][0] > self.nodes[0].due_time:
+            return_time = current_time + dist * 1 + wait_time + service_time \
+                          + self.node_dist_mat[next_index][0]
+            if return_time  > self.nodes[0].due_time:
+                # Depot time window constraint
                 continue
 
-            # 不可以服务due time之外的旅客
             if current_time + dist > self.nodes[next_index].due_time:
+                # Time window constraint
                 continue
 
-            if nearest_distance is None or self.node_dist_mat[current_index][next_index] < nearest_distance:
-                nearest_distance = self.node_dist_mat[current_index][next_index]
-                nearest_ind = next_index
+            if nearest_distance is None or dist < nearest_distance:
+                nearest_distance = dist
+                nearest_index = next_index
 
-        return nearest_ind
+        return nearest_index
 
 
 class PathMessage: