from __future__ import print_function
import pandas as pd
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import requests
import json
import urllib
Parâmetros de entrada¶
O modelo recebe como entrada 3 parâmetros:
- A matriz de distância entre as localizações;
- A quantidade de veículos;
- O índice da matriz que corresponde ao depósito.
A matriz de distância pode ser inserida diretamente ou via API da Google a partir dos endereços.
- Para saber como conectar pela API da Google tem este guia: Google Distance Matrix API.
- Para saber como criar uma matriz de distância a partir de uma tabela de lagitudes e longitudes, recomendo este artigo.
Vale lembrar que a matriz de distância da API do google retorna distância real entre os endereços. Os cálculos de distância a partir de arcos, pares de valores (x,y) entre outros retornam as ditâncias de acordo com o método aplicado: euclidiana, manhattan, etc.
Neste exemplo iremos utilizar o seguintes endereços para rotas:
- Imbuí;
- Hospital São Rafael;
- Plataforma;
- Cajazeiras;
- Farol de Itapuã;
- Igreja do Bonfim;
- UNEB (Cabula);
- Candeal;
- Centro de convenções;
- Fonte Nova;
- Rio Vermelho;
- Santo Antônio Além do Carmo;
- Farol da Barra;
- Shopping da Bahia.
A matriz de distância entre esses pontos ficou assim:
pd.DataFrame(
[[0, 7814, 18289, 19643, 12776, 13956, 5503, 9102, 4569, 12095, 11124, 13080, 17796, 6014],
[9860, 0, 13938, 10385, 14181, 18519, 10063, 13657, 11305, 16649, 18204, 17635, 22351, 10568],
[13982, 13002, 0, 11940, 22180, 9327, 11615, 16020, 17400, 15527, 17083, 10324, 16462, 12548],
[20551, 11021, 17413, 0, 18457, 23920, 18183, 22589, 20572, 22096, 23652, 21038, 27798, 19117],
[10936, 11397, 23013, 17869, 0, 22970, 14516, 19209, 9956, 21254, 18340, 22240, 26956, 16887],
[13558, 19555, 11620, 22886, 30064, 0, 11638, 11055, 17737, 9107, 14555, 6035, 12174, 10554],
[5908, 11913, 12024, 13378, 22422, 10480, 0, 9922, 9326, 7856, 10985, 7600, 15131, 6528],
[7301, 13299, 16637, 17990, 23807, 10836, 7145, 0, 11275, 5903, 3700, 7996, 8775, 4297],
[3904, 8263, 21478, 18817, 8207, 15655, 7485, 11155, 0, 13201, 10286, 14187, 18903, 7996],
[8261, 14259, 17597, 18951, 24768, 7426, 8105, 3583, 12441, 0, 4927, 2827, 6990, 5258],
[10386, 16384, 19722, 21075, 19105, 12100, 10230, 2764, 10898, 5408, 0, 7501, 8280, 7383],
[9835, 15833, 11518, 18315, 26341, 5784, 7068, 5156, 14015, 2489, 6500, 0, 6907, 6831],
[13713, 19711, 18696, 24402, 30219, 12963, 12586, 8081, 15768, 6271, 5362, 8364, 0, 10709],
[4764, 10762, 19364, 20718, 14991, 13542, 9438, 7050, 6784, 11088, 7233, 12073, 16789, 0]])
Como a matriz foi puxada a partir da API da Google, perceba que as distâncias não são simétricas: a rota de um trecho (0 -> 1) é diferente do inverso (1 -> 0).
Inserindo os dados de entrada
- Matriz de distância;
- Quantidade de veículos - 1 para o caso do Problema do Caixieiro Viajante (PCV);
- Índice do depósito - 0
def create_data_model():
"""Stores the data for the problem."""
data = {}
data['distance_matrix'] = [
[0, 7814, 18289, 19643, 12776, 13956, 5503, 9102, 4569, 12095, 11124, 13080, 17796, 6014],
[9860, 0, 13938, 10385, 14181, 18519, 10063, 13657, 11305, 16649, 18204, 17635, 22351, 10568],
[13982, 13002, 0, 11940, 22180, 9327, 11615, 16020, 17400, 15527, 17083, 10324, 16462, 12548],
[20551, 11021, 17413, 0, 18457, 23920, 18183, 22589, 20572, 22096, 23652, 21038, 27798, 19117],
[10936, 11397, 23013, 17869, 0, 22970, 14516, 19209, 9956, 21254, 18340, 22240, 26956, 16887],
[13558, 19555, 11620, 22886, 30064, 0, 11638, 11055, 17737, 9107, 14555, 6035, 12174, 10554],
[5908, 11913, 12024, 13378, 22422, 10480, 0, 9922, 9326, 7856, 10985, 7600, 15131, 6528],
[7301, 13299, 16637, 17990, 23807, 10836, 7145, 0, 11275, 5903, 3700, 7996, 8775, 4297],
[3904, 8263, 21478, 18817, 8207, 15655, 7485, 11155, 0, 13201, 10286, 14187, 18903, 7996],
[8261, 14259, 17597, 18951, 24768, 7426, 8105, 3583, 12441, 0, 4927, 2827, 6990, 5258],
[10386, 16384, 19722, 21075, 19105, 12100, 10230, 2764, 10898, 5408, 0, 7501, 8280, 7383],
[9835, 15833, 11518, 18315, 26341, 5784, 7068, 5156, 14015, 2489, 6500, 0, 6907, 6831],
[13713, 19711, 18696, 24402, 30219, 12963, 12586, 8081, 15768, 6271, 5362, 8364, 0, 10709],
[4764, 10762, 19364, 20718, 14991, 13542, 9438, 7050, 6784, 11088, 7233, 12073, 16789, 0]
]
data['num_vehicles'] = 1
data['depot'] = 0
return data
O código a seguir cria o gerenciador de índice (manager) e o modelo de rota (routing). O método manager.IndexToNode converte os índices internos do solver (que você pode ignorar com segurança) em números de localizações. Os números de localização correspondem aos índices da matriz de distância.
As entradas para RoutingIndexManager são:
- O número de linhas da matriz de distância, que é o número de locais (incluindo o depósito).
- O número de veículos no problema.
- O nó correspondente ao depósito.
# Criando uma variável com os dados
data = create_data_model()
# Criando o index manager
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']), data['num_vehicles'], data['depot'])
# Criando o modelo de rota.
routing = pywrapcp.RoutingModel(manager)
Para usar o solver de rotas, você precisa criar um callback de distância: uma função que pega qualquer par de locais e retorna a distância entre eles. Por isso a entrada é em formato de matriz, facilita muito o callback.
A função distance_callback faz exatamente isso: converte o índice da matriz no nós (valores de distância).
A função RegisterTransitCallback registra o callback no solver como transit_callback_index. O callback aceita dois índices, from_index e to_index, e retorna a entrada correspondente da matriz de distância.
def distance_callback(from_index, to_index):
"""Retorna a distância entre dois nós."""
# Converter de índice da matriz para distância (valor do cruzamento da matriz).
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
O avaliador do custo do arco diz ao solucionador como calcular o custo da viagem entre quaisquer dois locais - em outras palavras, o custo da linha (ou rota) que os une no gráfico para o problema. O código a seguir define o avaliador de custo do arco.
Neste exemplo, o avaliador do custo do arco é transit_callback_index, que é a referência interna do solucionador para o o callback de distância. Isso significa que o custo da viagem entre quaisquer dois locais é apenas a distância entre eles. Em outros casos, este custo pode ser alterado de acordo outros fatores envolvidos.
Você também pode definir vários avaliadores de custo de arco que dependem de qual veículo está viajando entre os locais, usando o método routing.SetArcCostEvaluatorOfVehicle(). Por exemplo, se os veículos têm velocidades diferentes, você pode definir o custo da viagem entre os locais como a distância dividida pela velocidade do veículo - em outras palavras, o tempo de viagem.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
O código a seguir define os parâmetros de busca padrão e um método heurístico para encontrar a primeira solução:
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
O código define a primeira estratégia de solução para PATH_CHEAPEST_ARC, que cria uma rota inicial para o solver, adicionando repetidamente arestas com o menor peso que não conduzem a um nó visitado anteriormente (diferente do depósito). Isso faz com que o programa não precise testas todas as combinações possíveis.
A função que exibe a solução retornada pelo solucionador é mostrada abaixo. A função extrai a rota da solução e a imprime no console.
def print_solution(manager, routing, solution):
"""Prints solution on console."""
print('Menor distância percorrida: {} m'.format(solution.ObjectiveValue()))
index = routing.Start(0)
plan_output = 'Rota do veículo 0:\n'
route_distance = 0
while not routing.IsEnd(index):
plan_output += ' {} ->'.format(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
plan_output += ' {}\n'.format(manager.IndexToNode(index))
print(plan_output)
plan_output += 'Route distance: {}miles\n'.format(route_distance)
solution = routing.SolveWithParameters(search_parameters)
if solution:
print_solution(manager, routing, solution)
def get_routes(solution, routing, manager):
"""Get vehicle routes from a solution and store them in an array."""
# Get vehicle routes and store them in a two dimensional array whose
# i,j entry is the jth location visited by vehicle i along its route.
routes = []
for route_nbr in range(routing.vehicles()):
index = routing.Start(route_nbr)
route = [manager.IndexToNode(index)]
while not routing.IsEnd(index):
index = solution.Value(routing.NextVar(index))
route.append(manager.IndexToNode(index))
routes.append(route)
return routes
routes = get_routes(solution, routing, manager)
# Display the routes.
for i, route in enumerate(routes):
print('Rota', i, route)
Mais de um veículo¶
O código é bem semelhante, observe que só existe uma alteração nos dados de entrada: num_vehicles e uma funcão nova que define o máximo a ser percorrido por cada veículo.
def create_data_model():
data = {}
data['distance_matrix'] = [
[0, 7814, 18289, 19643, 12776, 13956, 5503, 9102, 4569, 12095, 11124, 13080, 17796, 6014],
[9860, 0, 13938, 10385, 14181, 18519, 10063, 13657, 11305, 16649, 18204, 17635, 22351, 10568],
[13982, 13002, 0, 11940, 22180, 9327, 11615, 16020, 17400, 15527, 17083, 10324, 16462, 12548],
[20551, 11021, 17413, 0, 18457, 23920, 18183, 22589, 20572, 22096, 23652, 21038, 27798, 19117],
[10936, 11397, 23013, 17869, 0, 22970, 14516, 19209, 9956, 21254, 18340, 22240, 26956, 16887],
[13558, 19555, 11620, 22886, 30064, 0, 11638, 11055, 17737, 9107, 14555, 6035, 12174, 10554],
[5908, 11913, 12024, 13378, 22422, 10480, 0, 9922, 9326, 7856, 10985, 7600, 15131, 6528],
[7301, 13299, 16637, 17990, 23807, 10836, 7145, 0, 11275, 5903, 3700, 7996, 8775, 4297],
[3904, 8263, 21478, 18817, 8207, 15655, 7485, 11155, 0, 13201, 10286, 14187, 18903, 7996],
[8261, 14259, 17597, 18951, 24768, 7426, 8105, 3583, 12441, 0, 4927, 2827, 6990, 5258],
[10386, 16384, 19722, 21075, 19105, 12100, 10230, 2764, 10898, 5408, 0, 7501, 8280, 7383],
[9835, 15833, 11518, 18315, 26341, 5784, 7068, 5156, 14015, 2489, 6500, 0, 6907, 6831],
[13713, 19711, 18696, 24402, 30219, 12963, 12586, 8081, 15768, 6271, 5362, 8364, 0, 10709],
[4764, 10762, 19364, 20718, 14991, 13542, 9438, 7050, 6784, 11088, 7233, 12073, 16789, 0]
]
data['num_vehicles'] = 4
data['depot'] = 0
return data
def print_solution(data, manager, routing, solution):
"""Imprime a solução no console"""
max_route_distance = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Rota do veículo {}:\n'.format(vehicle_id)
route_distance = 0
while not routing.IsEnd(index):
plan_output += ' {} -> '.format(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id)
plan_output += '{}\n'.format(manager.IndexToNode(index))
plan_output += 'Distancia da rota: {}m\n'.format(route_distance)
print(plan_output)
max_route_distance = max(route_distance, max_route_distance)
print('Distância máxima entre as rotas: {}m'.format(max_route_distance))
def main():
"""Solver"""
# Cria uma variável com os dados
data = create_data_model()
# Manager de rota
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['depot'])
# Modelo de rota
routing = pywrapcp.RoutingModel(manager)
# Callback de distância
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Para pescar as distâncias na matriz
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Definição do custo - nesse caso custo = distância
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Restrição de distância
dimension_name = 'Distance'
routing.AddDimension(
transit_callback_index,
0,
50000, # maximo
True, # start cumul to zero
dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)
# Primeira soluções heuristicas
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# Solver
solution = routing.SolveWithParameters(search_parameters)
# Imprimir no console
if solution:
print_solution(data, manager, routing, solution)
if __name__ == '__main__':
main()