Resolvendo o problema do caixeiro viajante

Nov 29 2022

Otimize as rotas para entrega de encomendas usando python para economizar custos de entrega (Caso de estudo: entrega de encomendas em Bandung, Indonésia com dados simples) O Problema do Caixeiro Viajante ou TSP é um problema de otimização combinatória que tenta responder à pergunta “Dada uma lista de cidades e distâncias entre cada par de cidades, qual é a rota mais curta possível que visita cada cidade exatamente uma vez e retorna à cidade de origem?”. De forma simples, o TSP tem a tarefa de encontrar a rota mais curta entre um conjunto de pontos que devem ser visitados.

Otimize as rotas para entrega de encomendas usando python para economizar custos de entrega (caso de estudo: entrega de encomendas em Bandung, Indonésia com dados simples)

Foto de José Martín Ramírez Carrasco no Unsplash

O Traveling Salesman Problem ou TSP é um problema de otimização combinatória que tenta responder à pergunta “Dada uma lista de cidades e as distâncias entre cada par de cidades, qual é a rota mais curta possível que visita cada cidade exatamente uma vez e retorna à cidade de origem? ”. De forma simples, o TSP tem a tarefa de encontrar a rota mais curta entre um conjunto de pontos que devem ser visitados. Torna-se um problema real na cadeia de suprimentos e no setor de logística, à medida que disparam após o aumento do comércio eletrônico.

Então, por que o TSP é importante? Em essência, ajuda a empresa a obter mais lucro economizando tempo e recursos. No setor de logística, uma das formas de gerar mais lucro é pela eficiência nos custos e prazos de entrega. Existem várias maneiras de conseguir isso, uma delas é resolvendo o Problema do Caixeiro Viajante (TSP), onde você está tentando encontrar as rotas mais eficientes para seguir na estrada. Quanto mais eficientemente for resolvido, menos tempo é gasto dirigindo, mais combustível é economizado, menos horas são necessárias e ainda mais pacotes são entregues . Como resultado, o balanço patrimonial de qualquer atividade comercial baseada em entrega será duplamente beneficiado.

Portanto, estou tentando criar uma demonstração deste Problema do Caixeiro Viajante para um mensageiro de uma empresa de entrega de encomendas em Bandung para reduzir os custos de entrega .

Nota : como esta é uma demonstração simples, os dados usados são apenas 8 pontos fictícios de entrega e os dados são dados gerados aleatoriamente.

Cenário

Você é gerente de um centro de serviços de entrega de encomendas em Bandung. Você deve entregar pacotes para alguns dos clientes do seu depósito com 1 veículo. A distribuição dos pontos de entrega e do depósito pode ser observada a seguir (Figura 1).

Figura 1. Distribuição espacial dos pontos de entrega

**De qualquer forma, você pode ajustar o número de veículos e o número de pontos de entrega conforme desejar editando o código-fonte abaixo

Objetivos

Encontre as melhores rotas para entregar todas as encomendas aos clientes.

Para rastrear a qualidade do modelo ou solução que estamos tentando implementar, é melhor definir as métricas de negócios. Como os dados dos casos relacionados não estão disponíveis, vou apenas mencionar o potencial sem medir o quão boa é a solução. Essas potenciais métricas de negócios são:

Custos de entrega
Tempo gasto
Taxa de entrega no prazo
Pontuação de satisfação do cliente (pontuação CSAT)

Utilizando o Google OR-Tools , a melhor rota com um veículo é:

Depósito -> Endereço 5 -> Endereço 6 -> Endereço 7 -> Endereço 4 -> Endereço 3 -> Endereço 2 -> Endereço 1 -> Depósito

Distância do percurso: 7,44 km

Figura 2. A animação da rota mais curta

Etapas Técnicas

Figura 3. Fluxograma de processamento em Python

O código completo é fornecido aqui .

I. Importar biblioteca e ler dados

Antes de tudo, temos que importar as bibliotecas para o Google Colab. Vamos usar algumas bibliotecas.

numpy e pandas : para operações numéricas e manipulação de dados
itertools : para criar iteradores para um loop eficiente
ast : para processar árvores da gramática de sintaxe abstrata do Python
request : para fazer requisições HTTP
json : para trabalhar com dados JSON
networkx : para a criação, manipulação e estudo da estrutura, dinâmica e funções de redes complexas
osmnx : para baixar dados geoespaciais do OpenStreetMap e modelar, projetar, visualizar e analisar redes de ruas do mundo real e quaisquer outras geometrias geoespaciais
folium : para visualizar dados que foram manipulados em Python em um mapa de folheto interativo
ortools : para resolver problemas de otimização combinatória

# Install and Import Library
pip install osmnx
pip install ortools

import numpy as np
import pandas as pd
import itertools
import ast
import requests
import json
import networkx as nx
import osmnx as ox
import folium
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

from google.colab import drive
drive.mount('/content/drive')

import warnings 
warnings.filterwarnings('ignore')

# Read data
df_points = pd.read_excel('/content/drive/MyDrive/dataset/delivery_destinations.xlsx')

Figura 4. O conjunto de dados do ponto de entrega

II. Geocodificação

Geocodificação é o processo de transformar a descrição de um local — como um par de coordenadas, um endereço ou o nome de um local — em um local na superfície da Terra. Em resumo, estamos tentando recuperar a latitude e a longitude do endereço do conjunto de dados. Essa latitude e longitude serão utilizadas posteriormente para calcular a distância percorrida entre os pontos e determinar a melhor rota de entrega.

Estou usando a API HERE para geocodificação, considerando que é bastante precisa e gratuita (com chamadas limitadas). Você pode ler este artigo para obter os detalhes desse processo.

# Define variables
apikey = '<YOUR-API-KEY-HERE>'
url = 'https://discover.search.hereapi.com/v1/discover'
headers = {'Content-Type': 'application/json'}
origin_point = '-6.8918336,107.6103212'
latlong_origin = []
latlong_points = []

# Get lat long using HERE Map API
for i, data in df_points.iterrows():
  # your place name is defined below
  place_name = data.address
  my_params = {'at' : origin_point,
               'limit' : 1,
               'apikey' : apikey,
               'q' : place_name}
  r = requests.get(url, params=my_params, headers=headers)
  output = json.loads(r.text)
  latlong_dict = output['items'][0]['position']
  latlong = ', '.join(map(str, latlong_dict.values()))
  latlong_points += [latlong]

# Create dataframe
df_points['lat_lng'] = latlong_points
df_points['lat_lng'] = df_points.lat_lng.apply(ast.literal_eval)

Figura 5. DataFrame após geocodificação

Observe que agora temos um campo chamado lat_lng que contém a latitude e a longitude dos pontos.

III. Calcular distância de viagem entre pontos

Em seguida é calcular a distância de viagem entre os pontos. É importante no Problema do Caixeiro Viajante, pois a rota mais curta é gerada a partir da distância total percorrida de todas as rotas possíveis. Em vez de usar a distância euclidiana (desenhar uma linha entre os pontos), usaremos uma distância mais relevante que é criar um caminho seguindo a estrada entre os pontos. Este caminho representará a distância entre os pontos.

Para fazer isso, utilizaremos o método shortest_path de networkx. Mas antes disso, devemos criar o DataFrame origem-destino para facilitar o cálculo da distância entre os pontos. Este DataFrame é gerado fazendo todas as combinações/permutações possíveis dos pontos de origem e destino.

# Create dataframe of origin-destination #

# Create variables
list_points_name = df_points['point_name']
# list_points_latlong = df_points['lat_long']
list_points_latlong = df_points['lat_lng']

# All points combinations
list_pair_name = [i for i in itertools.product(list_points_name, repeat=2)]
list_pair_latlong = [i for i in itertools.product(list_points_latlong, repeat=2)]
df_nodes = pd.DataFrame({'pair_name': list_pair_name, 'pair_latlong': list_pair_latlong})

# Source/Target
df_nodes['origin'] = df_nodes['pair_name'].apply(lambda t: t[0])
df_nodes['destination'] = df_nodes['pair_name'].apply(lambda t: t[1])
df_nodes['latlong_origin'] = df_nodes['pair_latlong'].apply(lambda t: t[0])
df_nodes['latlong_destination'] = df_nodes['pair_latlong'].apply(lambda t: t[1])
df_nodes.drop(['pair_name', 'pair_latlong'], axis =1, inplace = True)

Figura 6. DataFrame de origem e destino

Agora, podemos calcular a distância entre os pontos usando networkx.

# Calculate distance from point to point using networkx #

# Location where you want to find your route
place     = 'Bandung, West Java, Indonesia'
# Find shortest route based on the mode of travel
mode      = 'drive'        # 'drive', 'bike', 'walk'
# Find shortest path based on distance or time
optimizer = 'length'        # 'length','time'
# Create graph from OSM within the boundaries of some geocodable place(s)
graph = ox.graph_from_place(place, network_type = mode)

# Create lists
list_route = []
list_route_length = []

# Determining distance and route
for i in range(len(df_nodes)):
  # find the nearest node to the start location
  orig_node = ox.get_nearest_node(graph, df_nodes.iloc[i]['latlong_origin'])
  # find the nearest node to the end location
  dest_node = ox.get_nearest_node(graph, df_nodes.iloc[i]['latlong_destination'])
  #  find the shortest path
  shortest_route = nx.shortest_path(graph,
                                    orig_node,
                                    dest_node,
                                    weight=optimizer)
  shortest_route_length = nx.shortest_path_length(graph, orig_node, dest_node, weight=optimizer)
  # append list
  list_route.append(shortest_route)
  list_route_length.append(shortest_route_length)

Figura 7. Distância entre pontos DataFrame

4. Determine a melhor rota de veículo

Em seguida, podemos determinar a melhor rota para entregar encomendas a todos os clientes utilizando o Google OR-Tools . Primeiro, temos que definir as funções para nos ajudar a encontrar a rota mais curta. Refere-se a esta página com algumas modificações.

def create_data_model(distance_matrix, num_vehicles, depot_order):
    """Stores the data for the problem."""
    data = {}
    data['distance_matrix'] = distance_matrix
    data['num_vehicles'] = num_vehicles
    data['depot'] = depot_order
    return data

def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f'Objective: {solution.ObjectiveValue()}')
    max_route_distance = 0
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        plan_output = 'Route for vehicle {}:\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 += 'Distance of the route: {}m\n'.format(route_distance)
        print(plan_output)
        max_route_distance = max(route_distance, max_route_distance)
    print('Maximum of the route distances: {} m'.format(max_route_distance))

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

# Instantiate the data problem.
data = create_data_model(distance_matrix=distance_matrix, 
                         num_vehicles=1, 
                         depot_order=0)

# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
                                        data['num_vehicles'], data['depot'])

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

# Create and register a transit callback.
transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Add Distance constraint.
dimension_name = 'Distance'
routing.AddDimension(
    transit_callback_index,
    0,  # no slack
    50000,  # vehicle maximum travel distance
    True,  # start cumul to zero
    dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)

# Print solution on console.
if solution:
    print_solution(data, manager, routing, solution)
else:
    print('No solution found !')

Depósito -> Endereço 5 -> Endereço 6 -> Endereço 7 -> Endereço 4 -> Endereço 3 -> Endereço 2 -> Endereço 1 -> Depósito

Esta rota mais curta terá uma distância de cerca de 7,44 km.

V. Crie um caminho para a rota mais eficaz

A visualização de dados é uma das melhores formas de facilitar a compreensão desse caso. Portanto, nesta última etapa, faremos uma visualização dos dados espaciais para retratar a melhor rota. Devemos criar um novo DataFrame que inclua apenas a melhor rota e, em seguida, criar o caminho.

# Create path for the most effective route #

# Create DataFrame of route order
df_nodes_best = pd.DataFrame({'origin' : route_name[:-1], 
                              'destination': route_name[1:]})
df_nodes_best = df_nodes_best.merge(df_nodes, on=['origin', 'destination'], how='inner')
df_nodes_best["route_order"] = [f"Route {i}" for i in range(1, len(df_nodes_best)+1)]
df_nodes_best

# Create lists
list_route_best = []
list_route_length_best = []

# Determining distance and route
for i in range(len(df_nodes_best)):
  # find the nearest node to the start location
  orig_node_best = ox.get_nearest_node(graph, df_nodes_best.iloc[i]['latlong_origin'])
  # find the nearest node to the end location
  dest_node_best = ox.get_nearest_node(graph, df_nodes_best.iloc[i]['latlong_destination'])
  #  find the shortest path
  shortest_route_best = nx.shortest_path(graph,
                                    orig_node_best,
                                    dest_node_best,
                                    weight=optimizer)
  shortest_route_length_best = nx.shortest_path_length(graph, orig_node_best, dest_node_best, weight=optimizer)
  # append list
  list_route_best.append(shortest_route_best)
  list_route_length_best.append(shortest_route_length_best)

# Store best route distance in a list
distance_result_best = list_route_length_best.copy()

# Convert nodes code into lat long
all_list_nodes_latlong = []

for i in range(len(list_route_best)):
  list_nodes_latlong = []
  for j in range(len(list_route_best[i])):
    tuple_nodes_latlong = (graph.nodes[list_route_best[i][j]]['y'], graph.nodes[list_route_best[i][j]]['x'])
    list_nodes_latlong.append(tuple_nodes_latlong)
  all_list_nodes_latlong.append(list_nodes_latlong)

# Load map
my_map = folium.Map(location=[-6.897097, 107.621903],
                    zoom_start=15,
                    tiles='cartodbpositron')

# Plot route polyline
for i in range(len(all_list_nodes_latlong)):
  folium.PolyLine(all_list_nodes_latlong[i],
                  tooltip=f"{df_nodes_best['route_order'].iloc[i].upper()}:\
                  {df_nodes_best['origin'].iloc[i]} to {df_nodes_best['destination'].iloc[i]}\
                  - Distance: {round(distance_result_best[i]/1000, 2)} km",
                  # color=random_color(),
                  weight=5).add_to(my_map)

# Plot points
for i in range(len(df_points)):
  if i != 0:
    folium.Marker(location = df_points['lat_lng'][i], 
                  popup = df_points['point_name'][i]).add_to(my_map)
  else:
    folium.Marker(location = df_points['lat_lng'][i], 
                  popup = df_points['point_name'][i],
                  icon = folium.Icon(color='crimson')).add_to(my_map) # mark depot with red symbology

print(f'Total distance: {round(sum(distance_result_best)/1000, 2)} km')
my_map

      
                
                    
                    
       Figure 8. The shortest route

A solução pode nos ajudar a encontrar as melhores rotas para entregar todas as encomendas aos clientes. A distância mais curta a percorrer é de 7,44 km com o seguinte percurso: