Investigación de operaciones

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

VRP con restricciones de capacidad

Las variaciones del problema de enrutamiento de vehículos simple (VRP), tienen como objetivo adherir al modelo base restricciones que le permitan ajustarse con mayor rigurosidad a un contexto operacional real.

¿Qué es un CVRP?

El problema de enrutamiento de vehículos capacitados (CVRP), también conocido como VRP con restricciones de capacidad; es una variación del VRP básico, en el que los vehículos con capacidad de carga limitada necesitan recoger o entregar artículos en varios lugares. Los artículos tienen un valor (cantidad) asociado a magnitudes como peso o volumen, y los vehículos tienen una capacidad máxima que pueden transportar (en las mismas magnitudes). El problema consiste en recoger o entregar los artículos de forma óptima (según el criterio de optimización), sin exceder la capacidad de los vehículos (Braekers et al., 2016).

Figura 1: Esquema general de un modelo CVRP

De acuerdo a lo anterior, cada nodo que debe visitarse tendrá asociado una cantidad (demanda) que se acumulará en cada vehículo en la medida en que este lo visite (Figura 1); de tal manera que se hace necesario considerar una nueva dimensión en el modelo. Del mismo modo, cada vehículo contará con una capacidad limitada. En el caso en que todos los vehículos que componen la flota cuenten con la misma capacidad, el problema se denomina de capacidad homogénea, y en la caso de que esta capacidad sea diferente, se considera un problema de capacidad heterogénea (HFVRP).

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.

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 con restricciones de capacidad (CVRP).

El problema (CVRP)

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

Figura 2: Mapa representativo del Centro de Distribución, los clientes y la demanda asociada

Desde el Centro de Distribución se consolidan los diferentes productos que demanda cada cliente en pallets o estibas. La demanda asociada a cada cliente puede apreciarse en la Figura 2 (estibas / carga paletizada).

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

La compañía cuenta con 4 camiones, cada uno de los cuales tiene una capacidad máxima de 15 estibas. 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 CVRP 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 CVRP

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).
  • demanda: Cada ubicación tiene una demanda correspondiente a la cantidad, por ejemplo, peso o volumen, del artículo a recoger. En el caso de nuestro problema serán pallets o estibas.
  • capacidad_vehiculos: Cada vehículo tiene una capacidad: la cantidad máxima que puede contener el vehículo. A medida que un vehículo viaja a lo largo de su ruta, la cantidad total de artículos que transporta nunca puede exceder su capacidad. En el caso de nuestro problema serán 15 pallets o estibas.
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
    data['demanda'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
    data['capacidad_vehiculos'] = [15, 15, 15, 15]
    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. El orden de la data es importante, así entonces, podemos apreciar que la demanda asociada a cada nodo se ordena de acuerdo al índice de cada cliente, partiendo con una demanda de 0 pallets asociada al depósito.

Ya que el problema considera la disponibilidad de 4 vehículos, el vector de entrada de la capacidad de la flota tendrá 4 datos correspondientes a la capacidad de cada uno de ellos. Para efectos de nuestro ejemplo se trata de capacidad homogénea.

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):
    """Imprimir la solución en la consola."""
    total_distance = 0
    total_load = 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
        route_load = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += data['demanda'][node_index]
            plan_output += ' {0} Pallets({1}) -> '.format(node_index, route_load)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += ' {0} Pallets({1})\n'.format(manager.IndexToNode(index),
                                                 route_load)
        plan_output += 'Distancia de la ruta: {}m\n'.format(route_distance)
        plan_output += 'Pallets entregados en la ruta: {}\n'.format(route_load)
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print('Distancia total de todas las rutas: {}m'.format(total_distance))
    print('Pallets entregados en todas las rutas: {}'.format(total_load))

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: Definir la devolución del llamado de demanda y crear la restricción de capacidad

Además de la devolución de llamada a distancia, el solucionador también requiere una devolución de llamada de demanda, que devuelve la demanda en cada ubicación y una dimensión para las limitaciones de capacidad. 
    def demand_callback(from_index):
        """Retorna la demanda asociada a cada nodo"""
        # Convierte  desde la variable de ruta Index hacia
        # la matriz de distancia NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data['demanda'][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(
        demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # Sin holgura en la capacidad de los vehículos
        data['capacidad_vehiculos'],  # Capacidad máxima de los vehículos
        True,  # Iniciar el acumulador en cero
        'Capacity')

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

El siguiente código establece los parámetros de búsqueda predeterminados, un método heurístico para encontrar la primera solución y la metaheurística del modelo: 
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.FromSeconds(15)

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

El solucionador considera 6 opciones de búsqueda local:

  • Automática: AUTOMATIC
  • Algoritmo voraz: GREEDY_DESCENT
  • Búsqueda local guiada: GUIDED_LOCAL_SEARCH
  • Algoritmo de recocido simulado: SIMULATED_ANNEALING
  • Búsqueda tabú: TABU_SEARCH
  • Búsqueda de objetivos tabú: OBJECTIVE_TABU_SEARCH

Generalmente, la metaheurística que presenta mejores resultados en modelos de enrutamiento corresponde a la búsqueda local guiada, razón por la cual utilizaremos esta opción en nuestro solucionador.

Respecto a los parámetros de búsqueda, limitaremos al solucionador a 15 segundos de ejecución.

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 Capacitados (CVRP).

"""Problema de enrutamiento de vehículos capacitados (CVRP)

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
    data['demanda'] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8] 
    data['capacidad_vehiculos'] = [15, 15, 15, 15]
    return data


def print_solution(data, manager, routing, solution):
    """Imprimir la solución en la  consola."""
    total_distance = 0
    total_load = 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
        route_load = 0
        while not routing.IsEnd(index):
            node_index = manager.IndexToNode(index)
            route_load += data['demanda'][node_index]
            plan_output += ' {0} Pallets({1}) -> '.format(node_index, route_load)
            previous_index = index
            index = solution.Value(routing.NextVar(index))
            route_distance += routing.GetArcCostForVehicle(
                previous_index, index, vehicle_id)
        plan_output += ' {0} Pallets({1})\n'.format(manager.IndexToNode(index),
                                                 route_load)
        plan_output += 'Distancia de la ruta: {}m\n'.format(route_distance)
        plan_output += 'Pallets entregados en la ruta: {}\n'.format(route_load)
        print(plan_output)
        total_distance += route_distance
        total_load += route_load
    print('Distancia total de todas las rutas: {}m'.format(total_distance))
    print('Pallets entregados en todas las rutas: {}'.format(total_load))



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 restricción de capacidad.
    def demand_callback(from_index):
        """Retorna la demanda asociada a cada nodo"""
        # Convierte desde la variable de ruta Index hacia
        # la matriz de distancia NodeIndex.
        from_node = manager.IndexToNode(from_index)
        return data['demanda'][from_node]

    demand_callback_index = routing.RegisterUnaryTransitCallback(
        demand_callback)
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # Sin holgura en la capacidad de los vehículos
        data['capacidad_vehiculos'],  # Capacidad máxima de los vehículos
        True,  # Iniciar el acumulador en cero
        'Capacity')

    # Configurar los parámetros de búsqueda.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.FromSeconds(15)

    # 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?

En el artículo de VRP simple abordamos esta misma pregunta, ya que no existían restricciones de capacidad. Así entonces, pudimos observar el impacto en el modelo de disminuir una unidad de transporte de la flota. Ahora bien, en el caso del presente modelo es preciso que la sumatoria de las demandas sea igual o inferior a la sumatoria de las capacidades de la flota de transporte; en caso contrario el modelo no hallará solución.

Esta es quizá la principal limitación del modelo CVRP tal como se ha abordado hasta el momento, puesto que si bien adiciona al modelo básico del VRP las restricciones de capacidad, no considera una situación normal de cualquier contexto operacional: que la demanda sea superior a la capacidad de la flota de transporte.

Ahora bien, existen variaciones del modelo CVRP que considera la posibilidad de que la demanda supere la capacidad de la flota de transporte: CVRP con penalizaciones y abandonos, modelos que abordaremos en próximos artículos.

¿Qué pasaría si uno de los vehículos cuenta con una mayor capacidad de transporte?

Consideremos el hecho de que uno de los vehículos de la flota tenga una capacidad de carga superior al resto: 25 pallets para ser exacto. En este caso nuestro modelo corresponde a un problema de enrutamiento de vehículos capacitados con flota de transporte heterogénea (HFVRP). Tal como se ha formulado el modelo, podemos evidenciar los resultados de este planteamiento, por lo tanto modificamos la capacidad de uno de los vehículos (vehículo 3).

Los resultados obtenidos son:

Podemos evidenciar que la consideración de un vehículo de mayor capacidad (25 pallets), permite que el modelo evalúe rutas más eficientes, ya que, incluso considerando el uso de las 4 unidades de transporte, logra una distancia total recorrida menor (5844 m) a la obtenida en el problema original (6208m).

¿Qué pasaría si empleo una metaheurística alternativa?

Tal como lo mencionamos en el artículo de VRP, los problemas de ruteo corresponden a la categoría de optimización combinatoria, esto implica que requieran de metaheurísticas dada la cantidad de posibles soluciones. De acuerdo a lo citado en el paso 8, es posible utilizar diversas metaheurísticas en Google Or-Tools, algunas de las cuales pueden arrojar resultados diferentes.

Siguiendo con el planteamiento del anterior interrogante (¿Qué pasaría si uno de los vehículos cuenta con mayor capacidad de transporte?), vamos a abordar el modelo haciendo uso de la metaheurística de algoritmo voraz.

Modificamos los parámetros de búsqueda:

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GREEDY_DESCENT)
    search_parameters.time_limit.FromSeconds(15)

La solución obtenida:

Podemos observar que esta metaheurística arroja un resultado (6208 m) menos satisfactorio que el logrado por medio de búsqueda local guiada (5844 m).

El modelo de problema de enrutamiento de vehículos capacitados (CVRP) 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 de enrutamiento de transporte, como es el caso de los VRPTW (ventanas de tiempo) y los modelos CVRP con penalizaciones y abandonos.

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
Bryan Salazar López
Etiquetas: CVRPGoogle OR-ToolsOptimizaciónProblema de enrutamiento de vehículosProblemas de ruteoPythonRuteoTSPVRP

Entradas recientes

El sentido común y la Teoría de Restricciones (TOC)

En una pequeña comunidad agrícola en Michoacán, México, un niño llamado José Hernández soñaba con…

hace % días

La restricción nos blinda contra las malas noticias

Sábado por la mañana, Robert acaba de acompañar a su mujer a su clase de…

hace % días