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

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).

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.

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.

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):

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
0	0	548	776	696	582	274	502	194	308	194	536	502	388	354	468	776	662
1	548	0	684	308	194	502	730	354	696	742	1084	594	480	674	1016	868	1210
2	776	684	0	992	878	502	274	810	468	742	400	1278	1164	1130	788	1552	754
3	696	308	992	0	114	650	878	502	844	890	1232	514	628	822	1164	560	1358
4	582	194	878	114	0	536	764	388	730	776	1118	400	514	708	1050	674	1244
5	274	502	502	650	536	0	228	308	194	240	582	776	662	628	514	1050	708
6	502	730	274	878	764	228	0	536	194	468	354	1004	890	856	514	1278	480
7	194	354	810	502	388	308	536	0	342	388	730	468	354	320	662	742	856
8	308	696	468	844	730	194	194	342	0	274	388	810	696	662	320	1084	514
9	194	742	742	890	776	240	468	388	274	0	342	536	422	388	274	810	468
10	536	1084	400	1232	1118	582	354	730	388	342	0	878	764	730	388	1152	354
11	502	594	1278	514	400	776	1004	468	810	536	878	0	114	308	650	274	844
12	388	480	1164	628	514	662	890	354	696	422	764	114	0	194	536	388	730
13	354	674	1130	822	708	628	856	320	662	388	730	308	194	0	342	422	536
14	468	1016	788	1164	1050	514	514	662	320	274	388	650	536	342	0	764	194
15	776	868	1552	560	674	1050	1278	742	1084	810	1152	274	388	422	764	0	798
16	662	1210	754	1358	1244	708	480	856	514	468	354	844	730	536	194	798	0

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.

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:

El siguiente diagrama muestra las rutas asignadas:

¿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:

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.

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.

Publicado por