path: root/vrptw_base.py

import numpy as np
import copy


class Node:
    def __init__(self, id:  int, x: float, y: float, demand: float, ready_time: float, due_time: float, service_time: float):
        super()
        self.id = id

        if id == 0:
            self.is_depot = True
        else:
            self.is_depot = False

        self.x = x
        self.y = y
        self.demand = demand
        self.ready_time = ready_time
        self.due_time = due_time
        self.service_time = service_time


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()
        self.node_num, self.nodes, self.node_dist_mat, self.vehicle_num, self.vehicle_capacity \
            = self.create_from_file(file_path)
        self.rho = rho

        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):
        new_graph = copy.deepcopy(self)

        # 信息素
        new_graph.init_pheromone_val = init_pheromone_val
        new_graph.pheromone_mat = np.ones((new_graph.node_num, new_graph.node_num)) * init_pheromone_val

        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
            for line in f:
                if count == 5:
                    vehicle_num, vehicle_capacity = line.split()
                    vehicle_num = int(vehicle_num)
                    vehicle_capacity = int(vehicle_capacity)
                elif count >= 10:
                    node_list.append(line.split())
                count += 1
        node_num = len(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]
            node_dist_mat[i][i] = 1e-8
            for j in range(i+1, node_num):
                node_b = nodes[j]
                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

    @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):
        self.pheromone_mat[start_ind][end_ind] = (1-self.rho) * self.pheromone_mat[start_ind][end_ind] + \
                                                  self.rho * self.init_pheromone_val

    def global_update_pheromone(self, best_path, best_path_distance):
        """
        更新信息素矩阵
        :return:
        """
        self.pheromone_mat = (1-self.rho) * self.pheromone_mat

        current_ind = best_path[0]
        for next_ind in best_path[1:]:
            self.pheromone_mat[current_ind][next_ind] += self.rho/best_path_distance
            current_ind = next_ind

    def nearest_neighbor_heuristic(self, max_vehicle_num=None):
        """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
        travel_distance = 0
        travel_path = [0]

        if max_vehicle_num is None:
            max_vehicle_num = self.node_num

        while len(index_to_visit) > 0 and max_vehicle_num > 0:
            # 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 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        # all vehicles depart at t=0 ?
                travel_path.append(0)
                current_index = 0

                max_vehicle_num -= 1
            else:
                # Add nearest neighbour node to vehicle route
                current_load += self.nodes[nn_index].demand

                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(nn_index)

                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
        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
        """
        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
            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

            if current_time + dist > self.nodes[next_index].due_time:
                # Time window constraint
                continue

            if nearest_distance is None or dist < nearest_distance:
                nearest_distance = dist
                nearest_index = next_index

        return nearest_index


class PathMessage:
    def __init__(self, path, distance):
        if path is not None:
            self.path = copy.deepcopy(path)
            self.distance = copy.deepcopy(distance)
            self.used_vehicle_num = self.path.count(0) - 1
        else:
            self.path = None
            self.distance = None
            self.used_vehicle_num = None

    def get_path_info(self):
        return self.path, self.distance, self.used_vehicle_num