El Problema de Rutas de Vehículos (VRP)

-Problema de Rutas de Vehículos (del inglés “Vehicle Routing Problem”,

VRP), hace referencia en realidad a un conjunto de problemas de rutas
en los que se dispone de una flota con varios vehículos.
- Gran cantidad de aplicaciones en logística.
- Elementos del VRP:
o Depósito central
o Conjunto de clientes a los que hay que servir
o Conjunto de vehículos situados en el depósito central
o Coste o tiempo de viaje entre cada par de clientes
o Restricciones adicionales (capacidad, ventanas de tiempo…)
- OBJETIVO: Encontrar un conjunto de rutas para los vehículos con coste
total mínimo atendiendo las necesidades de todos los clientes.

4. PROBLEMAS DE RUTAS
 El Problema de Rutas de Vehículos (VRP): Ejemplo

Según las restricciones adicionales que se añaden se obtienen distintas versiones

4. PROBLEMAS DE RUTAS
El VRP con Capacidades (CVRP)

- Problema de Rutas de Vehículos con Capacidades (del inglés “Capacitated

Vehicle Routing Problem”, CVRP), es el problema básico y más sencillo
dentro de los VRP.
- En general, también se hace referencia a él con las siglas VRP.
- Los vehículos tienen una capacidad máxima que no se puede exceder.
DATOS

- Cualquier cliente puede ser servido por cualquier vehículo:

- Si algún arco (i,j) no existe, se pone cij =∞.
- No se admiten lazos, es decir, para todo i, cii =∞.
- Opcionalmente: bk : coste fijo por usar el vehículo k

4. PROBLEMAS DE RUTAS
Modelo de programación matemática del CVRP

VARIABLES DE DECISIÓN

Restricciones de
conservación de flujo (cada
cliente debe ser visitado
una y sólo una vez)

Cada vehículo se usa a lo

sumo una vez (sale del
depósito y entra en él a lo
sumo una vez)

4. PROBLEMAS DE RUTAS
Modelo de programación matemática del CVRP

Rutas continuas

Capacidad máxima vehículos

Variables binarias

Función objetivo

4. PROBLEMAS DE RUTAS
Modelo de programación matemática del CVRP

- Es necesario añadir restricciones de eliminación de subciclos:

4. PROBLEMAS DE RUTAS
Modelo completo del CVRP

4. PROBLEMAS DE RUTAS
El VRP Multidepósito (MDVRP)

- Problema de Rutas de Vehículos Multidepósito (del inglés “Multi Depot

Vehicle Routing Problem”, MDVRP).
- CVRP con varios depósitos donde se almacena la mercancía (y desde
donde salen los vehículos y a donde deben volver).
- Primeras investigaciones: Kulkarni y Bhave (1985): m-TSP, VRP y MDVRP.

Múltiples
aplicaciones
en logística

4. PROBLEMAS DE RUTAS
Modelo para el MDVRP

4. PROBLEMAS DE RUTAS
Modelo para el MDVRP

4. PROBLEMAS DE RUTAS
Modelo para el MDVRP

4. PROBLEMAS DE RUTAS
Modelo para el MDVRP

4. PROBLEMAS DE RUTAS
Modelo para el MDVRP

4. PROBLEMAS DE RUTAS
Modelo para el MDVRP

4. PROBLEMAS DE RUTAS
Modelo para el MDVRP

4. PROBLEMAS DE RUTAS
MDVRP: Flotas fijas a cada depósito

- MDVRP clásico  cada vehículo puede partir de cualquier depósito

- Modificación  cada depósito tiene un número máximo de vehículos

- Es necesario añadir un nuevo conjunto de restricciones

- Se sabe a priori cuántos vehículos parten de cada depósito

En muchos casos es más realista

4. PROBLEMAS DE RUTAS
MDVRP: Vehículos que regresan a otro depósito

- MDVRP clásico  cada vehículo regresa al depósito del que partió

- Modificación  los vehículos pueden regresar a cualquier depósito
- Hay que modificar las restricciones de conservación de flujo

- Si p es un cliente, las restricciones de conservación de flujo se mantienen

para asegurar la obtención de rutas continuas
- Si p es un depósito, se eliminan para permitir rutas abiertas

4. PROBLEMAS DE RUTAS
El VRP Periódico (PVRP)

- Problema de Rutas de Vehículos Periódico (del inglés “Periodic Vehicle

Routing Problem”, PVRP).
- CVRP  Horizonte temporal unitario (por ejemplo 1 día).
- PVPR  Horizonte temporal no unitario (por ejemplo T días).
- Los vehículos realizan sus trayectos diariamente y cada día tienen la opción
de visitar o no a cada cliente, según sea su demanda.

Día 1

Día 2

4. PROBLEMAS DE RUTAS
El VRP Periódico (PVRP)

- Primeras investigaciones: Beltrami y Bodin (1974). Estudian una

aplicación de recogida de basuras con un período de planificación de 6
días y desarrollan tres heurísticas sencillas para su resolución:
1) En una primera fase resuelve el problema de asignación y en la
segunda fase utiliza un algoritmo de rutas
2) Algoritmo de mejora, que parte de la solución obtenida con la
primera heurística y la mejora realizando intercambios de
cadenas (intercambios r-óptimos)
3) Una modificación del algoritmo de los ahorros de Clarke y
Wright (1964) que puede aplicarse a problemas de mayor
tamaño.
- La mayoría de las heurísticas usan 2 fases (íntimamente relacionadas):
o FASE 1: planificación de visitas a clientes en días
o FASE 2: resolución del problema de rutas asociado

4. PROBLEMAS DE RUTAS
El VRP Periódico (PVRP)

DATOS

OBJETIVO: rutas óptimas de los vehículos para cada día satisfaciendo

la demanda de los clientes con la frecuencia requerida

4. PROBLEMAS DE RUTAS
El VRP Periódico (PVRP)

- Para cada cliente hay varias configuraciones de visitas distintas que

cumplen con la frecuencia exigida.
- Cada configuración de un cliente i se denomina Calendario.
- Cada calendario de un cliente i viene determinado por el día inicial

- La longitud de cada calendario (medida auxiliar) es:

  T   1 si w  mod(T , T ) 
  Ti  i 

L(Cw )  
i

  T  si w  mod(T , T ) 
  Ti  i


4. PROBLEMAS DE RUTAS
PVRP : Modelo de Programación Matemática
VARIABLES DE DECISIÓN

o Calendario elegido para cada cliente

1 si para el cliente i se elige el calendario Cwi
ziw  
0 en otro caso i  1,ꞏꞏꞏ, n  w  1,ꞏꞏꞏ, Ti 

o Días de visita para cada cliente

1 si el cliente i es visitado el dia d
yid  
0 en otro caso i  1,ꞏꞏꞏ, n  d  1,ꞏꞏꞏ, T 

o Rutas de los vehículos

1 si el vehiculo k visita el dia d al cliente j justo despues del cliente i
x 
d

i, j  N  0 (i  j ) k  V d  1,ꞏꞏꞏ, T 
ijk
0 en otro caso

o Eliminación de subciclos
u id iN d  1,ꞏꞏꞏ, T 

4. PROBLEMAS DE RUTAS
PVRP : Modelo de Programación Matemática

FUNCIÓN OBJETIVO
T  n n v v n
d 
min     cij  xijk    bk  x0 jk 
d

d 1  i 0 j 0 k 1 k 1 j 1 

RESTRICCIONES DE ASIGNACIÓN
Ti

z
w1
iw 1 i  N

 yid  L(Cwi ) ziw i  N , w  1,ꞏꞏꞏ, Ti 

d Cwi

4. PROBLEMAS DE RUTAS
PVRP : Modelo de Programación Matemática

LIMITACIONES DE LOS VEHÍCULOS


j N
x 0d jk  1  k  V ,  d  1,ꞏꞏꞏ, T 

 i N
x id0 k  1  k  V ,  d  1,ꞏꞏꞏ, T 

 i N
di 
j N  0
d
x ijk  qk  k  V ,  d  1,ꞏꞏꞏ, T 

PROBLEMA DE RUTAS


iN 0
xijkd  
iN 0
x djik  0 j  N  0 , k V , d  1,ꞏꞏꞏ, T 

 
k 1 iN 0
d
xijk  y jd j  N , d  1,ꞏꞏꞏ, T 
i j

4. PROBLEMAS DE RUTAS
PVRP : Modelo de Programación Matemática

ELIMINACIÓN DE SUBCICLOS

uid  nyid i  N , d  1,ꞏꞏꞏ, T 

v
uid  u jd  ( n  1)  xijk
d
n i  j , i, j  N , d  1,ꞏꞏꞏ, T 
k 1

DOMINIO DE LAS VARIABLES

ziw , yid  0,1 i  N , d  1,ꞏꞏꞏ, T  , w  1,ꞏꞏꞏ, Ti 

uid   i  N , d  1,ꞏꞏꞏ, T 

i, j  N  0 , k V ,
d
xijk  0,1
d  1,ꞏꞏꞏ, T  , w  1,ꞏꞏꞏ, Ti 

4. PROBLEMAS DE RUTAS
El VRP con Carga Divisible (SDVRP)

- Problema de Rutas de Vehículos con Carga Divisible (del inglés “Split

Delivery Vehicle Routing Problem”, SDVRP).

- CVRP  La carga de un cliente no puede dividirse en varios envíos y ser

servida por distintos vehículos. Cada cliente es visitado 1 y sólo 1 vez.

- SDVPR  Se permite que un cliente sea servido por varios vehículos.

4. PROBLEMAS DE RUTAS
El VRP con Carga Divisible (SDVRP)

- Fue tratado por primera vez por Dror y Trudeau en 1989.

- Ha tardado en atraer la atención de los investigadores, en comparación

con otras variantes del VRP que han sido notablemente más estudiadas.

- La posibilidad de dividir la carga complica notablemente su resolución.

- Esta versión es realista si la carga a repartir o recoger se puede partir de

forma natural y se puede entregar en distintos instantes de tiempo.

- Tiene multitud de aplicaciones en logística.

4. PROBLEMAS DE RUTAS
SDVRP: Modelo de Programación Matemática
DATOS
Mantenemos la notación utilizada en el modelo del CVRP

VARIABLES DE DECISIÓN

RESTRICCIONES QUE SE MANTIENEN

4. PROBLEMAS DE RUTAS
SDVRP: Modelo de Programación Matemática

RESTRICCIONES NUEVAS PARA EL SDVRP

4. PROBLEMAS DE RUTAS
SDVRP: Restricciones Eliminación Subciclos
- Deben imponer que la solución sea conexa y no tenga subciclos, pero
que permita que un mismo cliente sea visitado varias veces.
- Se obtendrán a partir de las restricciones de eliminación de subciclos
del TSP y el VRP.

(E.1)
reforzando

(E.1’)

V(B) número mínimo de vehículos para satisfacer la demanda de los

clientes de B. Resolver Bin Packing Problem o tomar

- (E.1) y (E.1’) son restricciones de eliminación de

subciclos válidas para el VRP pero no para el SDVRP.

4. PROBLEMAS DE RUTAS
SDVRP: Restricciones Eliminación Subciclos

(E.2)
reforzando

(E.2’)

- (E.2) y (E.2’) son restricciones de eliminación de subciclos válidas para

el CVRP y (E.2’) TAMBIÉN LO SON para el SDVRP.

- (E.1’) y (E.2’) son equivalentes para el CVRP porque el semigrado de

cualquier vértice es 1 en una solución óptima.
- Sin embargo, esto no es así en el SDVRP.

4. PROBLEMAS DE RUTAS
SDVRP: Ejemplo Eliminación Subciclos

B  2,3, 4,5, 6 qk  3 k  1,ꞏꞏꞏ, v 

V ( B)  2
di  1 i   2,3, 4,5 d6  2

4 6 5

2 1 3

Solución válida pero que no verifica (E.1’)

4. PROBLEMAS DE RUTAS
El VRP con Entrega y Recogida (VRPPD)
- Problema de Rutas de Vehículos con Entrega y Recogida de Mercancías
(del inglés “Vehicle Routing Problem with Pickup and Deliveries”, VRPPD).

- CVRP  Todos los clientes son del mismo tipo y demandan todos reparto
o todos entrega de mercancías (ambos problemas son equivalentes).

- VPRPD  Algunos clientes demandan reparto (delivery) y otros entrega

(pick up) de mercancías.

- La existencia de clientes de entrega y recogida es especialmente

importante en las restricciones de capacidad máxima de los vehículos.

- Hay mercancía que sale y otra que entra, ocupando espacio de carga.

-Esto complica notablemente la estructura de las rutas y consecuentemente

la resolución del problema.

- Tratado por primera vez por Wilson, Sussman, Wang y Higonnet (1971):
algoritmos de inserción para problemas de transporte de personas.

4. PROBLEMAS DE RUTAS
Algunas simplificaciones en el VRPPD

1) Cada cliente requiere entrega o recogida de mercancías, Se hace

pero no las dos al mismo tiempo, es decir, no es posible casi
que se tenga una determinada demanda de mercancía siempre
pero a la vez se quiera devolver parte de la que se tiene.

2) La mercancía que se recoge de los clientes a lo largo de la Disminuye

ruta se devuelve directamente al depósito, es decir, no hay mucho la
intercambio de mercancías entre los clientes (no es posible complejidad
que la mercancía que uno devuelve se entregue a otro).

3) Los vehículos deben realizar primero todos los repartos de Versión

mercancías que se les hayan asignado y posteriormente propia: VRP
visitar a los clientes que desean realizar devoluciones, de with
manera que no se mezclen distintos tipos de clientes a lo Backhauls
largo de las rutas. (VRPB)

4. PROBLEMAS DE RUTAS
Modelo de programación matemática (VRPPD)

DATOS

4. PROBLEMAS DE RUTAS
Modelo de programación matemática (VRPPD)

VARIABLES DE DECISIÓN

VARIABLES AUXILIARES

ui i  N para impedir subciclos

FUNCIÓN OBJETIVO

4. PROBLEMAS DE RUTAS
 Modelo de programación matemática (VRPPD)
RESTRICCIONES


iN o ( k )
xijk  
iN d ( k )
x jik  0 k  V , j  N

xijk ( Lki  l j  Lkj )  0 k  V , (i, j )  Ak , j  d (k )

v
ui  u j  (n  m  1) xijk  n  m i, j  N
k 1

4. PROBLEMAS DE RUTAS
 Modelo de programación matemática (VRPPD)

0  Lki  qk  li k  V , i  N d

xijk ( Lki  l j  Lkj )  0 k  V , (i, j )  Ak , j  d (k )

RESTRICCIONES NO LINEALES

( Lki  l j  Lkj )  (1  xijk )qk k  V , (i, j )  Ak , j  d (k )

RESTRICCIONES LINEALES EQUIVALENTES

MODELO DE PROGRAMACIÓN LINEAL ENTERA

4. PROBLEMAS DE RUTAS
El VRP con Ventanas de Tiempo (VRPTW)
- Problema de Rutas de Vehículos con Ventanas de Tiempo (del inglés
“Vehicle Routing Problem with Time Windows”, VRPTW).
- CVRP  No hay restricciones temporales para las visitas a los clientes.
- VPRTW  Sólo puede visitarse a los clientes dentro de unos límites
preestablecidos denominados ventanas de tiempo.
- Las ventanas de tiempo son muy comunes es muchas aplicaciones reales
debido a la existencia de horarios fijos de apertura.
-Tratado por primera vez por Pullen y Webb (1967) en un estudio de casos.

o Versión fuerte: las ventanas de tiempo no se

pueden violar. Los vehículos pueden esperar si
llegan antes de tiempo pero no se les permite
- Dos versiones: llegar tarde. Esta es la versión más estudiada.
o Versión débil: las ventanas de tiempo se
pueden violar pagando una penalización. Menos
estudiada pero en muchos casos más real.

4. PROBLEMAS DE RUTAS
Modelo de programación matemática (VRPTW)

DATOS

N  1,..., n : conjunto de clientes

di : demanda del cliente i
 i , i  : ventana de tiempo del cliente i
V  1,..., v : conjunto de vehículos disponibles
o(k ) : depósito origen del vehículo k
d (k ) : depósito destino del vehículo k
V k  N  o(k ), d (k ) : conjunto de nodos visitables por el vehículo k
Ak  V k  V k : conjunto de arcos transitables por el vehículo k
qk : capacidad del vehículo k
bk : coste fijo del vehículo k
cijk : coste de viaje del vehículo k de i a j
tijk : duración de viaje del vehículo k de i a j

4. PROBLEMAS DE RUTAS
Modelo de programación matemática (VRPTW)

VARIABLES DE DECISIÓN

VARIABLES AUXILIARES

FUNCIÓN OBJETIVO

4. PROBLEMAS DE RUTAS
 Modelo de programación matemática (VRPTW)
RESTRICCIONES COMUNES AL VRPPD


iN o ( k )
xijk  
iN d ( k )
x jik  0 k  V , j  N

RESTRICCIONES NUEVAS

d 
iN
i
jN d ( k )
xijk  qk k  V

4. PROBLEMAS DE RUTAS
Modelo de programación matemática (VRPTW)
RESTRICCIONES NO LINEALES

RESTRICCIONES LINEALIZADAS

Redundante si  j   i  tijk

4. PROBLEMAS DE RUTAS