{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e9c925ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "from optimization.koneksi import ConDB\n",
    "\n",
    "import sql_connection\n",
    "import json\n",
    "import time\n",
    "import random\n",
    "import datetime\n",
    "import copy\n",
    "\n",
    "from optimization.acs import ACS_TSP\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "from matplotlib.cm import get_cmap\n",
    "from matplotlib.patches import FancyArrowPatch\n",
    "\n",
    "import warnings\n",
    "warnings.filterwarnings('ignore')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7135851a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from optimization.koneksi import ConDB\n",
    "import random\n",
    "import math\n",
    "import copy\n",
    "import time\n",
    "import json\n",
    "import datetime\n",
    "import numpy as np\n",
    "import time\n",
    "from optimization.bso import BSO_VRP,BSO_TSP\n",
    "\n",
    "class ACSBSO_VRP(object):\n",
    "    def __init__(self,alpha_t = 1,beta = 1,q0 = 0.1,init_pheromone = 0.1,rho = 0.1,alpha = 0.1,num_ant = 30,max_iter_acs = 200,max_iter_bso=15,p0=0.5,p1=0.4,p2=0.4,p3=0.5,p4=0.5,max_idem_acs=30,max_idem_bso=10,random_state=None):\n",
    "        self.db = ConDB()\n",
    "        \n",
    "        #ACS parameter setting\n",
    "        self.alpha_t = alpha_t #relative value for pheromone (in transition rule)\n",
    "        self.beta = beta #relative value for heuristic value (in transition rule)\n",
    "        self.q0 = q0 #threshold in ACS transition rule\n",
    "        self.init_pheromone = init_pheromone #initial pheromone on all edges\n",
    "        self.rho = rho #evaporation rate local pheromone update\n",
    "        self.alpha = alpha #evaporation rate global pheromone update\n",
    "        self.num_ant = num_ant #number of ants\n",
    "        self.max_iter_acs = max_iter_acs #max iteration ACS\n",
    "        self.max_idem = max_idem_acs #stop if the best fitness doesn't increase for max_idem iteration\n",
    "\n",
    "        #hybrid setting\n",
    "        self.p0 = p0 #less than: no BSO, more than: do BSO \n",
    "\n",
    "        # BSO parameter setting\n",
    "        self.p1 = p1 #less than: 2-opt, more than: 2-interchange\n",
    "        self.p2 = p2 #less than: center, more than: random cluster (2-opt)\n",
    "        self.p3 = p3 #less than: interchange a cluster and rest nodes, more than: interchange between clusters\n",
    "        self.p4 = p4 #less than: center, more than: random cluster\n",
    "        \n",
    "        self.max_iter_bso = max_iter_bso #max iteration of BSO\n",
    "        self.max_idem_bso = max_idem_bso #stop if the best fitness doesn't increase for max_idem iteration\n",
    "        self.bso_model = BSO_VRP(p1=self.p1,p2=self.p2,p3=self.p3,p4=self.p4,\n",
    "                                max_iter=self.max_iter_bso,max_idem=self.max_idem_bso,\n",
    "                                two_opt_method = \"first\",random_state=random_state)\n",
    "\n",
    "        # data model setting\n",
    "        self.tour = None #POI yang dipilih oleh user untuk dikunjungi\n",
    "        self.hotel = None #hotel yang dipilih oleh user\n",
    "        self.timematrix = None\n",
    "        self.max_travel_time = None\n",
    "        self.travel_days = None\n",
    "        \n",
    "        #degree of interest (DOI for MAUT) setting\n",
    "        self.degree_waktu = 1\n",
    "        self.degree_tarif = 1\n",
    "        self.degree_rating = 1\n",
    "        self.degree_poi = 1\n",
    "        self.degree_poi_penalty = 1\n",
    "        self.degree_time_penalty = 1\n",
    "        \n",
    "        #scaler setting\n",
    "        self.min_rating = None\n",
    "        self.max_rating = None\n",
    "        self.min_tarif = None\n",
    "        self.max_tarif = None\n",
    "        self.min_waktu = None\n",
    "        self.max_waktu = None\n",
    "        self.min_poi = None\n",
    "        self.max_poi = None\n",
    "        self.min_poi_penalty = None\n",
    "        self.max_poi_penalty = None\n",
    "        self.min_time_penalty = None\n",
    "        self.max_time_penalty = None\n",
    "        \n",
    "        #set random seed\n",
    "        self.random_state = random_state\n",
    "        random.seed(self.random_state)\n",
    "    \n",
    "    def set_model(self,tour,hotel,timematrix,travel_days = 3, depart_time = datetime.time(8,0,0),max_travel_time = datetime.time(20,0,0),degree_waktu = 1,degree_tarif = 1,degree_rating = 1):\n",
    "        #initiate model\n",
    "        self.tour = copy.deepcopy(tour)\n",
    "        self.hotel = copy.deepcopy(hotel)\n",
    "        self.travel_days = travel_days\n",
    "        self.hotel.depart_time = depart_time\n",
    "        self.max_travel_time = max_travel_time\n",
    "        self.timematrix = self.add_pheromone_to_timematrix(copy.deepcopy(timematrix))\n",
    "        \n",
    "        self.degree_waktu = degree_waktu\n",
    "        self.degree_tarif = degree_tarif\n",
    "        self.degree_rating = degree_rating\n",
    "        \n",
    "        self.min_rating = min([node.rating for node in self.tour])\n",
    "        self.max_rating = max([node.rating for node in self.tour])\n",
    "        self.min_tarif = min([node.tarif for node in self.tour])\n",
    "        self.max_tarif = sum([node.tarif for node in self.tour])\n",
    "        self.min_waktu = 0\n",
    "        self.max_waktu = (self.diff_second_between_time(depart_time,max_travel_time))*self.travel_days\n",
    "        self.min_poi = 0\n",
    "        self.max_poi = len(self.tour)\n",
    "        self.min_poi_penalty = 0\n",
    "        self.max_poi_penalty = len(self.tour)\n",
    "        self.min_time_penalty = 0\n",
    "        self.max_time_penalty = ((24*3600)-self.diff_second_between_time(max_travel_time,depart_time))*travel_days\n",
    "            \n",
    "    def set_max_iter_acs(self,max_iter_acs):\n",
    "        self.max_iter_acs = max_iter_acs\n",
    "\n",
    "    def time_to_second(self,time):\n",
    "        return (time.hour*3600)+(time.minute*60)+time.second\n",
    "    \n",
    "    def second_to_time(self,second):\n",
    "        second = int(second)\n",
    "        return datetime.time(second//3600,(second//60)%60,0) #ignore second detail\n",
    "    \n",
    "    def diff_second_between_time(self,time_a,time_b):\n",
    "        #input: time_a and time_b, datetime.time()\n",
    "        #output: time_b - time_a, seconds (int)\n",
    "        return self.time_to_second(time_b) - self.time_to_second(time_a)\n",
    "    \n",
    "    def add_pheromone_to_timematrix(self, timematrix):\n",
    "        for i in timematrix:\n",
    "            for j in timematrix[i]:\n",
    "                timematrix[i][j]['pheromone'] = self.init_pheromone\n",
    "        return timematrix\n",
    "    \n",
    "    def min_max_scaler(self,min_value,max_value,value):\n",
    "        if max_value-min_value == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return (value-min_value)/(max_value-min_value)\n",
    "    \n",
    "    def MAUT(self,solutions,consider_total_poi = True,use_penalty = True):\n",
    "        #input: optimization solutions, format = [{\"index\":[],\"waktu\":[],\"rating\":[],\"tarif\":[]},...]\n",
    "        #output: fitness value calculated using MAUT\n",
    "        \n",
    "        #concat all attribute lists (except for waktu)\n",
    "        index_ls = sum([i['index'] for i in solutions],[])\n",
    "        rating_ls = sum([i['rating'] for i in solutions],[])\n",
    "        tarif_ls = sum([i['tarif'] for i in solutions],[])\n",
    "        \n",
    "        waktu_ls = [i['waktu'] for i in solutions]\n",
    "        \n",
    "        #rating\n",
    "        avg_rating = sum(rating_ls)/len(rating_ls)\n",
    "        score_rating = self.min_max_scaler(self.min_rating,self.max_rating,avg_rating)*self.degree_rating\n",
    "        \n",
    "        #tarif\n",
    "        sum_tarif = sum(tarif_ls)\n",
    "        score_tarif = (1-self.min_max_scaler(self.min_tarif,self.max_tarif,sum_tarif)) * self.degree_tarif\n",
    "        \n",
    "        #waktu\n",
    "        waktu_per_day = [self.diff_second_between_time(i[0],i[-1]) for i in waktu_ls]\n",
    "        sum_waktu = sum(waktu_per_day)\n",
    "        score_waktu = (1-self.min_max_scaler(self.min_waktu,self.max_waktu,sum_waktu))*self.degree_waktu\n",
    "        \n",
    "        #poi\n",
    "        count_poi = len(index_ls)\n",
    "        score_poi = self.min_max_scaler(self.min_poi,self.max_poi,count_poi) if consider_total_poi == True else 0\n",
    "        \n",
    "        if use_penalty==True:\n",
    "            #poi penalty\n",
    "            penalty_index = [node._id for node in self.tour if node._id not in index_ls]\n",
    "            count_penalty = len(penalty_index)\n",
    "            score_poipenalty = (1-self.min_max_scaler(self.min_poi_penalty,self.max_poi_penalty,count_penalty)) * self.degree_poi_penalty\n",
    "            \n",
    "            #time penalty\n",
    "            penalty_per_day = [max(self.diff_second_between_time(i[-1],self.max_travel_time),0) for i in waktu_ls]\n",
    "            sum_time_penalty = sum(penalty_per_day)\n",
    "            score_timepenalty = (1-self.min_max_scaler(self.min_time_penalty,self.max_time_penalty,sum_time_penalty)) * self.degree_time_penalty\n",
    "        else:\n",
    "            score_poipenalty = 0\n",
    "            score_timepenalty = 0\n",
    "            \n",
    "        #MAUT\n",
    "        degree_rating = self.degree_rating\n",
    "        degree_tarif = self.degree_tarif\n",
    "        degree_waktu = self.degree_waktu\n",
    "        degree_poi = self.degree_poi if consider_total_poi == True else 0\n",
    "        degree_poi_penalty = self.degree_poi_penalty if use_penalty == True else 0\n",
    "        degree_time_penalty = self.degree_time_penalty if use_penalty == True else 0\n",
    "\n",
    "        pembilang = score_rating+score_tarif+score_waktu+score_poi+score_poipenalty+score_timepenalty\n",
    "        penyebut = degree_rating+degree_tarif+degree_waktu+degree_poi+degree_poi_penalty+degree_time_penalty\n",
    "        maut = pembilang/penyebut\n",
    "        return maut\n",
    "    \n",
    "    def MAUT_between_two_nodes(self,current_node,next_node):\n",
    "        score_rating = self.degree_rating * self.min_max_scaler(self.min_rating,self.max_rating,next_node.rating)\n",
    "        score_tarif = self.degree_tarif * (1-self.min_max_scaler(self.min_tarif,self.max_tarif,next_node.rating))\n",
    "        score_waktu = self.degree_waktu * (1-self.min_max_scaler(self.min_waktu,self.max_waktu,self.timematrix[current_node._id][next_node._id]['waktu']))\n",
    "        maut = (score_rating+score_tarif+score_waktu)/(self.degree_rating+self.degree_tarif+self.degree_waktu)\n",
    "        return maut\n",
    "    \n",
    "    def exploitation(self,current_node,next_node_candidates,local_pheromone_matrix):\n",
    "        max_pos = np.argmax([local_pheromone_matrix[current_node._id][next_node._id]['pheromone']*(self.MAUT_between_two_nodes(current_node,next_node)**self.beta) for next_node in next_node_candidates])\n",
    "        next_node = next_node_candidates[max_pos]\n",
    "        return next_node\n",
    "    \n",
    "    def exploration(self,current_node,next_node_candidates,local_pheromone_matrix):\n",
    "        #penyebut\n",
    "        sum_sample = 0\n",
    "        for next_node in next_node_candidates:\n",
    "            pheromone_in_edge = local_pheromone_matrix[current_node._id][next_node._id]['pheromone']**self.alpha_t\n",
    "            heuristic_val = self.MAUT_between_two_nodes(current_node,next_node)**self.beta\n",
    "            sum_sample += pheromone_in_edge*heuristic_val\n",
    "        \n",
    "        #probability\n",
    "        sum_sample = 0.0001 if sum_sample == 0 else sum_sample\n",
    "        next_node_prob = []\n",
    "        for next_node in next_node_candidates:\n",
    "            pheromone_in_edge = local_pheromone_matrix[current_node._id][next_node._id]['pheromone']**self.alpha_t\n",
    "            heuristic_val = self.MAUT_between_two_nodes(current_node,next_node)**self.beta\n",
    "            node_prob = (pheromone_in_edge*heuristic_val)/sum_sample\n",
    "            node_prob = 0.0001 if node_prob == 0 else node_prob\n",
    "            next_node_prob.append(node_prob)\n",
    "        \n",
    "        next_node = random.choices(next_node_candidates,next_node_prob,k=1)\n",
    "        return next_node[0]\n",
    "    \n",
    "    def transition_rule(self,current_node,next_node_candidates,local_pheromone_matrix):\n",
    "        q = random.uniform(0,1)\n",
    "        if q <= self.q0: #exploitation\n",
    "            next_node = self.exploitation(current_node,next_node_candidates,local_pheromone_matrix)\n",
    "        else: #exploration\n",
    "            next_node = self.exploration(current_node,next_node_candidates,local_pheromone_matrix)\n",
    "        return next_node\n",
    "    \n",
    "    def next_node_check(self,current_node,next_node):\n",
    "        time_needed = self.time_to_second(current_node.depart_time)+self.timematrix[current_node._id][next_node._id][\"waktu\"]+next_node.waktu_kunjungan\n",
    "        time_limit = self.time_to_second(self.max_travel_time)\n",
    "        if (time_needed <= time_limit) and (time_needed <= self.time_to_second(next_node.jam_tutup)):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def set_next_node_depart_arrive_time(self,current_node,next_node):\n",
    "        arrive_time = self.time_to_second(current_node.depart_time)+self.timematrix[current_node._id][next_node._id][\"waktu\"]\n",
    "        arrive_time = max([arrive_time,self.time_to_second(next_node.jam_buka)])\n",
    "        next_node.arrive_time = self.second_to_time(arrive_time)\n",
    "        if next_node.tipe.lower() != \"hotel\":\n",
    "            next_node.depart_time = self.second_to_time(arrive_time+next_node.waktu_kunjungan)\n",
    "        return next_node\n",
    "    \n",
    "    def local_pheromone_update(self,solutions,fitness,local_pheromone_matrix):\n",
    "        for day in solutions:\n",
    "            nodes = [self.hotel._id] + day['index'] + [self.hotel._id]\n",
    "            i = 1\n",
    "            while i < len(nodes):\n",
    "                pheromone = local_pheromone_matrix[nodes[i-1]][nodes[i]]['pheromone']\n",
    "                pheromone = ((1-self.rho)*pheromone)+(self.rho*fitness)\n",
    "                local_pheromone_matrix[nodes[i-1]][nodes[i]]['pheromone'] = pheromone\n",
    "                i += 1\n",
    "        return local_pheromone_matrix\n",
    "    \n",
    "    def global_pheromone_update(self,best_solutions,best_fitness):\n",
    "        solutions = copy.deepcopy(best_solutions)\n",
    "        solution_index = []\n",
    "        for day in solutions:\n",
    "            day_solution = [self.hotel._id] + day['index'] + [self.hotel._id] \n",
    "            day_solution = [(day_solution[i-1],day_solution[i]) for i in range(1,len(day['index']))]\n",
    "            solution_index = solution_index + day_solution\n",
    "        \n",
    "        for node in self.timematrix:\n",
    "            for next_node in self.timematrix[node]:\n",
    "                pheromone = self.timematrix[node][next_node]['pheromone']\n",
    "                if (node,next_node) in solution_index:\n",
    "                    pheromone = ((1-self.alpha)*pheromone)+(self.alpha*best_fitness)\n",
    "                else:\n",
    "                    pheromone = ((1-self.alpha)*pheromone)+0\n",
    "                self.timematrix[node][next_node]['pheromone'] = pheromone\n",
    "    \n",
    "    def construct_solution(self):\n",
    "        best_solution = None\n",
    "        best_fitness = 0\n",
    "        idem_counter = 0\n",
    "        counter = 0\n",
    "        for i in range(self.max_iter_acs): #iteration\n",
    "            counter += 1\n",
    "            best_found_solution = None\n",
    "            best_found_solution_dict = None\n",
    "            best_found_fitness = 0\n",
    "            local_pheromone_matrix = copy.deepcopy(self.timematrix)\n",
    "            for ant in range(self.num_ant): #step\n",
    "                ant_solution = []\n",
    "                ant_solution_dict = []\n",
    "                day = 1\n",
    "                tabu_nodes = []\n",
    "                while day<=self.travel_days:\n",
    "                    current_node = self.hotel\n",
    "                    ant_day_solution = []\n",
    "                    ant_day_solution_dict = {\"index\":[],\"waktu\":[current_node.depart_time],\"rating\":[],\"tarif\":[]}\n",
    "                    \n",
    "                    for pos in range(len(self.tour)+1):\n",
    "                        #recheck next node candidates (perlu dicek jam sampainya apakah melebihi max time)\n",
    "                        next_node_candidates = [node for node in self.tour if self.next_node_check(current_node,node)==True and node._id not in tabu_nodes]\n",
    "                        \n",
    "                        if len(next_node_candidates) > 0:\n",
    "                            #transition rules\n",
    "                            next_node = self.transition_rule(current_node,next_node_candidates,local_pheromone_matrix)\n",
    "                            next_node = self.set_next_node_depart_arrive_time(current_node,next_node)\n",
    "\n",
    "                            #change current node and delete it from available nodes\n",
    "                            current_node = next_node\n",
    "                            ant_day_solution.append(current_node)\n",
    "                            ant_day_solution_dict['index'].append(current_node._id)\n",
    "                            ant_day_solution_dict['rating'].append(current_node.rating)\n",
    "                            ant_day_solution_dict['tarif'].append(current_node.tarif)\n",
    "                            ant_day_solution_dict['waktu'].append(current_node.arrive_time)\n",
    "                            tabu_nodes.append(current_node._id)\n",
    "                        elif len(next_node_candidates) == 0 and current_node._id != self.hotel._id:\n",
    "                            last_node = copy.deepcopy(self.hotel)\n",
    "                            last_node = self.set_next_node_depart_arrive_time(current_node,last_node)\n",
    "                            ant_day_solution_dict['waktu'].append(last_node.arrive_time)\n",
    "                            break\n",
    "                        else:\n",
    "                            break\n",
    "                    \n",
    "                    if len(ant_day_solution_dict['index'])>0:\n",
    "                        ant_solution.append(ant_day_solution)\n",
    "                        ant_solution_dict.append(ant_day_solution_dict)\n",
    "\n",
    "                    if len(tabu_nodes) == len(self.tour):\n",
    "                        break\n",
    "                    day += 1\n",
    "                \n",
    "                fitness = self.MAUT(ant_solution_dict)\n",
    "                if fitness > best_found_fitness:\n",
    "                    best_found_fitness = fitness\n",
    "                    best_found_solution = copy.deepcopy(ant_solution)\n",
    "                    best_found_solution_dict = copy.deepcopy(ant_solution_dict)\n",
    "                \n",
    "                # local pheromone update\n",
    "                local_pheromone_matrix = self.local_pheromone_update(ant_solution_dict,fitness,local_pheromone_matrix)\n",
    "            \n",
    "            #BSO\n",
    "            if random.uniform(0,1) > self.p0:\n",
    "                self.bso_model.set_model(self.tour,self.hotel,self.timematrix,init_solution=best_found_solution,\n",
    "                                        travel_days=self.travel_days,degree_waktu = self.degree_waktu,\n",
    "                                        degree_tarif = self.degree_tarif,degree_rating = self.degree_rating)\n",
    "\n",
    "                _,new_solution,new_fitness = self.bso_model.construct_solution()\n",
    "\n",
    "            \n",
    "                if new_fitness > best_found_fitness:\n",
    "                    best_found_solution_dict = new_solution\n",
    "                    best_found_fitness = new_fitness\n",
    "            \n",
    "            #global pheromone update\n",
    "            self.global_pheromone_update(best_found_solution_dict,best_found_fitness)\n",
    "            \n",
    "            #checking best vs best found\n",
    "            if best_found_fitness > best_fitness:\n",
    "                best_fitness = best_found_fitness\n",
    "                best_solution = copy.deepcopy(best_found_solution_dict)\n",
    "                idem_counter = 0\n",
    "            else:\n",
    "                idem_counter += 1\n",
    "                if idem_counter > self.max_idem:\n",
    "                    return best_solution,best_fitness,counter\n",
    "        \n",
    "        return best_solution,best_fitness,counter\n",
    "\n",
    "class ACSBSO_TSP(object):\n",
    "    def __init__(self,alpha_t = 1,beta = 3,q0 = 0.1,init_pheromone = 0.1,rho = 0.9,alpha = 0.1,num_ant = 30,max_iter_acs = 200,max_iter_bso=15,p0=0.5,p1=0.9,max_idem_acs=30,max_idem_bso=10,random_state=None):\n",
    "        self.db = ConDB()\n",
    "        \n",
    "        #ACS parameter setting\n",
    "        self.alpha_t = alpha_t #relative value for pheromone (in transition rule)\n",
    "        self.beta = beta #relative value for heuristic value (in transition rule)\n",
    "        self.q0 = q0 #threshold in ACS transition rule\n",
    "        self.init_pheromone = init_pheromone #initial pheromone on all edges\n",
    "        self.rho = rho #evaporation rate local pheromone update\n",
    "        self.alpha = alpha #evaporation rate global pheromone update\n",
    "        self.num_ant = num_ant #number of ants\n",
    "        self.max_iter_acs = max_iter_acs #max iteration ACS\n",
    "        self.max_idem = max_idem_acs #stop if the best fitness doesn't increase for max_idem iteration\n",
    "        \n",
    "        #hybrid setting\n",
    "        self.p0 = p0 #less than: no BSO, more than: do BSO \n",
    "\n",
    "        #BSO model\n",
    "        self.bso_model = BSO_TSP(p1=p1,max_iter=max_iter_bso,max_idem=max_idem_bso,\n",
    "                                two_opt_method=\"first\",random_state=random_state)\n",
    "        \n",
    "        # data model setting\n",
    "        self.tour = None #POI yang dipilih oleh user untuk dikunjungi\n",
    "        self.hotel = None #hotel yang dipilih oleh user\n",
    "        self.timematrix = None\n",
    "        self.max_travel_time = None\n",
    "        self.travel_days = None\n",
    "        \n",
    "        #degree of interest (DOI for MAUT) setting\n",
    "        self.degree_waktu = 1\n",
    "        self.degree_tarif = 1\n",
    "        self.degree_rating = 1\n",
    "        self.degree_poi = 1\n",
    "        self.degree_poi_penalty = 1\n",
    "        self.degree_time_penalty = 1\n",
    "        \n",
    "        #scaler setting\n",
    "        self.min_rating = None\n",
    "        self.max_rating = None\n",
    "        self.min_tarif = None\n",
    "        self.max_tarif = None\n",
    "        self.min_waktu = None\n",
    "        self.max_waktu = None\n",
    "        self.max_waktu_tsp = None\n",
    "        self.min_poi = None\n",
    "        self.max_poi = None\n",
    "        self.min_poi_penalty = None\n",
    "        self.max_poi_penalty = None\n",
    "        self.min_time_penalty = None\n",
    "        self.max_time_penalty = None\n",
    "        \n",
    "        #set random seed\n",
    "        if random_state != None:\n",
    "            random.seed(random_state)\n",
    "    \n",
    "    def set_model(self,tour,hotel,timematrix,travel_days = 3, depart_time = datetime.time(8,0,0),max_travel_time = datetime.time(20,0,0),degree_waktu = 1,degree_tarif = 1,degree_rating = 1):\n",
    "        #initiate model\n",
    "        self.tour = copy.deepcopy(tour)\n",
    "        self.hotel = copy.deepcopy(hotel)\n",
    "        self.travel_days = travel_days\n",
    "        self.hotel.depart_time = depart_time\n",
    "        self.max_travel_time = max_travel_time\n",
    "        self.timematrix = self.add_pheromone_to_timematrix(copy.deepcopy(timematrix))\n",
    "        \n",
    "        self.degree_waktu = degree_waktu\n",
    "        self.degree_tarif = degree_tarif\n",
    "        self.degree_rating = degree_rating\n",
    "        \n",
    "        self.min_rating = min([node.rating for node in self.tour])\n",
    "        self.max_rating = max([node.rating for node in self.tour])\n",
    "        self.min_tarif = min([node.tarif for node in self.tour])\n",
    "        self.max_tarif = sum([node.tarif for node in self.tour])\n",
    "        self.min_waktu = 0\n",
    "        self.max_waktu = (self.diff_second_between_time(depart_time,max_travel_time))*self.travel_days\n",
    "        self.min_poi = 0\n",
    "        self.max_poi = len(self.tour)\n",
    "        self.min_poi_penalty = 0\n",
    "        self.max_poi_penalty = len(self.tour)\n",
    "        self.min_time_penalty = 0\n",
    "        self.max_time_penalty = ((24*3600)-self.diff_second_between_time(max_travel_time,depart_time))*travel_days\n",
    "        \n",
    "        self.max_waktu_tsp = 0  # Initialize the total waktu to 0\n",
    "\n",
    "        for source, destinations in self.timematrix.items():\n",
    "            for destination, values in destinations.items():\n",
    "                self.max_waktu_tsp += values['waktu']\n",
    "\n",
    "        self.bso_model.set_model(tour,hotel,timematrix,init_solution=[],travel_days=travel_days,degree_waktu = degree_waktu,degree_tarif = degree_tarif,degree_rating = degree_rating)\n",
    "    \n",
    "    def set_max_iter_acs(self,max_iter_acs):\n",
    "        self.max_iter_acs = max_iter_acs\n",
    "\n",
    "    def time_to_second(self,time):\n",
    "        return (time.hour*3600)+(time.minute*60)+time.second\n",
    "    \n",
    "    def second_to_time(self,second):\n",
    "        second = int(second)\n",
    "        return datetime.time(second//3600,(second//60)%60,0) #ignore second detail\n",
    "    \n",
    "    def diff_second_between_time(self,time_a,time_b):\n",
    "        #input: time_a and time_b, datetime.time()\n",
    "        #output: time_b - time_a, seconds (int)\n",
    "        return self.time_to_second(time_b) - self.time_to_second(time_a)\n",
    "    \n",
    "    def add_pheromone_to_timematrix(self, timematrix):\n",
    "        for i in timematrix:\n",
    "            for j in timematrix[i]:\n",
    "                timematrix[i][j]['pheromone'] = self.init_pheromone\n",
    "        return timematrix\n",
    "    \n",
    "    def min_max_scaler(self,min_value,max_value,value):\n",
    "        if max_value-min_value == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return (value-min_value)/(max_value-min_value)\n",
    "    \n",
    "    def MAUT_TSP(self,solutions):\n",
    "        #concat all attribute lists (except for waktu)\n",
    "        index_ls = solutions['index']\n",
    "        rating_ls = solutions['rating']\n",
    "        tarif_ls = solutions['tarif']\n",
    "                \n",
    "        #rating\n",
    "        avg_rating = sum(rating_ls)/len(rating_ls)\n",
    "        score_rating = self.min_max_scaler(self.min_rating,self.max_rating,avg_rating)*self.degree_rating\n",
    "        \n",
    "        #tarif\n",
    "        sum_tarif = sum(tarif_ls)\n",
    "        score_tarif = (1-self.min_max_scaler(self.min_tarif,self.max_tarif,sum_tarif)) * self.degree_tarif\n",
    "        \n",
    "        #waktu\n",
    "        sum_waktu = solutions['waktu']\n",
    "        score_waktu = (1-self.min_max_scaler(self.min_waktu,self.max_waktu_tsp,sum_waktu))*self.degree_waktu\n",
    "        \n",
    "        #MAUT\n",
    "        pembilang = score_rating+score_tarif+score_waktu\n",
    "        penyebut = self.degree_rating+self.degree_tarif+self.degree_waktu\n",
    "        maut = pembilang/penyebut\n",
    "        return maut\n",
    "    \n",
    "    def MAUT(self,solutions,consider_total_poi = True,use_penalty = True):\n",
    "        #input: optimization solutions, format = [{\"index\":[],\"waktu\":[],\"rating\":[],\"tarif\":[]},...]\n",
    "        #output: fitness value calculated using MAUT\n",
    "        \n",
    "        #concat all attribute lists (except for waktu)\n",
    "        index_ls = sum([i['index'] for i in solutions],[])\n",
    "        rating_ls = sum([i['rating'] for i in solutions],[])\n",
    "        tarif_ls = sum([i['tarif'] for i in solutions],[])\n",
    "        \n",
    "        waktu_ls = [i['waktu'] for i in solutions]\n",
    "        \n",
    "        #rating\n",
    "        avg_rating = sum(rating_ls)/len(rating_ls)\n",
    "        score_rating = self.min_max_scaler(self.min_rating,self.max_rating,avg_rating)*self.degree_rating\n",
    "        \n",
    "        #tarif\n",
    "        sum_tarif = sum(tarif_ls)\n",
    "        score_tarif = (1-self.min_max_scaler(self.min_tarif,self.max_tarif,sum_tarif)) * self.degree_tarif\n",
    "        \n",
    "        #waktu\n",
    "        waktu_per_day = [self.diff_second_between_time(i[0],i[-1]) for i in waktu_ls]\n",
    "        sum_waktu = sum(waktu_per_day)\n",
    "        score_waktu = (1-self.min_max_scaler(self.min_waktu,self.max_waktu,sum_waktu))*self.degree_waktu\n",
    "        \n",
    "        #poi\n",
    "        count_poi = len(index_ls)\n",
    "        score_poi = self.min_max_scaler(self.min_poi,self.max_poi,count_poi) if consider_total_poi == True else 0\n",
    "        \n",
    "        if use_penalty==True:\n",
    "            #poi penalty\n",
    "            penalty_index = [node._id for node in self.tour if node._id not in index_ls]\n",
    "            count_penalty = len(penalty_index)\n",
    "            score_poipenalty = (1-self.min_max_scaler(self.min_poi_penalty,self.max_poi_penalty,count_penalty)) * self.degree_poi_penalty\n",
    "            \n",
    "            #time penalty\n",
    "            penalty_per_day = [max(self.diff_second_between_time(i[-1],self.max_travel_time),0) for i in waktu_ls]\n",
    "            sum_time_penalty = sum(penalty_per_day)\n",
    "            score_timepenalty = (1-self.min_max_scaler(self.min_time_penalty,self.max_time_penalty,sum_time_penalty)) * self.degree_time_penalty\n",
    "        else:\n",
    "            score_poipenalty = 0\n",
    "            score_timepenalty = 0\n",
    "            \n",
    "        #MAUT\n",
    "        degree_rating = self.degree_rating\n",
    "        degree_tarif = self.degree_tarif\n",
    "        degree_waktu = self.degree_waktu\n",
    "        degree_poi = self.degree_poi if consider_total_poi == True else 0\n",
    "        degree_poi_penalty = self.degree_poi_penalty if use_penalty == True else 0\n",
    "        degree_time_penalty = self.degree_time_penalty if use_penalty == True else 0\n",
    "\n",
    "        pembilang = score_rating+score_tarif+score_waktu+score_poi+score_poipenalty+score_timepenalty\n",
    "        penyebut = degree_rating+degree_tarif+degree_waktu+degree_poi+degree_poi_penalty+degree_time_penalty\n",
    "        maut = pembilang/penyebut\n",
    "        return maut\n",
    "    \n",
    "    def MAUT_between_two_nodes(self,current_node,next_node):\n",
    "        score_rating = self.degree_rating * self.min_max_scaler(self.min_rating,self.max_rating,next_node.rating)\n",
    "        score_tarif = self.degree_tarif * (1-self.min_max_scaler(self.min_tarif,self.max_tarif,next_node.rating))\n",
    "        score_waktu = self.degree_waktu * (1-self.min_max_scaler(self.min_waktu,self.max_waktu,self.timematrix[current_node._id][next_node._id]['waktu']))\n",
    "        maut = (score_rating+score_tarif+score_waktu)/(self.degree_rating+self.degree_tarif+self.degree_waktu)\n",
    "        return maut\n",
    "    \n",
    "    def exploitation(self,current_node,next_node_candidates,local_pheromone_matrix):\n",
    "        max_pos = np.argmax([local_pheromone_matrix[current_node._id][next_node._id]['pheromone']*(self.MAUT_between_two_nodes(current_node,next_node)**self.beta) for next_node in next_node_candidates])\n",
    "        next_node = next_node_candidates[max_pos]\n",
    "        return next_node\n",
    "    \n",
    "    def exploration(self,current_node,next_node_candidates,local_pheromone_matrix):\n",
    "        #penyebut\n",
    "        sum_sample = 0\n",
    "        for next_node in next_node_candidates:\n",
    "            pheromone_in_edge = local_pheromone_matrix[current_node._id][next_node._id]['pheromone']**self.alpha_t\n",
    "            heuristic_val = self.MAUT_between_two_nodes(current_node,next_node)**self.beta\n",
    "            sum_sample += pheromone_in_edge*heuristic_val\n",
    "        \n",
    "        #probability\n",
    "        sum_sample = 0.0001 if sum_sample == 0 else sum_sample\n",
    "        next_node_prob = []\n",
    "        for next_node in next_node_candidates:\n",
    "            pheromone_in_edge = local_pheromone_matrix[current_node._id][next_node._id]['pheromone']**self.alpha_t\n",
    "            heuristic_val = self.MAUT_between_two_nodes(current_node,next_node)**self.beta\n",
    "            node_prob = (pheromone_in_edge*heuristic_val)/sum_sample\n",
    "            node_prob = 0.0001 if node_prob == 0 else node_prob\n",
    "            next_node_prob.append(node_prob)\n",
    "        \n",
    "        next_node = random.choices(next_node_candidates,next_node_prob,k=1)\n",
    "        return next_node[0]\n",
    "    \n",
    "    def transition_rule(self,current_node,next_node_candidates,local_pheromone_matrix):\n",
    "        q = random.uniform(0,1)\n",
    "        if q <= self.q0: #exploitation\n",
    "            next_node = self.exploitation(current_node,next_node_candidates,local_pheromone_matrix)\n",
    "        else: #exploration\n",
    "            next_node = self.exploration(current_node,next_node_candidates,local_pheromone_matrix)\n",
    "        return next_node\n",
    "    \n",
    "    def next_node_check(self,current_node,next_node):\n",
    "        time_needed = self.time_to_second(current_node.depart_time)+self.timematrix[current_node._id][next_node._id][\"waktu\"]+next_node.waktu_kunjungan\n",
    "        time_limit = self.time_to_second(self.max_travel_time)\n",
    "        if (time_needed <= time_limit) and (time_needed <= self.time_to_second(next_node.jam_tutup)):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def set_next_node_depart_arrive_time(self,current_node,next_node):\n",
    "        arrive_time = self.time_to_second(current_node.depart_time)+self.timematrix[current_node._id][next_node._id][\"waktu\"]\n",
    "        arrive_time = max([arrive_time,self.time_to_second(next_node.jam_buka)])\n",
    "        next_node.arrive_time = self.second_to_time(arrive_time)\n",
    "        if next_node.tipe.lower() != \"hotel\":\n",
    "            next_node.depart_time = self.second_to_time(arrive_time+next_node.waktu_kunjungan)\n",
    "        return next_node\n",
    "    \n",
    "    def local_pheromone_update(self,solutions,fitness,local_pheromone_matrix):\n",
    "        nodes = [self.hotel._id] + solutions['index'] + [self.hotel._id]\n",
    "        i = 1\n",
    "        while i < len(nodes):\n",
    "            pheromone = local_pheromone_matrix[nodes[i-1]][nodes[i]]['pheromone']\n",
    "            pheromone = ((1-self.rho)*pheromone)+(self.rho*fitness)\n",
    "            local_pheromone_matrix[nodes[i-1]][nodes[i]]['pheromone'] = pheromone\n",
    "            i += 1\n",
    "        return local_pheromone_matrix\n",
    "    \n",
    "    def global_pheromone_update(self,best_solutions,best_fitness):\n",
    "        solutions = [self.hotel._id] + best_solutions['index'] + [self.hotel._id]\n",
    "        solution_index = [(solutions[i-1],solutions[i]) for i in range(1,len(solutions))]\n",
    "        \n",
    "        for node in self.timematrix:\n",
    "            for next_node in self.timematrix[node]:\n",
    "                pheromone = self.timematrix[node][next_node]['pheromone']\n",
    "                if (node,next_node) in solution_index:\n",
    "                    pheromone = ((1-self.alpha)*pheromone)+(self.alpha*best_fitness)\n",
    "                else:\n",
    "                    pheromone = ((1-self.alpha)*pheromone)+0\n",
    "                self.timematrix[node][next_node]['pheromone'] = pheromone\n",
    "     \n",
    "    def TSP(self):\n",
    "        best_solution = None\n",
    "        best_fitness = 0\n",
    "        idem_counter = 0\n",
    "        counter = 0\n",
    "        for i in range(self.max_iter_acs): #iteration\n",
    "            counter += 1\n",
    "            best_found_solution = None\n",
    "            best_found_solution_dict = None\n",
    "            best_found_fitness = 0\n",
    "            local_pheromone_matrix = copy.deepcopy(self.timematrix)\n",
    "            for ant in range(self.num_ant): #step\n",
    "                ant_solution = []\n",
    "                ant_solution_dict = {\"index\":[],\"waktu\":0,\"rating\":[],\"tarif\":[]}\n",
    "                current_node = self.hotel\n",
    "                \n",
    "                for pos in range(len(self.tour)+1):\n",
    "                    #generate next node candidates\n",
    "                    next_node_candidates = [node for node in self.tour if node._id not in ant_solution_dict['index']]\n",
    "                    \n",
    "                    if len(next_node_candidates)>0:\n",
    "                        #transition rules\n",
    "                        next_node = self.transition_rule(current_node,next_node_candidates,local_pheromone_matrix)\n",
    "                        \n",
    "                        #add to solution list\n",
    "                        ant_solution.append(next_node)\n",
    "                        ant_solution_dict['index'].append(next_node._id)\n",
    "                        ant_solution_dict['rating'].append(next_node.rating)\n",
    "                        ant_solution_dict['tarif'].append(next_node.tarif)\n",
    "                        ant_solution_dict['waktu'] += self.timematrix[current_node._id][next_node._id]['waktu']+next_node.waktu_kunjungan\n",
    "                        \n",
    "                        #change current node\n",
    "                        current_node = next_node\n",
    "                    elif len(next_node_candidates) == 0 and current_node._id != self.hotel._id:\n",
    "                        last_node = copy.deepcopy(self.hotel)\n",
    "                        ant_solution_dict['waktu'] += self.timematrix[current_node._id][last_node._id]['waktu']\n",
    "                        break\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "                fitness = self.MAUT_TSP(ant_solution_dict)\n",
    "                if fitness >= best_found_fitness:\n",
    "                    best_found_fitness = fitness\n",
    "                    best_found_solution = copy.deepcopy(ant_solution)\n",
    "                    best_found_solution_dict = copy.deepcopy(ant_solution_dict)\n",
    "                \n",
    "                # local pheromone update\n",
    "                local_pheromone_matrix = self.local_pheromone_update(ant_solution_dict,fitness,local_pheromone_matrix)\n",
    "            \n",
    "            #BSO\n",
    "            if random.uniform(0,1) > self.p0:\n",
    "                self.bso_model.set_init_solution(best_found_solution)\n",
    "                new_solution,new_fitness = self.bso_model.TSP()\n",
    "            \n",
    "            \n",
    "                if new_fitness >= best_found_fitness:\n",
    "                    best_found_solution = new_solution\n",
    "                    best_found_solution_dict = self.bso_model.create_solution_dict_TSP(new_solution)\n",
    "                    best_found_fitness = new_fitness\n",
    "            \n",
    "            #global pheromone update\n",
    "            self.global_pheromone_update(best_found_solution_dict,best_found_fitness)\n",
    "\n",
    "            #checking best vs best found\n",
    "            if best_found_fitness >= best_fitness:\n",
    "                best_fitness = best_found_fitness\n",
    "                best_solution = copy.deepcopy(best_found_solution)\n",
    "                idem_counter = 0\n",
    "            else:\n",
    "                idem_counter += 1\n",
    "                if idem_counter > self.max_idem:\n",
    "                    return best_solution,best_fitness,counter\n",
    "        \n",
    "        return best_solution,best_fitness,counter\n",
    "    \n",
    "    def construct_solution(self):\n",
    "        solution,fitness,counter = self.TSP()\n",
    "        day = 1\n",
    "        final_solution = []\n",
    "        tabu_nodes = []\n",
    "        while day <= self.travel_days:\n",
    "            current_node = self.hotel\n",
    "            day_solution = {\"index\":[],\"waktu\":[current_node.depart_time],\"rating\":[],\"tarif\":[]}\n",
    "            next_node_candidates = [node for node in solution if node._id not in tabu_nodes]\n",
    "            for i in range(len(next_node_candidates)):\n",
    "                time_needed = self.time_to_second(current_node.depart_time)+self.timematrix[current_node._id][next_node_candidates[i]._id][\"waktu\"]+next_node_candidates[i].waktu_kunjungan\n",
    "                if time_needed >= self.time_to_second(next_node_candidates[i].jam_tutup):\n",
    "                    continue\n",
    "                elif self.next_node_check(current_node,next_node_candidates[i]):\n",
    "                    next_node_candidates[i] = self.set_next_node_depart_arrive_time(current_node,next_node_candidates[i])\n",
    "                    day_solution['index'].append(next_node_candidates[i]._id)\n",
    "                    day_solution['waktu'].append(next_node_candidates[i].arrive_time)\n",
    "                    day_solution['rating'].append(next_node_candidates[i].rating)\n",
    "                    day_solution['tarif'].append(next_node_candidates[i].tarif)\n",
    "                    tabu_nodes.append(next_node_candidates[i]._id)\n",
    "                    current_node = next_node_candidates[i]\n",
    "                else:\n",
    "                    break\n",
    "            if current_node._id != self.hotel._id:\n",
    "                self.hotel = self.set_next_node_depart_arrive_time(current_node,self.hotel)\n",
    "                day_solution['waktu'].append(self.hotel.arrive_time)\n",
    "            \n",
    "            if len(day_solution['index']) > 0:\n",
    "                final_solution.append(day_solution)\n",
    "            \n",
    "            if len(tabu_nodes) == len(self.tour):\n",
    "                break\n",
    "\n",
    "            day += 1\n",
    "        \n",
    "        final_fitness = self.MAUT(final_solution)\n",
    "        return final_solution,final_fitness,counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b202b724",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ACS_VRP(object):\n",
    "    def __init__(self,alpha_t = 1,beta = 3,q0 = 0.1,init_pheromone = 0.1,rho = 0.9,alpha = 0.1,num_ant = 30,max_iter = 200,max_idem=30,random_state=None):\n",
    "        self.db = ConDB()\n",
    "        \n",
    "        #parameter setting\n",
    "        self.alpha_t = alpha_t #relative value for pheromone (in transition rule)\n",
    "        self.beta = beta #relative value for heuristic value (in transition rule)\n",
    "        self.q0 = q0 #threshold in ACS transition rule\n",
    "        self.init_pheromone = init_pheromone #initial pheromone on all edges\n",
    "        self.rho = rho #evaporation rate local pheromone update\n",
    "        self.alpha = alpha #evaporation rate global pheromone update\n",
    "        self.num_ant = num_ant #number of ants\n",
    "        self.max_iter = max_iter #max iteration ACS\n",
    "        self.max_idem = max_idem #stop if the best fitness doesn't increase for max_idem iteration\n",
    "        \n",
    "        # data model setting\n",
    "        self.tour = None #POI yang dipilih oleh user untuk dikunjungi\n",
    "        self.hotel = None #hotel yang dipilih oleh user\n",
    "        self.timematrix = None\n",
    "        self.max_travel_time = None\n",
    "        self.travel_days = None\n",
    "        \n",
    "        #degree of interest (DOI for MAUT) setting\n",
    "        self.degree_waktu = 1\n",
    "        self.degree_tarif = 1\n",
    "        self.degree_rating = 1\n",
    "        self.degree_poi = 1\n",
    "        self.degree_poi_penalty = 1\n",
    "        self.degree_time_penalty = 1\n",
    "        \n",
    "        #scaler setting\n",
    "        self.min_rating = None\n",
    "        self.max_rating = None\n",
    "        self.min_tarif = None\n",
    "        self.max_tarif = None\n",
    "        self.min_waktu = None\n",
    "        self.max_waktu = None\n",
    "        self.min_poi = None\n",
    "        self.max_poi = None\n",
    "        self.min_poi_penalty = None\n",
    "        self.max_poi_penalty = None\n",
    "        self.min_time_penalty = None\n",
    "        self.max_time_penalty = None\n",
    "        \n",
    "        #set random seed\n",
    "        if random_state != None:\n",
    "            random.seed(random_state)\n",
    "    \n",
    "    def set_model(self,tour,hotel,timematrix,travel_days = 3, depart_time = datetime.time(8,0,0),max_travel_time = datetime.time(20,0,0),degree_waktu = 1,degree_tarif = 1,degree_rating = 1):\n",
    "        #initiate model\n",
    "        self.tour = copy.deepcopy(tour)\n",
    "        self.hotel = copy.deepcopy(hotel)\n",
    "        self.travel_days = travel_days\n",
    "        self.hotel.depart_time = depart_time\n",
    "        self.max_travel_time = max_travel_time\n",
    "        self.timematrix = self.add_pheromone_to_timematrix(copy.deepcopy(timematrix))\n",
    "        \n",
    "        self.degree_waktu = degree_waktu\n",
    "        self.degree_tarif = degree_tarif\n",
    "        self.degree_rating = degree_rating\n",
    "        \n",
    "        self.min_rating = min([node.rating for node in self.tour])\n",
    "        self.max_rating = max([node.rating for node in self.tour])\n",
    "        self.min_tarif = min([node.tarif for node in self.tour])\n",
    "        self.max_tarif = sum([node.tarif for node in self.tour])\n",
    "        self.min_waktu = 0\n",
    "        self.max_waktu = (self.diff_second_between_time(depart_time,max_travel_time))*self.travel_days\n",
    "        self.min_poi = 0\n",
    "        self.max_poi = len(self.tour)\n",
    "        self.min_poi_penalty = 0\n",
    "        self.max_poi_penalty = len(self.tour)\n",
    "        self.min_time_penalty = 0\n",
    "        self.max_time_penalty = ((24*3600)-self.diff_second_between_time(max_travel_time,depart_time))*travel_days\n",
    "    \n",
    "    def set_max_iter(self,max_iter):\n",
    "        self.max_iter = max_iter\n",
    "\n",
    "    def time_to_second(self,time):\n",
    "        return (time.hour*3600)+(time.minute*60)+time.second\n",
    "    \n",
    "    def second_to_time(self,second):\n",
    "        second = int(second)\n",
    "        return datetime.time(second//3600,(second//60)%60,0) #ignore second detail\n",
    "    \n",
    "    def diff_second_between_time(self,time_a,time_b):\n",
    "        #input: time_a and time_b, datetime.time()\n",
    "        #output: time_b - time_a, seconds (int)\n",
    "        return self.time_to_second(time_b) - self.time_to_second(time_a)\n",
    "    \n",
    "    def add_pheromone_to_timematrix(self, timematrix):\n",
    "        for i in timematrix:\n",
    "            for j in timematrix[i]:\n",
    "                timematrix[i][j]['pheromone'] = self.init_pheromone\n",
    "        return timematrix\n",
    "    \n",
    "    def min_max_scaler(self,min_value,max_value,value):\n",
    "        if max_value-min_value == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return (value-min_value)/(max_value-min_value)\n",
    "    \n",
    "    def MAUT(self,solutions,consider_total_poi = True,use_penalty = True):\n",
    "        #input: optimization solutions, format = [{\"index\":[],\"waktu\":[],\"rating\":[],\"tarif\":[]},...]\n",
    "        #output: fitness value calculated using MAUT\n",
    "        \n",
    "        #concat all attribute lists (except for waktu)\n",
    "        index_ls = sum([i['index'] for i in solutions],[])\n",
    "        rating_ls = sum([i['rating'] for i in solutions],[])\n",
    "        tarif_ls = sum([i['tarif'] for i in solutions],[])\n",
    "        \n",
    "        waktu_ls = [i['waktu'] for i in solutions]\n",
    "        \n",
    "        #rating\n",
    "        avg_rating = sum(rating_ls)/len(rating_ls)\n",
    "        score_rating = self.min_max_scaler(self.min_rating,self.max_rating,avg_rating)*self.degree_rating\n",
    "        \n",
    "        #tarif\n",
    "        sum_tarif = sum(tarif_ls)\n",
    "        score_tarif = (1-self.min_max_scaler(self.min_tarif,self.max_tarif,sum_tarif)) * self.degree_tarif\n",
    "        \n",
    "        #waktu\n",
    "        waktu_per_day = [self.diff_second_between_time(i[0],i[-1]) for i in waktu_ls]\n",
    "        sum_waktu = sum(waktu_per_day)\n",
    "        score_waktu = (1-self.min_max_scaler(self.min_waktu,self.max_waktu,sum_waktu))*self.degree_waktu\n",
    "        \n",
    "        #poi\n",
    "        count_poi = len(index_ls)\n",
    "        score_poi = self.min_max_scaler(self.min_poi,self.max_poi,count_poi) if consider_total_poi == True else 0\n",
    "        \n",
    "        if use_penalty==True:\n",
    "            #poi penalty\n",
    "            penalty_index = [node._id for node in self.tour if node._id not in index_ls]\n",
    "            count_penalty = len(penalty_index)\n",
    "            score_poipenalty = (1-self.min_max_scaler(self.min_poi_penalty,self.max_poi_penalty,count_penalty)) * self.degree_poi_penalty\n",
    "            \n",
    "            #time penalty\n",
    "            penalty_per_day = [max(self.diff_second_between_time(i[-1],self.max_travel_time),0) for i in waktu_ls]\n",
    "            sum_time_penalty = sum(penalty_per_day)\n",
    "            score_timepenalty = (1-self.min_max_scaler(self.min_time_penalty,self.max_time_penalty,sum_time_penalty)) * self.degree_time_penalty\n",
    "        else:\n",
    "            score_poipenalty = 0\n",
    "            score_timepenalty = 0\n",
    "            \n",
    "        #MAUT\n",
    "        degree_rating = self.degree_rating\n",
    "        degree_tarif = self.degree_tarif\n",
    "        degree_waktu = self.degree_waktu\n",
    "        degree_poi = self.degree_poi if consider_total_poi == True else 0\n",
    "        degree_poi_penalty = self.degree_poi_penalty if use_penalty == True else 0\n",
    "        degree_time_penalty = self.degree_time_penalty if use_penalty == True else 0\n",
    "\n",
    "        pembilang = score_rating+score_tarif+score_waktu+score_poi+score_poipenalty+score_timepenalty\n",
    "        penyebut = degree_rating+degree_tarif+degree_waktu+degree_poi+degree_poi_penalty+degree_time_penalty\n",
    "        maut = pembilang/penyebut\n",
    "        return maut\n",
    "    \n",
    "    def MAUT_between_two_nodes(self,current_node,next_node):\n",
    "        score_rating = self.degree_rating * self.min_max_scaler(self.min_rating,self.max_rating,next_node.rating)\n",
    "        score_tarif = self.degree_tarif * (1-self.min_max_scaler(self.min_tarif,self.max_tarif,next_node.rating))\n",
    "        score_waktu = self.degree_waktu * (1-self.min_max_scaler(self.min_waktu,self.max_waktu,self.timematrix[current_node._id][next_node._id]['waktu']))\n",
    "        maut = (score_rating+score_tarif+score_waktu)/(self.degree_rating+self.degree_tarif+self.degree_waktu)\n",
    "        return maut\n",
    "    \n",
    "    def exploitation(self,current_node,next_node_candidates,local_pheromone_matrix):\n",
    "        max_pos = np.argmax([local_pheromone_matrix[current_node._id][next_node._id]['pheromone']*(self.MAUT_between_two_nodes(current_node,next_node)**self.beta) for next_node in next_node_candidates])\n",
    "        next_node = next_node_candidates[max_pos]\n",
    "        return next_node\n",
    "    \n",
    "    def exploration(self,current_node,next_node_candidates,local_pheromone_matrix):\n",
    "        #penyebut\n",
    "        sum_sample = 0\n",
    "        for next_node in next_node_candidates:\n",
    "            pheromone_in_edge = local_pheromone_matrix[current_node._id][next_node._id]['pheromone']**self.alpha_t\n",
    "            heuristic_val = self.MAUT_between_two_nodes(current_node,next_node)**self.beta\n",
    "            sum_sample += pheromone_in_edge*heuristic_val\n",
    "        \n",
    "        #probability\n",
    "        sum_sample = 0.0001 if sum_sample == 0 else sum_sample\n",
    "        next_node_prob = []\n",
    "        for next_node in next_node_candidates:\n",
    "            pheromone_in_edge = local_pheromone_matrix[current_node._id][next_node._id]['pheromone']**self.alpha_t\n",
    "            heuristic_val = self.MAUT_between_two_nodes(current_node,next_node)**self.beta\n",
    "            node_prob = (pheromone_in_edge*heuristic_val)/sum_sample\n",
    "            node_prob = 0.0001 if node_prob == 0 else node_prob\n",
    "            next_node_prob.append(node_prob)\n",
    "        \n",
    "        next_node = random.choices(next_node_candidates,next_node_prob,k=1)\n",
    "        return next_node[0]\n",
    "    \n",
    "    def transition_rule(self,current_node,next_node_candidates,local_pheromone_matrix):\n",
    "        q = random.uniform(0,1)\n",
    "        if q <= self.q0: #exploitation\n",
    "            next_node = self.exploitation(current_node,next_node_candidates,local_pheromone_matrix)\n",
    "        else: #exploration\n",
    "            next_node = self.exploration(current_node,next_node_candidates,local_pheromone_matrix)\n",
    "        return next_node\n",
    "    \n",
    "    def next_node_check(self,current_node,next_node):\n",
    "        time_needed = self.time_to_second(current_node.depart_time)+self.timematrix[current_node._id][next_node._id][\"waktu\"]+next_node.waktu_kunjungan\n",
    "        time_limit = self.time_to_second(self.max_travel_time)\n",
    "        if (time_needed <= time_limit) and (time_needed <= self.time_to_second(next_node.jam_tutup)):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def set_next_node_depart_arrive_time(self,current_node,next_node):\n",
    "        arrive_time = self.time_to_second(current_node.depart_time)+self.timematrix[current_node._id][next_node._id][\"waktu\"]\n",
    "        arrive_time = max([arrive_time,self.time_to_second(next_node.jam_buka)])\n",
    "        next_node.arrive_time = self.second_to_time(arrive_time)\n",
    "        if next_node.tipe.lower() != \"hotel\":\n",
    "            next_node.depart_time = self.second_to_time(arrive_time+next_node.waktu_kunjungan)\n",
    "        return next_node\n",
    "    \n",
    "    def local_pheromone_update(self,solutions,fitness,local_pheromone_matrix):\n",
    "        for day in solutions:\n",
    "            nodes = [self.hotel._id] + day['index'] + [self.hotel._id]\n",
    "            i = 1\n",
    "            while i < len(nodes):\n",
    "                pheromone = local_pheromone_matrix[nodes[i-1]][nodes[i]]['pheromone']\n",
    "                pheromone = ((1-self.rho)*pheromone)+(self.rho*fitness)\n",
    "                local_pheromone_matrix[nodes[i-1]][nodes[i]]['pheromone'] = pheromone\n",
    "                i += 1\n",
    "        return local_pheromone_matrix\n",
    "    \n",
    "    def global_pheromone_update(self,best_solutions,best_fitness):\n",
    "        solutions = copy.deepcopy(best_solutions)\n",
    "        solution_index = []\n",
    "        for day in solutions:\n",
    "            day_solution = [self.hotel._id] + day['index'] + [self.hotel._id] \n",
    "            day_solution = [(day_solution[i-1],day_solution[i]) for i in range(1,len(day['index']))]\n",
    "            solution_index = solution_index + day_solution\n",
    "        \n",
    "        for node in self.timematrix:\n",
    "            for next_node in self.timematrix[node]:\n",
    "                pheromone = self.timematrix[node][next_node]['pheromone']\n",
    "                if (node,next_node) in solution_index:\n",
    "                    pheromone = ((1-self.alpha)*pheromone)+(self.alpha*best_fitness)\n",
    "                else:\n",
    "                    pheromone = ((1-self.alpha)*pheromone)+0\n",
    "                self.timematrix[node][next_node]['pheromone'] = pheromone\n",
    "    \n",
    "    def construct_solution(self):\n",
    "        best_solution = None\n",
    "        best_fitness = 0\n",
    "        idem_counter = 0\n",
    "        counter = 0\n",
    "        for i in range(self.max_iter): #iteration\n",
    "            counter += 1\n",
    "            best_found_solution = None\n",
    "            best_found_fitness = 0\n",
    "            local_pheromone_matrix = copy.deepcopy(self.timematrix)\n",
    "            for ant in range(self.num_ant): #step\n",
    "                ant_solution = []\n",
    "                day = 1\n",
    "                tabu_nodes = []\n",
    "                while day<=self.travel_days:\n",
    "                    current_node = self.hotel\n",
    "                    ant_day_solution = {\"index\":[],\"waktu\":[current_node.depart_time],\"rating\":[],\"tarif\":[]}\n",
    "                    \n",
    "                    for pos in range(len(self.tour)+1):\n",
    "                        #recheck next node candidates (perlu dicek jam sampainya apakah melebihi max time)\n",
    "                        next_node_candidates = [node for node in self.tour if self.next_node_check(current_node,node)==True and node._id not in tabu_nodes]\n",
    "                        \n",
    "                        if len(next_node_candidates) > 0:\n",
    "                            #transition rules\n",
    "                            next_node = self.transition_rule(current_node,next_node_candidates,local_pheromone_matrix)\n",
    "                            next_node = self.set_next_node_depart_arrive_time(current_node,next_node)\n",
    "\n",
    "                            #change current node and delete it from available nodes\n",
    "                            current_node = next_node\n",
    "                            ant_day_solution['index'].append(current_node._id)\n",
    "                            ant_day_solution['rating'].append(current_node.rating)\n",
    "                            ant_day_solution['tarif'].append(current_node.tarif)\n",
    "                            ant_day_solution['waktu'].append(current_node.arrive_time)\n",
    "                            tabu_nodes.append(current_node._id)\n",
    "                        elif len(next_node_candidates) == 0 and current_node._id != self.hotel._id:\n",
    "                            last_node = copy.deepcopy(self.hotel)\n",
    "                            last_node = self.set_next_node_depart_arrive_time(current_node,last_node)\n",
    "                            ant_day_solution['waktu'].append(last_node.arrive_time)\n",
    "                            break\n",
    "                        else:\n",
    "                            break\n",
    "                    \n",
    "                    if len(ant_day_solution['index'])>0:\n",
    "                        ant_solution.append(ant_day_solution)\n",
    "\n",
    "                    if len(tabu_nodes) == len(self.tour):\n",
    "                        break\n",
    "\n",
    "                    day += 1\n",
    "                \n",
    "                fitness = self.MAUT(ant_solution)\n",
    "                if fitness > best_found_fitness:\n",
    "                    best_found_fitness = fitness\n",
    "                    best_found_solution = copy.deepcopy(ant_solution)\n",
    "                \n",
    "                # local pheromone update\n",
    "                local_pheromone_matrix = self.local_pheromone_update(ant_solution,fitness,local_pheromone_matrix)\n",
    "            \n",
    "            #global pheromone update\n",
    "            self.global_pheromone_update(best_found_solution,best_found_fitness)\n",
    "            \n",
    "            #checking best vs best found\n",
    "            if best_found_fitness > best_fitness:\n",
    "                best_fitness = best_found_fitness\n",
    "                best_solution = copy.deepcopy(best_found_solution)\n",
    "                idem_counter = 0\n",
    "            else:\n",
    "                idem_counter += 1\n",
    "                if idem_counter > self.max_idem:\n",
    "                    return best_solution,best_fitness,counter\n",
    "        \n",
    "        return best_solution,best_fitness,counter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "85fa35c9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_data(n = 30, random_state = None):\n",
    "    random.seed(random_state)\n",
    "    query = \"\"\"SELECT \n",
    "                    p.post_id,\n",
    "                    p.post_type,\n",
    "                    CASE\n",
    "                        WHEN pj.pj_jam_buka = pj.pj_jam_tutup THEN \"tutup\"\n",
    "                        ELSE \"buka\"\n",
    "                    END AS is_operate\n",
    "                FROM \n",
    "                    posts p\n",
    "                LEFT JOIN\n",
    "                    posts_jadwal pj\n",
    "                    ON p.post_id = pj.pj_id_tempat AND pj.pj_hari = \"minggu\"\n",
    "                \"\"\"\n",
    "\n",
    "    df_location = sql_connection.read_from_sql(query)\n",
    "    \n",
    "    tourid = df_location[(df_location['post_type']==\"location\")&\n",
    "                         (df_location['is_operate'] != \"tutup\")]['post_id'].values.tolist()\n",
    "    tourid = random.sample(tourid,n)\n",
    "    idhotel = df_location[df_location['post_type']==\"hotel\"]['post_id'].values.tolist()\n",
    "    idhotel = idhotel[random.randint(0,len(idhotel)-1)]\n",
    "    \n",
    "    db = ConDB()\n",
    "\n",
    "    hotel = db.HotelbyID(idhotel)\n",
    "    tur = db.WisatabyID(tourid)\n",
    "    timematrix = db.TimeMatrixbyID(hotel._id,tourid)\n",
    "    \n",
    "    return hotel,tur,timematrix\n",
    "\n",
    "def find_node(node_id,tour):\n",
    "    for node in tour:\n",
    "        if node._id == node_id:\n",
    "            return node\n",
    "    return False\n",
    "\n",
    "def get_analysis(model,hotel,tur,timematrix,travel_days,dwaktu,dtarif,drating):\n",
    "    start = time.time()\n",
    "    model.set_model(tour=tur,hotel=hotel,timematrix=timematrix,\n",
    "                    travel_days=travel_days,\n",
    "                    degree_waktu = dwaktu,degree_tarif = dtarif,degree_rating = drating)\n",
    "    \n",
    "    solution,fitness,counter = model.construct_solution()\n",
    "    end = time.time()\n",
    "    run_time = end-start\n",
    "    results = {\"fitness\":fitness,\n",
    "               \"run_time\":run_time,\n",
    "               \"num_iter\":counter}\n",
    "    \n",
    "    return results\n",
    "\n",
    "def get_analysis_runtime(model,hotel,tur,timematrix,travel_days,dwaktu,dtarif,drating):\n",
    "    start = time.time()\n",
    "    model.set_model(tour=tur,hotel=hotel,timematrix=timematrix,\n",
    "                    travel_days=travel_days,\n",
    "                    degree_waktu = dwaktu,degree_tarif = dtarif,degree_rating = drating)\n",
    "    \n",
    "    solution,fitness = model.construct_solution()\n",
    "    end = time.time()\n",
    "    run_time = end-start\n",
    "    results = {\"run_time\":run_time}\n",
    "    \n",
    "    return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "1c49f784",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n =  5\n",
      "n =  10\n",
      "n =  15\n",
      "n =  20\n",
      "n =  25\n",
      "n =  30\n",
      "n =  35\n",
      "n =  40\n",
      "n =  45\n",
      "n =  50\n",
      "n =  55\n",
      "n =  60\n",
      "n =  65\n",
      "n =  70\n",
      "n =  75\n",
      "n =  80\n",
      "n =  87\n"
     ]
    }
   ],
   "source": [
    "n = [5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,87]\n",
    "run_time_analysis = {\n",
    "    \"acs_vrp\": [],\n",
    "    \"acs_tsp\": [],\n",
    "    \"bso_vrp\": [],\n",
    "    \"bso_tsp\": [],\n",
    "    \"acsbso_vrp\": [],\n",
    "    \"acsbso_tsp\": []\n",
    "}\n",
    "\n",
    "for i in n:\n",
    "    # setting\n",
    "    hotel,tur,timematrix = generate_data(n=i,random_state=30)\n",
    "    travel_days = 3\n",
    "    dwaktu,dtarif,drating = 1,1,1\n",
    "    \n",
    "    print(\"n = \",i)\n",
    "    \n",
    "    acsbso_vrp = ACSBSO_VRP(random_state=100)\n",
    "    results_acsbso_vrp = get_analysis(acsbso_vrp,hotel,tur,timematrix,travel_days,dwaktu,dtarif,drating)\n",
    "    run_time_analysis[\"acsbso_vrp\"].append(results_acsbso_vrp)\n",
    "\n",
    "    acsbso_tsp = ACSBSO_TSP(random_state=100)\n",
    "    results_acsbso_tsp = get_analysis(acsbso_tsp,hotel,tur,timematrix,travel_days,dwaktu,dtarif,drating)\n",
    "    run_time_analysis[\"acsbso_tsp\"].append(results_acsbso_tsp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "c85529fe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'acs_vrp': [],\n",
       " 'acs_tsp': [],\n",
       " 'bso_vrp': [],\n",
       " 'bso_tsp': [],\n",
       " 'acsbso_vrp': [{'fitness': 0.8871090534979426,\n",
       "   'run_time': 0.523247241973877,\n",
       "   'num_iter': 34},\n",
       "  {'fitness': 0.6521678424456201,\n",
       "   'run_time': 4.088707208633423,\n",
       "   'num_iter': 65},\n",
       "  {'fitness': 0.6153649113966573,\n",
       "   'run_time': 3.0989885330200195,\n",
       "   'num_iter': 40},\n",
       "  {'fitness': 0.6438124632569079,\n",
       "   'run_time': 7.597972631454468,\n",
       "   'num_iter': 83},\n",
       "  {'fitness': 0.7030226563559895,\n",
       "   'run_time': 22.404173612594604,\n",
       "   'num_iter': 140},\n",
       "  {'fitness': 0.6924740386265574,\n",
       "   'run_time': 35.13963317871094,\n",
       "   'num_iter': 138},\n",
       "  {'fitness': 0.6647941396343559,\n",
       "   'run_time': 24.918997287750244,\n",
       "   'num_iter': 79},\n",
       "  {'fitness': 0.6490533283588839,\n",
       "   'run_time': 82.1964681148529,\n",
       "   'num_iter': 189},\n",
       "  {'fitness': 0.6290064506871007,\n",
       "   'run_time': 81.9681396484375,\n",
       "   'num_iter': 161},\n",
       "  {'fitness': 0.614246999528495,\n",
       "   'run_time': 108.57296133041382,\n",
       "   'num_iter': 149},\n",
       "  {'fitness': 0.6055980654362337,\n",
       "   'run_time': 89.47370219230652,\n",
       "   'num_iter': 114},\n",
       "  {'fitness': 0.608312406692506,\n",
       "   'run_time': 152.0643572807312,\n",
       "   'num_iter': 158},\n",
       "  {'fitness': 0.602657584772457,\n",
       "   'run_time': 210.43045234680176,\n",
       "   'num_iter': 200},\n",
       "  {'fitness': 0.587594123970585,\n",
       "   'run_time': 181.9523994922638,\n",
       "   'num_iter': 139},\n",
       "  {'fitness': 0.5891579724634121,\n",
       "   'run_time': 265.4540708065033,\n",
       "   'num_iter': 200},\n",
       "  {'fitness': 0.5864081337421732,\n",
       "   'run_time': 267.9887914657593,\n",
       "   'num_iter': 172},\n",
       "  {'fitness': 0.5766677310080689,\n",
       "   'run_time': 311.8600091934204,\n",
       "   'num_iter': 153}],\n",
       " 'acsbso_tsp': [{'fitness': 0.8871090534979426,\n",
       "   'run_time': 1.825735330581665,\n",
       "   'num_iter': 200},\n",
       "  {'fitness': 0.6509332745443855,\n",
       "   'run_time': 6.508529186248779,\n",
       "   'num_iter': 200},\n",
       "  {'fitness': 0.5957157554379778,\n",
       "   'run_time': 2.2220771312713623,\n",
       "   'num_iter': 32},\n",
       "  {'fitness': 0.5130180776014107,\n",
       "   'run_time': 26.073946952819824,\n",
       "   'num_iter': 164},\n",
       "  {'fitness': 0.6050178062678063,\n",
       "   'run_time': 23.188172578811646,\n",
       "   'num_iter': 102},\n",
       "  {'fitness': 0.5914689807546951,\n",
       "   'run_time': 18.93401336669922,\n",
       "   'num_iter': 66},\n",
       "  {'fitness': 0.5175336298751397,\n",
       "   'run_time': 53.1764440536499,\n",
       "   'num_iter': 137},\n",
       "  {'fitness': 0.6044136933025822,\n",
       "   'run_time': 35.34837889671326,\n",
       "   'num_iter': 113},\n",
       "  {'fitness': 0.5572424889769501,\n",
       "   'run_time': 79.22019934654236,\n",
       "   'num_iter': 161},\n",
       "  {'fitness': 0.49145201362442203,\n",
       "   'run_time': 56.4786696434021,\n",
       "   'num_iter': 114},\n",
       "  {'fitness': 0.4720598216003859,\n",
       "   'run_time': 67.66477918624878,\n",
       "   'num_iter': 110},\n",
       "  {'fitness': 0.4531237225423672,\n",
       "   'run_time': 188.85940837860107,\n",
       "   'num_iter': 186},\n",
       "  {'fitness': 0.5275912135535603,\n",
       "   'run_time': 90.41211247444153,\n",
       "   'num_iter': 135},\n",
       "  {'fitness': 0.5302211247209904,\n",
       "   'run_time': 116.19810771942139,\n",
       "   'num_iter': 156},\n",
       "  {'fitness': 0.46306144428710977,\n",
       "   'run_time': 121.09349298477173,\n",
       "   'num_iter': 140},\n",
       "  {'fitness': 0.49787764896051145,\n",
       "   'run_time': 112.98970460891724,\n",
       "   'num_iter': 162},\n",
       "  {'fitness': 0.5149172269867764,\n",
       "   'run_time': 169.94827485084534,\n",
       "   'num_iter': 200}]}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "run_time_analysis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "3c6276a4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n =  5\n",
      "n =  10\n",
      "n =  15\n",
      "n =  20\n",
      "n =  25\n",
      "n =  30\n",
      "n =  35\n",
      "n =  40\n",
      "n =  45\n",
      "n =  50\n",
      "n =  55\n",
      "n =  60\n",
      "n =  65\n",
      "n =  70\n",
      "n =  75\n",
      "n =  80\n",
      "n =  87\n"
     ]
    }
   ],
   "source": [
    "n = [5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,87]\n",
    "run_time_analysis_1 = {\n",
    "    \"acs_vrp\": [],\n",
    "    \"acs_tsp\": [],\n",
    "    \"bso_vrp\": [],\n",
    "    \"bso_tsp\": [],\n",
    "    \"acsbso_vrp\": [],\n",
    "    \"acsbso_tsp\": []\n",
    "}\n",
    "\n",
    "for i in n:\n",
    "    # setting\n",
    "    hotel,tur,timematrix = generate_data(n=i,random_state=30)\n",
    "    travel_days = 3\n",
    "    dwaktu,dtarif,drating = 1,1,1\n",
    "    \n",
    "    print(\"n = \",i)\n",
    "    \n",
    "    acs_vrp = ACS_VRP(random_state=100)\n",
    "    results_acs_vrp = get_analysis(acs_vrp,hotel,tur,timematrix,travel_days,dwaktu,dtarif,drating)\n",
    "    run_time_analysis_1[\"acs_vrp\"].append(results_acs_vrp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "a941ca6c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'acs_vrp': [{'fitness': 0.8871090534979426,\n",
       "   'run_time': 0.1209268569946289,\n",
       "   'num_iter': 39},\n",
       "  {'fitness': 0.6519106407995295,\n",
       "   'run_time': 0.6992928981781006,\n",
       "   'num_iter': 75},\n",
       "  {'fitness': 0.6215377509028303,\n",
       "   'run_time': 0.8479659557342529,\n",
       "   'num_iter': 49},\n",
       "  {'fitness': 0.6493433793270394,\n",
       "   'run_time': 1.1750760078430176,\n",
       "   'num_iter': 46},\n",
       "  {'fitness': 0.6970555781666891,\n",
       "   'run_time': 2.320909261703491,\n",
       "   'num_iter': 69},\n",
       "  {'fitness': 0.6752524041214517,\n",
       "   'run_time': 1.925980567932129,\n",
       "   'num_iter': 46},\n",
       "  {'fitness': 0.6564085955924697,\n",
       "   'run_time': 5.0770533084869385,\n",
       "   'num_iter': 97},\n",
       "  {'fitness': 0.6424735646354003,\n",
       "   'run_time': 9.389315605163574,\n",
       "   'num_iter': 159},\n",
       "  {'fitness': 0.6182695512564123,\n",
       "   'run_time': 10.063584327697754,\n",
       "   'num_iter': 155},\n",
       "  {'fitness': 0.6095609084529636,\n",
       "   'run_time': 8.652856826782227,\n",
       "   'num_iter': 116},\n",
       "  {'fitness': 0.6015472188247385,\n",
       "   'run_time': 12.491825819015503,\n",
       "   'num_iter': 144},\n",
       "  {'fitness': 0.5963971808177438,\n",
       "   'run_time': 8.652019262313843,\n",
       "   'num_iter': 92},\n",
       "  {'fitness': 0.5835172226039644,\n",
       "   'run_time': 9.063151836395264,\n",
       "   'num_iter': 90},\n",
       "  {'fitness': 0.5857950760879688,\n",
       "   'run_time': 11.4388267993927,\n",
       "   'num_iter': 98},\n",
       "  {'fitness': 0.5823288626890798,\n",
       "   'run_time': 12.325547456741333,\n",
       "   'num_iter': 98},\n",
       "  {'fitness': 0.5722121344320837,\n",
       "   'run_time': 16.100229740142822,\n",
       "   'num_iter': 117},\n",
       "  {'fitness': 0.5629081181272565,\n",
       "   'run_time': 14.069304466247559,\n",
       "   'num_iter': 95}],\n",
       " 'acs_tsp': [],\n",
       " 'bso_vrp': [],\n",
       " 'bso_tsp': [],\n",
       " 'acsbso_vrp': [],\n",
       " 'acsbso_tsp': []}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "run_time_analysis_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "bf7fd149",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n =  5\n",
      "n =  10\n",
      "n =  15\n",
      "n =  20\n",
      "n =  25\n",
      "n =  30\n",
      "n =  35\n",
      "n =  40\n",
      "n =  45\n",
      "n =  50\n",
      "n =  55\n",
      "n =  60\n",
      "n =  65\n",
      "n =  70\n",
      "n =  75\n",
      "n =  80\n",
      "n =  87\n"
     ]
    }
   ],
   "source": [
    "n = [5,10,15,20,25,30,35,40,45,50,55,60,65,70,75,80,87]\n",
    "run_time_analysis = {\n",
    "    \"acs_vrp\": [],\n",
    "    \"acs_tsp\": [],\n",
    "    \"bso_vrp\": [],\n",
    "    \"bso_tsp\": [],\n",
    "    \"acsbso_vrp\": [],\n",
    "    \"acsbso_tsp\": []\n",
    "}\n",
    "max_runtime = 100*60 #100 minutes\n",
    "for i in n:\n",
    "    # setting\n",
    "    hotel,tur,timematrix = generate_data(n=i,random_state=30)\n",
    "    travel_days = 3\n",
    "    dwaktu,dtarif,drating = 1,1,1\n",
    "    \n",
    "    print(\"n = \",i)\n",
    "    \n",
    "    if len(run_time_analysis[\"acs_tsp\"])==0 or run_time_analysis[\"acs_tsp\"][-1] < max_runtime:\n",
    "        acs_tsp = ACS_TSP(random_state=100)\n",
    "        results_acs_tsp = get_analysis_runtime(acs_tsp,hotel,tur,timematrix,travel_days,dwaktu,dtarif,drating)\n",
    "        run_time_analysis[\"acs_tsp\"].append(results_acs_tsp[\"run_time\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "26bfa069",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'acs_vrp': [],\n",
       " 'acs_tsp': [0.786677360534668,\n",
       "  1.3663792610168457,\n",
       "  1.739077091217041,\n",
       "  2.6816861629486084,\n",
       "  3.8282876014709473,\n",
       "  7.715126276016235,\n",
       "  8.01999831199646,\n",
       "  7.103944540023804,\n",
       "  14.246813297271729,\n",
       "  14.141031265258789,\n",
       "  14.911083936691284,\n",
       "  16.040632009506226,\n",
       "  16.398995399475098,\n",
       "  30.745311975479126,\n",
       "  45.492440938949585,\n",
       "  29.923640251159668,\n",
       "  37.423826932907104],\n",
       " 'bso_vrp': [],\n",
       " 'bso_tsp': [],\n",
       " 'acsbso_vrp': [],\n",
       " 'acsbso_tsp': []}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "run_time_analysis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "89e78b07",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
