Doctorado en Ingeniería · 2017
Algoritmos de solución para el problema multidepósito y multiobjetivo de ruteo de vehículos considerando recogida de productos y restricción de precedencia
En esta tesis se presenta la aplicación de diferentes técnicas heurísticas y metaheurísticas para la solución del problema de ruteo de vehículos con restricción de precedencia, heurísticas como el vecino más cercano y la del ahorro con inserción secuencial, y metaheurísticas como búsqueda tabú y optimización por colonia de hormigas son utilizadas y ajustadas para resolver eficientemente diferentes variantes del problema de ruteo de vehículos con entrega y recogida de paquetes con restricción de precedencia, considerando el caso monodepósito y multidepósito, mono y multiobjetivo. Cada ruta realizada consta de una sub-ruta en la que se realiza sólo la tarea de entrega y otra sub-ruta en la que se realiza sólo el proceso de recolección, esta última se inicia solo cuando el vehículo está vacío. Los algoritmos y metaheurísticas propuestas tratan de encontrar el mejor orden para visitar a los clientes en cada ruta realizada. Además, el enfoque propuesto determina la mejor conexión entre los sub-rutas de entrega y recogida, con el fin de obtener una solución global minimizando el número de vehículos, la distancia recorrida, el tiempo empleado y la cantidad de energía consumida por los vehículos. El estudio multiobjetivo permitió encontrar un conjunto de soluciones ordenadas en los frentes de Pareto considerando el concepto de dominancia. Adicionalmente, para el modelo multiobjetivo, se plantea la metodología de ponderaciones de los valores de cada función objetivo se selecciona una alternativa de solución con dominancia en el número de vehículos usados. La eficacia del enfoque propuesto se examina teniendo en cuenta un conjunto de casos adaptados de la literatura. También, se propone un modelo exacto, el cual es resuelto mediante la técnica de rutas abiertas con enlace óptimo. Los resultados computacionales muestran resultados de alta calidad en tiempos de procesamiento competitivos. Los resultados computacionales se comparan con los existentes en la literatura especializada y entre los diferentes algoritmos propuestos. Por último, se presentan las conclusiones y sugerencias para trabajos futuros.
Texto completo 133 páginas con texto
Leer la tesis completa Ficha en el repositorio
Contenido
- Figura 1. Ruteo abierto de vehículos con restricción de capacidad – OCVRPp. 27
- Figura 2. Ruteo de vehículos con restricción de capacidad – CVRPp. 28
- Figura 3. Ruteo de vehículos con Backhauls – VRPBp. 28
- Figura 4. Ruteo mixto de vehículos con backhauls – MVRPBp. 29
- Figura 5. Ruteo mixto de vehículos multi-depósito con backhauls – MVRPBp. 30
- Figura 6. Ruteo mixto vehículos con ventana de tiempo y backhauls – MVRPBTWp. 31
- Figura 7. Ruteo de vehículos con entrega y recolección – VRPSDPp. 32
- Figura 8. Ruteo de vehículos con backhauls en forma de lazop. 33
- Figura 9. Ruteo de vehículos multi-depósito sin recargap. 34
- Figura 10. Ruteo de vehículos multi-depósito con recarga (los clientes Backhaul son depósitos)p. 34
- Figura 11. Categoria revistas articulos revisados - VRPBp. 35
- Figura 12. Publicaciones según heurística, metaheurística y modelo EXACTO – VRPBp. 36
- Figura 13. Publicaciones según tipos de heurística y metaheurística utilizadas - VRPBp. 37
- Figura 14. Publicaciones según número de depósitos - VRPBp. 37
- Figura 15. Publicaciones según tipo de funcion objetivo – VRPBp. 38
- Figura 16. Publicaciones según numero de articulos por pais – VRPBp. 38
- Figura 17. Publicaciones según numero de articulos por año - VRPBp. 39
- Figura 18. Publicaciones según autores con más de dos (2) publicaciones en VRPBp. 39
- Figura 19. Codificación de una alternativa de soluciónp. 55
- Figura 20. Movimiento de acuerdo al primer criterio de vecindadp. 55
- Figura 21. Movimiento de acuerdo al segundo criterio de vecindadp. 56
- Figura 22. Movimiento de acuerdo al tercer criterio de vecindadp. 56
- Figura 23. Diagrama de flujo para el algoritmo propuestop. 57
- Figura 24. Codificación de la matriz distanciap. 67
- Figura 25. Codificación de la matriz neta deposito-cliente y cliente-clientep. 68
- Figura 26. Codificación de la Matriz de Feromonas Depósito-Cliente y Cliente-Clientep. 68
- Figura 27. Codificación de la matriz neta entre depósitosp. 69
- Figura 28. Codificación de la matriz de feromonas entre depósitosp. 69
- Figura 29. Codificación del vector de clientes Linehaul factiblesp. 69
- Figura 30. Codificación del vector de clientes Backhaul factiblesp. 69
- Figura 31. Codificación vector ruta soluciónp. 70
- Figura 32. Codificación de la Matriz Vectores Ruta Soluciónp. 70
- Figura 33. Esquema Ruta Linehaul – Backhaulp. 71
- Figura 34. Esquema Ruta solo Linehaulp. 72
- Figura 35. Esquema ruta solo Backhaulp. 72
- Figura 36. Esquema ruta consolidadap. 73
- Figura 37. Diagrama de flujo construcción rutas con algoritmo Colonia de Hormigas MDVRPBp. 75
- Figura 38. Correlación Distancia – Tiempop. 81
- Figura 39. Frente de Pareto Distancia – Tiempop. 82
- Figura 40. Correlación entre distancia y tiempop. 86
- Figura 41. Correlación entre tiempo y energíap. 86
- Figura 42. Correlación distancia y energíap. 86
- Figura 43. Optimización con Colonia de Hormigas con Frente de Pareto: tiempo – energíap. 88
- Figura 44. Optimización con Colonia de Hormigas con Frente de Pareto: distancia – energíap. 88
- Figura 45. Optimización con Colonia de Hormigas con Frente de Pareto: distancia- tiempop. 89
- Figura 46. Comparativo optimizando número de vehículos (Gris Optimiza, Negro No Optimiza Vehículos)p. 93
- Figura 47. Configuración inicial de depósitos y clientes linehaul y backhaulp. 97
- Figura 48. Cálculo de distancias ida y regreso entre clientes linehaul y cada depósitop. 97
- Figura 49. Cálculo de distancias ida y regreso entre clientes backahul y cada depósitop. 98
- Figura 50. Cálculo de matrices de ahorro entre clientes linehaul – linehaul, linehaul – backhaul y backhaul – backhaulp. 98
- Figura 51. Construcción de las rutas con el algoritmo Clarke y Wright con inserción secuencialp. 99
- Figura 52. Ejemplo de VRPB, solución óptima para 20 clientes (Ver Tabla 13)p. 105
- (líneas discontinuas) para 20 clientesp. 110
- de grado 2 - rutas linehaul (líneas continuas) y rutas backhaul (líneas discontinuas) para 20 clientesp. 112
- Figura 55 Instancia K4 de conjunto de datos GJp. 116
- Figura 56. Instancia M4 del conjunto de datos GJp. 117
- Tabla 1. Artículos Revistas Indexadas (103): Algoritmos de solución para el problema multidepósito - VRPBp. 40
- Tabla 2. Categoria revistas y cantidad de artículos revisados – VRPBp. 49
- Tabla 3. Resumen de resultados con 10000 iteraciones del algoritmo implementadop. 58
- Tabla 4. Instancias MDVRPB Salhi y Nagy [44]p. 77
- Tabla 5. Resumen de resultados en 10 ejecuciones con 100 iteraciones del algoritmo implementadop. 78
- Tabla 6. Resultados obtenidos para 10 ejecuciones cada una con 100 iteraciones del algoritmo propuestop. 83
- Tabla 7. Parámetros energíap. 85
- Tabla 8. Tipo de vehículos usados en cada instanciap. 85
- Tabla 9. Resultados obtenidos para 10 ejecuciones cada una con 100 iteraciones del algoritmo PACO propuestop. 87
- propuestosp. 90
- propuestop. 95
- Inserción Secuencial propuestop. 100
- Tabla 13. Coordenadas y cargas para 20 clientesp. 105
- Las distancias euclidianas se redondearon a un decimal y el resultado final se redondeó a un número enterop. 114
- Tabla 15. Resultados computacionales para los casos VRPB de Toth y Vigo [13]p. 118
- Tabla 16. Ejemplos de resultados que minimizan el número de vehículosp. 119
- euclidianas redondeadas a enterosp. 119