Investigación de operaciones

Problema de Enrutamiento de Vehículos (VRP) con Google OR-Tools

Photo of Bryan Salazar López Bryan Salazar López Send an email julio 6, 2021
5.874 13 minutos de lectura

Una de las aplicaciones más importantes del modelamiento de Cadenas de Suministro, es el diseño de red de abastecimiento, en el cual, el diseño de rutas de transporte (enrutamiento de vehículos) cumple un rol importante. Su objetivo es encontrar las mejores rutas para una flota de vehículos que visitan un conjunto de ubicaciones. Por lo general, el objetivo de la optimización se centra en determinar una menor distancia, un menor tiempo o un menor costo total (Ballou, 2004).

¿Qué es un VRP?

Una versión más general del Problema del Agente Viajero básico (TSP), es el problema de enrutamiento de vehículos, ampliamente conocido como VRP, por sus siglas en inglés. La principal diferencia entre el TSP y el VRP consiste en la consideración de varios vehículos en el modelo de enrutamiento (Ver Figura 1), es decir, cómo atender óptimamente a un conjunto de clientes, geográficamente dispersos alrededor de un depósito central, a través de una flota de vehículos homogénea (en su versión más básica – VRP puro) (Clarke & Wright, 1964) (Asghari & Mirzapour Al-e-hashem, 2021).

VRP
Figura 1: Esquema general de un modelo VRP
El modelamiento de rutas de vehículos se encuentra entre los problemas de optimización más estudiados en la literatura académica. Los primeros estudios datan de 1959, cuando Dantzig y Ramser abordaron por primera vez el problema de despacho de camiones homogéneos para atender estaciones de servicio (Dantzig & Ramser, 1959). Posteriormente, Clarke y Wright en 1964, abordaron el problema que consistía en atender un número de clientes geográficamente dispersos, por medio de una flota de vehículos con capacidades heterogéneas, modelo denominado VRP (Vehicle Routing Problem), o Problema de Enrutamiento de Vehículos (Clarke & Wright, 1964). Desde entonces, el modelamiento de rutas de vehículos ha sido uno de los temas más abordados dentro del marco de la investigación de operaciones, la ingeniería industrial, la logística y el transporte.

¿Cuál es la complejidad matemática de un VRP?

Es necesario considerar que, los problemas de enrutamiento de vehículos (VRP) y sus extensiones, están clasificados como problemas de optimización combinatoria.

El número de rutas posibles está determinado por la ecuación (n – 1)!, donde n, es igual al número de ubicaciones que componen el problema de enrutamiento (Ver Figura 2). Un problema con 10 ubicaciones (sin contar el depósito o punto de partida), cuenta con 362880 rutas posibles; mientras un problema con 20 ubicaciones cuenta con 2432902008176640000 rutas posibles. Una búsqueda exhaustiva, que evalúe cada una de las posibles soluciones, garantizaría encontrar la ruta óptima; sin embargo, computacionalmente esta es una cuestión intratable, salvo para los conjuntos de pequeñas soluciones (Google OR-Tools, 2020). En la mayor parte de los casos prácticos se requiere de la consideración de técnicas de optimización de búsqueda inteligente, que puedan arrojar soluciones óptimas, o casi óptimas.

Problemas de ruteo nodos rutas
Figura 2: Cantidad de rutas por número de ubicaciones

La formulación matemática para abordar problemas de enrutamiento de vehículos ha sido ampliamente divulgada. La modelación requiere de la consideración de restricciones de flujo, de balance, de limitación de formación de sub-ciclos, por citar algunas. Hoy por hoy, para efectos de aplicaciones prácticas, lo ideal consiste en utilizar programación basada en restricciones, de manera que los modelos no se aborden en notación algebraica.

El objetivo de este artículo consiste en utilizar las librerías del software Google OR-Tools para abordar problemas de enrutamiento de vehículos (VRP).

El problema (VRP)

Puppis PetShop suministra a las veterinarias de Ciudad de México, diversos productos de cuidado y aseo para mascotas. Cuentan con un pequeño centro de distribución desde el cual abastecen periódicamente a sus clientes, los cuales se localizan tal como se muestra tentativamente en la figura 3.

Problema de enrutamiento de vehículos
Figura 3: Mapa representativo del Centro de Distribución y los clientes

Para efectos de resolver el problema con mayor rapidez, el encargado de levantar la información ha considerado que las distancias entre dos puntos son iguales sin importar el sentido de estos (distancias simétricas).

Las distancias entre el centro distribución (0) y los 16 clientes que deben abastecer se detallan en la siguiente matriz de distancias (metros):

012345678910111213141516
00548776696582274502194308194536502388354468776662
15480684308194502730354696742108459448067410168681210
277668409928785022748104687424001278116411307881552754
36963089920114650878502844890123251462882211645601358
45821948781140536764388730776111840051470810506741244
527450250265053602283081942405827766626285141050708
6502730274878764228053619446835410048908565141278480
71943548105023883085360342388730468354320662742856
830869646884473019419434202743888106966623201084514
91947427428907762404683882740342536422388274810468
1053610844001232111858235473038834208787647303881152354
11502594127851440077610044688105368780114308650274844
1238848011646285146628903546964227641140194536388730
1335467411308227086288563206623887303081940342422536
144681016788116410505145146623202743886505363420764194
15776868155256067410501278742108481011522743884227640798
166621210754135812447084808565144683548447305361947980

Si la compañía tiene 4 camiones, es deseable desarrollar un plan de rutas en el cual se determine cuántos camiones utilizar para minimizar la distancia total recorrida.

Publicaciones relacionadas

Resolución del modelo VRP mediante Google OR-Tools

De acuerdo a lo mencionado en el artículo de introducción a Google OR-Tools, esta herramienta soporta múltiples lenguajes de programación, en esta ocasión, haremos uso del lenguaje de programación Python.

Paso 1: Importar la librería

El siguiente fragmento de código importa las librerías necesarias para resolver un VRP:

# Importar la librería de Google OR-Tools
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

Paso 2: Crear la data del modelo VRP

La data necesaria para modelar un VRP consiste en:

  • matriz_distancias: Una matriz de distancias entre nodos (de acuerdo a una misma unidad de medida)
  • num_vehiculos: Número de vehículos disponibles en la flota.
  • deposito: Cuál es el índice que identifica al depósito (lugar en el cual todos los vehículos inician y terminan su ruta).
def create_data_model():
    """Almacena los datos de entrada del problema"""
    data = {}
    data['matriz_distancias'] = [
        [
            0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,
            468, 776, 662
        ],
        [
            548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
            1016, 868, 1210
        ],
        [
            776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164,
            1130, 788, 1552, 754
        ],
        [
            696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
            1164, 560, 1358
        ],
        [
            582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
            1050, 674, 1244
        ],
        [
            274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,
            514, 1050, 708
        ],
        [
            502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,
            514, 1278, 480
        ],
        [
            194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320,
            662, 742, 856
        ],
        [
            308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662,
            320, 1084, 514
        ],
        [
            194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388,
            274, 810, 468
        ],
        [
            536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,
            730, 388, 1152, 354
        ],
        [
            502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114,
            308, 650, 274, 844
        ],
        [
            388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194,
            536, 388, 730
        ],
        [
            354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0,
            342, 422, 536
        ],
        [
            468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536,
            342, 0, 764, 194
        ],
        [
            776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274,
            388, 422, 764, 0, 798
        ],
        [
            662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730,
            536, 194, 798, 0
        ],
    ]
    data['num_vehiculos'] = 4
    data['deposito'] = 0
    return data

Cada fila y columna de la matriz de distancias tiene un índice de a cuerdo a su posición iniciando desde 0. Así entonces, el índice 0 se reserva en este caso para el depósito.

Paso 2: Definir las salidas del solucionador

El siguiente fragmento de código define la función que imprime la solución del modelo:

def print_solution(data, manager, routing, solution):
    """Imprime la solución sobre la consola"""
    max_route_distance = 0
    for vehicle_id in range(data['num_vehiculos']):
        index = routing.Start(vehicle_id)
        plan_output = 'Ruta para el vehí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 de la ruta: {}m\n'.format(route_distance)
        print(plan_output)
        max_route_distance += route_distance
        max_route_distance = max(route_distance, max_route_distance)
    print('Distancia total de todas las rutas: {}m'.format(max_route_distance))

Paso 3: Definir el punto de entrada del programa

El siguiente fragmento de código define la función principal del programa, e invoca la data de entrada:

def main():
    """Punto de entrada del programa."""
    # Invocar la data de entrada.
    data = create_data_model()

Paso 4: Crear el administrador de índice de rutas

El siguiente código en la sección principal de los programas crea el administrador de índices (administrador) y el modelo de enrutamiento (enrutamiento). El método manager.IndexToNode convierte los índices internos del solucionador (que puede ignorar con seguridad) en números para ubicaciones. Los números de ubicación corresponden a los índices de la matriz de distancias.

    manager = pywrapcp.RoutingIndexManager(len(data['matriz_distancias']),
                                           data['num_vehiculos'], data['deposito'])

Paso 5: Crear el modelo de enrutamiento

El siguiente código crea el modelo de enrutamiento:

    routing = pywrapcp.RoutingModel(manager)

Paso 6: Definir la devolución del llamado de distancia

El siguiente fragmento de código permite crear una función que devuelve la llamada de una distancia entre dos nodos y los pasa al solucionador para su consideración. Es decir, de acuerdo a la matriz de distancias dada, esta función establece, de acuerdo a dos ubicaciones, cual es su distancia correspondiente.

Así mismo, esta función permite establecer los costos del arco (útil para los casos que aborden dimensiones adicionales a las distancias).

def distance_callback(from_index, to_index):
    """Retorna la distancia entre dos nodos"""
    # Convierte desde la variable de ruta Index hacia
    # la matriz de distancia NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['matriz_distancias'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

Paso 7: Adherir una dimensión de distancia

Para resolver un VRP es necesario crear una dimensión que represente la distancia acumulada recorrida por cada vehículo a lo largo de su ruta.

dimension_name = 'Distancia'
routing.AddDimension(
    transit_callback_index,
    0,  # Sin holgura
    3000,  # Distancia máxima de viaje para un vehículo
    True,  # Iniciar el acumulador en cero
    dimension_name)
distance_dimension = routing.GetDimensionOrDie(dimension_name)
distance_dimension.SetGlobalSpanCostCoefficient(100)

Paso 8: Configurar los parámetros de búsqueda

El siguiente código establece los parámetros de búsqueda predeterminados y un método heurístico para encontrar la primera solución:

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

El solucionador considera 14 estrategias de primera solución. En este caso, utilizaremos la estrategia de ruta más corta: PATH_CHEAPEST_ARC.

Paso 9: Invocar el solucionador

El siguiente fragmento de código sirve para invocar el solucionador del modelo:

 solution = routing.SolveWithParameters(search_parameters)

Paso 10: Imprimir la solución

 if solution:
print_solution(data, manager, routing, solution)
else:
print('No se encuentra solución !')

 

Es posible que el desarrollo de los diez pasos anteriores demande algún grado de complejidad subyacente del uso de un lenguaje de programación; sin embargo, es preciso mencionar que, el modelo anterior queda perfectamente configurado, y puede replicarse con modificaciones menores en múltiples problemas de enrutamiento de vehículos básicos (VRP).

¿Cómo ejecutar el modelo?

Alternativa 1, ejecución en nuestro equipo:

Lo primero que debemos considerar, en el caso de que queramos ejecutar este código en nuestro equipo, es que es preciso contar con la instalación de Python en nuestro equipo de cómputo, así mismo debemos contar con la última versión del comando pip y por supuesto, el software OR-Tools. Una guía detallada de la instalación de estos requerimientos la podrás encontrar en el siguiente enlace:

Instalación de OR-Tools para Python

Ahora, lo recomendable es trabajar con algún editor de código práctico (IDE), por ejemplo: Sublime Text, o Spyder (Una herramienta más completa y por ende más robusta y pesada).

Alternativa 2, ejecución en un entorno virtual (Recomendado):

Podemos utilizar del mismo modo, un entorno virtual. En este caso recomendamos el uso de Colaboratory de Google, un entorno que cuenta con todas las herramientas necesarias para nuestros desarrollos. No tendremos que instalar nada en nuestro equipo, y aprovecharemos la potencia de las máquinas de Google.

El código completo de nuestro desarrollo lo presentamos a continuación. También puedes ver el cuaderno de este módulo en nuestro Colaboratory: Problema de Enrutamiento de Vehículos (VRP).

"""Problema de enrutamiento de vehículos simple (VRP)

Ejercicio de ejemplo: MSc. Ing. Bryan Salazar López 2021

"""

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Almacena los datos de entrada del problema"""
    data = {}
    data['matriz_distancias'] = [
        [
            0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354,
            468, 776, 662
        ],
        [
            548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
            1016, 868, 1210
        ],
        [
            776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164,
            1130, 788, 1552, 754
        ],
        [
            696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
            1164, 560, 1358
        ],
        [
            582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
            1050, 674, 1244
        ],
        [
            274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628,
            514, 1050, 708
        ],
        [
            502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856,
            514, 1278, 480
        ],
        [
            194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320,
            662, 742, 856
        ],
        [
            308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662,
            320, 1084, 514
        ],
        [
            194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388,
            274, 810, 468
        ],
        [
            536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764,
            730, 388, 1152, 354
        ],
        [
            502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114,
            308, 650, 274, 844
        ],
        [
            388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194,
            536, 388, 730
        ],
        [
            354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0,
            342, 422, 536
        ],
        [
            468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536,
            342, 0, 764, 194
        ],
        [
            776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274,
            388, 422, 764, 0, 798
        ],
        [
            662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730,
            536, 194, 798, 0
        ],
    ]
    data['num_vehiculos'] = 4
    data['deposito'] = 0
    return data


def print_solution(data, manager, routing, solution):
    """Imprime la solución sobre la consola"""
    max_route_distance = 0
    for vehicle_id in range(data['num_vehiculos']):
        index = routing.Start(vehicle_id)
        plan_output = 'Ruta para el vehí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 de la ruta: {}m\n'.format(route_distance)
        print(plan_output)
        max_route_distance += route_distance
        max_route_distance = max(route_distance, max_route_distance)
    print('Distancia total de todas las rutas: {}m'.format(max_route_distance))



def main():
    """Punto de entrada del programa"""
    # Invocar la data de entrada.
    data = create_data_model()

    # Crea el administrador del índice de rutas.
    manager = pywrapcp.RoutingIndexManager(len(data['matriz_distancias']),
                                           data['num_vehiculos'], data['deposito'])

    # Crea el modelo de enrutamiento.
    routing = pywrapcp.RoutingModel(manager)


    # Crea y registra una devolución de llamada de distancia.
    def distance_callback(from_index, to_index):
        """Retorna la distancia entre dos nodos."""
        # Convierte desde la variable de ruta Index hasta la matriz de distancia NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['matriz_distancias'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define el costo de cada arco.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Adhiere la dimensión de distancia.
    dimension_name = 'Distancia'
    routing.AddDimension(
        transit_callback_index,
        0,  # Sin holgura
        3000,  # Distancia máxima de viaje del vehículo
        True,  # Iniciar el acumulador en cero
        dimension_name)
    distance_dimension = routing.GetDimensionOrDie(dimension_name)
    distance_dimension.SetGlobalSpanCostCoefficient(100)

    # Configurar los parámetros de búsqueda.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    # Solucionador del problema.
    solution = routing.SolveWithParameters(search_parameters)

    # Imprimir la solución en la consola.
    if solution:
        print_solution(data, manager, routing, solution)
    else:
        print('No se encuentra solución !')


if __name__ == '__main__':
    main()

Al ejecutar nuestro desarrollo en Colaboratory, tenemos:

VRP_solucion

El siguiente diagrama muestra las rutas asignadas:

VRP

¿Qué pasaría si se dispone de un vehículo menos?

Las bondades de la programación basada en restricciones nos permiten efectuar este tipo de modificaciones con suma facilidad. Así entonces, modificamos la cantidad de vehículos en los datos de entrada para evidenciar los resultados:

VRP_solucion_II

Los resultados evidencian que, de acuerdo a las condiciones del ejercicio, disponer de un vehículo menos en la flota de transporte, representaría una menor distancia total recorrida. ¿Cómo explicamos este fenómeno? Pues bien, el solucionador con las condiciones actuales, determina que los clientes que deberían ser visitados por el cuarto vehículo se distribuyan en los vehículos restantes; esto implica que por lo menos, un vehículo no tendrá que desplazarse desde y hacia el depósito, lo cual puede incidir en la distancia total recorrida.

Ahora bien, en la práctica los vehículos presentan una capacidad limitada, ya sea por volumen, peso, tiempo, combustible, entre otros, lo cual suele restringir aún más el modelo de transporte. Es muy probable que en la práctica no fuese posible reasignar los clientes desatendidos ante la disponibilidad de un vehículo menos en la flota de transporte.

El modelo de problema de enrutamiento de vehículos simple (VRP) y el script del solucionador quedaron desarrollados en un lenguaje de programación estándar y ampliamente utilizado. Desde luego, las posibilidades de integrar datos de entrada y procesar los datos de salidas son interesantes. Por ejemplo, es posible desarrollar un script mediante el cual el código ya desarrollado tome los datos de entrada desde un archivo de Excel, o desde un servidor externo.

También, es posible desarrollar una interfaz amigable desde la cual se ingrese la información; o vincular los datos de salida con algún modelo o documento determinado.

En próximos artículos abordaremos las distintas variaciones del modelo general de enrutamiento de transporte, como es el caso de los CVRP, VRPTW y muchos más, como por ejemplo, aplicaciones desde las cuales se integre Google Maps a un modelo de enrutamiento.

Fuente
Salazar López, B. A. (2021). Modelo de abastecimiento de aceite usado de cocina para la producción sostenible de biodiésel. Universidad Autónoma de Occidente (UAO).Ballou, R. H. (2004). Logística. administración de la cadena de suministro (Pearson Educación (ed.); Quinta).Clarke, G., y Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568-581.Asghari, M., y Mirzapour Al-e-hashem, S. M. J. (2021). Green vehicle routing problem: A state-of-the-art review. International Journal of Production Economics, 231(June 2020), 107899.Google OR-Tools. (2020b). Vehicle Routing. https://developers.google.com/optimization/routing
Etiquetas
Photo of Bryan Salazar López Bryan Salazar López Send an email julio 6, 2021
5.874 13 minutos de lectura
Photo of Bryan Salazar López

Bryan Salazar López

Ingeniero Industrial y Magíster en Logística Integral especializado en productividad y modelamiento de procesos bajo dimensiones de sostenibilidad, industria 4.0, transformación digital y modelos de optimización. Docente universitario de pregrado y posgrado con experiencia en la enseñanza de estos temas. Fundador de Ingenieriaindustrialonline.com, un sitio en donde se recogen las aportaciones de investigaciones, artículos y referencias relevantes para la industria.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Botón volver arriba