{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "088901fd",
   "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",
    "\n",
    "class GA_VRP(object):\n",
    "    def __init__(self,population_size = 50,crossover_rate=0.8,mutation_rate=0.2,max_iter = 300,max_idem = 15,random_state=None):\n",
    "        self.db = ConDB()\n",
    "        \n",
    "        # parameter setting\n",
    "        self.population_size = population_size #max size of population\n",
    "        self.crossover_rate = crossover_rate\n",
    "        self.mutation_rate = mutation_rate\n",
    "        self.max_iter = max_iter #max iteration of tabu search\n",
    "        self.max_idem = max_idem #stop if the best fitness doesn't increase for max_idem iteration\n",
    "\n",
    "        # set initial solution\n",
    "        self.init_solution = [] #2D list of nodes, [[node1,node2,....],[node4,node5,....]]\n",
    "        self.rest_nodes = [] #1D list of nodes, [node1,node2,node4,node5,....]\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,init_solution=[],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 = 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 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 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 solution_list_of_nodes_to_dict(self, solutions):\n",
    "        solution_dict = []\n",
    "        for day in solutions:\n",
    "            day_solution = {\"index\":[],\"waktu\":[self.hotel.depart_time],\"rating\":[],\"tarif\":[]}\n",
    "            day_solution['index'] = [i._id for i in day]\n",
    "            day_solution['rating'] = [i.rating for i in day]\n",
    "            day_solution['tarif'] = [i.tarif for i in day]\n",
    "            \n",
    "            last_waktu = self.time_to_second(day[-1].depart_time) + self.timematrix[day[-1]._id][self.hotel._id]['waktu']\n",
    "            day_solution['waktu'].extend([i.arrive_time for i in day] + [self.second_to_time(last_waktu)])\n",
    "            \n",
    "            solution_dict.append(day_solution)\n",
    "        return solution_dict\n",
    "    \n",
    "    def split_itinerary(self,init_itinerary):\n",
    "        final_solution = [] #2d list of nodes\n",
    "        day = 1\n",
    "        tabu_nodes = [] #list of tabu node's id\n",
    "        while day <= self.travel_days:\n",
    "            current_node = self.hotel\n",
    "            day_solution = [] #list of nodes\n",
    "            next_node_candidates = [node for node in init_itinerary if node._id not in tabu_nodes]\n",
    "            for i in range(len(next_node_candidates)):\n",
    "                if 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.append(next_node_candidates[i])\n",
    "                    tabu_nodes.append(next_node_candidates[i]._id)\n",
    "                    current_node = next_node_candidates[i]\n",
    "            \n",
    "            if len(day_solution) > 0:\n",
    "                final_solution.append(day_solution)\n",
    "            \n",
    "            if len(tabu_nodes) == len(self.tour):\n",
    "                break\n",
    "            \n",
    "            day += 1\n",
    "        return final_solution\n",
    "    \n",
    "    def partially_mapped_crossover(self,parent1,parent2): #PMX\n",
    "        start,end = sorted(random.sample(range(len(parent1)), 2))\n",
    "        child1 = [None] * len(parent1)\n",
    "        child2 = copy.deepcopy(child1)\n",
    "        mapping1 = {parent1[i]._id:parent2[i] for i in range(start,end+1)}\n",
    "        mapping2 = {parent2[i]._id:parent1[i] for i in range(start,end+1)}\n",
    "\n",
    "        for i in range(len(parent1)):\n",
    "            if start <= i <= end:\n",
    "                child1[i],child2[i] = parent1[i],parent2[i] \n",
    "            else:\n",
    "                gene1,gene2 = parent2[i],parent1[i]\n",
    "                while gene1._id in mapping1:\n",
    "                    gene1 = mapping1[gene1._id]\n",
    "                while gene2._id in mapping2:\n",
    "                    gene2 = mapping2[gene2._id]\n",
    "                child1[i],child2[i] = gene1,gene2\n",
    "\n",
    "        return child1,child2\n",
    "    \n",
    "    def swap_mutation(self,individual):\n",
    "        individu = copy.deepcopy(individual)\n",
    "        pos1,pos2 = random.sample(range(len(individu)),2)\n",
    "        individu[pos1],individu[pos2] = individu[pos2],individu[pos1]\n",
    "        return individu\n",
    "    \n",
    "    def construct_solution(self):\n",
    "        solution_dict = {}\n",
    "        fitness = 0\n",
    "        \n",
    "        idem_counter = 0\n",
    "        population = [random.sample(self.tour,len(self.tour)) for i in range(self.population_size)]\n",
    "        for i in range(self.max_iter):\n",
    "                        \n",
    "            #crossover and mutation\n",
    "            offspring = []\n",
    "            for ind in range(0,self.population_size,2):\n",
    "                parent1,parent2 = population[ind],population[ind+1]\n",
    "\n",
    "                #crossover\n",
    "                if random.uniform(0,1) < self.crossover_rate:\n",
    "                    child1,child2 = self.partially_mapped_crossover(parent1,parent2)\n",
    "                else:\n",
    "                    child1,child2 = copy.deepcopy(parent1),copy.deepcopy(parent2)\n",
    "                \n",
    "                #mutation\n",
    "                if random.uniform(0,1) < self.mutation_rate:\n",
    "                    child1 = self.swap_mutation(child1)\n",
    "                if random.uniform(0,1) < self.mutation_rate:\n",
    "                    child2 = self.swap_mutation(child2)\n",
    "                \n",
    "                offspring.append(child1)\n",
    "                offspring.append(child2)\n",
    "            \n",
    "            #selection roulette wheel\n",
    "            all_individuals = population + offspring\n",
    "            fitness_values = [self.MAUT(self.solution_list_of_nodes_to_dict(self.split_itinerary(individual))) for individual in all_individuals]\n",
    "            \n",
    "            population = random.choices(all_individuals,weights=np.array(fitness_values)/sum(fitness_values),k=self.population_size)\n",
    "\n",
    "            best_solution = max(population,key=lambda x: self.MAUT(self.solution_list_of_nodes_to_dict(self.split_itinerary(x))))\n",
    "            best_solution_dict = self.solution_list_of_nodes_to_dict(self.split_itinerary(best_solution))\n",
    "            best_fitness = self.MAUT(best_solution_dict)\n",
    "            \n",
    "            if fitness < best_fitness:\n",
    "                fitness = best_fitness\n",
    "                solution_dict = best_solution_dict\n",
    "                idem_counter = 0\n",
    "            else:\n",
    "                idem_counter += 1\n",
    "                if idem_counter > self.max_idem:\n",
    "                    return solution_dict,fitness\n",
    "        \n",
    "        return solution_dict,fitness"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "22e1be82",
   "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",
    "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')\n",
    "\n",
    "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",
    "# setting\n",
    "hotel,tur,timematrix = generate_data(n=30,random_state=30) #random state 50 blacklist\n",
    "travel_days = 3\n",
    "dwaktu,dtarif,drating = 1,1,1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "af1cbd03",
   "metadata": {},
   "outputs": [],
   "source": [
    "ga_vrp = GA_VRP(random_state=100)\n",
    "ga_vrp.set_model(tour=tur,hotel=hotel,timematrix=timematrix,\n",
    "                 travel_days=travel_days,degree_waktu = dwaktu,degree_tarif = dtarif,degree_rating = drating)\n",
    "a,b = ga_vrp.construct_solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "7c627264",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'index': [73, 76, 93, 9, 86, 18, 10, 4],\n",
       "  'waktu': [datetime.time(8, 0),\n",
       "   datetime.time(8, 24),\n",
       "   datetime.time(9, 32),\n",
       "   datetime.time(11, 8),\n",
       "   datetime.time(13, 50),\n",
       "   datetime.time(14, 24),\n",
       "   datetime.time(15, 31),\n",
       "   datetime.time(16, 37),\n",
       "   datetime.time(17, 43),\n",
       "   datetime.time(19, 29)],\n",
       "  'rating': [4.8, 4.5, 4.6, 4.7, 4.4, 4.5, 4.6, 4.6],\n",
       "  'tarif': [0, 0, 2500, 0, 0, 0, 0, 0]},\n",
       " {'index': [39, 34, 71, 88, 46],\n",
       "  'waktu': [datetime.time(8, 0),\n",
       "   datetime.time(8, 58),\n",
       "   datetime.time(11, 8),\n",
       "   datetime.time(14, 1),\n",
       "   datetime.time(16, 42),\n",
       "   datetime.time(17, 52),\n",
       "   datetime.time(19, 30)],\n",
       "  'rating': [4.6, 4.5, 4.5, 4.8, 5.0],\n",
       "  'tarif': [6000, 0, 5000, 0, 0]},\n",
       " {'index': [16, 35, 7, 54, 22, 95, 1],\n",
       "  'waktu': [datetime.time(8, 0),\n",
       "   datetime.time(8, 20),\n",
       "   datetime.time(11, 0),\n",
       "   datetime.time(12, 9),\n",
       "   datetime.time(13, 47),\n",
       "   datetime.time(15, 23),\n",
       "   datetime.time(17, 9),\n",
       "   datetime.time(18, 14),\n",
       "   datetime.time(19, 52)],\n",
       "  'rating': [4.4, 4.6, 4.8, 3.7, 4.5, 4.3, 4.8],\n",
       "  'tarif': [0, 10000, 0, 0, 0, 0, 0]}]"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "2f017030",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6560393530631624"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "c7609707",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([{'index': [53, 46, 1, 7, 9, 73],\n",
       "   'waktu': [datetime.time(8, 0),\n",
       "    datetime.time(12, 0),\n",
       "    datetime.time(14, 2),\n",
       "    datetime.time(15, 36),\n",
       "    datetime.time(17, 9),\n",
       "    datetime.time(18, 10),\n",
       "    datetime.time(18, 57),\n",
       "    datetime.time(20, 4)],\n",
       "   'rating': [5.0, 5.0, 4.8, 4.8, 4.7, 4.8],\n",
       "   'tarif': [25000, 0, 0, 0, 0, 0]},\n",
       "  {'index': [93, 74, 64, 10, 4],\n",
       "   'waktu': [datetime.time(8, 0),\n",
       "    datetime.time(8, 50),\n",
       "    datetime.time(11, 44),\n",
       "    datetime.time(14, 18),\n",
       "    datetime.time(16, 33),\n",
       "    datetime.time(17, 39),\n",
       "    datetime.time(19, 25)],\n",
       "   'rating': [4.6, 4.8, 4.7, 4.6, 4.6],\n",
       "   'tarif': [2500, 0, 25000, 0, 0]},\n",
       "  {'index': [39, 69, 35, 88, 71, 22],\n",
       "   'waktu': [datetime.time(8, 0),\n",
       "    datetime.time(8, 58),\n",
       "    datetime.time(10, 55),\n",
       "    datetime.time(12, 4),\n",
       "    datetime.time(13, 7),\n",
       "    datetime.time(14, 48),\n",
       "    datetime.time(17, 36),\n",
       "    datetime.time(19, 11)],\n",
       "   'rating': [4.6, 4.6, 4.6, 4.8, 4.5, 4.5],\n",
       "   'tarif': [6000, 8000, 10000, 0, 5000, 0]}],\n",
       " 0.6089920298603771)"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "b1c2bfdd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Pasar Ngasem(09:32:00-10:17:00),\n",
       " Situs Gua Seluman(00:00:00-00:00:00),\n",
       " Pakualaman Palace(00:00:00-00:00:00),\n",
       " The Lost World Castle(11:11:00-12:41:00),\n",
       " Grojogan Watu Purbo Gate(14:43:00-16:13:00),\n",
       " Jogja T-Shirt Jethe(16:47:00-17:32:00),\n",
       " Paintball Jupiter Jogja(08:21:00-10:21:00),\n",
       " Desa Wisata Pentingsari(12:49:00-14:49:00),\n",
       " Bukit Pangol(00:00:00-00:00:00),\n",
       " Gembira Loka Zoo(13:48:00-15:18:00),\n",
       " Klenteng Poncowinatan(00:00:00-00:00:00),\n",
       " Mandira Baruga(10:24:00-11:24:00),\n",
       " Kampung Wisata Basen(10:32:00-11:17:00)]"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ts_vrp.rest_nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "b40f6b58",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[MALIOBORO JOGJAKARTA(00:00:00-00:00:00),\n",
       " Bringin Kembar Yogyakarta(00:00:00-00:00:00),\n",
       " Titik Nol Km Yogyakarta(00:00:00-00:00:00),\n",
       " Tarunasura Wijilan Gate(00:00:00-00:00:00),\n",
       " Yogyakarta Northern Square(00:00:00-00:00:00),\n",
       " Pasar Ngasem(00:00:00-00:00:00),\n",
       " Situs Gua Seluman(00:00:00-00:00:00),\n",
       " Pakualaman Palace(00:00:00-00:00:00),\n",
       " Bentara Budaya Yogyakarta (BBY)(00:00:00-00:00:00),\n",
       " The Lost World Castle(00:00:00-00:00:00),\n",
       " Grojogan Watu Purbo Gate(00:00:00-00:00:00),\n",
       " House of Chocolate Monggo & Gelato Tirtodipuran(00:00:00-00:00:00),\n",
       " Sermo Reservoir Dam(00:00:00-00:00:00),\n",
       " Jogja T-Shirt Jethe(00:00:00-00:00:00),\n",
       " ALUN ALUN KIDUL YOGYAKARTA(00:00:00-00:00:00),\n",
       " Paintball Jupiter Jogja(00:00:00-00:00:00),\n",
       " Desa Wisata Pentingsari(00:00:00-00:00:00),\n",
       " GOLDEN BIOSKOP VIRTUAL REALITY(00:00:00-00:00:00),\n",
       " Bukit Pangol(00:00:00-00:00:00),\n",
       " Bukit Rhema Gereja Ayam(00:00:00-00:00:00),\n",
       " The Palace of Yogyakarta(00:00:00-00:00:00),\n",
       " Hutan Pinus Pengger(00:00:00-00:00:00),\n",
       " Gembira Loka Zoo(00:00:00-00:00:00),\n",
       " Makam Panembahan Senopati(00:00:00-00:00:00),\n",
       " Tourism Village Mlangi(00:00:00-00:00:00),\n",
       " Klenteng Poncowinatan(00:00:00-00:00:00),\n",
       " Mandira Baruga(00:00:00-00:00:00),\n",
       " Jogokariyan Mosque(00:00:00-00:00:00),\n",
       " Seribu Batu Songgo Langit(00:00:00-00:00:00),\n",
       " Kampung Wisata Basen(00:00:00-00:00:00)]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3cc32cf4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6a1bb455",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum([[1,2,3],[4,5,6]],[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "ccc3659d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{11: Sermo Reservoir Dam(00:00:00-00:00:00), 72: ALUN ALUN KIDUL YOGYAKARTA(00:00:00-00:00:00), 39: GOLDEN BIOSKOP VIRTUAL REALITY(00:00:00-00:00:00), 35: Bentara Budaya Yogyakarta (BBY)(00:00:00-00:00:00), 40: Klenteng Poncowinatan(00:00:00-00:00:00), 51: Pasar Ngasem(00:00:00-00:00:00), 9: Tarunasura Wijilan Gate(00:00:00-00:00:00), 53: Kampung Wisata Basen(00:00:00-00:00:00), 64: MALIOBORO JOGJAKARTA(00:00:00-00:00:00), 7: Hutan Pinus Pengger(00:00:00-00:00:00), 88: Yogyakarta Northern Square(00:00:00-00:00:00)}\n",
      "{39: Pasar Ngasem(00:00:00-00:00:00), 46: Gembira Loka Zoo(00:00:00-00:00:00), 53: Sermo Reservoir Dam(00:00:00-00:00:00), 22: House of Chocolate Monggo & Gelato Tirtodipuran(00:00:00-00:00:00), 76: Jogja T-Shirt Jethe(00:00:00-00:00:00), 11: Desa Wisata Pentingsari(00:00:00-00:00:00), 9: Tarunasura Wijilan Gate(00:00:00-00:00:00), 95: GOLDEN BIOSKOP VIRTUAL REALITY(00:00:00-00:00:00), 1: Bukit Rhema Gereja Ayam(00:00:00-00:00:00), 71: Titik Nol Km Yogyakarta(00:00:00-00:00:00), 10: Jogokariyan Mosque(00:00:00-00:00:00)}\n",
      "10\n",
      "got  10\n",
      "46\n",
      "got  46\n",
      "93\n",
      "74\n",
      "95\n",
      "got  95\n",
      "got  53\n",
      "got  39\n",
      "got  11\n",
      "1\n",
      "got  1\n",
      "34\n",
      "73\n",
      "54\n",
      "76\n",
      "got  76\n",
      "86\n",
      "47\n",
      "16\n",
      "4\n",
      "29\n",
      "18\n",
      "71\n",
      "got  71\n",
      "22\n",
      "got  22\n",
      "69\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([The Palace of Yogyakarta(00:00:00-00:00:00),\n",
       "  Klenteng Poncowinatan(00:00:00-00:00:00),\n",
       "  Mandira Baruga(00:00:00-00:00:00),\n",
       "  Situs Gua Seluman(00:00:00-00:00:00),\n",
       "  Pasar Ngasem(00:00:00-00:00:00),\n",
       "  Gembira Loka Zoo(00:00:00-00:00:00),\n",
       "  Sermo Reservoir Dam(00:00:00-00:00:00),\n",
       "  House of Chocolate Monggo & Gelato Tirtodipuran(00:00:00-00:00:00),\n",
       "  Jogja T-Shirt Jethe(00:00:00-00:00:00),\n",
       "  Desa Wisata Pentingsari(00:00:00-00:00:00),\n",
       "  Tarunasura Wijilan Gate(00:00:00-00:00:00),\n",
       "  GOLDEN BIOSKOP VIRTUAL REALITY(00:00:00-00:00:00),\n",
       "  Bukit Rhema Gereja Ayam(00:00:00-00:00:00),\n",
       "  Titik Nol Km Yogyakarta(00:00:00-00:00:00),\n",
       "  Jogokariyan Mosque(00:00:00-00:00:00),\n",
       "  Kampung Wisata Basen(00:00:00-00:00:00),\n",
       "  Seribu Batu Songgo Langit(00:00:00-00:00:00),\n",
       "  The Lost World Castle(00:00:00-00:00:00),\n",
       "  Hutan Pinus Pengger(00:00:00-00:00:00),\n",
       "  MALIOBORO JOGJAKARTA(00:00:00-00:00:00),\n",
       "  Bentara Budaya Yogyakarta (BBY)(00:00:00-00:00:00),\n",
       "  Makam Panembahan Senopati(00:00:00-00:00:00),\n",
       "  Grojogan Watu Purbo Gate(00:00:00-00:00:00),\n",
       "  Pakualaman Palace(00:00:00-00:00:00),\n",
       "  Bukit Pangol(00:00:00-00:00:00),\n",
       "  Yogyakarta Northern Square(00:00:00-00:00:00),\n",
       "  Bringin Kembar Yogyakarta(00:00:00-00:00:00),\n",
       "  Tourism Village Mlangi(00:00:00-00:00:00),\n",
       "  ALUN ALUN KIDUL YOGYAKARTA(00:00:00-00:00:00),\n",
       "  Paintball Jupiter Jogja(00:00:00-00:00:00)],\n",
       " [Jogokariyan Mosque(00:00:00-00:00:00),\n",
       "  Gembira Loka Zoo(00:00:00-00:00:00),\n",
       "  Seribu Batu Songgo Langit(00:00:00-00:00:00),\n",
       "  Tourism Village Mlangi(00:00:00-00:00:00),\n",
       "  Sermo Reservoir Dam(00:00:00-00:00:00),\n",
       "  ALUN ALUN KIDUL YOGYAKARTA(00:00:00-00:00:00),\n",
       "  GOLDEN BIOSKOP VIRTUAL REALITY(00:00:00-00:00:00),\n",
       "  Bentara Budaya Yogyakarta (BBY)(00:00:00-00:00:00),\n",
       "  Klenteng Poncowinatan(00:00:00-00:00:00),\n",
       "  Pasar Ngasem(00:00:00-00:00:00),\n",
       "  Tarunasura Wijilan Gate(00:00:00-00:00:00),\n",
       "  Kampung Wisata Basen(00:00:00-00:00:00),\n",
       "  MALIOBORO JOGJAKARTA(00:00:00-00:00:00),\n",
       "  Hutan Pinus Pengger(00:00:00-00:00:00),\n",
       "  Yogyakarta Northern Square(00:00:00-00:00:00),\n",
       "  Desa Wisata Pentingsari(00:00:00-00:00:00),\n",
       "  Bukit Rhema Gereja Ayam(00:00:00-00:00:00),\n",
       "  Grojogan Watu Purbo Gate(00:00:00-00:00:00),\n",
       "  Makam Panembahan Senopati(00:00:00-00:00:00),\n",
       "  Bukit Pangol(00:00:00-00:00:00),\n",
       "  Jogja T-Shirt Jethe(00:00:00-00:00:00),\n",
       "  Mandira Baruga(00:00:00-00:00:00),\n",
       "  Paintball Jupiter Jogja(00:00:00-00:00:00),\n",
       "  Situs Gua Seluman(00:00:00-00:00:00),\n",
       "  Bringin Kembar Yogyakarta(00:00:00-00:00:00),\n",
       "  The Lost World Castle(00:00:00-00:00:00),\n",
       "  Pakualaman Palace(00:00:00-00:00:00),\n",
       "  Titik Nol Km Yogyakarta(00:00:00-00:00:00),\n",
       "  House of Chocolate Monggo & Gelato Tirtodipuran(00:00:00-00:00:00),\n",
       "  The Palace of Yogyakarta(00:00:00-00:00:00)])"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "import copy\n",
    "random.seed(100)\n",
    "def partially_mapped_crossover(parent1,parent2): #PMX\n",
    "    start,end = sorted(random.sample(range(len(parent1)), 2))\n",
    "    child1 = [None] * len(parent1)\n",
    "    child2 = copy.deepcopy(child1)\n",
    "    mapping1 = {parent1[i]._id:parent2[i] for i in range(start,end+1)}\n",
    "    mapping2 = {parent2[i]._id:parent1[i] for i in range(start,end+1)}\n",
    "    print(mapping1)\n",
    "    print(mapping2)\n",
    "\n",
    "    for i in range(len(parent1)):\n",
    "        if start <= i <= end:\n",
    "            child1[i],child2[i] = parent1[i],parent2[i] \n",
    "        else:\n",
    "            gene1,gene2 = parent2[i],parent1[i]\n",
    "            while gene1._id in mapping1:\n",
    "                gene1 = mapping1[gene1._id]            \n",
    "            print(gene2._id)\n",
    "            while gene2._id in mapping2:\n",
    "                print(\"got \", gene2._id)\n",
    "                gene2 = mapping2[gene2._id]\n",
    "            child1[i],child2[i] = gene1,gene2\n",
    "\n",
    "    return child1,child2\n",
    "\n",
    "partially_mapped_crossover(a,b)\n",
    "# partially_mapped_crossover(tur[:5],tur[5:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "987845e2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[6, 2, 3, 4, 5, 1]"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def partially_mapped_crossover(parent1, parent2):\n",
    "    # Perform crossover\n",
    "    start, end = sorted(random.sample(range(len(parent1)), 2))\n",
    "    child = [None] * len(parent1)\n",
    "    mapping = {parent1[i]: parent2[i] for i in range(start, end + 1)}\n",
    "\n",
    "    # Resolve conflicts and complete mapping\n",
    "    for i in range(len(parent1)):\n",
    "        if start <= i <= end:\n",
    "            child[i] = parent1[i]\n",
    "        else:\n",
    "            gene = parent2[i]\n",
    "            while gene in mapping:\n",
    "                print(gene)\n",
    "                gene = mapping[gene]\n",
    "            child[i] = gene\n",
    "\n",
    "    return child\n",
    "\n",
    "partially_mapped_crossover([1,2,3,4,5,6],[6,5,4,3,2,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "72bf26fe",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[The Palace of Yogyakarta(00:00:00-00:00:00),\n",
       " Jogja T-Shirt Jethe(00:00:00-00:00:00),\n",
       " Mandira Baruga(00:00:00-00:00:00),\n",
       " Situs Gua Seluman(00:00:00-00:00:00),\n",
       " Sermo Reservoir Dam(00:00:00-00:00:00),\n",
       " ALUN ALUN KIDUL YOGYAKARTA(00:00:00-00:00:00),\n",
       " GOLDEN BIOSKOP VIRTUAL REALITY(00:00:00-00:00:00),\n",
       " Bentara Budaya Yogyakarta (BBY)(00:00:00-00:00:00),\n",
       " Klenteng Poncowinatan(00:00:00-00:00:00),\n",
       " Pasar Ngasem(00:00:00-00:00:00),\n",
       " Tarunasura Wijilan Gate(00:00:00-00:00:00),\n",
       " Kampung Wisata Basen(00:00:00-00:00:00),\n",
       " MALIOBORO JOGJAKARTA(00:00:00-00:00:00),\n",
       " Hutan Pinus Pengger(00:00:00-00:00:00),\n",
       " Yogyakarta Northern Square(00:00:00-00:00:00),\n",
       " Desa Wisata Pentingsari(00:00:00-00:00:00),\n",
       " Seribu Batu Songgo Langit(00:00:00-00:00:00),\n",
       " The Lost World Castle(00:00:00-00:00:00),\n",
       " Titik Nol Km Yogyakarta(00:00:00-00:00:00),\n",
       " Bukit Rhema Gereja Ayam(00:00:00-00:00:00),\n",
       " House of Chocolate Monggo & Gelato Tirtodipuran(00:00:00-00:00:00),\n",
       " Makam Panembahan Senopati(00:00:00-00:00:00),\n",
       " Grojogan Watu Purbo Gate(00:00:00-00:00:00),\n",
       " Pakualaman Palace(00:00:00-00:00:00),\n",
       " Bukit Pangol(00:00:00-00:00:00),\n",
       " Jogokariyan Mosque(00:00:00-00:00:00),\n",
       " Bringin Kembar Yogyakarta(00:00:00-00:00:00),\n",
       " Tourism Village Mlangi(00:00:00-00:00:00),\n",
       " Gembira Loka Zoo(00:00:00-00:00:00),\n",
       " Paintball Jupiter Jogja(00:00:00-00:00:00)]"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "866da700",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Roulette Wheel Selection for Elimination\n",
    "def roulette_wheel_selection(population, fitness_values):\n",
    "    total_fitness = sum(fitness_values)\n",
    "    roulette_spin = random.uniform(0, total_fitness)\n",
    "    cumulative_fitness = 0\n",
    "    for i, fitness in enumerate(fitness_values):\n",
    "        cumulative_fitness += fitness\n",
    "        if cumulative_fitness >= roulette_spin:\n",
    "            return population[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "155c2ae2",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[6, 5, 4, 3, 2, 1], [7, 6, 5, 34, 7, 8], [1, 2, 3, 4, 5, 6]]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parents = [roulette_wheel_selection([[1,2,3,4,5,6],[6,5,4,3,2,1],[7,6,5,34,7,8]], [0.7,0.4,0.9]) for _ in range(3)]\n",
    "parents"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "fa264fe1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "for i in range(0, 3, 2):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "c11fb9a5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[7, 6, 5, 34, 7, 8], [7, 6, 5, 34, 7, 8]]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random.choices([[1,2,3,4,5,6],[6,5,4,3,2,1],[7,6,5,34,7,8]],weights=np.array([0.7,0.4,0.9]),k=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "488be8d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6996ea50",
   "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
}
