{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# A Multiagent transportation system\n",
    "\n",
    "Auteur : Philippe Mathieu, [CRISTAL Lab](https://www.cristal.univ-lille.fr/), [SMAC Team](https://www.cristal.univ-lille.fr/?rubrique26&id=7), [University of Lille](http://www.univ-lille1.fr), email : philippe.mathieu@univ-lille.fr\n",
    "\n",
    "Contributeurs : Corwin Fèvre (CRISTAL/SMAC , CRISTAL/OSM)\n",
    "\n",
    "Creation : 15/01/2020\n",
    "\n",
    "\n",
    "## Principe général\n",
    "\n",
    "\n",
    "Cette feuille fait suite à [mas_basics_fr.ipynb](mas_basics_fr.ipynb) qui fournit les bases de la construction d'un système multi-agents sur un reseau social.\n",
    "En s'appuyant sur le même modèle, cette feuille a pour objectif de montrer comment réaliser un système de transport routier et plus précisément modéliser un système de co-voiturage à l'aide d'un système multi-agents.\n",
    "\n",
    "Des passagers avec leurs propres objectifs cherchent à arriver à destination en partant avec des conducteurs qui les \"rapprochent\". Un passager aura sans doute besoin de plusieurs étapes de co-voiturage afin d'arriver à ses fins. Bien évidemment ces différents agents essayent de minimiser les distances parcourues en prenant le chemin le plus court (ce qui n'amène pas forcément au trajet le plus rapide)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import random as random\n",
    "import matplotlib.pyplot as plt\n",
    "import itertools\n",
    "import numpy as np\n",
    "from timeit import default_timer as timer\n",
    "from math import ceil, floor\n",
    "import copy\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## L'environnement : le réseau routier\n",
    "Dans une simulation de trafic, l'environnement est évidemment constitué par le réseau routier. Celui-ci peut être réalisé à un grain plus ou moins fin (route triviale entre 2 points, route avec largeur de voies, inclinaison de la route), et à des échelles plus ou moins précises (une simple route, à une ou plusieurs voies).\n",
    "Dans cette feuille nous nous intéressons à la modélisation d'une pseudo ville, avec des routes bi-directionnelles constituées d'un arc simple entre deux points. En quelque sorte, un graphe de routes, à la manière de Manhattan. \n",
    "Pour cela nous générons à l'aide de la librairie `NetworkX` un graphe de taille fixée (fonction `grid_2d_graph`), sur lequel nous supprimons quelques arrêtes (fonction `remove_edge`) afin que les recherches de plus court chemin aient un intérêt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#fonction permettant de générer un graphe en grille aléatoire avec perturbation d'arête \n",
    "#n indique la taille de la grille initiale (constituée de n^2 noeuds)\n",
    "#coef suppr détermine le coefficient de suppression des arêtes\n",
    "#show précise si on souhaite afficher le graphe ou non\n",
    "def generate_2D_graph(n, coef_suppr=False, show=False):\n",
    "    graph = nx.grid_2d_graph(n, n)  # n x n grid\n",
    "\n",
    "    if coef_suppr != False:\n",
    "        nb_suppr = int(len(list(graph.nodes))*coef_suppr)\n",
    "        random_edge(graph, nb_suppr, delete=True)\n",
    "    pos = nx.spring_layout(graph, iterations=100)\n",
    "\n",
    "    graph.remove_nodes_from(list(nx.isolates(graph)))\n",
    "    graph = graph.to_directed()\n",
    "    \n",
    "    if show:\n",
    "        nx.draw(graph, pos, node_color='b', node_size=20, with_labels=False)\n",
    "        plt.title(\"Road network\")\n",
    "        plt.show()\n",
    "        \n",
    "    return graph\n",
    "\n",
    "#ajoute ou supprime un nombre d'arêtes dans un graphe\n",
    "def random_edge(graph, nb_edges, delete=True):\n",
    "    edges = list(graph.edges)\n",
    "    nonedges = list(nx.non_edges(graph))\n",
    "\n",
    "    # random edge choice\n",
    "    if delete:\n",
    "        # delete chosen edge\n",
    "        chosen_edges = random.sample(edges, nb_edges)\n",
    "        for edge in chosen_edges :\n",
    "            graph.remove_edge(edge[0], edge[1])\n",
    "    # add new edge\n",
    "    else:\n",
    "        chosen_nonedges = random.sample(nonedges, nb_edges)\n",
    "        for non_edge in chosen_nonedges:\n",
    "            graph.add_edge(non_edge[0], non_edge[1])\n",
    "\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = generate_2D_graph(5, coef_suppr=0.2, show=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Les Agents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les agents de notre système disposent toujours d'un identifiant unique `id` et d'un état `alive?` indiquant s'ils sont vivants ou morts. Cet état indique leur activité dans le système : si ils sont vivants, ils sont actifs et\n",
    " interagissent avec leur environnement, sinon ils sont considérés comme sortis du système.\n",
    " Dans ce système de co-voiturage il y a 2 types d'agents:\n",
    " - les conducteurs\n",
    " - les passagers\n",
    " \n",
    " Le conducteur n'est pas très complexe à écrire, il ne fait \"que\" aller à sa destination. Le passager est un peu plus compliqué : quand il perçoit un conducteur, il doit décider s'il monte avec lui ou pas.\n",
    " \n",
    " Quels qu'ils soient, pour simplifier, ils se déplacent de noeud en noeud sur le graphe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Agent:\n",
    "    def __init__(self, id):\n",
    "        self.id = id\n",
    "        self.alive = True\n",
    "    \n",
    "    def update(self) -> None:\n",
    "        pass\n",
    "    \n",
    "    def decide(self) -> None:\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L'agent conducteur\n",
    "Un agent conducteur est caractérisé par un noeud de destination `final`, un trajet à effectuer (succession de positions contiguës qu'il va parcourir) `trip` et un noeud indiquant sa position actuelle `current`.\n",
    "À chaque pas de simulation, il supprime le premier élément de son trajet et met à jour le noeud actuel, simulant ainsi une avancée d'un pas dans son voyage.\n",
    "Son comportement est ici très simple : il avance obligatoirement à chaque pas de simulation d'un noeud du trajet et meurt quand il est arrivé au bout. Sa procédure de décision consiste donc à mettre dans `currrent` le noeud suivant s'il en reste encore."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DriverAgent(Agent):\n",
    "    def __init__(self, id, trip):\n",
    "        super().__init__(id)\n",
    "        self.final = trip[-1]\n",
    "        self.current = trip[0]\n",
    "        self.trip = trip\n",
    "        self.alive = True\n",
    "        \n",
    "    def to_string(self):\n",
    "        print(\"I am driver\",self.id,\"- trip:\",self.trip)\n",
    "        \n",
    "    def update(self) :\n",
    "        pass\n",
    "            \n",
    "    def decide(self) :\n",
    "        if len(self.trip)>1:\n",
    "            old = self.trip.pop(0)\n",
    "            self.current = self.trip[0]\n",
    "            print(\"Driver\",self.id,\"moving from\",old,\"to\",self.current)\n",
    "        else :\n",
    "            self.alive = False\n",
    "            print(\"Driver\",self.id,\"arrived\")         "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant que l'on a un conducteur, on peut simuler l'avancée de ce conducteur dans le graphe défini précédemment : appeler `decide`tant qu'il n'est pas encore arrivé à destination (`alive`). Afin de donner un peu \"d'intelligence\" à nos conducteurs on leur passe toujours le chemin le plus court d'un point à un autre (fonction `shortest_path`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# on récupère 2 noeuds aléatoires dans le graphe\n",
    "n1, n2 = random.sample(list(graph.nodes),2) \n",
    "# on récupère le chemin le plus court entre ces deux noeuds\n",
    "trip = nx.shortest_path(graph, n1, n2)\n",
    "#puis on créer un agent conducteur et on associe ce chemin à son itinéraire\n",
    "d = DriverAgent(0, trip)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d.to_string()\n",
    "#tant que le conducteur n'est pas arrivé à destination\n",
    "while d.alive == True:\n",
    "    #il fait une action\n",
    "    d.decide()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L'agent passager\n",
    "Comme pour l'agent conducteur, un agent passager dispose d'un noeud de départ `start`, d'un noeud d'arrivée `final` et d'un noeud actuel `current`.\n",
    "Son but est de rejoindre son noeud d'arrivée en empruntant le véhicule de conducteurs passant par son noeud, tel un auto-stoppeur. Il n'a donc pas de `trip`. À chaque pas de simulation, il recherchera sur son noeud si il y a un ou plusieurs agents conducteurs lui permettant d'avancer dans son objectif, dans le cas contraire il reste sur son noeud. Quand il arrive à sa position finale, il meurt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RiderAgent(Agent):\n",
    "    def __init__(self, id, start, final, strategy='transition'):\n",
    "        super().__init__(id)\n",
    "        self.start = start\n",
    "        self.current = start\n",
    "        self.final = final\n",
    "        \n",
    "    def to_string(self):\n",
    "        print(\"I am rider\",self.id,\"- dep:\",self.start,\", arr:\",self.final)            \n",
    "            \n",
    "    def update(self):\n",
    "        cur_node = self.current\n",
    "        global agentList\n",
    "        #si il existe au moins un véhicule sur ce noeud actuellement\n",
    "        #alors on s'interroge sur une eventuelle prise en charge\n",
    "        caragent = [agent for agent in agentList if (agent.__class__.__name__ == \"DriverAgent\" and agent.current == self.current and len(agent.trip)>1)]\n",
    "        if len(caragent) > 0:\n",
    "            best_driver = None\n",
    "            for ad in caragent:\n",
    "                next_node = ad.trip[1]\n",
    "                #on effectue la différence de la distance actuelle entre le passager et son noeud d'arrivé\n",
    "                #avec la distance potentielle en empruntant le véhicule.\n",
    "                #Si la valeur est positive, alors le véhicule fait avancer le passager dans son trajet.\n",
    "                contrib = nx.shortest_path_length(graph, source=self.current, target=self.final) - nx.shortest_path_length(graph, source=next_node, target=self.final)\n",
    "                if contrib > 0:\n",
    "                    best_driver = ad\n",
    "                    break\n",
    "            \n",
    "            if best_driver != None :\n",
    "                #le passager le prends et met à jour sa position\n",
    "                new_node = best_driver.trip[1]\n",
    "                print(\"Agent rider\",self.id,\"move from\",self.current,\"to\",new_node,\"using car\",best_driver.id)\n",
    "                #si c'est son arrivée, l'agent meurt\n",
    "                if new_node == self.final:\n",
    "                    print(\"Rider n°\",self.id,\"arrived\")\n",
    "                    self.alive = False\n",
    "                    return\n",
    "            #sinon l'agent ne bouge pas    \n",
    "            else : \n",
    "                print(\"Agent rider\",self.id,\"doesn't move\")\n",
    "                new_node = cur_node\n",
    "            \n",
    "        #sinon l'agent ne bouge pas    \n",
    "        else:\n",
    "            print(\"Agent rider\",self.id,\"doesn't move\")\n",
    "            new_node = cur_node\n",
    "        \n",
    "        self.v_r = new_node\n",
    "        \n",
    "    def decide(self):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut alors créer des agents conducteurs et des agents passagers :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "agentList = []\n",
    "\n",
    "# 10 conducteurs\n",
    "for i in range(10) :\n",
    "    n1, n2 = random.sample(list(graph.nodes),2) \n",
    "    trip = nx.shortest_path(graph, n1, n2)\n",
    "    d = DriverAgent(i, trip)\n",
    "    agentList.append(d)\n",
    "  \n",
    "# 5 passagers\n",
    "for i in range(10,11):\n",
    "    #on récupère 2 noeuds aléatoires dans le graphe\n",
    "    n1, n2 = random.sample(list(graph.nodes),2) \n",
    "    #puis on créer un agent passager avec pour départ et destination ces noeuds\n",
    "    r = RiderAgent(i, n1, n2)\n",
    "    agentList.append(r)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Et les faire évoluer dans notre environnement : Pour tester on prend les agents dans l'ordre de la liste et on continue l'éxécution tant que les conducteurs ne sont pas tous arrivés à destination."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for a in agentList :\n",
    "    a.to_string()\n",
    "    \n",
    "while len([agent for agent in agentList if (agent.__class__.__name__ == \"DriverAgent\")]) > 0:\n",
    "    for a in agentList:\n",
    "        a.update()\n",
    "        a.decide()\n",
    "        \n",
    "    for a in agentList:\n",
    "        if a.alive == False:\n",
    "            agentList.remove(a)\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Le SMA\n",
    "\n",
    "Afin de faire évoluer des ensembles importants d'agents, et cela de manière équitable, on instancie un \"Système Multi-Agents\" qui crée les agents et gère les tours de parole. A chaque \"tour' chaque agent a la parole et décide de ce qu'il veut faire : il est autonome. La méthode `run` prend en paramètre le nombre de tours de paroles. \n",
    "On rappelle que les agents passagers et conducteurs sont considérés `alive` tant qu'ils ne sont pas arrivés à leur destination. Le SMA s'occupe de mettre à jour la liste des agents du système en fonction de leur état. Il s'occupe par ailleurs de stocker les informations macroscopiques à collecter des agents arrivés à destination (temps de trajet etc...)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "class SMA:\n",
    "    def __init__(self, verbose=False):\n",
    "        self.tick=0\n",
    "        self.resetTicks()\n",
    "        self.agentList = []\n",
    "        self.graph = None\n",
    "        self.verbose = verbose\n",
    "        #déclaration variable de la recup des données\n",
    "        self.data = {}\n",
    "\n",
    "    def resetTicks(self):\n",
    "        tick=0\n",
    "          \n",
    "    def setRoadGraph(self,graph):\n",
    "        self.graph = graph\n",
    "        \n",
    "    def addAgent(self,ag):\n",
    "        self.agentList.append(ag)\n",
    " \n",
    "    def run(self,rounds):\n",
    "        #initialisation\n",
    "        self.data[\"mean_travel_time_r\"] = []\n",
    "        \n",
    "        for i in range(0,rounds):\n",
    "            self.runOnce()\n",
    "\n",
    "    def runOnce(self):\n",
    "        self.tick+=1\n",
    "        #random.shuffle(self.agentList)\n",
    "        for ag in self.agentList :\n",
    "            ag.update()\n",
    "            ag.decide()\n",
    "            \n",
    "        for ag in self.agentList:\n",
    "            if ag.alive == False:\n",
    "                #si c'est un agent passager\n",
    "                if ag.__class__.__name__ == \"RiderAgent\":\n",
    "                    #on recupère son temps total d'attente\n",
    "                    self.data[\"mean_travel_time_r\"].append(ag.travel_time)\n",
    "                self.agentList.remove(ag)\n",
    "                \n",
    "        if self.verbose == True:      \n",
    "            print(\"tick \"+str(self.tick)+\" ended\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On réécrit légèrement nos précédents agents afin qu'ils se basent maintenant sur le graphe et la liste des agents du sma."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class RiderAgent(Agent):\n",
    "    def __init__(self, id, start, final, strategy='transition'):\n",
    "        super().__init__(id)\n",
    "        self.start = start\n",
    "        self.current = start\n",
    "        self.final = final\n",
    "        self.travel_time = 0\n",
    "        \n",
    "    def to_string(self):\n",
    "        print(\"I am rider\",self.id,\"- dep:\",self.start,\", arr:\",self.final)\n",
    "                 \n",
    "            \n",
    "    def update(self):\n",
    "        cur_node = self.current\n",
    "        #on retire ici cette ligne\n",
    "        #global agentList\n",
    "       \n",
    "        #ici on modifie en sma.agentList\n",
    "        caragent = [agent for agent in sma.agentList if (agent.__class__.__name__ == \"DriverAgent\" and agent.current == self.current and len(agent.trip)>1)]\n",
    "        if len(caragent) > 0:\n",
    "            best_driver = None\n",
    "            for ad in caragent:\n",
    "                next_node = ad.trip[1]\n",
    "                #ici en sma.graph\n",
    "                contrib = nx.shortest_path_length(sma.graph, source=self.current, target=self.final) - nx.shortest_path_length(sma.graph, source=next_node, target=self.final)\n",
    "                if contrib > 0:\n",
    "                    best_driver = ad\n",
    "                    break\n",
    "            \n",
    "            if best_driver != None :\n",
    "                new_node = best_driver.trip[1]\n",
    "                if sma.verbose == True:\n",
    "                    print(\"Agent rider\",self.id,\"move from\",self.current,\"to\",new_node,\"using car\",best_driver.id)\n",
    "                if new_node == self.final:\n",
    "                    if sma.verbose == True:\n",
    "                        print(\"Rider n°\",self.id,\"arrived\")\n",
    "                    self.alive = False\n",
    "                    return    \n",
    "            else : \n",
    "                if sma.verbose == True:\n",
    "                    print(\"Agent rider\",self.id,\"doesn't move\")\n",
    "                new_node = cur_node\n",
    "               \n",
    "        else:  \n",
    "            if sma.verbose == True:\n",
    "                print(\"Agent rider\",self.id,\"doesn't move\")\n",
    "            new_node = cur_node\n",
    "        \n",
    "        self.current = new_node\n",
    "        self.travel_time += 1\n",
    "        \n",
    "    def decide(self):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DriverAgent(Agent):\n",
    "    def __init__(self, id, trip):\n",
    "        super().__init__(id)\n",
    "        self.final = trip[-1]\n",
    "        self.current = trip[0]\n",
    "        self.trip = trip\n",
    "        \n",
    "    def to_string(self):\n",
    "        print(\"I am driver\",self.id,\"- trip:\",self.trip)\n",
    "        \n",
    "    def update(self) :\n",
    "        pass\n",
    "            \n",
    "    def decide(self) :\n",
    "        if len(self.trip)>1:\n",
    "            old = self.trip.pop(0)\n",
    "            self.current = self.trip[0]\n",
    "            if sma.verbose == True:\n",
    "                print(\"Driver\",self.id,\"moving from\",old,\"to\",self.current)\n",
    "        else :\n",
    "            self.alive = False\n",
    "            if sma.verbose == True:\n",
    "                print(\"Driver\",self.id,\"arrived\")  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut ainsi créer notre SMA, lui associer des passagers et des conducteurs et effectuer 6 runs par exemple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sma = SMA(verbose=True)\n",
    "sma.graph = graph\n",
    "\n",
    "#conducteurs\n",
    "for i in range(5) :\n",
    "    n1, n2 = random.sample(list(sma.graph.nodes),2) \n",
    "    trip = nx.shortest_path(sma.graph, n1, n2)\n",
    "    d = DriverAgent(i, trip)\n",
    "    sma.addAgent(d)\n",
    "  \n",
    "#passagers\n",
    "for i in range(5,10):\n",
    "    n1, n2 = random.sample(list(sma.graph.nodes),2) \n",
    "    r = RiderAgent(i, n1, n2)\n",
    "    sma.addAgent(r)\n",
    "\n",
    "sma.run(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### L'agent générateur de trafic\n",
    "\n",
    "Pour une simulation réaliste, comme les Conducteurs et les Passagers arrivent vite à destination, il est souhaitable d'avoir un flux continu de conducteurs et passagers. On crée pour cela un agent \"générateur de trafic\" qui a pour objectif, d'alimenter en permanence la simulation.\n",
    "On notera que pour la première fois, nous créons ici non seulement un agent qui ne se voit pas, mais qui ne bouge pas non plus. C'est maintenant l'agent `GeneratorAgent` qui va s'occuper de créer les autres agents."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GeneratorAgent(Agent):\n",
    "    def __init__(self, current_id, max_drivers, max_riders, seed=None):\n",
    "        super().__init__(current_id)\n",
    "        self.n_id = current_id+1\n",
    "        self.seed = seed\n",
    "        if self.seed!=None:\n",
    "            random.seed(seed)\n",
    "        \n",
    "        self.max_drivers = max_drivers\n",
    "        self.max_riders = max_riders\n",
    "        \n",
    "    #gestion des id unique    \n",
    "    def next_id(self):\n",
    "        self.n_id += 1\n",
    "        return self.n_id\n",
    "\n",
    "    #genere les agents conducteurs\n",
    "    def driverAgentGenerator(self):\n",
    "        n1, n2 = random.sample(list(sma.graph.nodes),2) \n",
    "        trip = nx.shortest_path(sma.graph, n1, n2)\n",
    "        d = DriverAgent(self.next_id(), trip)\n",
    "        sma.addAgent(d)\n",
    "        \n",
    "    #genere les agents passagers\n",
    "    def riderAgentGenerator(self):\n",
    "        n1, n2 = random.sample(list(sma.graph.nodes),2) \n",
    "        r = RiderAgent(self.next_id(), n1, n2)\n",
    "        sma.addAgent(r)\n",
    "        \n",
    "    def update(self):\n",
    "        \n",
    "        #on récupère le nombre d'agents dans le système\n",
    "        nb_drivers = len([agent for agent in sma.agentList if (agent.__class__.__name__ == \"DriverAgent\")])\n",
    "        nb_riders = len([agent for agent in sma.agentList if (agent.__class__.__name__ == \"RiderAgent\")])\n",
    "        \n",
    "        #puis on complète par rapport au nombre maximal fixé\n",
    "        driver_difference = self.max_drivers - nb_drivers\n",
    "        rider_difference = self.max_riders - nb_riders\n",
    "        \n",
    "        for i in range(driver_difference):\n",
    "            self.driverAgentGenerator()\n",
    "        if sma.verbose == True:\n",
    "            print(driver_difference,\"drivers generated.\")\n",
    "            \n",
    "        for i in range(rider_difference):\n",
    "            self.riderAgentGenerator()\n",
    "        if sma.verbose == True:\n",
    "            print(rider_difference,\"riders generated.\") \n",
    "        \n",
    "    def decide(self):\n",
    "        pass\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On définit maintenant les paramètres de notre simulation à l'aide de 4 variables:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SIZE_MAP = 5 #graphe en grille donc 5x5 noeuds\n",
    "MAX_NB_DRIVERS = 20\n",
    "MAX_NB_RIDERS = 10\n",
    "NB_RUN = 200"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "puis on lance le SMA !"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sma = SMA()\n",
    "sma.setRoadGraph(generate_2D_graph(SIZE_MAP, coef_suppr=0.1, show=True))\n",
    "sma.addAgent(GeneratorAgent(0,MAX_NB_DRIVERS,MAX_NB_RIDERS))\n",
    "sma.run(NB_RUN)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Temps moyen de trajet des passagers arrivés a destination:\", np.mean(sma.data[\"mean_travel_time_r\"]),\"tours de paroles\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Expérimentations et Résultats\n",
    "Nous avons défini le coeur de notre simulateur de trafic, il s'agit maintenant de mettre en place des indicateurs afin de déterminer si une configuration est meilleure qu'une autre et pourquoi.\n",
    "\n",
    "### Le temps de trajet :\n",
    "On peut émettre une hypothèse simple : plus il y a de véhicules disponibles, plus il y a de possibilités d'acheminement pour les passagers et donc ces derniers arrivent vite à destination. En conséquence, le temps moyen de trajet des agents passagers devrait décroître en fonction du nombre d'agents conducteurs.\n",
    "\n",
    "Pour démontrer simplement ce cas de figure, il est necessaire d'effectuer plusieurs simulations avec le même réseau routier, le même nombre de passagers mais en faisant varier le nombre de conducteurs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SIZE_MAP = 5\n",
    "MAX_NB_DRIVERS = np.arange(5,50,3)\n",
    "MAX_NB_RIDERS = 20\n",
    "NB_RUN = 200"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mean_travel_time_per_d = []\n",
    "graph = generate_2D_graph(SIZE_MAP, coef_suppr=0.1, show=True)\n",
    "\n",
    "\n",
    "for nb_d in MAX_NB_DRIVERS :\n",
    "    sma = SMA()\n",
    "    sma.setRoadGraph(graph)\n",
    "    sma.addAgent(GeneratorAgent(0,nb_d,MAX_NB_RIDERS, seed=42))\n",
    "    sma.run(NB_RUN)\n",
    "    mean_travel_time_per_d.append(np.mean(sma.data[\"mean_travel_time_r\"]))\n",
    "    \n",
    "f = plt.figure(figsize=(15, 5))\n",
    "plt.plot(MAX_NB_DRIVERS,mean_travel_time_per_d)\n",
    "plt.xlabel('Max number of drivers')\n",
    "plt.ylabel(\"Mean travel time of riders (ticks)\")\n",
    "#plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Même expérience mais avec un réseau routier plus important :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SIZE_MAP = 15\n",
    "MAX_NB_DRIVERS = np.arange(5,200,20)\n",
    "MAX_NB_RIDERS = 20\n",
    "NB_RUN = 200\n",
    "\n",
    "mean_travel_time_per_d = []\n",
    "graph = generate_2D_graph(SIZE_MAP, coef_suppr=0.1, show=True)\n",
    "\n",
    "\n",
    "for nb_d in MAX_NB_DRIVERS :\n",
    "    sma = SMA()\n",
    "    sma.setRoadGraph(graph)\n",
    "    sma.addAgent(GeneratorAgent(0,nb_d,MAX_NB_RIDERS, seed=42))\n",
    "    sma.run(NB_RUN)\n",
    "    mean_travel_time_per_d.append(np.mean(sma.data[\"mean_travel_time_r\"]))\n",
    "    \n",
    "f = plt.figure(figsize=(15, 5))\n",
    "plt.plot(MAX_NB_DRIVERS,mean_travel_time_per_d)\n",
    "plt.xlabel('Max number of drivers')\n",
    "plt.ylabel(\"Mean travel time of riders (ticks)\")\n",
    "#plt.legend()\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercices\n",
    "\n",
    "1. Ajouter des indicateurs (le temps d'attente, le taux de service, le nombre de transfert par exemple). Tracer une courbe pour chacun de ces indicateurs : un indicateur brut en fonction du temps (le nombre de transferts cumulé) et un indicateur agrégé (le temps d'attente cumulé par rapport au temps d'attente moyen).\n",
    "2. Faire varier le nombre de conducteurs et le nombre de nœuds, montrer l'impact de ces paramètres sur les performances.\n",
    "3. Proposer une meilleure stratégie (ou alternative) que la stratégie naïve :\n",
    "    1. Modéliser une perception (prise en compte limitée de l'environnement)\n",
    "    2. Modéliser des comportements ?\n",
    "    3. Constater avec les indicateurs les + et les - (petit point sur la complexité).\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bibliographie\n",
    "\n",
    "- Agatz, N., Erera, A. L., Savelsbergh, M. W., and Wang, X. (2011). Dynamic ride-sharing: a simulation study in metro atlanta. Procedia - Social and Behavioral Sciences, 17:532–550.\n",
    "- Fèvre Corwin, Hayfa Zgaya-Biau, Philippe Mathieu, Slim Hammadi, Multi-agent Systems and R-Trees for Dynamic and Optimised Ridesharing. IEEE International Conference on Systems, Man, and Cybernetics, Oct 2021, Melbourne, Australia. pp.1352--1358\n",
    "- Philippe Mathieu, Antoine Nongaillard. Effective evaluation of autonomous taxi fleets\n",
    "ICAART 2018 - 10th International Conference on Agents and Artificial Intelligence, Jan 2018, Funchal, Portugal \n",
    "- Antoine Nongaillard, Philippe Mathieu. L'évaluation efficace de flottes de taxis autonomes\n",
    "Journées Francophones sur les Systèmes Multi-Agents (JFSMA 2017), Jul 2017, Caen, France \n",
    "- Alexandre Bonhomme, Philippe Mathieu, Sébastien Picault. A Versatile MultiAgent Traffic Simulator Framework Based on Real Data. International Journal on Artificial Intelligence Tools (IJAIT), 2016, Special Issue on 26th IEEE International Conference on Tools with Artificial Intelligence (ICTAI-2014), 25 (1), pp.20.\n"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Format de la Cellule Texte Brut",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}