vrp.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: osmium in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (3.6.0)Note: you may need to restart the kernel to use updated packages.\n",
      "\n",
      "Requirement already satisfied: folium in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (0.14.0)\n",
      "Requirement already satisfied: requests in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (from osmium) (2.28.2)\n",
      "Requirement already satisfied: jinja2>=2.9 in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (from folium) (3.1.2)\n",
      "Requirement already satisfied: numpy in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (from folium) (1.24.2)\n",
      "Requirement already satisfied: branca>=0.6.0 in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (from folium) (0.6.0)\n",
      "Requirement already satisfied: MarkupSafe>=2.0 in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (from jinja2>=2.9->folium) (2.1.2)\n",
      "Requirement already satisfied: idna<4,>=2.5 in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (from requests->osmium) (3.4)\n",
      "Requirement already satisfied: urllib3<1.27,>=1.21.1 in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (from requests->osmium) (1.26.15)\n",
      "Requirement already satisfied: certifi>=2017.4.17 in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (from requests->osmium) (2022.12.7)\n",
      "Requirement already satisfied: charset-normalizer<4,>=2 in c:\\users\\addison\\documents\\github\\vrp_planificacion_inteligente\\addison_env\\lib\\site-packages (from requests->osmium) (3.1.0)\n"
     ]
    }
   ],
   "source": [
    "%pip install osmium folium"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import genetic_algorithms_vin as gav\n",
    "import geographs\n",
    "import folium\n",
    "import random\n",
    "import vrp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Depot_coord = (18.463521, -69.934688) #(18.481891, -69.913954)8299470296\n",
    "qty_clients = 40\n",
    "cap_trucks = 100\n",
    "truck_vel = 60\n",
    "start_time = 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Loading data... \")\n",
    "geoGraph = geographs.GeoGraph(limit_coords=Depot_coord)\n",
    "print(\"Data loaded! \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Depot_node, clients, qty_trucks = vrp.create_nodes(geoGraph, Depot_coord, qty_clients, cap_trucks)\n",
    "\n",
    "print(\"Depot node: \", Depot_node)\n",
    "print(\"qty of trucks: \", qty_trucks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "colors = ['red', 'blue', 'green', 'purple', 'darkblue']\n",
    "depot_color = 'black'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "map = folium.Map(location=Depot_coord, zoom_start=17)\n",
    "\n",
    "for client in clients:\n",
    "    client_node_marker = [client.node.lat, client.node.lon]\n",
    "    folium.Marker(client_node_marker,popup=client.node.name).add_to(map)\n",
    "\n",
    "depot_marker = [Depot_node.lat, Depot_node.lon]\n",
    "folium.Marker(depot_marker,popup=Depot_node.name, icon=folium.Icon(color=depot_color)).add_to(map)\n",
    "\n",
    "map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "qty_poblacion = 200\n",
    "n_elite = 10\n",
    "n_generations = 50\n",
    "prob_de_mut = 0.5\n",
    "\n",
    "create_clusters = vrp.create_clusters(geoGraph, qty_clients, qty_trucks, cap_trucks, qty_poblacion, n_elite, n_generations, clients, prob_de_mut)\n",
    "solution = create_clusters.create_clusters()\n",
    "print(\"solution: \", solution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "map = folium.Map(location=Depot_coord, zoom_start=17)\n",
    "\n",
    "for truck_id in range(qty_trucks):\n",
    "    clients_id = vrp.find_indices(solution, truck_id)\n",
    "    for client_id in clients_id:\n",
    "        client = clients[client_id]\n",
    "        client_node_marker = [client.node.lat, client.node.lon]\n",
    "        folium.Marker(client_node_marker,popup=client.node.name, icon=folium.Icon(color=colors[truck_id])).add_to(map)\n",
    "\n",
    "depot_marker = [Depot_node.lat, Depot_node.lon]\n",
    "folium.Marker(depot_marker,popup=Depot_node.name, icon=folium.Icon(color=depot_color)).add_to(map)\n",
    "\n",
    "map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_nearest_nodes = 4\n",
    "\n",
    "routes, paths = vrp.create_routes(geoGraph, Depot_node, clients, qty_trucks, solution, n_nearest_nodes)\n",
    "\n",
    "print(\"routes: \", routes)\n",
    "for graph in routes:\n",
    "    print(graph.get_nodes())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "map = folium.Map(location=Depot_coord, zoom_start=17)\n",
    "\n",
    "i = 0\n",
    "for route in paths:\n",
    "    for initial_node_name in route:\n",
    "        for goal_node_name in route[initial_node_name]:\n",
    "            \n",
    "            initial_node = routes[i].get_node_by_name(initial_node_name)\n",
    "            goal_node = routes[i].get_node_by_name(goal_node_name)\n",
    "\n",
    "            initial_marker = [initial_node.lat, initial_node.lon]\n",
    "            folium.Marker(initial_marker,popup=initial_node.name, icon=folium.Icon(color=colors[i])).add_to(map)\n",
    "            \n",
    "            goal_marker = [goal_node.lat, goal_node.lon]\n",
    "            folium.Marker(goal_marker,popup=goal_node.name, icon=folium.Icon(color=colors[i])).add_to(map)\n",
    "\n",
    "            path = route[initial_node_name][goal_node_name]\n",
    "            points = []\n",
    "\n",
    "            for node in path:\n",
    "                point = [node.lat, node.lon]\n",
    "                points.append(point)\n",
    "\n",
    "            folium.PolyLine(points, color=colors[i], weight=5, opacity=1).add_to(map)\n",
    "    i+=1\n",
    "\n",
    "depot_marker = [Depot_node.lat, Depot_node.lon]\n",
    "folium.Marker(depot_marker,popup=Depot_node.name, icon=folium.Icon(color=depot_color)).add_to(map)\n",
    "\n",
    "map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "answers = []\n",
    "for route in routes:\n",
    "    SUCCESS = False\n",
    "\n",
    "    while not SUCCESS:\n",
    "        graph = route.get_adj_matrix(Depot_node)\n",
    "\n",
    "        #Params\n",
    "        num_gen = 5000\n",
    "        population_num = 50\n",
    "        solutions_to_choose = 5\n",
    "        mutation_prob = 0.7\n",
    "\n",
    "        cities = list(range(0,len(graph)))\n",
    "        \n",
    "        initial_city = 0\n",
    "\n",
    "        #initial population\n",
    "        solutions = gav.create_population(population_num, cities, initial_city)\n",
    "        #print('Propulation: ', solutions)\n",
    "\n",
    "        best_solutions_by_gen = []\n",
    "\n",
    "        #For each generation\n",
    "        for gen in range(num_gen):\n",
    "\n",
    "            #Calculate the total distance of each solution\n",
    "            distances = gav.calc_distances_paths(graph, initial_city, solutions)\n",
    "            #print(\"distances: \", distances)\n",
    "            \n",
    "            #Calculate the fitness for each solution\n",
    "            fitnesess = gav.calc_fitness(distances)\n",
    "            #print(\"fitnesess: \", fitnesess)\n",
    "\n",
    "            if(sum(fitnesess) == 0):\n",
    "                choosen_solutions = solutions[:solutions_to_choose]\n",
    "            else:\n",
    "                #Choose k solutions randomly based on their fitnesess\n",
    "                choosen_solutions = random.choices(solutions, weights=fitnesess, k=solutions_to_choose)\n",
    "            #print(\"choosen solutions\", choosen_solutions)\n",
    "\n",
    "            #Save the best k solutions of this generation\n",
    "            best_solutions_by_gen.append(choosen_solutions)\n",
    "\n",
    "            #Use best solutions to create a new generation by croosover and mutation (based in mutation_prob)\n",
    "            crossovered_solutions = gav.crossover_solutions(choosen_solutions, population_num)\n",
    "            #print(\"Crossovered_solutions: \", crossovered_solutions)\n",
    "            solutions = gav.mutate_solutions(crossovered_solutions, mutation_prob)\n",
    "            #print(\"Mutated_solutions: \", solutions)\n",
    "\n",
    "        best_solution_by_gen = []\n",
    "\n",
    "        for gen_solutions in best_solutions_by_gen:\n",
    "            distances = gav.calc_distances_paths(graph, initial_city, gen_solutions)\n",
    "            best_solution_of_gen = gav.sort_solutions_by_distance(gen_solutions, distances)[-1]\n",
    "            best_solution_by_gen.append(best_solution_of_gen)\n",
    "\n",
    "        final_answer, cost = sorted(best_solution_by_gen,key=lambda x: x[1])[0]\n",
    "        final_answer.append(initial_city)\n",
    "\n",
    "        print(\"Answer: \", final_answer, cost)\n",
    "        SUCCESS = cost != float('inf')\n",
    "\n",
    "    answers.append(final_answer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "map = folium.Map(location=Depot_coord, zoom_start=17)\n",
    "\n",
    "i = 0\n",
    "for route_graph, route, answer in zip(routes, paths, answers):\n",
    "    nodes_answers = [route_graph.index_to_node[answer_node] for answer_node in answer]\n",
    "\n",
    "    #print(\"Nodes answers: \", nodes_answers)\n",
    "\n",
    "    truck_time = start_time\n",
    "    j = 0\n",
    "\n",
    "    for j in range(len(nodes_answers)-1):\n",
    "        initial_node = routes[i].get_node_by_name(nodes_answers[j])\n",
    "        goal_node = routes[i].get_node_by_name(nodes_answers[j+1])\n",
    "\n",
    "        truck_time += route_graph.get_cost(initial_node, goal_node) / truck_vel\n",
    "        hour = int(truck_time)\n",
    "        minutes = (truck_time % 1) * 60\n",
    "        \n",
    "        goal_marker = [goal_node.lat, goal_node.lon]\n",
    "        goal_popup = f\"{goal_node.name}\\nCamion #{i+1}\\nParada #{j+1}\\nHora de llegada: {hour}:{str(int(minutes)).zfill(2)}\"  \n",
    "        folium.Marker(goal_marker,popup=goal_popup, icon=folium.Icon(color=colors[i])).add_to(map)\n",
    "\n",
    "        #print(\"Initial node: \", initial_node)\n",
    "        #print(\"goal node: \", goal_node)\n",
    "\n",
    "        path = route[initial_node.name][goal_node.name]\n",
    "        points = []\n",
    "\n",
    "        for node in path:\n",
    "            point = [node.lat, node.lon]\n",
    "            points.append(point)\n",
    "\n",
    "        folium.PolyLine(points, color=colors[i], weight=5, opacity=1).add_to(map)\n",
    "\n",
    "    i+=1\n",
    "\n",
    "depot_marker = [Depot_node.lat, Depot_node.lon]\n",
    "depot_popup = f\"Depto, {Depot_node.name} Hora de salida: {start_time}\"\n",
    "folium.Marker(depot_marker, popup=depot_popup, icon=folium.Icon(color=depot_color)).add_to(map)\n",
    "\n",
    "map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for i in range(qty_trucks):\n",
    "    map = folium.Map(location=Depot_coord, zoom_start=17)\n",
    "\n",
    "    route_graph,route, answer = routes[i],paths[i], answers[i]\n",
    "    nodes_answers = [route_graph.index_to_node[answer_node] for answer_node in answer]\n",
    "\n",
    "    #print(\"Nodes answers: \", nodes_answers)\n",
    "\n",
    "    truck_time = start_time\n",
    "    j = 0\n",
    "    \n",
    "    for j in range(len(nodes_answers)-1):\n",
    "        initial_node = routes[i].get_node_by_name(nodes_answers[j])\n",
    "        goal_node = routes[i].get_node_by_name(nodes_answers[j+1])\n",
    "\n",
    "        truck_time += route_graph.get_cost(initial_node, goal_node) / truck_vel\n",
    "        hour = int(truck_time)\n",
    "        minutes = (truck_time % 1) * 60\n",
    "        \n",
    "        goal_marker = [goal_node.lat, goal_node.lon]\n",
    "        goal_popup = f\"{goal_node.name}\\nCamion #{i+1}\\nParada #{j+1}\\nHora de llegada: {hour}:{str(int(minutes)).zfill(2)}\"  \n",
    "        folium.Marker(goal_marker,popup=goal_popup, icon=folium.Icon(color=colors[i])).add_to(map)\n",
    "\n",
    "        #print(\"Initial node: \", initial_node)\n",
    "        #print(\"goal node: \", goal_node)\n",
    "\n",
    "        path = route[initial_node.name][goal_node.name]\n",
    "        points = []\n",
    "\n",
    "        for node in path:\n",
    "            point = [node.lat, node.lon]\n",
    "            points.append(point)\n",
    "\n",
    "        folium.PolyLine(points, color=colors[i], weight=5, opacity=1).add_to(map)\n",
    "\n",
    "    depot_marker = [Depot_node.lat, Depot_node.lon]\n",
    "    depot_popup = f\"Depto, {Depot_node.name} Hora de salida: {start_time}\"\n",
    "    folium.Marker(depot_marker, popup=depot_popup, icon=folium.Icon(color=depot_color)).add_to(map)\n",
    "\n",
    "    display(map)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "addison_env",
   "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.10.9"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}