FinalFinalCVRP.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "FinalFinalCVRP.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python2",
      "display_name": "Python 2"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "V6ofm0MhalV8",
        "colab_type": "code",
        "outputId": "9606c845-3b1d-45a9-b2c2-aa6597e9c9ba",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 88
        }
      },
      "source": [
        "!pip install ortools"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Requirement already satisfied: ortools in /usr/local/lib/python2.7/dist-packages (7.3.7083)\n",
            "Requirement already satisfied: six>=1.10 in /usr/local/lib/python2.7/dist-packages (from ortools) (1.12.0)\n",
            "Requirement already satisfied: protobuf>=3.9.0 in /usr/local/lib/python2.7/dist-packages (from ortools) (3.11.0)\n",
            "Requirement already satisfied: setuptools in /usr/local/lib/python2.7/dist-packages (from protobuf>=3.9.0->ortools) (41.6.0)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "3Vq1xrkjaxsK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from __future__ import print_function\n",
        "from ortools.constraint_solver import routing_enums_pb2\n",
        "from ortools.constraint_solver import pywrapcp\n",
        "from __future__ import division\n",
        "import requests\n",
        "import json\n",
        "import urllib\n",
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-EQEruEfpu_F",
        "colab_type": "code",
        "outputId": "d3516dbe-5fe5-467f-ddbc-b2845f727dc9",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 55
        }
      },
      "source": [
        "x = requests.get('http://35.239.136.7:8080/bin')\n",
        "y = x.json()\n",
        "print(y)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[{u'lat': u'23.2696', u'lng': u'77.3956', u'id': 3}, {u'lat': u'23.2499', u'lng': u'77.4415', u'id': 5}, {u'lat': u'23.2196', u'lng': u'77.3927', u'id': 6}, {u'lat': u'23.2402', u'lng': u'77.5390', u'id': 7}, {u'lat': u'23.0871', u'lng': u'77.5275', u'id': 8}, {u'lat': u'23.2040', u'lng': u'77.4530', u'id': 9}, {u'lat': u'23.1247', u'lng': u'77.4128', u'id': 10}, {u'lat': u'23.3620', u'lng': u'77.3095', u'id': 11}, {u'lat': u'23.2520', u'lng': u'77.4635', u'id': 13}, {u'lat': u'23.3840', u'lng': u'77.4358', u'id': 14}, {u'lat': u'23.1915', u'lng': u'77.4788', u'id': 15}, {u'lat': u'23.2326', u'lng': u'77.3726', u'id': 16}, {u'lat': u'23.2386', u'lng': u'77.4099', u'id': 17}, {u'lat': u'23.2508', u'lng': u'77.4157', u'id': 18}, {u'lat': u'23.2764', u'lng': u'77.3716', u'id': 28}]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uGeoZ3rQq5-Z",
        "colab_type": "text"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WrkUR9cjq5sR",
        "colab_type": "text"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "pLmlwiaO_MpJ",
        "colab_type": "code",
        "outputId": "30d13075-790b-4cea-c396-26a86caaab28",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 55
        }
      },
      "source": [
        "coordinates = []\n",
        "leng = len(y)\n",
        "\n",
        "for i in range(1,leng):\n",
        "  coordinates.append(y[i]['lat'])\n",
        "  coordinates[i-1]+=','+y[i]['lng']\n",
        "  #coordinates[i-1]= coordinates[i-1]\n",
        "\n",
        "print(coordinates) \n"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[u'23.2499,77.4415', u'23.2196,77.3927', u'23.2402,77.5390', u'23.0871,77.5275', u'23.2040,77.4530', u'23.1247,77.4128', u'23.3620,77.3095', u'23.2520,77.4635', u'23.3840,77.4358', u'23.1915,77.4788', u'23.2326,77.3726', u'23.2386,77.4099', u'23.2508,77.4157', u'23.2764,77.3716']\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JTGk2aj2axvP",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "### Finding Distance Matrix ###\n",
        "\n",
        "\n",
        "def create_data_for_distance_matrix():\n",
        "  \"\"\"Creates the data.\"\"\"\n",
        "  data = {}\n",
        "  data['API_key'] = 'API_KEY'\n",
        "  data['addresses'] = coordinates\n",
        "                      \n",
        "  return data"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MwL_k3ucaxqp",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def create_distance_matrix(data):\n",
        "  addresses = data[\"addresses\"]\n",
        "  API_key = data[\"API_key\"]\n",
        "  # Distance Matrix API only accepts 100 elements per request, so get rows in multiple requests.\n",
        "  max_elements = 100\n",
        "  num_addresses = len(addresses) # 16 in this example.\n",
        "  # Maximum number of rows that can be computed per request (6 in this example).\n",
        "  max_rows = max_elements // num_addresses\n",
        "  # num_addresses = q * max_rows + r (q = 2 and r = 4 in this example).\n",
        "  q, r = divmod(num_addresses, max_rows)\n",
        "  dest_addresses = addresses\n",
        "  distance_matrix = []\n",
        "  # Send q requests, returning max_rows rows per request.\n",
        "  for i in range(q):\n",
        "    origin_addresses = addresses[i * max_rows: (i + 1) * max_rows]\n",
        "    response = send_request(origin_addresses, dest_addresses, API_key)\n",
        "    distance_matrix += build_distance_matrix(response)\n",
        "\n",
        "  # Get the remaining remaining r rows, if necessary.\n",
        "  if r > 0:\n",
        "    origin_addresses = addresses[q * max_rows: q * max_rows + r]\n",
        "    response = send_request(origin_addresses, dest_addresses, API_key)\n",
        "    distance_matrix += build_distance_matrix(response)\n",
        "  return distance_matrix"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6X5HSW45axoI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def send_request(origin_addresses, dest_addresses, API_key):\n",
        "  \"\"\" Build and send request for the given origin and destination addresses.\"\"\"\n",
        "  def build_address_str(addresses):\n",
        "    # Build a pipe-separated string of addresses\n",
        "    address_str = ''\n",
        "    for i in range(len(addresses) - 1):\n",
        "      address_str += addresses[i] + '|'\n",
        "    address_str += addresses[-1]\n",
        "    return address_str\n",
        "\n",
        "  request = 'https://maps.googleapis.com/maps/api/distancematrix/json?units=imperial'\n",
        "  origin_address_str = build_address_str(origin_addresses)\n",
        "  dest_address_str = build_address_str(dest_addresses)\n",
        "  request = request + '&origins=' + origin_address_str + '&destinations=' + \\\n",
        "                       dest_address_str + '&key=' + API_key\n",
        "  jsonResult = urllib.urlopen(request).read()\n",
        "  response = json.loads(jsonResult)\n",
        "  return response"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BBw9AelXdblt",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def build_distance_matrix(response):\n",
        "  distance_matrix = []\n",
        "  for row in response['rows']:\n",
        "    row_list = [row['elements'][j]['distance']['value'] for j in range(len(row['elements']))]\n",
        "    distance_matrix.append(row_list)\n",
        "  return distance_matrix"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yyZUa93Vdc9v",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "data_of_distance_matrix = create_data_for_distance_matrix()\n",
        "addresses = data_of_distance_matrix['addresses']\n",
        "API_key = data_of_distance_matrix['API_key']\n",
        "distance_matrix = create_distance_matrix(data_of_distance_matrix)\n",
        "\n",
        "\n",
        "  #### Distance Matrix Created ####"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "GO2zfs5IdmD3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#### CVRP Begins ####\n",
        "\n",
        "def create_data_model():\n",
        "    \"\"\"Stores the data for the problem.\"\"\"\n",
        "    data = {}\n",
        "    data['distance_matrix'] = distance_matrix\n",
        "    data['demands'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8,9]##############################\n",
        "    data['vehicle_capacities'] = [15 for i in range(6)]###############################\n",
        "    data['num_vehicles'] = 6 ################################\n",
        "    data['depot'] = 0 #############################\n",
        "    return data"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BrFoaW9rjs25",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "vehicle_to_route={}\n",
        "def print_solution(data, manager, routing, assignment):\n",
        "    \"\"\"Prints assignment on console.\"\"\"\n",
        "    total_distance = 0\n",
        "    total_load = 0\n",
        "    for vehicle_id in range(data['num_vehicles']):\n",
        "        index = routing.Start(vehicle_id)\n",
        "        plan_output = 'Route for vehicle {}:\\n'.format(vehicle_id)\n",
        "        route_distance = 0\n",
        "        route_load = 0\n",
        "        vehicle_to_route[vehicle_id ]=[coordinates[0]]\n",
        "        while not routing.IsEnd(index):\n",
        "            node_index = manager.IndexToNode(index)\n",
        "            route_load += data['demands'][node_index]\n",
        "            plan_output += ' {0} Load({1}) -> '.format(node_index, route_load)\n",
        "            vehicle_to_route[vehicle_id ].append(coordinates[node_index])\n",
        "            previous_index = index\n",
        "            index = assignment.Value(routing.NextVar(index))\n",
        "            route_distance += routing.GetArcCostForVehicle(\n",
        "                previous_index, index, vehicle_id)\n",
        "        plan_output += ' {0} Load({1})\\n'.format(manager.IndexToNode(index),\n",
        "                                                 route_load)\n",
        "        plan_output += 'Distance of the route: {}m\\n'.format(route_distance)\n",
        "        plan_output += 'Load of the route: {}\\n'.format(route_load)\n",
        "        print(plan_output)\n",
        "        total_distance += route_distance\n",
        "        total_load += route_load\n",
        "    print('Total distance of all routes: {}m'.format(total_distance))\n",
        "    print('Total load of all routes: {}'.format(total_load))\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "wMtf1gDAj1Uv",
        "colab_type": "code",
        "outputId": "15f8ce2e-5c1b-4c38-e233-30057fb7e7d3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 621
        }
      },
      "source": [
        "# Instantiate the data problem.\n",
        "    data = create_data_model()\n",
        "\n",
        "    # Create the routing index manager.\n",
        "    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),\n",
        "                                           data['num_vehicles'], data['depot'])\n",
        "\n",
        "    # Create Routing Model.\n",
        "    routing = pywrapcp.RoutingModel(manager)\n",
        "\n",
        "\n",
        "    # Create and register a transit callback.\n",
        "    def distance_callback(from_index, to_index):\n",
        "        \"\"\"Returns the distance between the two nodes.\"\"\"\n",
        "        # Convert from routing variable Index to distance matrix NodeIndex.\n",
        "        from_node = manager.IndexToNode(from_index)\n",
        "        to_node = manager.IndexToNode(to_index)\n",
        "        return data['distance_matrix'][from_node][to_node]\n",
        "\n",
        "    transit_callback_index = routing.RegisterTransitCallback(distance_callback)\n",
        "\n",
        "    # Define cost of each arc.\n",
        "    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)\n",
        "\n",
        "\n",
        "    # Add Capacity constraint.\n",
        "    def demand_callback(from_index):\n",
        "        \"\"\"Returns the demand of the node.\"\"\"\n",
        "        # Convert from routing variable Index to demands NodeIndex.\n",
        "        from_node = manager.IndexToNode(from_index)\n",
        "        return data['demands'][from_node]\n",
        "\n",
        "    demand_callback_index = routing.RegisterUnaryTransitCallback(\n",
        "        demand_callback)\n",
        "    routing.AddDimensionWithVehicleCapacity(\n",
        "        demand_callback_index,\n",
        "        0,  # null capacity slack\n",
        "        data['vehicle_capacities'],  # vehicle maximum capacities\n",
        "        True,  # start cumul to zero\n",
        "        'Capacity')\n",
        "\n",
        "    # Setting first solution heuristic.\n",
        "    search_parameters = pywrapcp.DefaultRoutingSearchParameters()\n",
        "    search_parameters.first_solution_strategy = (\n",
        "        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)\n",
        "\n",
        "    # Solve the problem.\n",
        "    assignment = routing.SolveWithParameters(search_parameters)\n",
        "\n",
        "    # Print solution on console.\n",
        "    if assignment:\n",
        "        print_solution(data, manager, routing, assignment)\n",
        "    print(vehicle_to_route)\n",
        "\n",
        "    final = {}\n",
        "    final[\"cor\"]=vehicle_to_route\n",
        "\n",
        "\n",
        "    final = json.dumps(final)\n",
        "    #print(final)\n",
        "    loaded = json.loads(final)\n",
        "    r  = requests.post('http://35.239.136.7:8081/bin',json = loaded)\n",
        "    #print(vehicle_to_route)\n",
        "    "
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Route for vehicle 0:\n",
            " 0 Load(0) ->  7 Load(8) ->  0 Load(8)\n",
            "Distance of the route: 5819m\n",
            "Load of the route: 8\n",
            "\n",
            "Route for vehicle 1:\n",
            " 0 Load(0) ->  0 Load(0)\n",
            "Distance of the route: 0m\n",
            "Load of the route: 0\n",
            "\n",
            "Route for vehicle 2:\n",
            " 0 Load(0) ->  0 Load(0)\n",
            "Distance of the route: 0m\n",
            "Load of the route: 0\n",
            "\n",
            "Route for vehicle 3:\n",
            " 0 Load(0) ->  12 Load(2) ->  6 Load(6) ->  8 Load(14) ->  0 Load(14)\n",
            "Distance of the route: 70495m\n",
            "Load of the route: 14\n",
            "\n",
            "Route for vehicle 4:\n",
            " 0 Load(0) ->  4 Load(4) ->  5 Load(6) ->  3 Load(8) ->  9 Load(9) ->  2 Load(10) ->  0 Load(10)\n",
            "Distance of the route: 78689m\n",
            "Load of the route: 10\n",
            "\n",
            "Route for vehicle 5:\n",
            " 0 Load(0) ->  11 Load(1) ->  1 Load(2) ->  10 Load(4) ->  13 Load(8) ->  0 Load(8)\n",
            "Distance of the route: 37925m\n",
            "Load of the route: 8\n",
            "\n",
            "Total distance of all routes: 192928m\n",
            "Total load of all routes: 40\n",
            "{0: [u'23.2499,77.4415', u'23.2499,77.4415', u'23.2520,77.4635'], 1: [u'23.2499,77.4415', u'23.2499,77.4415'], 2: [u'23.2499,77.4415', u'23.2499,77.4415'], 3: [u'23.2499,77.4415', u'23.2499,77.4415', u'23.2508,77.4157', u'23.3620,77.3095', u'23.3840,77.4358'], 4: [u'23.2499,77.4415', u'23.2499,77.4415', u'23.2040,77.4530', u'23.1247,77.4128', u'23.0871,77.5275', u'23.1915,77.4788', u'23.2402,77.5390'], 5: [u'23.2499,77.4415', u'23.2499,77.4415', u'23.2386,77.4099', u'23.2196,77.3927', u'23.2326,77.3726', u'23.2764,77.3716']}\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jiUia0mEj1Rx",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}