example_placement_of_charging_stations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "56f0b47e",
   "metadata": {},
   "source": [
    "# Example: Placement of Charging Stations"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d8cd7b01",
   "metadata": {},
   "source": [
    "Determining optimal locations to build new electric vehicle charging stations is a complex optimization problem. Many factors should be taken into consideration, like existing charger locations, points of interest (POIs), quantity to build, etc. In this example, we take a look at how we might formulate this optimization problem and solve it using the Dynex Neuromorphic Platform."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af01a808",
   "metadata": {},
   "source": [
    "## Problem Formulation"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b86bbd3d",
   "metadata": {},
   "source": [
    "There are many different variations of the electric vehicle charger placement problem that might be considered. For this demo, we examine the case in which a small region is under consideration, and all locations in our area of consideration are within walking distance. In this situation, we want to place new charging locations that are convenient to all POIs. For example, if the POIs are shops on a main street it is most convenient to park once in a central location. We will satisfy this need by considering the average distance from a potential new charging location all POIs. Additionally, we want to place new chargers away from existing and other new charging locations so as to minimize overlap and maximize coverage of the region.\n",
    "\n",
    "This problem can be considered as a set of 4 independent constraints (or objectives) with binary variables that represent each potential new charging station location."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5462db6e",
   "metadata": {},
   "source": [
    "## Minimize distance to POIs "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "85a3a5f7",
   "metadata": {},
   "source": [
    "For each potential new charging station location, we compute the average distance to all POIs on the map. Using this value as a linear bias on each binary variable, our program will prefer locations that are (on average) close to the POIs. Note that this constraint could be replaced by an alternative one depending on the real world scenario for this problem."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81e01b57",
   "metadata": {},
   "source": [
    "## Maximize distance to existing charging stations "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76c9ebec",
   "metadata": {},
   "source": [
    "For each potential new charging station location, we compute the average distance to all existing charging locations on the map. Using the negative of this value as a linear bias on each binary variable, our program will prefer locations that are (on average) far from existing chargers."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ddbc439f",
   "metadata": {},
   "source": [
    "## Maximize distance to other new charging stations "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "82bf3b88",
   "metadata": {},
   "source": [
    "For the pair of new charging station locations, we would like to maximize the distance between them. To do this, we consider all possible pairs of locations and compute the distance between them. Using the negative of this value as a quadratic bias on the product of the corresponding binary variables, our program will prefer locations that are far apart."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8f3e471",
   "metadata": {},
   "source": [
    "## Build exactly two new charging stations "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b41da02a",
   "metadata": {},
   "source": [
    "To select exactly two new charging stations, we use dimod.generators.combinations. This function in dimod's package sets exactly num_new_cs of our binary variables (bqm.variables) to have a value of 1, and applies a strength to this constraint (gamma4). See below for more information on the tunable strength parameter."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7172487a",
   "metadata": {},
   "source": [
    "## Parameter tuning "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a60ffbe",
   "metadata": {},
   "source": [
    "Each of these constraints is built into our BQM object with a coefficient (names all start with gamma). This term gamma is known as a Lagrange parameter and can be used to weight the constraints against each other to accurately reflect the requirements of the problem. You may wish to adjust this parameter depending on your problem requirements and size. The value set here in this program was chosen to empirically work well as a starting point for problems of a wide-variety of sizes. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "538b8380",
   "metadata": {},
   "source": [
    "# Implementation "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a08e9c86",
   "metadata": {},
   "source": [
    "First, we load the required packages:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "0f9a8b92",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product\n",
    "import json\n",
    "import random \n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import networkx as nx\n",
    "import matplotlib\n",
    "import matplotlib.pyplot as plt\n",
    "import dynex\n",
    "import dimod"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cdc6761b",
   "metadata": {},
   "source": [
    "We create a few helper functions to set up the scenario given the width and height of the grid as well as the number of points of intersts and existing number of charging stations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "d3b9d980",
   "metadata": {},
   "outputs": [],
   "source": [
    "def set_up_scenario(w, h, num_poi, num_cs):\n",
    "    \"\"\"Build scenario set up with specified parameters.\n",
    "    \n",
    "    Args:\n",
    "        w (int): Width of grid\n",
    "        h (int): Height of grid\n",
    "        num_poi (int): Number of points of interest\n",
    "        num_cs (int): Number of existing charging stations\n",
    "    \n",
    "    Returns:\n",
    "        G (networkx graph): Grid graph of size w by h\n",
    "        pois (list of tuples of ints): A fixed set of points of interest\n",
    "        charging_stations (list of tuples of ints): \n",
    "            Set of current charging locations\n",
    "        potential_new_cs_nodes (list of tuples of ints): \n",
    "            Potential new charging locations\n",
    "    \"\"\"\n",
    "\n",
    "    G = nx.grid_2d_graph(w, h)\n",
    "    nodes = list(G.nodes)\n",
    "\n",
    "    # Identify a fixed set of points of interest\n",
    "    pois = random.sample(nodes, k=num_poi)\n",
    "\n",
    "    # Identify a fixed set of current charging locations\n",
    "    charging_stations = random.sample(nodes, k=num_cs)\n",
    "\n",
    "    # Identify potential new charging locations\n",
    "    potential_new_cs_nodes = list(G.nodes() - charging_stations)\n",
    "\n",
    "    return G, pois, charging_stations, potential_new_cs_nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34f452ad",
   "metadata": {},
   "source": [
    "The distance function returns the distance between two coordinates:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "50f21d9b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(a, b):\n",
    "    return (a[0]**2 - 2*a[0]*b[0] + b[0]**2) + (a[1]**2 - 2*a[1]*b[1] + b[1]**2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "789e1ead",
   "metadata": {},
   "source": [
    "The following function builds a binary quadratic model (bqm) from our problem scenario:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "af54583d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_bqm(potential_new_cs_nodes, num_poi, pois, num_cs, charging_stations, num_new_cs):\n",
    "    \"\"\"Build bqm that models our problem scenario. \n",
    "\n",
    "    Args:\n",
    "        potential_new_cs_nodes (list of tuples of ints):\n",
    "            Potential new charging locations\n",
    "        num_poi (int): Number of points of interest\n",
    "        pois (list of tuples of ints): A fixed set of points of interest\n",
    "        num_cs (int): Number of existing charging stations\n",
    "        charging_stations (list of tuples of ints): \n",
    "            Set of current charging locations\n",
    "        num_new_cs (int): Number of new charging stations desired\n",
    "    \n",
    "    Returns:\n",
    "        bqm_np (BinaryQuadraticModel): QUBO model for the input scenario\n",
    "    \"\"\"\n",
    "\n",
    "    # Tunable parameters\n",
    "    gamma1 = len(potential_new_cs_nodes) * 4\n",
    "    gamma2 = len(potential_new_cs_nodes) / 3\n",
    "    gamma3 = len(potential_new_cs_nodes) * 1.7\n",
    "    gamma4 = len(potential_new_cs_nodes) ** 3\n",
    "\n",
    "    # Build BQM using adjVectors to find best new charging location s.t. min\n",
    "    # distance to POIs and max distance to existing charging locations\n",
    "    bqm = dimod.BinaryQuadraticModel(len(potential_new_cs_nodes), 'BINARY')\n",
    "\n",
    "    # Constraint 1: Min average distance to POIs\n",
    "    if num_poi > 0:\n",
    "        for i in range(len(potential_new_cs_nodes)):\n",
    "            # Compute average distance to POIs from this node\n",
    "            cand_loc = potential_new_cs_nodes[i]\n",
    "            avg_dist = sum(distance(cand_loc, loc) for loc in pois) / num_poi\n",
    "            bqm.linear[i] += avg_dist * gamma1\n",
    "\n",
    "    # Constraint 2: Max distance to existing chargers\n",
    "    if num_cs > 0:\n",
    "        for i in range(len(potential_new_cs_nodes)):\n",
    "            # Compute average distance to POIs from this node\n",
    "            cand_loc = potential_new_cs_nodes[i]\n",
    "            avg_dist = -sum(distance(cand_loc, loc)\n",
    "                            for loc in charging_stations) / num_cs\n",
    "            bqm.linear[i] += avg_dist * gamma2\n",
    "\n",
    "    # Constraint 3: Max distance to other new charging locations\n",
    "    if num_new_cs > 1:\n",
    "        for i in range(len(potential_new_cs_nodes)):\n",
    "            for j in range(i+1, len(potential_new_cs_nodes)):\n",
    "                ai = potential_new_cs_nodes[i]\n",
    "                aj = potential_new_cs_nodes[j]\n",
    "                dist = -distance(ai, aj)\n",
    "                bqm.add_interaction(i, j, dist * gamma3)\n",
    "\n",
    "    # Constraint 4: Choose exactly num_new_cs new charging locations\n",
    "    bqm.update(dimod.generators.combinations(bqm.variables, num_new_cs, strength=gamma4))\n",
    "\n",
    "    return bqm"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cd1f8e51",
   "metadata": {},
   "source": [
    "Next we define a function to retrieve the results in the terminal output:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "719805a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def printout_solution_to_cmdline(pois, num_poi, charging_stations, num_cs, new_charging_nodes, num_new_cs):\n",
    "    \"\"\"Print solution statistics to command line.\n",
    "    \n",
    "    Args:\n",
    "        pois (list of tuples of ints): A fixed set of points of interest\n",
    "        num_poi (int): Number of points of interest\n",
    "        charging_stations (list of tuples of ints): \n",
    "            A fixed set of current charging locations\n",
    "        num_cs (int): Number of existing charging stations\n",
    "        new_charging_nodes (list of tuples of ints): \n",
    "            Locations of new charging stations\n",
    "        num_new_cs (int): Number of new charging stations desired\n",
    "    \n",
    "    Returns:\n",
    "        None.\n",
    "    \"\"\"\n",
    "\n",
    "    print(\"\\nSolution returned: \\n------------------\")\n",
    "\n",
    "    print(\"\\nNew charging locations:\\t\\t\\t\\t\", new_charging_nodes)\n",
    "\n",
    "    if num_poi > 0:\n",
    "        poi_avg_dist = [0] * len(new_charging_nodes)\n",
    "        for loc in pois:\n",
    "            for i, new in enumerate(new_charging_nodes):\n",
    "                poi_avg_dist[i] += sum(abs(a - b) for a, b in zip(new, loc)) / num_poi\n",
    "        print(\"Average distance to POIs:\\t\\t\\t\", poi_avg_dist)\n",
    "\n",
    "    if num_cs > 0:\n",
    "        old_cs_avg_dist = [sum(abs(a - b) for a, b in zip(new, loc) for loc in charging_stations) / num_cs for new in new_charging_nodes]\n",
    "        print(\"Average distance to old charging stations:\\t\", old_cs_avg_dist)\n",
    "\n",
    "    if num_new_cs > 1:\n",
    "        new_cs_dist = 0\n",
    "        for i in range(num_new_cs):\n",
    "            for j in range(i+1, num_new_cs):\n",
    "                new_cs_dist += abs(new_charging_nodes[i][0]-new_charging_nodes[j][0])+abs(new_charging_nodes[i][1]-new_charging_nodes[j][1])\n",
    "        print(\"Distance between new chargers:\\t\\t\\t\", new_cs_dist)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2bbd8bd0",
   "metadata": {},
   "source": [
    "We also want to create an output image of the solution scenario. Black nodes represent available space, red nodes the current charger locations, nodes marked \"P\" the Point of Interest (POI) locations and finally blue nodes the new charger locations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e6e5ec4b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def save_output_image(G, pois, charging_stations, new_charging_nodes):\n",
    "    \"\"\" Create output image of solution scenario.\n",
    "            - Black nodes: available space\n",
    "            - Red nodes: current charger location\n",
    "            - Nodes marked 'P': POI locations\n",
    "            - Blue nodes: new charger locations\n",
    "\n",
    "    Args:\n",
    "        G (networkx graph): Grid graph of size w by h\n",
    "        pois (list of tuples of ints): A fixed set of points of interest\n",
    "        charging_stations (list of tuples of ints): \n",
    "            A fixed set of current charging locations\n",
    "        new_charging_nodes (list of tuples of ints): \n",
    "            Locations of new charging stations\n",
    "    \n",
    "    Returns:\n",
    "        None. Output saved to file \"map.png\".\n",
    "    \"\"\"\n",
    "\n",
    "    fig, (ax1, ax2) = plt.subplots(1, 2)\n",
    "    fig.suptitle('New EV Charger Locations')\n",
    "    pos = {x: [x[0],x[1]] for x in G.nodes()}\n",
    "\n",
    "    # Locate POIs in map\n",
    "    poi_graph = G.subgraph(pois)\n",
    "    poi_labels = {x: 'P' for x in poi_graph.nodes()}\n",
    "\n",
    "    # Locate old charging stations in map\n",
    "    cs_graph = G.subgraph(charging_stations)\n",
    "\n",
    "    # Locate old charging stations at POIs in map\n",
    "    poi_cs_list = set(pois) - (set(pois)-set(charging_stations))\n",
    "    poi_cs_graph = G.subgraph(poi_cs_list)\n",
    "    poi_cs_labels = {x: 'P' for x in poi_graph.nodes()}\n",
    "\n",
    "    # Draw old map (left image)\n",
    "    nx.draw_networkx(G, ax=ax1, pos=pos, with_labels=False, node_color='k', font_color='w')\n",
    "    nx.draw_networkx(poi_graph, ax=ax1, pos=pos, with_labels=True,\n",
    "                        labels=poi_labels, node_color='k', font_color='w')\n",
    "    nx.draw_networkx(cs_graph, ax=ax1, pos=pos, with_labels=False, node_color='r',\n",
    "                        font_color='k')\n",
    "    nx.draw_networkx(poi_cs_graph, ax=ax1, pos=pos, with_labels=True,\n",
    "                        labels=poi_cs_labels, node_color='r', font_color='w')\n",
    "\n",
    "    # Draw new map (right image)\n",
    "    new_cs_graph = G.subgraph(new_charging_nodes)\n",
    "    nx.draw_networkx(G, ax=ax2, pos=pos, with_labels=False, node_color='k',\n",
    "                        font_color='w')\n",
    "    nx.draw_networkx(poi_graph, ax=ax2, pos=pos, with_labels=True,\n",
    "                        labels=poi_labels,node_color='k', font_color='w')\n",
    "    nx.draw_networkx(cs_graph, ax=ax2, pos=pos, with_labels=False, node_color='r',\n",
    "                        font_color='k')\n",
    "    nx.draw_networkx(poi_cs_graph, ax=ax2, pos=pos, with_labels=True,\n",
    "                        labels=poi_cs_labels,  node_color='r', font_color='w')\n",
    "    nx.draw_networkx(new_cs_graph, ax=ax2, pos=pos, with_labels=False,\n",
    "                        node_color='#00b4d9', font_color='w')\n",
    "\n",
    "    # Save image\n",
    "    plt.savefig(\"map.png\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb637036",
   "metadata": {},
   "source": [
    "## Setting the Parameters"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "84445343",
   "metadata": {},
   "source": [
    "In our example we define a grid with the dimensions 15 x 15 and three Points of Interest (POI). We also place four existing charging stations and want to determine two new charging stations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "5932c423",
   "metadata": {},
   "outputs": [],
   "source": [
    "w = 15 # width of grid\n",
    "h = 15 # height of grid\n",
    "num_poi = 3 # number of points of interest\n",
    "num_cs = 4 # number of existing charging stations\n",
    "num_new_cs = 2 # number of new charging stations to be placed"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "966badba",
   "metadata": {},
   "source": [
    "Then be build the large grid graph for the city:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "3906fc5f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Build large grid graph for city\n",
    "G, pois, charging_stations, potential_new_cs_nodes = set_up_scenario(w, h, num_poi, num_cs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e4abb4de",
   "metadata": {},
   "source": [
    "And call the function to build the BQM:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "27f5237e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Build BQM\n",
    "bqm = build_bqm(potential_new_cs_nodes, num_poi, pois, num_cs, charging_stations, num_new_cs)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "813ee6dd",
   "metadata": {},
   "source": [
    "To run the BQM on the Dynex Neuromorphic Computing Platform, we create the Dynex Sampler:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "4208a5e2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[DYNEX] MODEL CONVERTED TO QUBO\n",
      "[ÐYNEX] PRECISION CUT FROM 1000.0 TO 1\n",
      "[DYNEX] PRECISION SET TO 1\n",
      "[DYNEX] QUBO: Constant offset of the binary quadratic model: 43175444.0\n"
     ]
    }
   ],
   "source": [
    "# run on Dynex:\n",
    "model = dynex.BQM(bqm);\n",
    "sampler = dynex.DynexSampler(model);"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e09041b8",
   "metadata": {},
   "source": [
    "We submit the model to the Dynex platform and specify that we want to read from 1024 Dynex chips after an annealing time of 100 integration steps:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "a3559fc9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[DYNEX|508] 0.29s #workers: 1 #chips: 1024 #steps: 100 global falsified softs: 220 global energy: 7097678632.0\n",
      "[DYNEX] FINISHED READ AFTER 0.29 SECONDS\n",
      "[DYNEX] SAMPLESET LOADED\n",
      "[DYNEX] MALLOB: JOB UPDATED: 508\n"
     ]
    }
   ],
   "source": [
    "sampleset = sampler.sample(num_reads=1024, annealing_time = 100);\n",
    "ss = sampler.dimod_assignments.first.sample;"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "854e9bc1",
   "metadata": {},
   "source": [
    "The sample with the lowest energy is captured in variable 'ss', which we now apply:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "b128ff6d",
   "metadata": {},
   "outputs": [],
   "source": [
    "new_charging_nodes = [potential_new_cs_nodes[k] for k, v in ss.items() if v == 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "03500f12",
   "metadata": {},
   "source": [
    "We print and plot the results for the new charging stations to be placed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "0435aa14",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Solution returned: \n",
      "------------------\n",
      "\n",
      "New charging locations:\t\t\t\t [(11, 5), (3, 8)]\n",
      "Average distance to POIs:\t\t\t [9.666666666666666, 10.0]\n",
      "Average distance to old charging stations:\t [10.0, 15.0]\n",
      "Distance between new chargers:\t\t\t 11\n"
     ]
    }
   ],
   "source": [
    "# Print results to commnand-line for user\n",
    "printout_solution_to_cmdline(pois, num_poi, charging_stations, num_cs, new_charging_nodes, num_new_cs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "9108a069",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAAEECAYAAACLCeeIAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAeLklEQVR4nO3df3Ac533f8fcXJE84UBJJGWRbVT9o1opKSWAcEVCk6aRqIjcxPTVtMFWiVL9oSTbjOnVaC6wEN2nipO2JKZiJMx0ktquUlDITuRIlhnXJqpanotxSKgGxDimZEcm0ouyqFkiJIEXiKAHE0z92YR1B3OF2cbf77N7nNfMd4u52954Dvnywt7f7gTnnEBGRZLSlPQARkVaiSVdEJEGadEVEEqRJV0QkQZp0RUQSpElXRCRBmnSl4czsdTP7WNrjyAoz22Vm96Y9DkmGJt0EhZPRiJktrLjvATN7PoHnLZvZ6Yr6d2Z2s5mdMbOLZ1jnf5nZr1XZ3qVm9gdm9ka4rb8Kb3c283U0g5ktNzNnZvMTer7fNrM/rbzPObfGObc1ieeX9GnSTd484NdTeN5POucurqhfc869BPwQ+IeVC5rZDcB1wJ9N34iZFYDvANcDHwcuBW4B3gZuauSALdCwHk1qYhWpRZNu8v4t0Gdmi2d60Mz+tpl928zeMbPXzOyXwvs/bGajU5OQmX3DzEYq1nvczP5pjPFsBe6Zdt89wE7n3NszLH8PcBXQ65z7vnNu0jk34pz7XefczorlPmpm+83spJl908zaw3EuMbNvmdkxMzsRfn1Fxet43sz+tZn9D2AMWGFmPx9+L06a2aCZ7TazByrWuc/MDobbe9bMrq54zJnZF8zsMHA4yjfGzC43sx3hz+KImX224rF5ZvblcC//XTN72cyuDB/7qpn9wMxOhff/THj/x4EvA78cvkP4i4rX/ED4dZuZ/YaZHQ3fFT1mZovCx6b2yu8N32UcN7N/UTGmm8xsOHzet8zs96O8XkmIc06VUAGvAx8Dngb+VXjfA8Dz4dcLgR8AnwHmAz8FHAeuCx9/A1gdfv0a8L+BlRWP/VSt563y2JXABHBleLuNYO/301WWfwLYWsfr3AtcDlwGHAR+NXzsQ8AvAh3AJcCTwPaKdZ8PX8v14fdgKXAKWBfe/nVgHHggXP5TwBFgZfj4bwB7KrbngG+H4yjOMNbl4TLzZ3jsBWAQaAc+ChwDfi58bCNwALgWMOAngQ+Fj90Vvs75wIPAj4D28LHfBv502vM8X/F67gtfzwrg4rBXHp821m8AxfA536vogReBu8OvLwZuTrvnVTP8/0h7AK1UfDDp3gCcDCeUykn3l4HvTlvna8BvhV8/DnwJ+OsEk+7vAb8KfBgYBdpqPO/pcJmp+mzF488BXw6//vvh5LKgyra+DTxSx+u8q+L27wF/XGXZjwInKm4/D/xOxe17gBcrbhvBL6apSWoXcH/F420Ee8hXh7fd1ERZ5fmnJrL50+6/EjgHXFJxXwnYEn79GvCpOn/uJ4CfDL+ebdL9DvCPKx67luCXzPyKsV5R8fhe4I7w6xeArwCdafe6qnrp8EIKnHOvAN8CHp720NXAT4eHEUbNbBS4k2CSBdgN/D3g7xL8B3seuDWs7zrnJms87aedc4sr6hsVj20F7g6/vht4wjk3XmU7bwN/Y/ZXyY8qvh4j2PPCzDrM7Gvh2+dT4etYbGbzKpb/QcXXl1fedsHs8sOKx68Gvlrx/XqHYGL+m1W2V6/LgXecc+9W3He0YrtXAn8104pm1hce7jgZjmkRUO+HjJeHz1P5nPOBv1Zx34zfW+B+4CeAvzSzITP7B3U+pyRIk256fgv4LBdODrunTY4XO+c+Hz6+G/gZgol3N/Dfgb9DMOnunsNYngauMLOfJXgbX+uT9OeAX7CKMzAiepBg7+2nnXOXEvwCgWCinFIZfff/gMpjvlZ5m+B7tmHa96zonNtTZXv1ehO4zMwuqbjvKuD/Vjzv35q+Unj89p8DvwQscc4tJnhXM/X6ZhvLmwS/SCqfcwJ4a7YBO+cOO+d+BVgGbAKemsPPSZpEk25KnHNHgG8CX6y4+1vAT5jZ3Wa2IKweM1sZrnMYKBMcM9ztnDtF8J/xF5nDpOucOwM8BfwH4KhzbrjG4o8TTDjbwg/92szsQ+GHSp+o4+kuCV/DqJldRvDLp5b/DHSZ2afDsw++wAd7/gB/DPSb2fUAZrbIzG6vYxzTXWRm7VNFMLnuAUrhfasI9iSnTvf698Dvmtk1FlhlZh8KX98EwSGa+Wb2LwnO8JjyFrDcqp+V8WfAP7Pgg9OLgX8DfNM5NzHbCzCzu8xsafiOZzS8u9a7H0mBJt10/Q7Bh2cAhG9lfx64g2CP50cEeywXVayzG3jbOfeDitsG7Jvluf6TnX+e7jPTHt9KsIf1WK2NOOfeIzgu/ZcEx3dPERxX7AT+5yxjAPgDgg+BjgMvAf9lluc7DtxOcFz4bYJT2YYJPkDCOfcMwffoifBwxSvAmjrGMd1pgl8GU/VzwK8QHEd9E3iG4Nj6c+Hyvw/8R+C/EnwPHg1f17PhazpEcGjgLOcf3ngy/PdtM5vpZ/YnBL/YXgD+T7j+P6nzNXwceNXMTgNfJTjWW65zXUmIBYfIRLIh3EP8IXCnc+6/pT0ekai0pyveM7NfMLPFZnYRwXmuRrCXLJI5mnQlC24hOFPgOPBJgjMx9LZZMkmHF0REEqQ9XRGRBGnSFRFJkCZdEZEEadIVEUmQJl0RkQRp0hURSZAmXRGRBGnSFRFJkCZdEZEEadIVEUmQJl0RkQRp0hURSZAmXRGRBGnSFRFJ0PxaD3Z2drrly5cnNBRpNS+//PJx59zSNJ5bvS3NVKu3a066y5cvZ3i41t8oFInPzI7OvlRzqLelmWr1tg4viIgkSJOuiEiCNOmKiCRIk66ISII06YqIJEiTrohIgjTpiogkSJOuiEiCal4cUa+RkRG2bNnC/v37OXnyJIsWLWLVqlV85jOfYenSpVrGs2VeffVVNm7cyMGDBxkbG6Ojo4OVK1eyefNmVq5c2dDnyjrffnZaJvu9bc65qg92d3e7WlftDA0NUSqV2LVrFwBnz5798WPFYhHnHDfffDMAL730kpZJeZnrrruON954g+PHj1NNZ2cnV111Fd///vfn9Fxr1qyhv7+fnp6eqs9lZi8757qrLtBE6u18LZOp3nbOVa3Vq1e7agYHB11HR4czMweoVOeVmbmOjg43ODhYtYeA4Vr918xSb6vi1lx7O1ZjTjVl2i9e5X/Vak48nHTV26p6K25vR27MvXv3qilzUOPj425yctJNTk66iYkJd/jwYbds2bKmPFdHR4cbGhryftJVb2e/kuxriNfbkc9eKJVKlMvlqKuJhx566CHa2tq46aabuOKKK9i+fXtTnqdcLlMqlZqy7UZSb+dDUn0N8Xo70qQ7MjLCrl27gl1kyY19+/axf/9+VqxY0ZTtO+fYuXMnx44da8r2G0G9nT/N7muI19uRJt0tW7ZEHZNkQE9PD6tWreLQoUNNew4z87p/fB6bxJNEX0P03o406e7fv/+8Uygk2zZt2sTk5CR79uzhyJEjrF27tmnPVS6XOXDgQNO2P1fq7fxIsq8hem9HmnRPnjwZeUDir6ljXwsWLKCrq4vR0dGmPt+JEyeauv25UG/nR9J9DdF6O9Kku2jRosiDEZmyZMmStIdQlXpb5iJKb0eadFetWkV7e3vkAYkUi0W6urrSHkZV6m2JK2pvR5p0169fH3U8IkDwKa/P/ePz2MRvUXs7UuDNsmXLWLNmDdu3b9epNRm3YMGCxJ7LzPjEJz7hdQiOejsfkuxriNfbkS+O6O/vp1gsRl1NWlixWKS/vz/tYcxKvS1RxentyJNuT08PAwMDFAqFqKtKCyoUCgwMDNDdnUqYWCTqbYkibm/HDjHXWzCpRxb7JItjluTF7hOFgqiaXQq8UeW1FHgjXlLgjeSVAm/ESwq8kbxS4I14S4E3klcKvBEvKfBG8kqBN+ItBd5IXinwRrykwBvJKwXeiHcUeCN5pcAb8ZICbySvovZ2pEl3KhTEzKKOSzJmKdAHPAbsCP/tAzpjbCtLgTfq7fxLvbd11Y6qsrrBbQM3Bu4MOFdRZ8L7t4XL1btNXZGm8qF86e3Ijemcc4ODg65QKKT+TVQ1tjaAOw1ugvMbcnpNhMttqGObhULBDQ4OzthHtRozjUlXvZ3f8qm3I+XpVnK6cidXNgCbgYV1LDsvXG5zePtrNZbNYp9kccxSnXe9HXVvQG/B8lfdBL/dXYw6DW71LNvX4QWVeluBN1KhH4h7slR7uH4tCryRtHjZ21H2Bt566y3X3t6e+m8vVeNqKcEHCDP9pq+3xsB1zvI87e3tbmRkxNs9XfV2/srX3lbgTYu7l6Bz5sKF26lFgTeSNF97W4E3LW4V0DHHbXSE26lFgTeSNF97W4E3LW5xgttR4I0kaXGC21HgjdRtNMHtKPBGkjSa4HYUeCN12w+MzXEbY+F2alHgjSTN297WJ7ytXb5+wquzF1R57W0F3uRM1DCPY8Au4FzM5zsH7ASO11hGgTfSCLnp7Sh7A87pqh1fay5hHj5etZP0nq5629/KW29HbkznFAriWzUizGNqG/U2pKuxrcpS4I1KvX1+KfAm4xoV5jH19WaCyx/n1djOOeAs8CC1A0Egm32SxTHnUW57O+regN6C+VPNeOu0GtxT1H4r91SVdauVDi+o1NtzOLzQ29vrzCz1H4oqOI4129uuajURNli1bXeCexDcVnB/Hv77ILN/kjtTmZlbt26d95OuetufynNvR2pMnVbjTyV1OkyjSqeMqdTbQSnwJqPuJfiJz4Vj9jCPRlHgjdQr772twJuMSirMo1EUeCP1yntvK/AmoxZ7tp16KPBG6rHYs+3UQ4E3LWDUs+3UQ4E3Uo9Rz7ZTDwXetICkwjwaRYE3Uq/c97Y+4c1m5f0TXp290LqV995W4E1GJRHm0SgKvJEoct/bUfYGnNNVOz5Vs8M8GlW6Ik2l3o55ccQUhYL4U80K82hUKfBGpd4+vxR4k3HNCvNolCz2SRbHnEe57e2oewN6C+ZnNSPMo1GlwwuquVTeejtyYyoUxO9qZJhHo0qBN6pGVF56O1Jj6rQaVdzSKWOqvJYCb8RLCryRvFLgjXhJgTeSVwq8EW8p8EbySoE34iUF3kheKfBGvKPAG8mrqL0dadJdv3591PGIAOCc87p/fB6b+C1qbyvwRppOgTeSV3F6O9KkC9Df30+xWIy6mrSwYrFIf39/2sOYlXpboorT25En3Z6eHtauXRt1NWlha9eupbu7O+1hzEq9LVHF6e3Ik+7Q0BA7duyIupq0sB07djA8PJz2MGal3pao4vR25Em3VCpRLpejriYtrFwuUyqV0h7GrNTbElWc3o406Y6MjLBr164gtEGkTs45du7cybFjx9IeSlXqbYkjTm8re0ESoewFyStlL4iXlL0geaXsBfGWshckr5S9IF5S9oLklbIXxDvKXpC8UvaCeEnZC5JXUXs70l8Dnro+ffv27Tq1RuqWpeyFVHt70WVwWy8svxYWXgJn3oXXX4PnnoZT/h4Pb2Vxejvyn2Dv7+/n2WefZWxsLOqq0qKylL2QSm9f0wW3fw66bwU3CRdV5D+8V4a7vgjDL8CTX4fD/p4B0ooSy14YGBigUChEXVVaUKFQYGBgIDPZC4n39po7oPQ43HwbFC46f8KF4HahPXi89HiwvHghbm9H3tOdosMLUo8s9kliY15zB9z/MLTXkWzWNi9Y7v6Hg9u7nmju2GRWcfskVuBNX18f4+PjsZ5QWsv4+Dh9fX2ZCbxJrLev6ap/wq00NfF+5IbmjEvqFre3FXgjTafAmxnc/jmIexijUAjWl9Qp8Ea8pMCbaRZdFnxo1jYv3vpt86DnVrjU34tNWoUCb8RbCrypcFtvcJbCXDgHH+ttzHhkThR4I15S4E2F5ddeeJZCVBcVg+1I6hR4I95S4E1o4SUN2s6ljdmOzJkCb8RLCrwJnXm3Qds51ZjtyJwp8Ea8o8CbCq+/FlxpNhfvlYPtSOoUeCNeUuBNhe88Axb5bM3zmcFzzzRmPDInUXs70k9+KhTEzKKOq6UtBfqAx4Ad4b99QGeag0pQlgJvEuntk+/A8G6YPBdv/clzMLTbixAc9Xb03o7867a/v59icY6fvLaIbmAbcBT4CnA38Mnw368Ab4SP+59KMDdZCrxJrLef/Dq8/368dd9/P1g/RertgAJvPLIBeB74FFAEOqY93hHe/6lwuQ0Jji1JCryp4vABePQROBvx2O7ZcrDekVeaM646qLcDCrzxyAZgM7CwjmXnhcttDm9/rVmDSkkW+ySxMU+F1tz/cHBpb60r1CbPBXu4jz6SatiNevsDsfvEOVe1Vq9e7abbu3ev6+jocIBqhuoGdzq4XihynQa32oPX0Ojq6OhwQ0NDF/QSMFyr/5pZXvX2R25w9P+h4+m/cGz7nuNbr31Q274X3N//h8Fy6m2vKk5vR27M3t5eZ2apv1hfaxu4CeI15gS4pzx4DY0uM3Pr1q3zftJNvbcvXeJYd5/jS5scv/lHwb/r7gvu9+DnqN5uTG9Hasy33nrLtbe3p/5Cfa2l4MaI15RTNQau04PX0uhqb293IyMj3k666m31dlK9rcCbBrqX4KcwFy7cTt4o8Cbb1NvVKfAmRau48JPcqDrC7eSNAm+yTb1dnQJvUrTYs+34RoE32bXYs+34RoE3KRn1bDu+UeBNdo16th3fKPAmJfuBuf7x7rFwO3mjwJtsU29XF7m39QmvPuFNonT2QrZLvd243lbgTQMdA3YBMWNMOAfsBI43bER+UOBN9qm3Zxart6PsDTinK9JmK121c2HpirR8lHq7Mb0duTGdc25wcNAVCoXUX7CvtYHozXk6XC/tsTe6CoWCGxwcnLGPajVmGpOuelu9nURvK/CmCaaCPTYD7QTBH9WcA84CD5K/QBDIZp9kccxJUW9/IHafRN0b0Fuw+ms1wfXmY+DOcP5v/zPh/U+Rz7ddlaXDC/kr9Xb83o7cmKmHgmSwOsE9CG4ruD8P/32QfH6SO1Mp8Ca/pd5W4I3K09IpY6q8lgJvxEsKvJG8UuCNeEmBN5JXCrwRbynwRvJKgTfiJQXeSF4p8Ea8o8AbyauovR1p0l2/fn3U8YgA4Jzzun98Hpv4LWpvR7oibSoUZPv27cH5ZiJ1yFLgjXrbY4sug9t6Yfm1sPASOPMuvP4aPPc0nErn84I4vR35MuD+/n6effZZxsbmmq4praJYLNLf35/2MGal3vbUNV1w++eg+1Zwk3BR8YPH3ivDXV+E4Rfgya/D4WTPkInT25EOLwD09PQwMDBAoVCIuqq0oEKhwMDAAN3d3WkPZVbqbQ+tuQNKj8PNt0HhovMnXAhuF9qDx0uPB8snJG5vK/BGmiqLfZLFMefSmjvg/oehvTj7sm3zguXufzi4veuJ5o6N+H0SeU93aGiIvr4+xsfHYz2htJbx8XH6+voYHh5OeyizUm975Jqu+ifcSlMT70duaM64KsTt7ciTbqlUolwuR11NWli5XKZUKqU9jFmptz1y++cg7mGeQiFYPwFxejvSpDsyMsKuXbv09ksicc6xc+dOjh07lvZQqlJve2TRZcGHZm210npraJsHPbfCpc2/GCdObyvwRhKhwBup2229wVkKc+EcfKy3MeOZhQJvxEsKvJG6Lb/2wrMUorqoGGwnAQq8EW8p8EbqsvCSBm3n0sZspw4KvBEvKfBG6nLm3QZt51RjtlMHBd6IdxR4I3V7/bXgSrO5eK8cbCcBCrwRLynwRur2nWfAIp/Nej4zeO6ZxoxnFlF7O9IrmwoFMbOo45IWlqXAG/W2B06+A8O7YfJcvPUnz8HQ7kRCcOL0duRfJ/39/RSLc/xkUVpKlgJv1NueePLr8P778dZ9//1g/QQo8Ea8o8AbieXwAXj0ETgb8dju2XKw3pFXmjOuCgq8ES9lsU+yOOZcmgqtuf/h4NLeWleoTZ4L9nAffSSRsBtQ4E3TjI+PMzk5yeTkJBMTExw+fJhly5alPazMUOCNnzLT17uegIfvghefg/fPXnhWw3vl4P4XnwuWS2jChTn0tnOuaq1evdpN19vb68zMAS1R4+PjbuPGjQ5wN954oyuXy27Pnj2pjytLZWZu3bp1F/QSMFyr/5pZrd7bmezrS5c41t3n+NImx2/+UfDvuvuC+zPU25EOL7R6KMi+ffvYv38/K1asSHsomVIZCuLrGQyt3NuZ6etTJ+DpP0l7FOeJ09sKvImgp6eHVatWcejQobSHkjkKvPGX+npuFHjTBJs2bWJycpI9e/Zw5MgR1q5dm/aQMkeBN/5RXzeGAm+a4KGHHqKtrY0FCxbQ1dXF6Oho2kPKJAXe+EV93TgKvBEvKfBG8kqBN+IdBd5IXinwRrykwBvJq6i9HemUsalQkO3bt7fMqTULFixIewiZl6XAm1bpbfV1YyjwRrykwBvJq8QCb3RqiUSxdu3azATeqLcliji9HSt7YceOHVFXkxa2Y8eOzGQvqLcliji9HXnSLZVKlMtz/FMa0lLK5TKlUintYcxKvS1RxentSJNuK1+fLvFVXp/uK/W2xBGnt5W9IIlQ9oLklbIXxEvKXpC8UvaCeEvZC5JXyl4QLyl7QfJK2QviHWUvSF4pe0G8pOwFyauovR1p0p26Pt3Moo5LWliWshfU2xKFshfES8pekLxKLHthYGCAQqEQdVVpQYVCgYGBgcxkL6i3pV5xezvypDtFV+5IPbLYJ1kcsyQvdp9U+9vszjlWr159wd9z37t3r+vo6Ejt78yrslcdHR1uaGjogl4Chmv1XzNLva1qRMXpbQXeSNMp8EbySoE34iUF3kheKfBGvKXAG8krBd6IlxR4I3mlwBvxlgJvJK8UeCNeUuCN5JUCb8Q7CryRvFLgjXhJgTeSVwq8Ee8o8EbySoE34iUF3kheKfBGvKPAG8krBd6Il7LYJ1kcsyRPgTcqb0uBN6q8lgJvxEsKvJG8UuCNeEmBN5JXCrwRbynwRvJKgTfiJQXeSF4p8Ea8pcAbySsF3oiXFHgjeaXAG/GOAm8krxR4I15S4I3klQJvJDFLgT7gMWBH+G8f0DltOQXeSNY0tbd11Y4qanWD2wZuDNwZcK6izoT3bwuXA12RpspOJdHbkRvTOecGBwddoVBI/RukSr42gDsNboLzG3J6TYTLfWHePDc4ODhjH9VqzDQmXfV2a1dSva3AG6nbBmAzsBCYN8uy88LlNp07x3UvvNDsoTWUerv1JNrbUfcGfHgLNj4+7iYnJ93k5KSbmJhwhw8fdsuWLUv9N2Weqzv87V5rD6BanQb36tat3u/pqrdbs5Lu7ciN2dvb68ws1W/S+Pi427hxowPcjTfe6MrlstuzZ0/qP7w81zZmf9tVrSbA7bn8cu8nXfV2a1bSvZ35wJt9+/axf/9+VqxYkfZQcmspsIbZ33ZVMw/46JtvcvzgwcYNqsHU260pjd7OfOBNT08Pq1at4tChQ2kPJbfuJdglmAsHvNLX14DRNId6uzWl0ttR3oLdeeedqb8VgPOPe42Pj7sDBw64xYsXpz6uvNZjxHvrNb2+++EPe3t4Qb3dmpVGb2c28Oahhx6ira2NBQsW0NXVxejoaNpDyq3FDdrOgjNnGrSlxlNvt6bFDdpOlN5W4I3MarRB2xlfuLBBW2o89XZrGm3QdqL0tgJvZFb7gbE5bmMMmFi5sgGjaQ71dmtKo7cVeCOz2grMNZHAgBsGBhowmuZQb7emVHo7yocNzvlxLqMq+dJ5uqq8ltfn6QL09/dTLBajriYZVwLi/jGbs8CiDPw1YPV2a0q8t6PuDTgXhIKkfbmkKvmaCgRxEeo0uOfvuGPGPsKzPV31dutWkr0dqzErm1Nvx1qroiYxVWtKXydd9XbrVlK9PZ+YPv/5z9PT00OpVGLnzp2YGeVy+cePF4tFnHPccsstALz44otzWub666/n6NGjHD9+vOqYOjs7ufrqq3n11VebPp5WXWarc3D99fyjo0fpOX4cB3RU/AzGCD5Y+N7ll7OoVOLWe+6Z8WflM/V2ay6TVG9bMCnPrLu72w0PD8+6kWPHjrFlyxYOHDjAiRMnWLJkCV1dXaxfv/7HieqNWubgwYP09fVx8OBBzpw5w8KFC1m5ciUDAwOsDE/bSHI8rbzM8YMHeaWvj/kHD7LgzBnGFy5kYuVKbhgYoLOOU2jM7GXnXPesCzaBelvLpNXbDZl0ReLIwqQrEket3o4dYi4iItFp0hURSZAmXRGRBGnSFRFJkCZdEZEEadIVEUmQJl0RkQRp0hURSVDNiyPM7BhwNLnhSIu52jm3NI0nVm9Lk1Xt7ZqTroiINJYOL4iIJEiTrohIgjTpiogkSJOuiEiCNOmKiCTo/wNn+xYBdWtB5gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Create scenario output image\n",
    "save_output_image(G, pois, charging_stations, new_charging_nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c5bd67d",
   "metadata": {},
   "source": [
    "## References "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1063cc65",
   "metadata": {},
   "source": [
    "[1] Pagany, Raphaela, Anna Marquardt, and Roland Zink. \"Electric Charging Demand Location Model—A User-and Destination-Based Locating Approach for Electric Vehicle Charging Stations.\" Sustainability 11.8 (2019): 2301. https://doi.org/10.3390/su11082301"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}