VRPTW_base.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import copy\n",
    "\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, id:  int, x: float, y: float, demand: float, ready_time: float, due_time: float, service_time: float):\n",
    "        super()\n",
    "        self.id = id\n",
    "\n",
    "        if id == 0:\n",
    "            self.is_depot = True\n",
    "        else:\n",
    "            self.is_depot = False\n",
    "\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "        self.demand = demand\n",
    "        self.ready_time = ready_time\n",
    "        self.due_time = due_time\n",
    "        self.service_time = service_time\n",
    "\n",
    "\n",
    "class vrptw_graph:\n",
    "    def __init__(self, file_path, rho=0.1):\n",
    "        super()\n",
    "        #number of nodes - node_num\n",
    "        #distance between nodes(matrix) node_dist_mat\n",
    "        #pheromone_mat (information density on the path between nodes)\n",
    "        self.node_num, self.nodes, self.node_dist_mat, self.vehicle_num, self.vehicle_capacity \\\n",
    "            = self.create_from_file(file_path)\n",
    "\n",
    "        self.rho = rho\n",
    "\n",
    "\n",
    "        self.nnh_travel_path, self.init_pheromone_val, _ = self.nearest_neighbor_heuristic()\n",
    "        self.init_pheromone_val = 1/(self.init_pheromone_val * self.node_num)\n",
    "        #create pheromone matrix\n",
    "        self.pheromone_mat = np.ones((self.node_num, self.node_num)) * self.init_pheromone_val\n",
    "        #create heuristic information matrix \n",
    "        self.heuristic_info_mat = 1 / self.node_dist_mat\n",
    "\n",
    "    def copy(self, init_pheromone_val):\n",
    "        new_graph = copy.deepcopy(self)\n",
    "\n",
    "        #pheromone matrix\n",
    "        new_graph.init_pheromone_val = init_pheromone_val\n",
    "        new_graph.pheromone_mat = np.ones((new_graph.node_num, new_graph.node_num)) * init_pheromone_val\n",
    "\n",
    "        return new_graph\n",
    "\n",
    "    def create_from_file(self, file_path):\n",
    "        #readinf the location of patient from the database\n",
    "        node_list = []\n",
    "        with open(file_path, 'rt') as f:\n",
    "            count = 1\n",
    "            for line in f:\n",
    "                if count == 5:\n",
    "                    vehicle_num, vehicle_capacity = line.split()\n",
    "                    vehicle_num = int(vehicle_num)\n",
    "                    vehicle_capacity = int(vehicle_capacity)\n",
    "                elif count >= 10:\n",
    "                    node_list.append(line.split())\n",
    "                count += 1\n",
    "                 \n",
    "        node_num = len(node_list)\n",
    "        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)\n",
    "\n",
    "        #creating node dist matrix\n",
    "        node_dist_mat = np.zeros((node_num, node_num))\n",
    "        for i in range(node_num):\n",
    "            node_a = nodes[i]\n",
    "            node_dist_mat[i][i] = 1e-8\n",
    "            for j in range(i+1, node_num):\n",
    "                node_b = nodes[j]\n",
    "                node_dist_mat[i][j] = vrptw_graph.calculate_dist(node_a, node_b)\n",
    "                node_dist_mat[j][i] = node_dist_mat[i][j]\n",
    "\n",
    "        return node_num, nodes, node_dist_mat, vehicle_num, vehicle_capacity\n",
    "\n",
    "    @staticmethod\n",
    "    def calculate_dist(node_a, node_b):\n",
    "        return np.linalg.norm((node_a.x - node_b.x, node_a.y - node_b.y))\n",
    "\n",
    "    def local_update_pheromone(self, start_ind, end_ind):\n",
    "        self.pheromone_mat[start_ind][end_ind] = (1-self.rho) * self.pheromone_mat[start_ind][end_ind] + \\\n",
    "                                                  self.rho * self.init_pheromone_val\n",
    "\n",
    "    def global_update_pheromone(self, best_path, best_path_distance):\n",
    "        #update pheromone matrix\n",
    "        self.pheromone_mat = (1-self.rho) * self.pheromone_mat\n",
    "\n",
    "        current_ind = best_path[0]\n",
    "        for next_ind in best_path[1:]:\n",
    "            self.pheromone_mat[current_ind][next_ind] += self.rho/best_path_distance\n",
    "            current_ind = next_ind\n",
    "    #finally go back to the hospital\n",
    "    def nearest_neighbor_heuristic(self, max_vehicle_num=None):\n",
    "        index_to_visit = list(range(1, self.node_num))\n",
    "        current_index = 0\n",
    "        current_load = 0\n",
    "        current_time = 0\n",
    "        travel_distance = 0\n",
    "        travel_path = [0]\n",
    "\n",
    "        if max_vehicle_num is None:\n",
    "            max_vehicle_num = self.node_num\n",
    "\n",
    "        while len(index_to_visit) > 0 and max_vehicle_num > 0:\n",
    "            nearest_next_index = self._cal_nearest_next_index(index_to_visit, current_index, current_load, current_time)\n",
    "\n",
    "            if nearest_next_index is None:\n",
    "                travel_distance += self.node_dist_mat[current_index][0]\n",
    "\n",
    "                current_load = 0\n",
    "                current_time = 0\n",
    "                travel_path.append(0)\n",
    "                current_index = 0\n",
    "\n",
    "                max_vehicle_num -= 1\n",
    "            else:\n",
    "                current_load += self.nodes[nearest_next_index].demand\n",
    "\n",
    "                dist = self.node_dist_mat[current_index][nearest_next_index]\n",
    "                wait_time = max(self.nodes[nearest_next_index].ready_time - current_time - dist, 0)\n",
    "                service_time = self.nodes[nearest_next_index].service_time\n",
    "\n",
    "                current_time += dist + wait_time + service_time\n",
    "                index_to_visit.remove(nearest_next_index)\n",
    "\n",
    "                travel_distance += self.node_dist_mat[current_index][nearest_next_index]\n",
    "                travel_path.append(nearest_next_index)\n",
    "                current_index = nearest_next_index\n",
    "\n",
    "        travel_distance += self.node_dist_mat[current_index][0]\n",
    "        travel_path.append(0)\n",
    "\n",
    "        vehicle_num = travel_path.count(0)-1\n",
    "        return travel_path, travel_distance, vehicle_num\n",
    "\n",
    "    def _cal_nearest_next_index(self, index_to_visit, current_index, current_load, current_time):\n",
    "        #find the nearest reachable index\n",
    "        nearest_ind = None\n",
    "        nearest_distance = None\n",
    "\n",
    "        for next_index in index_to_visit:\n",
    "            if current_load + self.nodes[next_index].demand > self.vehicle_capacity:\n",
    "                continue\n",
    "\n",
    "            dist = self.node_dist_mat[current_index][next_index]\n",
    "            wait_time = max(self.nodes[next_index].ready_time - current_time - dist, 0)\n",
    "            service_time = self.nodes[next_index].service_time\n",
    "             #checking whether you can return to the hospital after picking up a patient\n",
    "            if current_time + dist + wait_time + service_time + self.node_dist_mat[next_index][0] > self.nodes[0].due_time:\n",
    "                continue\n",
    "\n",
    "            #cannot pick up patient outside duetime\n",
    "            if current_time + dist > self.nodes[next_index].due_time:\n",
    "                continue\n",
    "\n",
    "            if nearest_distance is None or self.node_dist_mat[current_index][next_index] < nearest_distance:\n",
    "                nearest_distance = self.node_dist_mat[current_index][next_index]\n",
    "                nearest_ind = next_index\n",
    "\n",
    "        return nearest_ind\n",
    "\n",
    "\n",
    "class path_message:\n",
    "    def __init__(self, path, distance):\n",
    "        if path is not None:\n",
    "            self.path = copy.deepcopy(path)\n",
    "            self.distance = copy.deepcopy(distance)\n",
    "            self.used_vehicle_num = self.path.count(0) - 1\n",
    "        else:\n",
    "            self.path = None\n",
    "            self.distance = None\n",
    "            self.used_vehicle_num = None\n",
    "\n",
    "    def get_path_info(self):\n",
    "        return self.path, self.distance, self.used_vehicle_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}