CS代考计算机代写 algorithm Tema 5: Problema de Rutas de Vehículos
Tema 5: Problema de Rutas de Vehículos
Vehicle Rounting Problem (VRP)
•El problema de enrutamiento de vehículos es un problema combinatorio de programación entera.
• ¿Cuál es el conjunto óptimo de rutas de una flota de vehículos 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)
Características:
• Es una generalización 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 vehículos utilizados.
• Minimizar el número de vehículos utilizados satisfacer a todos los clientes.
• Minimizar la variación entre el tiempo de viaje y la carga del vehículo.
• Minimizar las penalizaciones por servicio de baja calidad.
Vehicle Rounting Problem (VRP)
Motivación:
• El uso de programas de optimización puede dar ahorros de 5% a compañías de transporte.
• El transporte por carretera representa el 49 % del total de mercancías transportadas en la UE en 2013.
• En 2013, el sector del transporte en la UE contribuyó en un 13 % y un 15 % al total de emisiones primarias de PM10 y PM2,5,
respectivamente.
Bin packing problem
• Los artículos de diferentes volúmenes deben empaquetarse en un número finito de contenedores de manera que se minimice el número 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 restricción es el peso o el volumen en litros.
Bin packing problema – 2D
• La restricción son las dimensiones ancho-largo.
Bin packing problema – 3D
• La restricción son las dimensiones del volumen del objeto, ancho- largo-alto.
Bin packing problema – 1D – Modelo Matemático
• Dado un conjunto de contenedores 1, 2 …
• Todos los contenedores de la misma capacidad .
• Y una lista de n objetos a empaquetar de tamaño 1, 2 … . • Encontrar el numero entero de contenedores . •Ylapartición 1∪⋯∪ delconjuntodeobjetos 1,…, .
• Consideramos la variable binaria de decisión 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 Matemático
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=
Número 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)
función objetivo
ocupación 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
función objetivo
ocupación 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 ningún contenedor, asigne el objeto a un nuevo contenedor.
• Calidad de la solución ≤ 2 ó 䫿
Bin packing problema – MFFD Algoritmo
• Grande > 1 2
• Clasificar los objetos según su tamaño:
• M e d i a n o > 31 .
• Pequeño > 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 más pequeño no
encaje en el contenedor, omita este contenedor.
• De lo contrario, coloque el elemento mediano restante más grande que quepa.
• Avance hacia atrás a través de los contenedores que no contienen un artículo mediano asignando los objetos pequeños.
• En cada uno: si los dos artículos pequeños restantes más pequeños no encajan, omita este contenedor.
• De lo contrario, coloque el artículo pequeño restante más pequeño y el artículo pequeño restante más grande que quepa.
Bin packing problema – MFFD Algoritmo
• Avance por todos los contenedores asignando los objetos restantes. • Si el elemento restante más pequeño de cualquier clase de
tamaño no encaja, omita este contenedor.
• De lo contrario, coloque el artículo más 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 único vehículo.
Restricciones:
• Cada ruta empieza y finaliza en el almacén = 0.
Función objetivo:
donde es el coste de viajar del nodo al nodo .
• Determinar el conjunto de rutas con el mínimo coste de transporte,
VRP – Modelo matemático
min , ·
, = 1 paratodonodo ≠0 j, = 1 paratodonodo ≠0
0, 0 =i,0 0
, ∈ ≤ −1 paratodosubconjunto de = 0,1 para todo arco ,
Capacitated Vehicle Routing Problem (CVRP)
Restricciones:
• Cada cliente ∈ es visitado exactamente una vez por un único
vehículo, que debe satisfacer su demanda ≥ .
• Cada ruta empieza y finaliza en el almacén = 0.
• La demanda total asignada aun vehículo no puede exceder la capacidad del vehículo .
Función objetivo:
• Determinar el conjunto de rutas con el mínimo 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 vehículo 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 están conectados directamente con el almacén.
• La demanda de la nueva ruta es inferior a la capacidad del vehículo.
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
Vehículos 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.
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 1 con los clientes 3 y 4.
Obtenemos la ruta 0-1-3-4-0 con demanda 1+2+4=7<10.
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 2 y 6. Obtenemos la ruta 0-2-6-0 con demanda 1+4=5<10.
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 delosclientes2y6conel cliente 8.
Obtenemos la ruta 0-2-6-8-0 con demanda 1+4+8=13>10.
¡No es válida!
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.
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
Solución:
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=44
Utilizamos 4 vehículos y obtenemos un coste total 307.
CVRP – Ejercicio 3D:
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
Variantes de VRP
Vehicle Routing Problem with Backhaul (VRPB):
• Un número de productos debe ser entregado desde nuestro almacén y otros ciertos productos son recogidos con destino nuestro almacén.
Variantes de VRP
Vehicle Routing Problem with Pickup and Delivery (VRPPD):
• Un número de productos necesita ser movido de cierta ubicación de recogida hacia otras ubicaciones de entrega. El objetivo es encontrar las rutas óptimas para una flota de vehículos para visitar las ubicaciones de recogida y entregar los productos en sus correspondientes ubicaciones.
Variantes de VRP
Vehicle Routing Problem with Time Windows (VRPTW):
• Cada cliente tiene una ventana de tiempo, dentro de las cuales se debe hacer la visita.
Variantes de VRP
Vehicle Routing Problem with Multiple Trips (VRPMT): • Los vehículos pueden hacer más de una ruta.
Variantes de VRP
VRP con flota heterogénea (HFVRP):
• Los vehículos tienen diferentes capacidades, costes de transporte o restricciones temporales.
Variantes de VRP
VRP con múltiples depósitos (MDVRP):
• Disponemos de un conjunto de almacenes y cada ruta de vehículo debe iniciar y terminar en el mismo depósito.
Variantes de VRP
VRP Periódico (PVRP):
• Los clientes requieren el servicio de recolección o distribución en más de una ocasión 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 patrón de servicio, en otras palabras, definir a que clientes se atenderá en que día de la semana.
Variantes de VRP
Green Vehicle Routing Problem (GVRP):
• Optimizar el consumo de energía del transporte a través de la armonización 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.
