[SOLVED] CS algorithm Tema 5: Problema de Rutas de Vehiculos

Tema 5: Problema de Rutas de Vehiculos

Vehicle Rounting Problem (VRP)
El problema de enrutamiento de vehiculos es un problema combinatorio de programacion entera.
Cual es el conjunto optimo de rutas de una flota de vehiculos para satisfacer la demanda de un conjunto de clientes?
Fue propuesto por George Dantzig y John Ramser en el 1959.

Vehicle Rounting Problem (VRP)

Vehicle Rounting Problem (VRP)
Caracteristicas:
Es una generalizacion del Problema del Viajante (TSP). Es un problema NP-hard.
Minimizar el coste total de las rutas:
Minimizar el coste total del transporte basado en la distancia total recorrida con los vehiculos utilizados.
Minimizar el numero de vehiculos utilizados satisfacer a todos los clientes.
Minimizar la variacion entre el tiempo de viaje y la carga del vehiculo.
Minimizar las penalizaciones por servicio de baja calidad.

Vehicle Rounting Problem (VRP)
Motivacion:
El uso de programas de optimizacion puede dar ahorros de 5% a companias de transporte.
El transporte por carretera representa el 49 % del total de mercancias transportadas en la UE en 2013.
En 2013, el sector del transporte en la UE contribuyo en un 13 % y un 15 % al total de emisiones primarias de PM10 y PM2,5,
respectivamente.

Bin packing problem
Los articulos de diferentes volumenes deben empaquetarse en un numero finito de contenedores de manera que se minimice el numero de contenedores utilizados.
Los contenedores pueden tener un mismo volumen o cada uno de un volumen diferente determinado.
Es un problema NP-hard.

Bin packing problema 1D
La restriccion es el peso o el volumen en litros.

Bin packing problema 2D
La restriccion son las dimensiones ancho-largo.

Bin packing problema 3D
La restriccion son las dimensiones del volumen del objeto, ancho- largo-alto.

Bin packing problema 1D Modelo Matematico
Dado un conjunto de contenedores 1, 2
Todos los contenedores de la misma capacidad .
Y una lista de n objetos a empaquetar de tamano 1, 2 . Encontrar el numero entero de contenedores . Ylaparticion1delconjuntodeobjetos 1,,.
Consideramos la variable binaria de decision con valor 1 si el contenedor es utilizado. Y las variables binarias si el objeto es empaquetado en el contenedor .

Bin packing problema 1D Modelo Matematico
min= =1
1
=1 =1
= 1 = 1 =1= 0,1 , = 0,1 ,=1

Bin packing problema 1D Solver
Peso de los objetos (Kg)
12
10
8
6
4
2
1
1=
Numero de contenedores necesarios: = 2,86

Bin packing problema 1D Solver
Peso de los objetos (Kg)
x1j
x2j
x3j
suma = 1
12 10 8 6 4 2 1
=SUMA(B2:D2) =SUMA(B3:D3) =SUMA(B4:D4) =SUMA(B5:D5) =SUMA(B6:D6) =SUMA(B7:D7) =SUMA(B8:D8)
y1
y2
y3
=SUMA(B10:D10)
funcion objetivo
ocupacion contenedor
=SUMAPRODUCTO($A$2:$A$8;B2:B8) =SUMAPRODUCTO($A$2:$A$8;C2:C8) =SUMAPRODUCTO($A$2:$A$8;D2:D8)
capacidad 15kg
=15*B10
=15*C10
=15*D10
contenedores necesarios:
=SUMA(A2:A8)/15

Bin packing problema 1D Solver
Peso de los objetos (Kg)
x1j
x2j
x3j
suma = 1
12 10 8 6 4 2 1
1
0
0
1 1 1 1 1 1 1
0
1
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
0
y1
y2
y3
1
1
1
3
funcion objetivo
ocupacion contenedor
15 14 14
capacidad 15kg
15
15
15
contenedores necesarios:
2,86666667

Bin packing problema FFD Algoritmo
First-Fit Algorithm:
El algoritmo procesa los elementos en orden arbitrario.
Para cada objeto, se intenta colocar en el primer contenedor que puede encajar.
Si no se encuentra ningun contenedor, asigne el objeto a un nuevo contenedor.
Calidad de la solucion 2 o

Bin packing problema MFFD Algoritmo
Grande > 1 2
Clasificar los objetos segun su tamano:
M e d i a n o > 31 .
Pequeno > 61
. .
Y enano.
Asignar cada objeto grande un contenedor de manera ordenada.

Bin packing problema MFFD Algoritmo
Avanza por los contenedores asignando los objetos medianos.
En cada uno: si el elemento medio restante mas pequeno no
encaje en el contenedor, omita este contenedor.
De lo contrario, coloque el elemento mediano restante mas grande que quepa.
Avance hacia atras a traves de los contenedores que no contienen un articulo mediano asignando los objetos pequenos.
En cada uno: si los dos articulos pequenos restantes mas pequenos no encajan, omita este contenedor.
De lo contrario, coloque el articulo pequeno restante mas pequeno y el articulo pequeno restante mas grande que quepa.

Bin packing problema MFFD Algoritmo
Avance por todos los contenedores asignando los objetos restantes. Si el elemento restante mas pequeno de cualquier clase de
tamano no encaja, omita este contenedor.
De lo contrario, coloque el articulo mas grande que quepa y permanezca en este contenedor.
Use FFD para empacar los elementos restantes en nuevos contenedores.

Ejercicio 1D MFFD Algoritmo

Ejercicio 2D

Ejercicio 3D

Vehicle Routing Problem (VRP)
Cada cliente es visitado exactamente una vez por un unico vehiculo.
Restricciones:
Cada ruta empieza y finaliza en el almacen = 0.
Funcion objetivo:
donde es el coste de viajar del nodo al nodo .
Determinar el conjunto de rutas con el minimo coste de transporte,

VRP Modelo matematico
min ,
, = 1 paratodonodo=0 j, = 1 paratodonodo=0
0, 0=i,00
, 1 paratodosubconjuntode = 0,1 para todo arco ,

Capacitated Vehicle Routing Problem (CVRP)
Restricciones:
Cada cliente es visitado exactamente una vez por un unico
vehiculo, que debe satisfacer su demanda .
Cada ruta empieza y finaliza en el almacen = 0.
La demanda total asignada aun vehiculo no puede exceder la capacidad del vehiculo .
Funcion objetivo:
Determinar el conjunto de rutas con el minimo coste de transporte,
donde es el coste de viajar del nodo al nodo .

CVRP Clarke and Wright Savings heuristic
=+ 1 1
Utiliza el concepto de ahorro asociado con cada arco para fusionar
rutas.
Inicialmente, cada cliente es visitado por un vehiculo diferente.
En cada paso, el arco con el mayor ahorro se selecciona si y solo si las dos rutas correspondientes se pueden combinar en una nueva ruta factible:
Los dos clientes estan conectados directamente con el almacen.
La demanda de la nueva ruta es inferior a la capacidad del vehiculo.

CVRP Clarke and Wright Savings heuristic
Matriz de costes
012345678 0
1 2 3 4 5 6 7 8
0
45
57
50
42
22
36
14
22
45
0
60
22
14
36
54
32
50
57
60
0
81
71
36
22
58
36
50
22
81
0
10
51
71
36
63
42
14
71
10
0
41
61
28
54
22
36
36
51
41
0
20
22
14
36
54
22
71
61
20
0
41
14
14
32
58
36
28
22
41
0
30
22
50
36
63
54
14
14
30
0
Vehiculos homogeneos con capacidad 10

CVRP Clarke and Wright Savings heuristic
12 = 01 + 02 12 = 45 + 57 60 = 42
112345678
2 3 4 5 6 7 8
Matriz de ahorros:
0
42
73
73
31
27
27
17
42
0
26
28
43
71
13
43
73
26
0
82
21
15
28
9
73
28
82
0
23
17
28
10
31
43
21
23
0
38
14
30
27
71
15
17
38
0
9
44
27
13
28
28
14
9
0
6
17
43
9
10
30
44
6
0

CVRP Clarke and Wright Savings heuristic
12345678 1
2 3 4 5 6 7
8
El mayor ahorro se encuentra en unir las rutas de los clientes 3 y 4.
Obtenemos la ruta 0-3-4-0 con demanda 2+4=6<10.0427373312727174202628437113437326082 21152897328820231728103143212303814302771151738094427132828149061743910304460CVRP Clarke and Wright Savings heuristic12345678 12 3 4 5 6 78El mayor ahorro se encuentra en unir las rutas del cliente 1 con los clientes 3 y 4.Obtenemos la ruta 0-1-3-4-0 con demanda 1+2+4=7<10.042 737331272717420262843711343732608221152897328820231728103143212303814302771151738094427132828149061743910304460CVRP Clarke and Wright Savings heuristic12345678 12 3 4 5 6 78El mayor ahorro se encuentra en unir las rutas de los clientes 2 y 6. Obtenemos la ruta 0-2-6-0 con demanda 1+4=5<10.04273733127271742026284371 1343732608221152897328820231728103143212303814302771151738094427132828149061743910304460CVRP Clarke and Wright Savings heuristic12345678 12 3 4 5 67 8El mayor ahorro se encuentra en unir las rutas delosclientes2y6conel cliente 8.Obtenemos la ruta 0-2-6-8-0 con demanda 1+4+8=13>10.
No es valida!
0
42
73
73
31
27
27
17
42
0
26
28
43
71
13
43
73
26
0
82
21
15
28
9
73
28
82
0
23
17
28
10
31
43
21
23
0
38
14
30
27
71
15
17
38
0
9
44
27
13
28
28
14
9
0
6
17
43
9
10
30
44
6
0

CVRP Clarke and Wright Savings heuristic
12345678 1
2 3 4 5 6 7 8
El mayor ahorro se encuentra en unir las rutas del cliente 5 con los clientes 2 y 6.
Obtenemos la ruta 0-5-2-6-0 con demanda 2+1+4=7<10.042737331272717420262843 711343732608221152897328820231728103143212303814302771151738094427132828149061743910304460CVRP Clarke and Wright Savings heuristicSolucion:0-1-3-4-0 d=7<10 c=119 0-5-2-6-0 d=7<10 c=116 0-7-0 d=8<10 c=28 0-8-0 d=8<10 c=44Utilizamos 4 vehiculos y obtenemos un coste total 307. CVRP Ejercicio 3D: Matriz de costes012345678 01 2 3 4 5 6 7 8045575042223614224506022143654325057600817136225836502281010517136634214711004161285422363651410202214365422716120041141432583628224103022503663541414300 Variantes de VRPVehicle Routing Problem with Backhaul (VRPB): Un numero de productos debe ser entregado desde nuestro almacen y otros ciertos productos son recogidos con destino nuestro almacen.Variantes de VRPVehicle Routing Problem with Pickup and Delivery (VRPPD): Un numero de productos necesita ser movido de cierta ubicacion de recogida hacia otras ubicaciones de entrega. El objetivo es encontrar las rutas optimas para una flota de vehiculos para visitar las ubicaciones de recogida y entregar los productos en sus correspondientes ubicaciones.Variantes de VRPVehicle Routing Problem with Time Windows (VRPTW): Cada cliente tiene una ventana de tiempo, dentro de las cuales se debe hacer la visita.Variantes de VRPVehicle Routing Problem with Multiple Trips (VRPMT): Los vehiculos pueden hacer mas de una ruta.Variantes de VRPVRP con flota heterogenea (HFVRP): Los vehiculos tienen diferentes capacidades, costes de transporte o restricciones temporales.Variantes de VRPVRP con multiples depositos (MDVRP): Disponemos de un conjunto de almacenes y cada ruta de vehiculo debe iniciar y terminar en el mismo deposito.Variantes de VRPVRP Periodico (PVRP): Los clientes requieren el servicio de recoleccion o distribucion en mas de una ocasion durante un horizonte de tiempo determinado. Debe determinarse la frecuencia semanal de servicio, es decir, la frecuencia con que se atiende a cada cliente y el patron de servicio, en otras palabras, definir a que clientes se atendera en que dia de la semana.Variantes de VRPGreen Vehicle Routing Problem (GVRP): Optimizar el consumo de energia del transporte a traves de la armonizacion de los costos ambientales. Los aspectos a tener en cuenta son la velocidad de desplazamiento, el peso de la carga y la distancia de transporte.