Route Optimization - specific start locations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# KniT Anemia Route Optimization - Specific Start Locations for Vehicles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ## Objective\n",
    "### a tool that can be used by survey supervisors to optimize the surveying strategy in terms of scheduling village visits and choosing sites for base of operations. \n",
    "\n",
    "### The tool will aid in choosing an optimal survey schedule for the next day, and can be rerun at the end of each day to update the schedule with latest data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm\n",
    "\n",
    "### Mixed linear programming has been used to solve the problem. \n",
    "\n",
    "### The engine uses Google OR tools, an opensource, free to use library for commercial and research purposes. \n",
    "\n",
    "### The routing library of the Google OR has been used to formulate the problem so as to ensure that the same engine can be easily modified to include other features. https://developers.google.com/reference/constraint_solver/routing/."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Version Specification\n",
    "\n",
    "### This version involves the routing when there are no time constraints associated with the villages,  but the vehicles can start and end at different villages which can be specified by the user.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python code \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## header files"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "importing required libraries for output processing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from __future__ import print_function\n",
    "from six.moves import xrange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "set the path to required directory in your system "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "sys.path.append(\"F:\\\\projects\\\\ameen\\\\ortools\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "import the google or-tools required to solve the problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.constraint_solver import pywrapcp\n",
    "from ortools.constraint_solver import routing_enums_pb2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "import the csv library for input handling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import csv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem Data Definition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### class definition - Vehicle()\n",
    "this class is associated with the properties of one particular vehicle\n",
    "the capacity , which is the maximum time(in seconds) that a vehicle spends outside the central facility is given as an input by the user\n",
    "#### input - max time that can be spend outside the central facility in seconds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Vehicle():\n",
    "    \"\"\"Stores the property of a vehicle\"\"\"\n",
    "    def __init__(self):\n",
    "        \"\"\"Initializes the vehicle properties\"\"\"\n",
    "        vehicle_capacity = input()\n",
    "        self._capacity = int(vehicle_capacity)\n",
    "\n",
    "\n",
    "    @property\n",
    "    def capacity(self):\n",
    "        \"\"\"Gets vehicle capacity\"\"\"\n",
    "        return self._capacity\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " ### class definition - DataProblem()\n",
    " \n",
    " #### This class handles all the data associated with the problem \n",
    "#### Any change in input methods or formats will have to be reflected in the methods of this class\n",
    "#### The data is hard-coded and can be provided through other means by modyfing the methods below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DataProblem():\n",
    "    \"\"\"Stores the data for the problem\"\"\"\n",
    "    def __init__(self):\n",
    "        \"\"\"Initializes the data for the problem\"\"\"\n",
    "        self._vehicle = Vehicle()\n",
    "        #self._num_vehicles = 2\n",
    "\n",
    "        self._depot = 0 \n",
    "\n",
    "        self._req_vehicles = 0\n",
    "        # dummy data\n",
    "        self._demands = [0, 4, 4, 6]\n",
    "\n",
    "        self._distances = [[0, 3, 3, 3],\n",
    "                            [3, 0, 3, 3],\n",
    "                            [3, 3, 0, 3],\n",
    "                            [3, 3, 3, 0]]\n",
    "        #we can explicitely specify the start points and end points of each of the vehicle thatll be used - each vehicle will be only used once\n",
    "        self._start_locations = [self._depot] * (len(self._demands)-1)\n",
    "        self._start_locations[0] = 2\n",
    "        self._end_locations = [self._depot] * (len(self._demands)-1)\n",
    "                    \n",
    "         \n",
    "\n",
    "        \n",
    "    @property        \n",
    "    def vehicle(self):\n",
    "        \"\"\"Gets a vehicle\"\"\"\n",
    "        return self._vehicle\n",
    "\n",
    "    @property\n",
    "    def demands(self):\n",
    "        \"\"\"Gets demands at each location\"\"\"\n",
    "        return self._demands\n",
    "\n",
    "    @property\n",
    "    def num_locations(self):\n",
    "        \"\"\"Gets number of locations\"\"\"\n",
    "        return len(self.demands)\n",
    "\n",
    "    @property\n",
    "    def num_vehicles(self):\n",
    "        \"\"\"Gets number of vehicles\"\"\"\n",
    "        return len(self.demands)-1\n",
    "\n",
    "    @property\n",
    "    def req_vehicles(self):\n",
    "        \"\"\"Gets number of vehicles\"\"\"\n",
    "        return self._req_vehicles\n",
    "\n",
    "    @property       \n",
    "    def depot(self):\n",
    "        \"\"\"Gets depot location index\"\"\"\n",
    "        return self._depot\n",
    "\n",
    "    @property\n",
    "    def distances(self):\n",
    "        \"\"\"Gets distance between each pair of locations\"\"\"\n",
    "        return self._distances\n",
    "\n",
    "    def printDemands(self):\n",
    "        for i in range(len(self._demands)): \n",
    "            print('{0} , '.format(self._demands[i]))\n",
    "\n",
    "    \"\"\"the formulator is to visit the villages which has more demands than that compleatable in a single visit\"\"\"\n",
    "    \"\"\"that falls outside the scope of optimizationa and should be visited before optimization - so as to reduce the demands to what is compleatable by a single visit\"\"\"\n",
    "    def formulator(self):\n",
    "        print('formulator\\n')\n",
    "\n",
    "        for x in xrange(0, len(self._demands)):\n",
    "            if ((self._demands[x] + 2*self._distances[self._depot][x]) > self._vehicle.capacity):\n",
    "                while ((self._demands[x] + 2*self._distances[self._depot][x]) > self._vehicle.capacity) :\n",
    "                    self._req_vehicles += 1\n",
    "                    \"\"\"updating the demands as we visit the villages\"\"\"\n",
    "                    self._demands[x] -= (self._vehicle.capacity - 2*self._distances[self._depot][x])\n",
    "                    print('Route of Vehilce {}\\n'.format(self._req_vehicles))\n",
    "                    print('{0} Load({1}) -> {2} Load({3}) -> {4} Load({5})\\n'.format(self._depot, 0,  x, self._vehicle.capacity - 2*self._distances[self._depot][x], self._depot, self._vehicle.capacity))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  Problem Constraints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### class definition - CreateDistanceEvaluator()\n",
    "#### this class has methods related to the distance(will be stored in terms of time required to travel , in seconds) betwen any pair of villages \n",
    "#### the name distance can be misleading - it represets the time required in seconds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CreateDistanceEvaluator(object): # pylint: disable=too-few-public-methods\n",
    "    \"\"\"Creates callback to return distance between points.\"\"\"\n",
    "    def __init__(self, data):\n",
    "        \"\"\"Initializes the distance matrix.\"\"\"\n",
    "        self._distances = data.distances\n",
    "\n",
    "    def distance_evaluator(self, from_node, to_node):\n",
    "        \"\"\"Returns the manhattan distance between the two nodes\"\"\"\n",
    "        return self._distances[from_node][to_node]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### class definition - CreateDemandEvaluator()\n",
    "#### this class has methods related to the demands of each village\n",
    "#### demand of a village - time in seconds to be spend at that village to compleate the surey process"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CreateDemandEvaluator(object): # pylint: disable=too-few-public-methods\n",
    "    \"\"\"Creates callback to get demands at each location.\"\"\"\n",
    "    def __init__(self, data):\n",
    "        \"\"\"Initializes the demand array.\"\"\"\n",
    "        self._demands = data.demands\n",
    "\n",
    "    def demand_evaluator(self, from_node, to_node):\n",
    "        \"\"\"Returns the demand of the current node\"\"\"\n",
    "        del to_node\n",
    "        return self._demands[from_node]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### class definition - CreateTimeEvaluator()\n",
    "#### this class has methods related to the totla travel time from one village to another \n",
    "#### compleating the survey in a village plus moving to the next village "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CreateTimeEvaluator(object):\n",
    "    \"\"\"Creates callback to get total times between locations.\"\"\"\n",
    "    @staticmethod\n",
    "    def service_time(data, node):\n",
    "        \"\"\"Gets the service time for the specified location.\"\"\"\n",
    "        return data.demands[node]\n",
    "\n",
    "    @staticmethod\n",
    "    def travel_time(data, from_node, to_node):\n",
    "        \"\"\"Gets the travel times between two locations.\"\"\"\n",
    "        if from_node == to_node:\n",
    "            travel_time = 0\n",
    "        else:\n",
    "            travel_time = data.distances[from_node][to_node]\n",
    "        return travel_time\n",
    "\n",
    "    def __init__(self, data):\n",
    "        \"\"\"Initializes the total time matrix.\"\"\"\n",
    "        self._total_time = {}\n",
    "        # precompute total time to have time callback in O(1)\n",
    "        for from_node in xrange(data.num_locations):\n",
    "            self._total_time[from_node] = {}\n",
    "            for to_node in xrange(data.num_locations):\n",
    "                if from_node == to_node:\n",
    "                    self._total_time[from_node][to_node] = 0\n",
    "                else:\n",
    "                    self._total_time[from_node][to_node] = int(\n",
    "                        self.service_time(data, from_node) +\n",
    "                        self.travel_time(data, from_node, to_node))\n",
    "\n",
    "    def time_evaluator(self, from_node, to_node):\n",
    "        \"\"\"Returns the total time between the two nodes\"\"\"\n",
    "        return self._total_time[from_node][to_node]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Function - Implementing the time constraints on the optimization problem"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def implement_time_constraint(routing, data, time_evaluator):\n",
    "    capacity = \"Capacity\"\n",
    "    time_dimension = routing.GetDimensionOrDie(capacity)\n",
    "    for location_idx, time_window in enumerate(data.time_windows):\n",
    "        time_dimension.CumulVar(location_idx).SetRange(time_window[0], time_window[1])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### function - add capacity constrain to the problem\n",
    "#### The maximum time spent by each group of interviewers outside the central facility (maximum working hour limit) < Q\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add_capacity_constraints(routing, data, time_evaluator):\n",
    "    \"\"\"Adds capacity constraint\"\"\"\n",
    "    capacity = \"Capacity\"\n",
    "    routing.AddDimension(\n",
    "        time_evaluator,\n",
    "        0, # null capacity slack\n",
    "        data.vehicle.capacity, # vehicle maximum capacity\n",
    "        True, # start cumul to zero\n",
    "        capacity)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Printer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### class defifnition - ConsolePrinter()\n",
    "#### this class has methods that prints the optimal route calculated \n",
    "#### there are several more information about the various routes analysed in the object - assignment \n",
    "#### we are only printing the most basic data , the order in which the villages are to be travelled \n",
    "#### you can handle the output - change it to any other format or extract more factors from the methods of this class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ConsolePrinter():\n",
    "    \"\"\"Print solution to console\"\"\"\n",
    "    def __init__(self, data, routing, assignment):\n",
    "        \"\"\"Initializes the printer\"\"\"\n",
    "        self._data = data\n",
    "        self._routing = routing\n",
    "        self._assignment = assignment\n",
    "\n",
    "    @property\n",
    "    def data(self):\n",
    "        \"\"\"Gets problem data\"\"\"\n",
    "        return self._data\n",
    "\n",
    "    @property\n",
    "    def routing(self):\n",
    "        \"\"\"Gets routing model\"\"\"\n",
    "        return self._routing\n",
    "\n",
    "    @property\n",
    "    def assignment(self):\n",
    "        \"\"\"Gets routing model\"\"\"\n",
    "        return self._assignment\n",
    "\n",
    "    def print(self):\n",
    "        \"\"\"Prints assignment on console\"\"\"\n",
    "        # Inspect solution.\n",
    "        print('after optimization\\n')\n",
    "        capacity_dimension = self.routing.GetDimensionOrDie('Capacity')\n",
    "        total_time = 0\n",
    "        req_vehicles = self.data.req_vehicles\n",
    "        for vehicle_id in xrange(self.data.num_vehicles):\n",
    "            index = self.routing.Start(vehicle_id)\n",
    "            plan_output = 'Route for vehicle {0}:\\n'.format(req_vehicles+1)\n",
    "            route_time = 0\n",
    "            while not self.routing.IsEnd(index):\n",
    "                node_index = self.routing.IndexToNode(index)\n",
    "                next_node_index = self.routing.IndexToNode(\n",
    "                    self.assignment.Value(self.routing.NextVar(index)))\n",
    "                #route_time += self.data.distances[node_index][next_node_index]\n",
    "                time_var = capacity_dimension.CumulVar(index)\n",
    "                route_time = self.assignment.Value(time_var)\n",
    "                plan_output += ' {0} Load({1}) ->'.format(node_index, route_time)\n",
    "                index = self.assignment.Value(self.routing.NextVar(index))\n",
    "\n",
    "            node_index = self.routing.IndexToNode(index)\n",
    "            time_var = capacity_dimension.CumulVar(index)\n",
    "            route_time = self.assignment.Value(time_var)\n",
    "            plan_output += ' {0} Load({1})\\n'.format(node_index, route_time)\n",
    "            if (route_time > 0) :\n",
    "                req_vehicles += 1\n",
    "                print(plan_output)\n",
    "        print('No Of Required Vehicles are {0}'.format(req_vehicles))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Main\n",
    "### entry point of the programme"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def main():\n",
    "    # Instantiate the data problem.\n",
    "    data = DataProblem()\n",
    "    data.formulator()\n",
    "    print('\\n')\n",
    "    data.printDemands()\n",
    "   # Create Routing Model\n",
    "    routing = pywrapcp.RoutingModel(data.num_locations, data.num_vehicles, data.start_locations, data.end_locations)\n",
    "    # Define weight of each edge\n",
    "    time_evaluator = CreateTimeEvaluator(data).time_evaluator\n",
    "    routing.SetArcCostEvaluatorOfAllVehicles(time_evaluator)\n",
    "    # Add Capacity constraint\n",
    "    add_capacity_constraints(routing, data, time_evaluator)\n",
    "    # Add Time Window constraint\n",
    "    #time_evaluator = CreateTimeEvaluator(data).time_evaluator\n",
    "    #add_time_window_constraints(routing, data, time_evaluator)\n",
    "\n",
    "    # Setting first solution heuristic (cheapest addition).\n",
    "    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()\n",
    "    search_parameters.first_solution_strategy = (\n",
    "        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)\n",
    "    # Solve the problem.\n",
    "    assignment = routing.SolveWithParameters(search_parameters)\n",
    "    printer = ConsolePrinter(data, routing, assignment)\n",
    "    printer.print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Driver"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}