Investigación de operaciones

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

VRP con restricciones de capacidad

Photo of Bryan Salazar López Bryan Salazar López Send an email julio 7, 2021
3.940 14 minutos de lectura

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

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

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

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

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.

Publicaciones relacionadas

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:

CVRP_solucion

El siguiente diagrama muestra las rutas asignadas:

CVRP

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

CVRP_no_solucion

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:

CVRP_solucion_ii

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:

CVRP_solucion_Greedy

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.

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).Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016). The vehicle routing problem: State of the art classification and review. Computers and Industrial Engineering, 99, 300–313.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.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 7, 2021
3.940 14 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.

3 comentarios

  2. hola buen día juan, que excelente explicación de mucha ayuda. He estado aplicando el código pero he tenido un problema en caso que lo he querido aplicar es necesario que los vehículos de transporte tienen poco espacio de almacenamiento no se como indicarles que cuando se queden sin mercancía tengan que regresar al origen por mercancía, si me pudieran ayudar se los agradecería mucho, saludos.

    Responder

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