gistfile1.txt

"""Vehicle Routing Problem"""
from __future__ import print_function
from six.moves import xrange
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
from math import sin, cos, sqrt, atan2, radians
import httplib2



###########################
# Problem Data Definition #
###########################
class CityBlock():
    """City block definition"""
    @property
    def width(self):
        """Gets Block size West to East"""
        return 228/2

    @property
    def height(self):
        """Gets Block size North to South"""
        return 80

class DataProblem():
    """Stores the data for the problem"""
    def __init__(self):
        """Initializes the data for the problem"""
        self._num_vehicles = 12

        # Locations in block unit
        # locations = \
        #         [(4, 4), # depot
        #          (2, 0), (8, 0), # row 0
        #          (0, 1), (1, 1),
        #          (5, 2), (7, 2),
        #          (3, 3), (6, 3),
        #          (5, 5), (8, 5),
        #          (1, 6), (2, 6),
        #          (3, 7), (6, 7),
        #          (0, 8), (7, 8)]


        locations = \
          [(-23.603777, -46.694043, 'CD'),
          (-23.547756, -46.686312, 'RUA BEATRIZ GALV?O, 100'),
          (-23.528586,-46.6410008, 'RUA SILVA PINTO, 264'),
          (-23.5777903,-46.6452118, 'Rua Estela, 215'),
          (-23.593267, -46.651174, 'R Leopoldo De Bulhoes, 35 Ap 1802'),
          (-23.531368, -46.637178, 'Rua Ribeiro De Lima, 446'),
           (-23.535441, -46.631832, 'Rua Vinte E Cinco De Janeiro, 180'),
           (-23.596343, -46.627435, 'Rua Borebi, 75 Ap 121'),
           (-23.594203, -46.624910, 'Rua Pico Della Mirandola, 101'), ## CORTE
           (-23.555997, -46.550229, 'RUA PEDREIRA, 189 '),
           (-23.554051, -46.576094, 'RUA PARACAMBI, 195 '),
           (-23.548151, -46.538311, 'AVENIDA CONSELHEIRO CARR?O, 2425'),
           (-23.546581, -46.560169, 'RUA EUCLIDES PACHECO, 1558'),
           (-23.591924, -46.558097, 'RUA MARCELO M?LLER, 1075'),
           (-23.512036, -46.626199, 'RUA DA P?TRIA, 967')
           ]    


# AIzaSyBzealmNKaYtdJn3CkieemHQexiEUqtNys

           # https://maps.googleapis.com/maps/api/directions/json?origin=-23.603777,-46.694043&destination=-23.570012,-46.692536&mode=bicycling&key=AIzaSyBzealmNKaYtdJn3CkieemHQexiEUqtNys

        # locations in meters using the city block dimension
        city_block = CityBlock()
        self._locations = [(
            loc[0],
            loc[1],
            loc[2]) for loc in locations]

        self._depot = 0

    @property
    def num_vehicles(self):
        """Gets number of vehicles"""
        return self._num_vehicles

    @property
    def locations(self):
        """Gets locations"""
        return self._locations

    @property
    def num_locations(self):
        """Gets number of locations"""
        return len(self.locations)

    @property
    def depot(self):
        """Gets depot location index"""
        return self._depot

#######################
# Problem Constraints #
#######################
def manhattan_distance(position_1, position_2):
    """Computes the Manhattan distance between two points"""
    # approximate radius of earth in km
    R = 6373.0

    lat1 = radians(position_1[0])
    lon1 = radians(position_1[1])
    lat2 = radians(position_2[0])
    lon2 = radians(position_2[1])

    dlon = lon2 - lon1
    dlat = lat2 - lat1

    a = sin(dlat / 2)**2 + cos(lat1) * cos(lat2) * sin(dlon / 2)**2
    c = 2 * atan2(sqrt(a), sqrt(1 - a))

    distance = R * c * 1000

    # url = "https://maps.googleapis.com/maps/api/directions/json?origin="
    # h = httplib2.Http(".cache")
    # h.request("http://example.org/", "GET")

    # "https://maps.googleapis.com/maps/api/directions/json?origin=-23.603777,-46.694043&destination=-23.570012,-46.692536&mode=bicycling&key=AIzaSyBzealmNKaYtdJn3CkieemHQexiEUqtNys"

    # print(distance, position_1[2], position_2[2])

    return distance
    
    #return (abs(position_1[0] - position_2[0]) +
     #       abs(position_1[1] - position_2[1]))

class CreateDistanceEvaluator(object): # pylint: disable=too-few-public-methods
    """Creates callback to return distance between points."""
    def __init__(self, data):
        """Initializes the distance matrix."""
        self._distances = {}

        # precompute distance between location to have distance callback in O(1)
        for from_node in xrange(data.num_locations):
            self._distances[from_node] = {}
            for to_node in xrange(data.num_locations):
                if from_node == to_node:
                    self._distances[from_node][to_node] = 0
                else:
                    self._distances[from_node][to_node] = (
                        manhattan_distance(
                            data.locations[from_node],
                            data.locations[to_node]))

    def distance_evaluator(self, from_node, to_node):
        """Returns the manhattan distance between the two nodes"""
        return self._distances[from_node][to_node]

class CreateMaxItemEvaluator(object): # pylint: disable=too-few-public-methods
    """Creates callback to return distance between points."""
    def __init__(self, data):
        """Initializes the distance matrix."""
        self._distances = {}

    def evaluator(self, from_node, to_node):
        return 1

def add_distance_dimension(routing, distance_evaluator):
    """Add Global Span constraint"""
    distance = "Distance"
    maximum_distance = 90000
    routing.AddDimension(
        distance_evaluator,
        0, # null slack
        maximum_distance, # maximum distance per vehicle
        True, # start cumul to zero
        distance)
    distance_dimension = routing.GetDimensionOrDie(distance)
    # Try to minimize the max distance among vehicles.
    # /!\ It doesn't mean the standard deviation is minimized
    distance_dimension.SetGlobalSpanCostCoefficient(100)


def add_maxitens_dimension(routing, evaluator):
    """Add Global Span constraint"""
    routing.AddDimension(
        evaluator,
        0, # null slack
        6, # maximum load per vehicle
        True, # start cumul to zero
        "Capacity")
    # distance_dimension = routing.GetDimensionOrDie("Capacity")
    # Try to minimize the max distance among vehicles.
    # /!\ It doesn't mean the standard deviation is minimized
    # distance_dimension.SetGlobalSpanCostCoefficient(100)

###########
# Printer #
###########
class ConsolePrinter():
    """Print solution to console"""
    def __init__(self, data, routing, assignment):
        """Initializes the printer"""
        self._data = data
        self._routing = routing
        self._assignment = assignment

    @property
    def data(self):
        """Gets problem data"""
        return self._data

    @property
    def routing(self):
        """Gets routing model"""
        return self._routing

    @property
    def assignment(self):
        """Gets routing model"""
        return self._assignment

    def print(self):
        """Prints assignment on console"""
        # Inspect solution.
        print("=====")
        total_dist = 0
        for vehicle_id in xrange(self.data.num_vehicles):
            index = self.routing.Start(vehicle_id)
            plan_output = 'Rota para veiculo {0}:\n'.format(vehicle_id)
            route_dist = 0
            while not self.routing.IsEnd(index):
                polyline = ""
                node_index = self.routing.IndexToNode(index)
                next_node_index = self.routing.IndexToNode(
                    self.assignment.Value(self.routing.NextVar(index)))
                route_dist += manhattan_distance(
                    self.data.locations[node_index],
                    self.data.locations[next_node_index])
                plan_output += ' [{location_id}] -> '.format(
                    location_id = self.data.locations[node_index][2]
                )
                polyline += 'lat: {0}, lng: {1} '.format(
                    self.data.locations[node_index][0],
                    self.data.locations[node_index][1]
                    )
                print(polyline)
                # plan_output += ' -> '.format(
                #     node_index=node_index)
                index = self.assignment.Value(self.routing.NextVar(index))

            node_index = self.routing.IndexToNode(index)
            total_dist += route_dist
            plan_output += ' {node_index}\n'.format(
                node_index=node_index)
            plan_output += 'Distancia da rota {0}: {dist}\n'.format(
                vehicle_id,
                dist=route_dist)
            print(plan_output)
        print('Distancia total de todas as rotas (em metros): {dist}'.format(dist=total_dist))

########
# Main #
########
def main():
    """Entry point of the program"""
    # Instantiate the data problem.
    data = DataProblem()

    # Create Routing Model
    routing = pywrapcp.RoutingModel(data.num_locations, data.num_vehicles, data.depot)
    # Define weight of each edge
    distance_evaluator = CreateDistanceEvaluator(data).distance_evaluator
    routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
    add_distance_dimension(routing, distance_evaluator)

    capacity_evaluator = CreateMaxItemEvaluator(data).evaluator
    add_maxitens_dimension(routing, capacity_evaluator)

    # Setting first solution heuristic (cheapest addition).
    search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    # Solve the problem.
    assignment = routing.SolveWithParameters(search_parameters)
    printer = ConsolePrinter(data, routing, assignment)
    printer.print()

if __name__ == '__main__':
  main()