ensayos

PROBLEMA DEL
TRANSPORTE
VRP
(VEHICLE ROUTING PROBLEM)

Contenido
•
•
•
•
•
•
•
•

Entorno.
Definición VRP.
Instancia de VRP.
Formulación con PLE (modelo).
Ejemplo instancia VRP con PLE.
Variantes del problema de VRP.
Técnicas de solución de VRP.
Conclusiones.

Entorno
Optimización combinatoria

Estudia el modelado y solución algorítmica de problemas
donde se buscamaximizar o minimizar una función de
varias variables definidas sobre un conjunto discreto
[Papadimitriou]

Entorno
Aplicaciones de Optimización Combinatoria

•
•
•
•
•
•
•

Industria, logística y ciencia.
Ingeniería y administración de empresas.
Ruteo y carga de vehículos en redes de distribución.
Diseño de redes de telecomunicaciones.
Planificación de la producción.
Asignaciónde tripulación en líneas aéreas.
Planificación de la generación de la electricidad.

Complejidad VRP

El problema del transporte (VRP) se encuentra dentro
de la denominada clase de problemas NP-completos
(el esfuerzo por encontrar una solución óptima crece de
manera exponencial con el tamaño del problema).

Teoría de complejidad
CLASIFICACIÓN EN
BASE AL TIPO DE
ALGORITMO QUE LORESUELVE

VRP

NP-COMPLET0

Definición VRP
Antecedentes VRP

Definición VRP
Definición general del VRP

El problema del transporte (VRP) es un nombre genérico
aplicado a una clase de problemas en los que debe
determinarse un conjunto de rutas para una flota de
vehículos que parten de uno o más depósitos o
almacenes para satisfacer la demanda de varios
clientes dispersosgeográficamente [Dantzing].

Variables involucradas en el planteamiento de una
instancia del problema VRP

•
•
•
•
•
•
•
•

Cantidad de los clientes.
Localización de los clientes.
Centros de distribución.
Capacidad de vehículos.
Demandas de los clientes.
Tiempo de transportación.
Costo de transportación.
Descripción de las vías de transporte.

Parámetros VRP
• Visitas. Entregas orecolección de paquetes.
• Depósitos. Donde comienzan todas las rutas y donde
terminan.
• Localizaciones geográficas tiempo/distancia origendestino.

Parámetros VRP
• Vehículos. Los vehículos que realizan los viajes (flota
homogénea todos los vehículos son iguales o
heterogénea).
• Capacidades. Las que se observan en el vehículo,
como es carga total, volumen total, número de lasplataformas entre otras.
• Pesos. Son el
localizaciones.

costo

de

recorrido

entre

las

Parámetros VRP

Instancia de VRP
•
•
•
•
•
•

5 Visitas por ruta.
2 Depósitos.
Localizaciones geográficas (a 30 minutos una de otra).
10 Vehículos (heterogéneos).
Capacidades (20 paquetes).
Pesos (no mayor a 200.00 pesos entre localidad y
localidad).

VRP
• La solución para VRPpuede ser dependiendo de la
instancia con métodos formales, heurísticas y meta
heurísticas.
• Para instancias pequeñas podemos formularlo como
modelo de PLE.
• Para instancias mayores el comportamiento es
exponencial entonces es necesario modelarlo de manera
general como un grafo.

Formulación de VRP
para modelo de PLE

La formulación para VRP de manera general con
programación linealentera es:
-Sea Z el costo total de distribución.
-Sea Xij (i =1,2,3,...m; j =1,2,3,...n) el número de
unidades que se distribuyen del origen i al destino j.

Formulación de VRP
para modelo de PLE
m

∑ ∑c x

Minimizar Z =

i =1

n

Sujeta a:
m

∑

j =1

∑x
i =1

n

ij

= si

x ij = d
xij ≥ 0

j =1

ij ij

para i=1,2,3…m

j

para j=1,2,3…n
para toda iy j

Formulación de VRP
para modelo de PLE
Tabla de costos
j

i
Origen

Demanda

Destino
1
2

1
2
.
.
.
.
.
M

C11 C12
C21 C22

Recursos
…

…
….

n

C1n
C2n

.
.
.
.
.
..
.

Cm1 Cm2
d 1 d2

S1
S2
.
.
.
.
..

Cmn

…

……

dn

Sm

Ejemplo VRP
para instancia pequeña PLE

Un Problema de Transporte:
• El objetivo es encontrar...