Vehicle Routing Problem: Variantes y ejemplos

¿Qué son los los problemas de optimización de rutas de vehículos?

El concepto de Vehicle Routing Problem (VRP) o Problema de Rutas de Vehículos es una generalización del conocido Traveling Salesman Problem (TSP) o Problema del Viajero. En concreto, el VRP es un problema de optimización pura cuyo objetivo es determinar qué ruta es la más eficiente. Por lo tanto, busca que una flota de vehículos realice sus entregas de bienes o servicios minimizando los costes lo máximo posible.

Básicamente, en TSP se dispone de un mapa de una ciudad con múltiples puntos que un individuo tiene que visitar para volver a su punto de origen realizando la ruta más corta posible. En cambio, el VRP no se limita a solo una persona. De hecho, pueden existir N individuos que, normalmente, deben entregar objetos en diversos puntos de la ciudad. De este modo, el problema se vuelve más complejo que el TSP.

En este artículo, veremos diferentes variantes de este problema y cómo plantear dichas variaciones para implementarlas en el solver de nuestra elección. Para ello, utilizaremos Google OR-Tools como ejemplo.

Vehicle Routing Problem: Variantes

Vehicle Routing Problem con capacidad

El Vehicle Routing Problem con Capacidad o CVRP (Capacitated Vehicle Routing Problem) es una variante del VRP que presenta una restricción consistente en que cada vehículo presenta una capacidad de carga limitada que no puede exceder.

En esta formulación más básica del VRP, tenemos N vehículos, X ciudades y queremos minimizar la distancia total recorrida. Además, es típico añadir una limitación más y es que cada una de las X ciudades tiene que ser abastecida con una cantidad de suministros que llamaremos X_s. A su vez, esto se incluye en el contexto de que cada uno de los N vehículos tiene una capacidad máxima de suministros que puede llevar, que llamaremos N_s. En definitiva, el problema se vuelve más realista al introducir esta restricción.

VRP con estaciones de recarga

Vehicle Routing Problem con Estaciones de Recarga (VRP-CR) es una variante del VRP enfocada en la planificación de rutas de vehículos. En este caso, tiene en cuenta los puntos donde el medio de transporte puede recargar.

Para ello, simplemente hemos de añadir nodos nuevos donde queremos poder recargar. A continuación, proporcionaremos a estos nodos una demanda negativa igual a la capacidad más grande de nuestros vehículos. Después, añadiremos un slack igual de grande y la restricción de que ningún vehículo puede llevar capacidad negativa.

De esta forma, podría haber un vehículo que en su viaje es capaz de poder recargarse con mercancía, lo cual permitiría su reutilización. De lo contrario, un vehículo sólo podría llevar, como mucho, su capacidad.

def add_capacity_constraints(routing, manager, data, demand_evaluator_index):
    """Adds capacity constraint"""
    vehicle_capacities = data["vehicle_capacities"]
    capacity = 'Capacity'
    routing.AddDimensionWithVehicleCapacity(
        demand_evaluator_index,
        30, # Slack equal to max possible load, so reloads can occur
        vehicle_capacities,
        True,  # start cumul to zero
        capacity)
    capacity_dimension = routing.GetDimensionOrDie(capacity)
    for v in range(manager.GetNumberOfVehicles()):
        end = routing.End(v)
        capacity_dimension.SetCumulVarSoftUpperBound(end, 0, 100_000) # End route empty
    # Allow dropping reloading nodes with zero cost.
    for node in [1]:
        node_index = manager.NodeToIndex(node)
        routing.AddDisjunction([node_index], 0)

VRP con carga y descarga en puntos específicos

En esta variante, hemos de añadir la restricción entre el punto A (del que queremos partir) al punto B (al que deseamos llegar), que la distancia recorrida por el vehículo es estrictamente menor en A que B y también que visita ambos nodos. Con esta formulación, también es posible dejar carga en el nodo visitado sin modificar las restricciones. Así pues, es posible indicar que en A recoge 5 objetos pero en B deja otros 5.

De este modo, podemos forzar el movimiento de objetos específicos de nodo A al nodo B. Esto puede ser importante en caso de que ciertos artículos sólo están presentes en un nodo y sean pedidos por otro.

def add_pickup_dropoff(routing, manager, data):      
    # Define Transportation Requests.
    for request in data["pickups_deliveries"]:
        pickup_index = manager.NodeToIndex(request[0])
        delivery_index = manager.NodeToIndex(request[1])
        routing.AddPickupAndDelivery(pickup_index, delivery_index)
        routing.solver().Add(routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index))
        distance_dimension = routing.GetDimensionOrDie('Distance')
        routing.solver().Add(distance_dimension.CumulVar(pickup_index)
            <= distance_dimension.CumulVar(delivery_index))

Vehicle Routing Problem con ventanas temporales

Esta formulación está enfocada en limitar cuándo se puede visitar una ciudad en un intervalo de tiempo válido. Para conseguirlo, es necesario añadir una nueva dimensión, la temporal, que mide en qué intervalo está cada vehículo en el momento del viaje. Con esta dimensión, sólo hemos de añadir la restricción de que si una ciudad es visitada, tiene que ser dentro de la ventana temporal indicada.

De esta manera, podemos añadir la restricción de que sólo un nodo puede ser servido durante ciertos tiempos. Esto es muy útil cuando, por ejemplo, es necesario que un producto llegue antes de cierta hora para ser procesado o servido.

def add_time_window_constraints(routing, manager, data, time_evaluator):
    """Add Time windows constraint"""
    time = 'Time'
    max_time = data['vehicle_max_time']
    routing.AddDimension(
        time_evaluator,
        max_time,  # Alow waiting time ( vehicles can idle )
        max_time,  # Maximum time per vehicle
        False,  
        time)
    time_dimension = routing.GetDimensionOrDie(time)
    # Add time window constraints for each location except depot
    for location_idx, time_window in enumerate(data['time_windows']):
        if location_idx == 0:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
        routing.AddToAssignment(time_dimension.SlackVar(index))
    # Add time window constraints for each vehicle start node
    for vehicle_id in range(data['num_vehicles']):
        index = routing.Start(vehicle_id)
        time_dimension.CumulVar(index).SetRange(data['time_windows'][0][0],
                                                data['time_windows'][0][1])
        routing.AddToAssignment(time_dimension.SlackVar(index))

Ejemplo con todas las restricciones

Para mostrar un problema que aplica todas las formulaciones que hemos mencionado anteriormente, implementamos un modelo que incluye todas esas restricciones.

Este modelo consiste de una flota de vehículos que tienen que transportar, durante un día, a personas de distintos puntos de partida a otros de llegada. Además, tienen una espera máxima permitida.

En cuanto a los datos para este ejemplo, creamos un dataset sintético pequeño. En él, hay 5 hoteles y 1 aeropuerto que poseen diversas necesidades de mover gente a ciertas horas entre esos dos puntos.

Matriz de distancia y tiempo de viaje

A continuación, vemos la matriz de distancias entre todas las localizaciones:

Esta sería la matriz de tiempo de viaje entre entre todas las localizaciones:

Limitaciones temporales

En cuanto a limitaciones temporales, tenemos a un grupo de personas que puede ser recogida hasta 30 minutos después del tiempo de llegada y que puede llegar, como máximo, 60 minutos tras la llegada. En este caso, las órdenes son las siguientes:

Además, en el modelo disponemos de 3 vehículos. Uno de ellos con capacidad de 10 personas y otros dos con espacio para 30.

Ruta de ejemplo

Aplicando todas las restricciones anteriores, generamos esta ruta de ejemplo:

Objective: 13637
dropped orders: []
dropped reload stations: []
Route for vehicle 0:
 Aeropuerto with demand: 0 Vehicle Load(0) Time(0,0) -> 
 Aeropuerto with demand: 20 Vehicle Load(0) Time(20,36) -> 
 EIX Lagotel Holiday Resort with demand: 10 Vehicle Load(20) Time(70,80) -> 
 EIX Lagotel Holiday Resort with demand: -20 Vehicle Load(30) Time(70,80) -> 
 EIX Lagotel Holiday Resort with demand: 20 Vehicle Load(10) Time(70,86) -> 
 Aeropuerto with demand: -10 Vehicle Load(30) Time(114,130) -> 
 Aeropuerto with demand: -20 Vehicle Load(20) Time(114,130) -> 
 Aeropuerto Load(0) Time(114,1500)
Distance of the route: 124km
Load of the route: 0
Time of the route: 114min

Route for vehicle 1:
 Aeropuerto with demand: 0 Vehicle Load(0) Time(0,0) -> 
 Aeropuerto with demand: 10 Vehicle Load(0) Time(0,18) -> 
 PortBlue Club Pollentia Resort & Spa with demand: -10 Vehicle Load(10) Time(42,60) -> 
 PortBlue Club Pollentia Resort & Spa with demand: 10 Vehicle Load(0) Time(70,100) -> 
 EIX Lagotel Holiday Resort with demand: -10 Vehicle Load(10) Time(80,130) -> 
 Aeropuerto Load(0) Time(124,1500)
Distance of the route: 133km
Load of the route: 0
Time of the route: 124min

Route for vehicle 2:
 Aeropuerto with demand: 0 Vehicle Load(0) Time(0,0) -> 
 Aeropuerto with demand: 10 Vehicle Load(0) Time(60,86) -> 
 Aeropuerto with demand: 0 Vehicle Load(10) Time(60,86) -> 
 Universal Hotel Lido Park & Spa with demand: -10 Vehicle Load(10) Time(94,120) -> 
 Aeropuerto with demand: 10 Vehicle Load(0) Time(130,150) -> 
 Aeropuerto with demand: 10 Vehicle Load(10) Time(130,150) -> 
 MLL Mediterranean Bay with demand: -10 Vehicle Load(20) Time(138,180) -> 
 AHOI! Urban Beach with demand: -10 Vehicle Load(10) Time(143,190) -> 
 Aeropuerto Load(0) Time(155,1500)
Distance of the route: 80km
Load of the route: 0
Time of the route: 155min

Total Distance of all routes: 337km
Total Load of all routes: 0
Total Time of all routes: 393min

Conclusión

Tal y como hemos visto, es posible alterar las restricciones del Vehicle Routing Problem para cubrir problemas más específicos. En conclusión, jugar con las limitaciones del modelo permite adaptar el VRP a distintos escenarios reales. Sin embargo, a veces es necesario plantearlo de una forma indirecta debido a la naturaleza de cómo se expresan estas restricciones. Además, en este artículo también hemos generado un problema sencillo donde ocurren las casuísticas analizadas.

Si te ha gustado el post, te animamos a visitar la categoría Algoritmos para ver otros artículos similares a este y a compartirlo en redes. ¡Hasta pronto!