Update.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "ename": "ModuleNotFoundError",
     "evalue": "No module named 'VRPTW_base'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mModuleNotFoundError\u001b[0m                       Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-10-97bc435d69d5>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      3\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mnumpy\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0mnp\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mcopy\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 5\u001b[1;33m \u001b[1;32mfrom\u001b[0m \u001b[0mVRPTW_base\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mvrptw_graph\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      6\u001b[0m \u001b[1;32mfrom\u001b[0m \u001b[0mthreading\u001b[0m \u001b[1;32mimport\u001b[0m \u001b[0mEvent\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      7\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mModuleNotFoundError\u001b[0m: No module named 'VRPTW_base'"
     ]
    }
   ],
   "source": [
    "#update local run search procedure\n",
    "  \n",
    "import numpy as np\n",
    "import copy\n",
    "from VRPTW_base import vrptw_graph\n",
    "from threading import Event\n",
    "\n",
    "\n",
    "class Ant:\n",
    "    def __init__(self, graph: vrptw_graph,start_index=0):\n",
    "        super()\n",
    "        self.graph = graph\n",
    "        self.current_index = start_index\n",
    "        self.vehicle_load = 0\n",
    "        self.vehicle_travel_time = 0\n",
    "        self.travel_path = [start_index]\n",
    "        self.arrival_time = [0]\n",
    "\n",
    "        self.index_to_visit = list(range(graph.node_num))\n",
    "        self.index_to_visit.remove(start_index)\n",
    "\n",
    "        self.total_travel_distance = 0\n",
    "    \n",
    "    def clear(self):\n",
    "        self.travel_path.clear()\n",
    "        self.index_to_visit.clear()\n",
    "        \n",
    "    def move_to_next_index(self, next_index):\n",
    "        #update ant path\n",
    "        self.travel_path.append(next_index)\n",
    "        self.total_travel_distance += self.graph.node_dist_mat[self.current_index][next_index]\n",
    "        \n",
    "        dist = self.graph.node_dist_mat[self.current_index][next_index]\n",
    "        self.arrival_time.append(self.vehicle_travel_time+dist)\n",
    "        \n",
    "        if self.graph.nodes[next_index].is_depot:\n",
    "            #if next location is a hospital, you need to clear the ambulance load, and reset the vehicle time\n",
    "            self.vehicle_load = 0\n",
    "            self.vehicle_travel_time = 0\n",
    "            \n",
    "        else:\n",
    "            #update ambulance load, travel distance, time\n",
    "            self.vehicle_load += self.graph.nodes[next_index].demand\n",
    "            #if the arrival time is earlier than the time window required by the patient(ready_time) you need to wait\n",
    "            \n",
    "            self.vehicle_travel_time+=dist + max(self.graph.nodes[next_index].ready_time - self.vehicle_travel_time-dist,0)+self.graph.nodes[next_index].service_time\n",
    "            self.index_to_visit.remove(next_index)\n",
    "            \n",
    "        self.current_index = next_index\n",
    "        \n",
    "    def index_to_visit_empty(self):\n",
    "        return len(self.index_to_visit)==0\n",
    "    \n",
    "    def get_active_vehicles_num(self):\n",
    "        return self.travel_path.count(0)-1\n",
    "    \n",
    "    def check_condition(self, next_index) -> bool:\n",
    "        #checking whether moving to the next point satifies the condition\n",
    "        \n",
    "        if self.vehicle_load+self.graph.nodes[next_index].demand>self.graph.vehicle_capacity:\n",
    "            return False\n",
    "        \n",
    "        dist = self.graph.node_dist_mat[self.current_index][next_index]\n",
    "        wait_time = max(self.graph.nodes[next_index].ready_time-self.vehicle_travel_time-dist,0)\n",
    "        service_time = self.graph.nodes[next_index].service_time\n",
    "        \n",
    "        #check whether you can go back to the hospital after visiting a patient\n",
    "        \n",
    "        if self.vehicle_travel_time + dist + wait_time + service_time + self.graph.node_dist_mat[next_index][0] > self.graph.nodes[0].due_time:\n",
    "            return False\n",
    "        #cannot serve patients out of due time\n",
    "        if self.vehicle_travel_time + dist > self.graph.nodes[next_index].due_time:\n",
    "            return False\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    def cal_next_index_meet_constraints(self):\n",
    "        #find all patients reachable from the current location(ant.current_index)\n",
    "        next_index_meet_constraints= []\n",
    "        for next_ind in self.index_to_visit:\n",
    "            if self.check_condition(next_ind):\n",
    "                next_index_meet_constraints.append(next_ind)\n",
    "                \n",
    "            return next_index_meet_constraints\n",
    "        def cal_nearest_next_index(self,next_index_list):\n",
    "            #select from the patients to be selected, the patients closest to the current location\n",
    "            current_ind = self.current_index\n",
    "            nearest_ind = next_index_list[0]\n",
    "            min_dist = self.graph.node_dist_mat[current_ind][next_index_list[0]]\n",
    "            \n",
    "            for next_ind in next_index_list[1:]:\n",
    "                dist = self.graph.node_dist_mat[current_ind][next_ind]\n",
    "                if dist<min_dist:\n",
    "                    min_dist = dist\n",
    "                    nearest_ind = next_ind \n",
    "                    \n",
    "            return nearest_ind\n",
    "        \n",
    "    @staticmethod \n",
    "    def cal_total_travel_distance(graph: vrptw_graph, travel_path):\n",
    "        distance = 0 \n",
    "        current_ind = travel_path[0]\n",
    "        for next_ind in travel_path[1:]:\n",
    "            distance += graph.node_dist_mat[current_ind][next_ind]\n",
    "            current_ind = next_ind\n",
    "        return distance\n",
    "    \n",
    "\n",
    "    def try_insert_on_path(self, node_id, stop_event: Event):\n",
    "        #inserting node_id into current travel_path and the inserted position cannot violate the load,time, and travel distance \n",
    "        #restrictions. if there are multiple locations, find the best one\n",
    "        \n",
    "        best_insert_index = None\n",
    "        best_distance = None\n",
    "        \n",
    "        for insert_index in range(len(self.travel_path)):\n",
    "            if stop_event.is_set():\n",
    "            # print('[try_insert_on_path]: receive stop event')\n",
    "                return\n",
    "            if self.graph.nodes[self.travel_path[insert_index]].is_depot:\n",
    "                continue\n",
    "                \n",
    "            #find the nearest depot in front of nearest_index \n",
    "            front_depot_index = insert_index\n",
    "            while front_depot_index>=0 and not self.graph.nodes[self.travel_path[front_depot_index]].is_depot:\n",
    "                front_depot -=1\n",
    "            front_depot_index = max(front_depot_index,0)\n",
    "            #check ant depart from front depot index\n",
    "            \n",
    "            check_ant = Ant(self.graph, self.travel_path[front_depot_index])\n",
    "            #let check_ant go through the point where the subscript in the path starts from front_depot_index to index-1\n",
    "            for i in range(front_depot_index+1, insert_index):\n",
    "                check_ant.move_to_next_index(self.travel_path[i])\n",
    "                \n",
    "            #starting to visit nodes in the sorted index_to_visit\n",
    "            if check_ant.check_condition(node_id):\n",
    "                \n",
    "                check_ant.move_to_next_index(node_id)\n",
    "            else:\n",
    "                continue\n",
    "            #if the node_id can be reached, ensure that the vehicle can travel back to the depot\n",
    "            for next_ind in self.travel_path[insert_index:]:\n",
    "                if stop_event.is_set():\n",
    "                    # print('[try_insert_on_path]: receive stop event')\n",
    "                    return\n",
    "                if check_ant.check_condition(next_ind):\n",
    "                    check_ant.move_to_next_index(next_ind)\n",
    "                    \n",
    "                    #if you return to the depot'\n",
    "                    if self.graph.nodes[next_index].is_depot:\n",
    "                        temp_front_index = self.travel_path[insert_index-1]\n",
    "                        temp_back_index = self.travel_path[insert_index]\n",
    "                        check_ant_distance = self.total_travel_distance - self.graph.node_dist_mat[temp_front_index][temp_back_index]\n",
    "                        +self.graph.node_dist_mat[temp_front_index][node_id]+self.graph.node_dist_mat[node_id][temp_back_index]\n",
    "\n",
    "                    if best_distance is None or check_ant_distance<best_distance:\n",
    "                        best_distance = check_ant_distance\n",
    "                        best_insert_index = insert_index\n",
    "\n",
    "                    break\n",
    "                \n",
    "                #if it is not possible to return to the previous depot, return to the previous level\n",
    "                else:\n",
    "                    break\n",
    "                    \n",
    "            return best_insert_index\n",
    "        def insertion_procedure(self, stop_even: Event):\n",
    "            #trying to find a suitable location for each unvisited node and insert it in the current travel_path. the inserted cannot \n",
    "            #violate load, time and travel distance restrictions\n",
    "            \n",
    "            if self.index_to_visit_empty():\n",
    "                return \n",
    "            success_to_insert = True\n",
    "            #insert until none of the unvisited nodes can be inserted successfully \n",
    "            \n",
    "            while success_to_insert:\n",
    "                success_to_insert = False\n",
    "                #get unvisited nodes\n",
    "                ind_to_visit = np.array(copy.deepcopy(self.index_to_visit))\n",
    "                \n",
    "                #get the demand for visiting customers, sorted in descending order \n",
    "                demand = np.zeros(len(ind_to_visit))\n",
    "                for i, ind in zip(range(len(ind_to_visit)), ind_to_visit):\n",
    "                    demand[i] = self.graph.nodes[ind].demand\n",
    "                    \n",
    "                arg_ind = np.argsort(demand)[::-1]\n",
    "                ind_to_visit = ind_to_visit[arg_ind]\n",
    "                for node_id in ind_to_visit:\n",
    "                    if stop_even.is_set():\n",
    "                        # print('[insertion_procedure]: receive stop event')\n",
    "                        return\n",
    "\n",
    "                    best_insert_index = self.try_insert_on_path(node_id, stop_even)\n",
    "                    if best_insert_index is not None:\n",
    "                        self.travel_path.insert(best_insert_index, node_id)\n",
    "                        self.index_to_visit.remove(node_id)\n",
    "                        # print('[insertion_procedure]: success to insert %d(node id) in %d(index)' % (node_id, best_insert_index))\n",
    "                        success_to_insert = True\n",
    "\n",
    "                del demand\n",
    "                del ind_to_visit\n",
    "            if self.index_to_visit_empty():\n",
    "                print('[insertion_procedure]: success in insertion')\n",
    "\n",
    "            self.total_travel_distance = Ant.cal_total_travel_distance(self.graph, self.travel_path)\n",
    "            \n",
    "        @staticmethod\n",
    "        \n",
    "        def local_search_once(graph: vrptw_graph, travel_path: list, travel_distance: float, i_start, stop_event: Event):\n",
    "            \n",
    "            #find the locations of all the depots in the path \n",
    "            depot_ind = []\n",
    "            for ind in range(len(travel_path)):\n",
    "                if graph.nodes[travel_path[ind]].is_depot:\n",
    "                    depot_ind.append(ind)\n",
    "                    \n",
    "            #divide self.travel_path into multiple segments, each segment starts with depot and ends with depot, called routes\n",
    "            \n",
    "            for i in range(i_start, len(depot_ind)):\n",
    "                for j in range(i+1, len(depot_ind)):\n",
    "                    \n",
    "                    if stop_event.is_set():\n",
    "                        return None, None, None\n",
    "                    for start_a in range(depot_ind[i-1]+1, depot_ind[i]):\n",
    "                        for end_a in range(start_a, min(depot_ind[i], start_a+6)):\n",
    "                            for start_b in range(depot_ind[j - 1] + 1, depot_ind[j]):\n",
    "                                for end_b in range(start_b, min(depot_ind[j], start_b + 6)):\n",
    "                                    if start_a == end_a and start_b == end_b:\n",
    "                                        continue\n",
    "                                    new_path = []\n",
    "                                    new_path.extend(travel_path[:start_a])\n",
    "                                    new_path.extend(travel_path[start_b:end_b + 1])\n",
    "                                    new_path.extend(travel_path[end_a:start_b])\n",
    "                                    new_path.extend(travel_path[start_a:end_a])\n",
    "                                    new_path.extend(travel_path[end_b + 1:])\n",
    "                                    \n",
    "                                    depot_before_start_a = depot_ind[i - 1]\n",
    "                                    depot_before_start_b = depot_ind[j - 1] + (end_b - start_b) - (end_a - start_a) + 1\n",
    "                                    if not graph.nodes[new_path[depot_before_start_b]].is_depot:\n",
    "                                        raise RuntimeError('error')\n",
    "                                    #determine whether the changes route is feasible \n",
    "                                    success_route_a = False\n",
    "                                    check_ant = Ant(graph, new_path[depot_before_start_a])\n",
    "                                    for ind in new_path[depot_before_start_a + 1:]:\n",
    "                                        if check_ant.check_condition(ind):\n",
    "                                            check_ant.move_to_next_index(ind)\n",
    "                                            if graph.nodes[ind].is_depot:\n",
    "                                                success_route_a = True\n",
    "                                                break\n",
    "                                        else:\n",
    "                                            break\n",
    "                                    check_ant.clear()\n",
    "                                    del check_ant\n",
    "                                    \n",
    "                                    #determine whether the changes route b is feasible \n",
    "                                    success_route_b = False\n",
    "                                    check_ant = Ant(graph, new_path[depot_before_start_b])\n",
    "                                    for ind in new_path[depot_before_start_b + 1:]:\n",
    "                                        if check_ant.check_condition(ind):\n",
    "                                            check_ant.move_to_next_index(ind)\n",
    "                                            if graph.nodes[ind].is_depot:\n",
    "                                                success_route_b = True\n",
    "                                                break\n",
    "                                        else:\n",
    "                                            break\n",
    "                                    check_ant.clear()\n",
    "                                    del check_ant\n",
    "                                    \n",
    "                                    if success_route_a and success_route_b:\n",
    "                                        new_path_distance = Ant.cal_total_travel_distance(graph, new_path)\n",
    "                                        if new_path_distance < travel_distance:\n",
    "                                            # print('success to search')\n",
    "                                            \n",
    "                                            #delete one of the depots connected together in a path\n",
    "                                            for temp_ind in range(1, len(new_path)):\n",
    "                                                if graph.nodes[new_path[temp_ind]].is_depot and graph.nodes[new_path[temp_ind - 1]].is_depot:\n",
    "                                                    new_path.pop(temp_ind)\n",
    "                                                    break\n",
    "                                            return new_path, new_path_distance, i\n",
    "                                    else:\n",
    "                                        new_path.clear()\n",
    "                                        \n",
    "                            \n",
    "            return None, None, None\n",
    "        \n",
    "        def local_search_procedure(self, stop_event: Event):\n",
    "            #use cross to perform a local search on the current travel_path that has visited all nodes in the graph\n",
    "            new_path = copy.deepcopy(self.travel_path)\n",
    "            new_path_distance = self.total_travel_distance\n",
    "            times = 100\n",
    "            count = 0\n",
    "            i_start = 1\n",
    "            while count < times:\n",
    "                temp_path, temp_distance, temp_i = Ant.local_search_once(self.graph, new_path, new_path_distance, i_start, stop_event)\n",
    "                if temp_path is not None:\n",
    "                    count+=1\n",
    "                    del new_path, new_path_distance\n",
    "                    new_path = temp_path\n",
    "                    new_path_distance = temp_distance\n",
    "                    #set i_start\n",
    "                    i_start = (i_start + 1) % (new_path.count(0)-1)\n",
    "                    i_start = max(i_start, 1)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            self.travel_path = new_path\n",
    "            self.total_travel_distance = new_path_distance\n",
    "            print('[local_search_procedure]: local search finished')\n",
    "                \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
}