[SOLVED] 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ón1∪⋯∪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,00
,∈ ≤ −1 paratodosubconjuntode = 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.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 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.042737331272717420262843 711343732608221152897328820231728103143212303814302771151738094427132828149061743910304460CVRP – Clarke and Wright Savings heuristicSolució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=44Utilizamos 4 vehículos 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 número de productos debe ser entregado desde nuestro almacén y otros ciertos productos son recogidos con destino nuestro almacén.Variantes de VRPVehicle 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 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 vehículos pueden hacer más de una ruta.Variantes de VRPVRP con flota heterogénea (HFVRP):• Los vehículos tienen diferentes capacidades, costes de transporte o restricciones temporales.Variantes de VRPVRP 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 VRPVRP 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 VRPGreen 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.