CVRP_GoogleOR.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "CVRP-GoogleOR.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "REY45efb1A45",
        "colab_type": "code",
        "outputId": "7c47a198-f547-44d5-ab7b-fc90feee9c13",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 85
        }
      },
      "source": [
        "!pip install ortools"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Requirement already satisfied: ortools in /usr/local/lib/python3.6/dist-packages (7.6.7691)\n",
            "Requirement already satisfied: protobuf>=3.11.2 in /usr/local/lib/python3.6/dist-packages (from ortools) (3.11.3)\n",
            "Requirement already satisfied: six>=1.10 in /usr/local/lib/python3.6/dist-packages (from ortools) (1.12.0)\n",
            "Requirement already satisfied: setuptools in /usr/local/lib/python3.6/dist-packages (from protobuf>=3.11.2->ortools) (46.1.3)\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qL1CN4_uAunz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "from scipy.spatial import distance\n",
        "import random"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Klodp2IZBnMK",
        "colab_type": "text"
      },
      "source": [
        "## RANDOM DATA"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TQUkzR9P1Kw_",
        "colab_type": "code",
        "outputId": "70426415-f514-4850-c10c-07d734bf4bcd",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 306
        }
      },
      "source": [
        "\"\"\"Capacited Vehicles Routing Problem (CVRP).\"\"\"\n",
        "\n",
        "from __future__ import print_function\n",
        "from ortools.constraint_solver import routing_enums_pb2\n",
        "from ortools.constraint_solver import pywrapcp\n",
        "\n",
        "\n",
        "def create_data_model():\n",
        "    \"\"\"Stores the data for the problem.\"\"\"\n",
        "    data = {}\n",
        "    data['distance_matrix'] = [ [ 0, 14, 25, 20, 22,  0],\n",
        "                                [14,  0, 11, 14, 36, 31],\n",
        "                                [25, 11,  0, 15, 46, 42],\n",
        "                                [20, 14, 15,  0, 36, 40],\n",
        "                                [22, 36, 46, 36,  0, 22],\n",
        "                                [ 0, 31, 42, 40, 22,  0]]\n",
        "    data['demands'] = [0, 1, 5, 8, 5, 5]\n",
        "    data['vehicle_capacities'] = [10, 10, 10]\n",
        "    data['num_vehicles'] = 3\n",
        "    data['depot'] = 0\n",
        "    return data\n",
        "\n",
        "def print_solution(data, manager, routing, solution):\n",
        "    \"\"\"Prints solution 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",
        "        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",
        "            previous_index = index\n",
        "            index = solution.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",
        "\n",
        "\n",
        "def testGoogleOR():\n",
        "    \"\"\"Solve the CVRP problem.\"\"\"\n",
        "    # 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",
        "    solution = routing.SolveWithParameters(search_parameters)\n",
        "\n",
        "    # Print solution on console.\n",
        "    if solution:\n",
        "        print_solution(data, manager, routing, solution)\n",
        "\n",
        "\n",
        "testGoogleOR()"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Route for vehicle 0:\n",
            " 0 Load(0) ->  3 Load(8) ->  0 Load(8)\n",
            "Distance of the route: 40m\n",
            "Load of the route: 8\n",
            "\n",
            "Route for vehicle 1:\n",
            " 0 Load(0) ->  1 Load(1) ->  2 Load(6) ->  0 Load(6)\n",
            "Distance of the route: 50m\n",
            "Load of the route: 6\n",
            "\n",
            "Route for vehicle 2:\n",
            " 0 Load(0) ->  5 Load(5) ->  4 Load(10) ->  0 Load(10)\n",
            "Distance of the route: 44m\n",
            "Load of the route: 10\n",
            "\n",
            "Total distance of all routes: 134m\n",
            "Total load of all routes: 24\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-FDXxKcKOKWN",
        "colab_type": "text"
      },
      "source": [
        "## TESTING PRE-DEFINED DATA N-15"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jNm5f6TL_u0o",
        "colab_type": "code",
        "outputId": "6789167d-1d32-4180-ea0a-1c0d6696189e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 561
        }
      },
      "source": [
        "# Data Source: \n",
        "numberOfCustomers = 15\n",
        "capacityOfVehicle = 35\n",
        "numberOfVehicles = 8\n",
        "C = [i for i in range(1, numberOfCustomers+1)] #set of customers\n",
        "V = [0] + C #+ [numberOfCustomers+1] #depot + customer nodes\n",
        "demandOfCustomers = {0:0,1:19,2:30,3:16,4:23,5:11,6:31,7:15,8:28,9:8,10:8,11:7,12:14,13:6,14:19,15:11}\n",
        "# demandOfCustomers[0] = 0\n",
        "# demandOfCustomers[numberOfCustomers+1] = 0\n",
        "\n",
        "xCoordinates = [30,37,49,52,31,52,42,52,57,62,42,27,43,58,58,37]\n",
        "yCoordinates = [40,52,49,64,62,33,41,41,58,42,57,68,67,48,27,69]\n",
        "\n",
        "# Cost matrix\n",
        "costMatrix = np.ndarray(shape=(len(V),len(V)))\n",
        "for i in range(len(V)):\n",
        "    for j in range(len(V)):\n",
        "        if(i == 0 and j == len(V)-1):\n",
        "            costMatrix[i][j] = 0\n",
        "            continue\n",
        "        \n",
        "        if(j == 0 and i == len(V)-1):\n",
        "            costMatrix[i][j] = 0\n",
        "            continue\n",
        "        \n",
        "        if(i!=j):\n",
        "            costMatrix[i][j] = int(distance.euclidean([xCoordinates[i],yCoordinates[i]], [xCoordinates[j],yCoordinates[j]]))\n",
        "        else:\n",
        "            costMatrix[i][j] = 0\n",
        "costMatrix"
      ],
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0., 13., 21., 32., 22., 23., 12., 22., 32., 32., 20., 28., 29.,\n",
              "        29., 30.,  0.],\n",
              "       [13.,  0., 12., 19., 11., 24., 12., 18., 20., 26.,  7., 18., 16.,\n",
              "        21., 32., 17.],\n",
              "       [21., 12.,  0., 15., 22., 16., 10.,  8., 12., 14., 10., 29., 18.,\n",
              "         9., 23., 23.],\n",
              "       [32., 19., 15.,  0., 21., 31., 25., 23.,  7., 24., 12., 25.,  9.,\n",
              "        17., 37., 15.],\n",
              "       [22., 11., 22., 21.,  0., 35., 23., 29., 26., 36., 12.,  7., 13.,\n",
              "        30., 44.,  9.],\n",
              "       [23., 24., 16., 31., 35.,  0., 12.,  8., 25., 13., 26., 43., 35.,\n",
              "        16.,  8., 39.],\n",
              "       [12., 12., 10., 25., 23., 12.,  0., 10., 22., 20., 16., 30., 26.,\n",
              "        17., 21., 28.],\n",
              "       [22., 18.,  8., 23., 29.,  8., 10.,  0., 17., 10., 18., 36., 27.,\n",
              "         9., 15., 31.],\n",
              "       [32., 20., 12.,  7., 26., 25., 22., 17.,  0., 16., 15., 31., 16.,\n",
              "        10., 31., 22.],\n",
              "       [32., 26., 14., 24., 36., 13., 20., 10., 16.,  0., 25., 43., 31.,\n",
              "         7., 15., 36.],\n",
              "       [20.,  7., 10., 12., 12., 26., 16., 18., 15., 25.,  0., 18., 10.,\n",
              "        18., 34., 13.],\n",
              "       [28., 18., 29., 25.,  7., 43., 30., 36., 31., 43., 18.,  0., 16.,\n",
              "        36., 51., 10.],\n",
              "       [29., 16., 18.,  9., 13., 35., 26., 27., 16., 31., 10., 16.,  0.,\n",
              "        24., 42.,  6.],\n",
              "       [29., 21.,  9., 17., 30., 16., 17.,  9., 10.,  7., 18., 36., 24.,\n",
              "         0., 21., 29.],\n",
              "       [30., 32., 23., 37., 44.,  8., 21., 15., 31., 15., 34., 51., 42.,\n",
              "        21.,  0., 46.],\n",
              "       [ 0., 17., 23., 15.,  9., 39., 28., 31., 22., 36., 13., 10.,  6.,\n",
              "        29., 46.,  0.]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QH3G4dgl9ppX",
        "colab_type": "code",
        "outputId": "6ab65030-6f22-4144-daf5-c4707351024e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 731
        }
      },
      "source": [
        "\"\"\"Vehicles Routing Problem (VRP).\"\"\"\n",
        "\n",
        "from __future__ import print_function\n",
        "from ortools.constraint_solver import routing_enums_pb2\n",
        "from ortools.constraint_solver import pywrapcp\n",
        "\n",
        "\n",
        "def create_data_model():\n",
        "    \"\"\"Stores the data for the problem.\"\"\"\n",
        "    data = {}\n",
        "    data['distance_matrix'] = costMatrix\n",
        "    data['demands'] = [0,19,30,16,23,11,31,15,28,8,8,7,14,6,19,11]\n",
        "    data['vehicle_capacities'] = [35, 35, 35, 35, 35, 35, 35, 35]\n",
        "    data['num_vehicles'] = 8\n",
        "    data['depot'] = 0\n",
        "    return data\n",
        "\n",
        "\n",
        "def print_solution(data, manager, routing, solution):\n",
        "    \"\"\"Prints solution 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",
        "        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",
        "            previous_index = index\n",
        "            index = solution.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",
        "\n",
        "\n",
        "def main():\n",
        "    \"\"\"Solve the CVRP problem.\"\"\"\n",
        "    # 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",
        "    solution = routing.SolveWithParameters(search_parameters)\n",
        "\n",
        "    # Print solution on console.\n",
        "    if solution:\n",
        "        print_solution(data, manager, routing, solution)\n",
        "\n",
        "\n",
        "if __name__ == '__main__':\n",
        "    main()"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Route for vehicle 0:\n",
            " 0 Load(0) ->  8 Load(28) ->  0 Load(28)\n",
            "Distance of the route: 64m\n",
            "Load of the route: 28\n",
            "\n",
            "Route for vehicle 1:\n",
            " 0 Load(0) ->  1 Load(19) ->  3 Load(35) ->  0 Load(35)\n",
            "Distance of the route: 64m\n",
            "Load of the route: 35\n",
            "\n",
            "Route for vehicle 2:\n",
            " 0 Load(0) ->  11 Load(7) ->  4 Load(30) ->  0 Load(30)\n",
            "Distance of the route: 57m\n",
            "Load of the route: 30\n",
            "\n",
            "Route for vehicle 3:\n",
            " 0 Load(0) ->  14 Load(19) ->  5 Load(30) ->  0 Load(30)\n",
            "Distance of the route: 61m\n",
            "Load of the route: 30\n",
            "\n",
            "Route for vehicle 4:\n",
            " 0 Load(0) ->  2 Load(30) ->  0 Load(30)\n",
            "Distance of the route: 42m\n",
            "Load of the route: 30\n",
            "\n",
            "Route for vehicle 5:\n",
            " 0 Load(0) ->  13 Load(6) ->  9 Load(14) ->  7 Load(29) ->  0 Load(29)\n",
            "Distance of the route: 68m\n",
            "Load of the route: 29\n",
            "\n",
            "Route for vehicle 6:\n",
            " 0 Load(0) ->  6 Load(31) ->  0 Load(31)\n",
            "Distance of the route: 24m\n",
            "Load of the route: 31\n",
            "\n",
            "Route for vehicle 7:\n",
            " 0 Load(0) ->  15 Load(11) ->  12 Load(25) ->  10 Load(33) ->  0 Load(33)\n",
            "Distance of the route: 36m\n",
            "Load of the route: 33\n",
            "\n",
            "Total distance of all routes: 416m\n",
            "Total load of all routes: 246\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "tnlGkmtE5Hmi",
        "colab_type": "text"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "abzZ4HXSA8Q3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "## TESTING PRE-DEFINED DATA N-20"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Rh8bKfOr5Kok",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 697
        },
        "outputId": "bf510d97-7270-4d3e-81d0-d07f8ffd86a1"
      },
      "source": [
        "numberOfCustomers = 19\n",
        "capacityOfVehicle = [160, 160]\n",
        "numberOfVehicles = 2\n",
        "C = [i for i in range(1, numberOfCustomers+1)] #set of customers\n",
        "V = [0] + C #[numberOfCustomers+1] #depot + customer nodes\n",
        "demandOfCustomers = [0, 19, 30, 16, 23, 11, 31, 15, 28, 8, 8, 7, 14, 6, 19, 11, 26, 17, 6, 15]\n",
        "# demandOfCustomers[0] = 0\n",
        "# demandOfCustomers[numberOfCustomers+1] = 0\n",
        "\n",
        "xCoordinates = [30, 37, 49, 52, 31, 52, 42, 52, 57, 62, 42, 27, 43, 58, 58, 37, 61, 62, 63, 45]\n",
        "yCoordinates = [40, 52, 49, 64, 62, 33, 41, 41, 58, 42, 57, 68, 67, 48, 27, 69, 33, 63, 69, 35]\n",
        "\n",
        "# Cost matrix\n",
        "costMatrix = np.ndarray(shape=(len(V),len(V)))\n",
        "for i in range(len(V)):\n",
        "    for j in range(len(V)):\n",
        "        if(i == 0 and j == len(V)-1):\n",
        "            costMatrix[i][j] = 0\n",
        "            continue\n",
        "        \n",
        "        if(j == 0 and i == len(V)-1):\n",
        "            costMatrix[i][j] = 0\n",
        "            continue\n",
        "        \n",
        "        if(i!=j):\n",
        "            costMatrix[i][j] = int(distance.euclidean([xCoordinates[i],yCoordinates[i]], [xCoordinates[j],yCoordinates[j]]))\n",
        "        else:\n",
        "            costMatrix[i][j] = 0\n",
        "costMatrix\n",
        "\n"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "array([[ 0., 13., 21., 32., 22., 23., 12., 22., 32., 32., 20., 28., 29.,\n",
              "        29., 30., 29., 31., 39., 43.,  0.],\n",
              "       [13.,  0., 12., 19., 11., 24., 12., 18., 20., 26.,  7., 18., 16.,\n",
              "        21., 32., 17., 30., 27., 31., 18.],\n",
              "       [21., 12.,  0., 15., 22., 16., 10.,  8., 12., 14., 10., 29., 18.,\n",
              "         9., 23., 23., 20., 19., 24., 14.],\n",
              "       [32., 19., 15.,  0., 21., 31., 25., 23.,  7., 24., 12., 25.,  9.,\n",
              "        17., 37., 15., 32., 10., 12., 29.],\n",
              "       [22., 11., 22., 21.,  0., 35., 23., 29., 26., 36., 12.,  7., 13.,\n",
              "        30., 44.,  9., 41., 31., 32., 30.],\n",
              "       [23., 24., 16., 31., 35.,  0., 12.,  8., 25., 13., 26., 43., 35.,\n",
              "        16.,  8., 39.,  9., 31., 37.,  7.],\n",
              "       [12., 12., 10., 25., 23., 12.,  0., 10., 22., 20., 16., 30., 26.,\n",
              "        17., 21., 28., 20., 29., 35.,  6.],\n",
              "       [22., 18.,  8., 23., 29.,  8., 10.,  0., 17., 10., 18., 36., 27.,\n",
              "         9., 15., 31., 12., 24., 30.,  9.],\n",
              "       [32., 20., 12.,  7., 26., 25., 22., 17.,  0., 16., 15., 31., 16.,\n",
              "        10., 31., 22., 25.,  7., 12., 25.],\n",
              "       [32., 26., 14., 24., 36., 13., 20., 10., 16.,  0., 25., 43., 31.,\n",
              "         7., 15., 36.,  9., 21., 27., 18.],\n",
              "       [20.,  7., 10., 12., 12., 26., 16., 18., 15., 25.,  0., 18., 10.,\n",
              "        18., 34., 13., 30., 20., 24., 22.],\n",
              "       [28., 18., 29., 25.,  7., 43., 30., 36., 31., 43., 18.,  0., 16.,\n",
              "        36., 51., 10., 48., 35., 36., 37.],\n",
              "       [29., 16., 18.,  9., 13., 35., 26., 27., 16., 31., 10., 16.,  0.,\n",
              "        24., 42.,  6., 38., 19., 20., 32.],\n",
              "       [29., 21.,  9., 17., 30., 16., 17.,  9., 10.,  7., 18., 36., 24.,\n",
              "         0., 21., 29., 15., 15., 21., 18.],\n",
              "       [30., 32., 23., 37., 44.,  8., 21., 15., 31., 15., 34., 51., 42.,\n",
              "        21.,  0., 46.,  6., 36., 42., 15.],\n",
              "       [29., 17., 23., 15.,  9., 39., 28., 31., 22., 36., 13., 10.,  6.,\n",
              "        29., 46.,  0., 43., 25., 26., 34.],\n",
              "       [31., 30., 20., 32., 41.,  9., 20., 12., 25.,  9., 30., 48., 38.,\n",
              "        15.,  6., 43.,  0., 30., 36., 16.],\n",
              "       [39., 27., 19., 10., 31., 31., 29., 24.,  7., 21., 20., 35., 19.,\n",
              "        15., 36., 25., 30.,  0.,  6., 32.],\n",
              "       [43., 31., 24., 12., 32., 37., 35., 30., 12., 27., 24., 36., 20.,\n",
              "        21., 42., 26., 36.,  6.,  0., 38.],\n",
              "       [ 0., 18., 14., 29., 30.,  7.,  6.,  9., 25., 18., 22., 37., 32.,\n",
              "        18., 15., 34., 16., 32., 38.,  0.]])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AedhK5sy5ZNP",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 241
        },
        "outputId": "cb73d932-1faf-4ae3-82bf-bc949a3eb1e4"
      },
      "source": [
        "\"\"\"Vehicles Routing Problem (VRP).\"\"\"\n",
        "\n",
        "from __future__ import print_function\n",
        "from ortools.constraint_solver import routing_enums_pb2\n",
        "from ortools.constraint_solver import pywrapcp\n",
        "\n",
        "\n",
        "def create_data_model():\n",
        "    \"\"\"Stores the data for the problem.\"\"\"\n",
        "    data = {}\n",
        "    data['distance_matrix'] = costMatrix\n",
        "    data['demands'] = demandOfCustomers\n",
        "    data['vehicle_capacities'] = [160, 160]\n",
        "    data['num_vehicles'] = 2\n",
        "    data['depot'] = 0\n",
        "    return data\n",
        "\n",
        "\n",
        "def print_solution(data, manager, routing, solution):\n",
        "    \"\"\"Prints solution 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",
        "        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",
        "            previous_index = index\n",
        "            index = solution.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",
        "\n",
        "\n",
        "def main():\n",
        "    \"\"\"Solve the CVRP problem.\"\"\"\n",
        "    # 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",
        "    solution = routing.SolveWithParameters(search_parameters)\n",
        "\n",
        "    # Print solution on console.\n",
        "    if solution:\n",
        "        print_solution(data, manager, routing, solution)\n",
        "\n",
        "\n",
        "if __name__ == '__main__':\n",
        "    main()"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Route for vehicle 0:\n",
            " 0 Load(0) ->  1 Load(19) ->  10 Load(27) ->  2 Load(57) ->  17 Load(74) ->  18 Load(80) ->  3 Load(96) ->  12 Load(110) ->  15 Load(121) ->  11 Load(128) ->  4 Load(151) ->  0 Load(151)\n",
            "Distance of the route: 121m\n",
            "Load of the route: 151\n",
            "\n",
            "Route for vehicle 1:\n",
            " 0 Load(0) ->  19 Load(15) ->  5 Load(26) ->  14 Load(45) ->  16 Load(71) ->  9 Load(79) ->  13 Load(85) ->  8 Load(113) ->  7 Load(128) ->  6 Load(159) ->  0 Load(159)\n",
            "Distance of the route: 86m\n",
            "Load of the route: 159\n",
            "\n",
            "Total distance of all routes: 207m\n",
            "Total load of all routes: 310\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "O5N0ZnZTFun-",
        "colab_type": "text"
      },
      "source": [
        "## TESTING PRE-DEFINED DATA N-31"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_Bb5nYvUFyLA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "numberOfCustomers = 31\n",
        "capacityOfVehicle = 100\n",
        "numberOfVehicles = 5\n",
        "C = [i for i in range(1, numberOfCustomers+1)] #set of customers\n",
        "V = [0] + C #+ [numberOfCustomers+1] #depot + customer nodes\n",
        "demandOfCustomers = [0,19,21,6,19,7,12,16,6,16,8,14,21,16,3,22,18,19,1,24,8,12,4,8,24,24,2,20,15,2,14,9]\n",
        "# demandOfCustomers[0] = 0\n",
        "# demandOfCustomers[numberOfCustomers+1] = 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NJGsipeMF6u_",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "xCoordinates = [82,96,50,49,13,29,58,84,14,2,3,5,98,84,61,1,88,91,19,93,50,98,5,42,61,9,80,57,23,20,85,98,82]\n",
        "yCoordinates = [76,44,5,8,7,89,30,39,24,39,82,10,52,25,59,65,51,2,32,3,93,14,42,9,62,97,55,69,15,70,60,5,76]\n",
        "\n",
        "# Cost matrix\n",
        "costMatrix = np.ndarray(shape=(len(V),len(V)))\n",
        "for i in range(len(V)):\n",
        "    for j in range(len(V)):\n",
        "        if(i == 0 and j == len(V)-1):\n",
        "            costMatrix[i][j] = 0\n",
        "            continue\n",
        "        \n",
        "        if(j == 0 and i == len(V)-1):\n",
        "            costMatrix[i][j] = 0\n",
        "            continue\n",
        "        \n",
        "        if(i!=j):\n",
        "            costMatrix[i][j] = int(distance.euclidean([xCoordinates[i],yCoordinates[i]], [xCoordinates[j],yCoordinates[j]]))\n",
        "        else:\n",
        "            costMatrix[i][j] = 0\n",
        "costMatrix"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "WjNxVAs0GTr3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\"\"\"Vehicles Routing Problem (VRP).\"\"\"\n",
        "\n",
        "from __future__ import print_function\n",
        "from ortools.constraint_solver import routing_enums_pb2\n",
        "from ortools.constraint_solver import pywrapcp\n",
        "\n",
        "\n",
        "def create_data_model():\n",
        "    \"\"\"Stores the data for the problem.\"\"\"\n",
        "    data = {}\n",
        "    data['distance_matrix'] = costMatrix\n",
        "    data['demands'] = demandOfCustomers\n",
        "    data['vehicle_capacities'] = [100, 100, 100, 100, 100]\n",
        "    data['num_vehicles'] = 5\n",
        "    data['depot'] = 0\n",
        "    return data\n",
        "\n",
        "\n",
        "def print_solution(data, manager, routing, solution):\n",
        "    \"\"\"Prints solution 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",
        "        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",
        "            previous_index = index\n",
        "            index = solution.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",
        "\n",
        "\n",
        "def main():\n",
        "    \"\"\"Solve the CVRP problem.\"\"\"\n",
        "    # 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",
        "    solution = routing.SolveWithParameters(search_parameters)\n",
        "\n",
        "    # Print solution on console.\n",
        "    if solution:\n",
        "        print_solution(data, manager, routing, solution)\n",
        "\n",
        "\n",
        "if __name__ == '__main__':\n",
        "    main()"
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}