Resolviendo el problema del vendedor ambulante

Nov 29 2022

Optimice las rutas para entregar paquetes usando python para ahorrar costos de entrega (Caso de estudio: entrega de paquetes en Bandung, Indonesia con datos simples) El problema del vendedor ambulante o TSP es un problema de optimización combinatoria que intenta responder a la pregunta “Dada una distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen?”. De manera sencilla, TSP tiene la tarea de encontrar la ruta más corta entre un conjunto de puntos que deben visitarse.

Optimice las rutas para entregar paquetes usando python para ahorrar costos de entrega (caso de estudio: entrega de paquetes en Bandung, Indonesia con datos simples)

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

El Problema del Vendedor Viajero o TSP es un problema de optimización combinatoria que trata de responder a la pregunta “Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa a la ciudad de origen? ”. De manera sencilla, TSP tiene la tarea de encontrar la ruta más corta entre un conjunto de puntos que deben visitarse. Se convierte en un problema real en la industria de la cadena de suministro y la logística a medida que se disparan tras el aumento del comercio electrónico.

Entonces, ¿por qué es importante TSP? En esencia, ayuda a la empresa a obtener más ganancias al ahorrar tiempo y recursos. En la industria de la logística, una de las formas de generar más ganancias es mediante la eficiencia en los costos y tiempos de entrega. Hay varias formas de lograrlo, una de ellas es resolviendo el Problema del viajante de comercio (TSP), donde intenta encontrar las rutas más eficientes para tomar en el camino. Cuanto más eficientemente se resuelve, menos tiempo se pasa conduciendo, más combustible se ahorra, menos horas se necesitan e incluso más paquetes se entregan . Como resultado, el balance de cualquier actividad comercial basada en la entrega se beneficiará dos veces.

Por lo tanto, estoy tratando de crear una demostración de este Problema del vendedor ambulante para un mensajero de una empresa de entrega de paquetes en Bandung para reducir los costos de entrega .

Nota : como esta es una demostración simple, los datos utilizados son solo 8 puntos ficticios de entrega y los datos se generan aleatoriamente.

Guión

Usted es gerente en un centro de servicio de entrega de paquetes en Bandung. Debe entregar paquetes a algunos de los clientes desde su depósito con 1 vehículo. La distribución de los puntos de entrega y el depósito se puede ver a continuación (Figura 1).

Figura 1. Distribución espacial de los puntos de entrega

**De todos modos, puede ajustar la cantidad de vehículos y la cantidad de puntos de entrega como desee editando el código fuente a continuación

Objetivos

Encuentra las mejores rutas para entregar todos los paquetes a los clientes.

Para rastrear qué tan bueno es el modelo o la solución que estamos tratando de implementar, es mejor definir las métricas comerciales. Dado que los datos de casos relacionados no están disponibles, solo mencionaré el potencial sin medir qué tan buena es la solución. Esas posibles métricas comerciales son:

Gastos de envío
Tiempo usado
Tasa de entrega a tiempo
Puntuación de satisfacción de los clientes (puntuación CSAT)

Utilizando Google OR-Tools , la mejor ruta con un vehículo es:

Depósito -> Dirección 5 -> Dirección 6 -> Dirección 7 -> Dirección 4 -> Dirección 3 -> Dirección 2 -> Dirección 1 -> Depósito

Distancia de la ruta: 7,44 km

Figura 2. La animación de la ruta más corta

Pasos técnicos

Figura 3. Diagrama de flujo de procesamiento en Python

El código completo se proporciona aquí .

I. Importar biblioteca y leer datos

Antes de todo, tenemos que importar las bibliotecas a Google Colab. Vamos a utilizar algunas bibliotecas.

numpy y pandas : para operaciones numéricas y manipulación de datos
itertools : para crear iteradores para bucles eficientes
ast : para procesar árboles de la gramática de sintaxis abstracta de Python
solicitudes : para hacer solicitudes HTTP
json : para trabajar con datos JSON
networkx : para la creación, manipulación y estudio de la estructura, dinámica y funciones de redes complejas
osmnx : para descargar datos geoespaciales de OpenStreetMap y modelar, proyectar, visualizar y analizar redes de calles del mundo real y cualquier otra geometría geoespacial
folium : para visualizar datos que han sido manipulados en Python en un mapa de folleto interactivo
ortools : para resolver problemas de optimización combinatoria

# 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. El conjunto de datos del punto de entrega

II. Geocodificación

La geocodificación es el proceso de transformar la descripción de una ubicación, como un par de coordenadas, una dirección o el nombre de un lugar, en una ubicación en la superficie terrestre. En resumen, estamos tratando de recuperar la latitud y la longitud de la dirección del conjunto de datos. Esta latitud y longitud se usarán más adelante para calcular la distancia de viaje entre puntos y determinar la mejor ruta de entrega.

Estoy usando HERE API para la codificación geográfica considerando que es bastante precisa y de uso gratuito (con llamadas limitadas). Puede leer este artículo para conocer los detalles de este proceso.

# 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. Marco de datos después de la geocodificación

Observe que ahora tenemos un campo llamado lat_lng que contiene la latitud y la longitud de los puntos.

tercero Calcular distancia de viaje entre puntos

Lo siguiente es calcular la distancia de viaje entre puntos. Es importante en el problema del viajante de comercio ya que la ruta más corta se genera a partir de la distancia total recorrida de todas las rutas posibles. En lugar de usar la distancia euclidiana (dibujar una línea entre los puntos), usaremos una distancia más relevante que crea un camino siguiendo el camino entre los puntos. Este camino representará la distancia entre puntos.

Para ello, utilizaremos el método shortest_path de networkx. Pero antes de eso, debemos crear el DataFrame origen-destino para que sea más fácil calcular la distancia entre puntos. Este DataFrame se genera haciendo todas las combinaciones/permutaciones posibles de los puntos de origen y 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. Trama de datos de origen y destino

Ahora, podemos calcular la distancia entre puntos 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. Distancia entre puntos DataFrame

IV. Determinar la mejor ruta del vehículo

Luego, podemos determinar la mejor ruta para entregar paquetes a todos los clientes que utilizan Google OR-Tools . Primero, tenemos que definir las funciones que nos ayuden a encontrar la ruta más corta. Hace referencia a esta página con algunas modificaciones.

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 -> Dirección 5 -> Dirección 6 -> Dirección 7 -> Dirección 4 -> Dirección 3 -> Dirección 2 -> Dirección 1 -> Depósito

Esta ruta más corta tendrá una distancia de alrededor de 7,44 km.

V. Crear un camino para la ruta más efectiva

La visualización de datos es una de las mejores formas de facilitar la comprensión de este caso. Por lo tanto, en este último paso, realizaremos una visualización de datos espaciales para representar la mejor ruta. Deberíamos crear un nuevo DataFrame que incluya solo la mejor ruta, luego crear la ruta.

# 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

La solución puede ayudarnos a encontrar las mejores rutas para entregar todos los paquetes a los clientes. La distancia más corta a recorrer es de 7,44 km con la siguiente ruta: