Especialización en Logística y Gestión de la Cadena de Abastecimiento · 2022
Ruteo de vehículos VRPTWPD para información de valor mediante el uso de algoritmos genéticos
Este trabajo de investigación se centra en Proponer una solución para el ruteo de vehículos VRPTWDP para el transporte de información de valor mediante el uso de algoritmos genéticos. Para el desarrollo se aborda usando un enfoque cuantitativo y alcance descriptivo, integrando un diseño experimental en donde se desarrolla iniciando desde el planteamiento del problema, revisión de la literatura, alcance de la investigación, desarrollo, recolección y análisis de datos. Bajo estas consideraciones se toma como soluciones padres la solución propuesta con la herramienta de Excel “vrp_spreadsheet_solver_v3.72” del profesor Günes Erdogan, las cuales se integran al algoritmo genético propuesto para la solución de un problema VRPTWDP. Como resultado se genera el análisis de soluciones factibles que cumplen con condiciones del problema de estudio.
Texto completo 99 páginas con texto
Leer la tesis completa Ficha en el repositorio
Contenido
- INTRODUCCIÓNp. 7
- CAPÍTULO 1: CARACTERÍSTICAS Y PLANTEAMIENTO DEL PROBLEMAp. 10
- Formulación del Problemap. 15
- Delimitación del Problemap. 10
- Objetivosp. 16
- Objetivo Generalp. 16
- Objetivos Específicosp. 16
- CAPÍTULO 2: MARCO DE REFERENCIAp. 17
- Problema de Ruteo de Vehículosp. 19
- Variantes del VRPp. 22
- Problemas con Restricciones de Capacidad (CVRP)p. 22
- Problema con Múltiples Depósitos (MDVRP)p. 23
- Problemas con Entregas y Devoluciones (VRPPD)p. 24
- Problemas con Ventanas de Tiempo (VRPTW)p. 24
- Métodos para Abordar el Problemap. 31
- Métodos Exactosp. 31
- Programación Lineal Enterap. 32
- Algoritmo de Ramificación y Acotamiento (Branch & Bound)p. 32
- Algoritmo de Ramificación y Corte (Branch & Cut)p. 32
- Técnicas de Relajaciónp. 33
- Métodos Heurísticosp. 33
- Heurísticas Constructivasp. 34
- Heurística del Vecino más Cercanop. 35
- Heurística de Dos Fasesp. 35
- Método de Rutear Primero y Asignar Despuésp. 35
- Método de Asignar Primero y Rutear Despuésp. 36
- Algoritmo de Barridop. 36
- Heurística de Pétalosp. 37
- Heurística de Mejorap. 37
- Métodos Metaheurísticosp. 38
- Algoritmos Genéticosp. 38
- Recocido Simuladop. 40
- Redes Neuronalesp. 40
- Búsqueda Tabúp. 41
- Algoritmo Colonia de Hormigasp. 41
- Algoritmo colonia de hormigas en el VRPTWp. 43
- CAPÍTULO 3: METODOLOGÍAp. 48
- Población de Estudiop. 48
- Muestra y Muestreop. 48
- Técnicas e instrumentos de recolección de datosp. 49
- Técnicas de análisis de datosp. 49
- Procedimiento para el Desarrollop. 49
- CAPÍTULO 4: SOLUCIÓN CASO VRPTWp. 51
- Descripción de la Operaciónp. 51
- Definición del modelo VRPTWp. 53
- Selección de Método de Solución Algoritmo Genéticop. 56
- Análisis Estadístico de Datos Históricosp. 61
- Generación de Rutas Iniciales Herramienta “VRP en Excel”p. 65
- Resultados Iniciales Utilizando Archivo “vrp_spreadsheet_solver_v3.72”p. 68
- Procedimiento para Generación de Población Inicial en AGp. 70
- Selección de individuos en AGp. 73
- Función de adaptación para AGp. 76
- Técnica de cruza para AG Order Crossover (OX)p. 78
- Técnica de Mutación por Intercambio Reciproco en AGp. 81
- Reparación de individuosp. 83
- RESULTADOSp. 86
- CONCLUSIONESp. 92
- RECOMENDACIONES Y TRABAJOS FUTUROSp. 93
- REFERENCIAS BIBLIOGRÁFICASp. 94
- ANEXOSp. 98
- Tabla 1 Porcentaje de cumplimiento de serviciosp. 13
- Tabla 2 Causas de incumplimiento de servicios a clientesp. 13
- Tabla 3 Resumen de Técnicas de Solución para VRPp. 45
- Tabla 4 Referencias trabajaos VRP- Tiempop. 57
- Tabla 5 Cantidad de clientes a simularp. 64
- Tabla 6 Parámetros iniciales VRPTWp. 67
- Tabla 7 Simulación 1, solución inicial VRPTWp. 69
- Tabla 8 Resumen de 10 soluciones simuladosp. 69
- Tabla 9 Representación de individuos – Rutasp. 71
- Tabla 10 Tiempo de solución para AGp. 87
- Tabla 11 Resultados Población Inicialp. 89
- Tabla 12 Resultados Población finalp. 89
- Tabla 13 Soluciones VRPTW- Resumenp. 90
- Tabla 14 Kilómetros de ahorro AGp. 91
- Figura 1 Causas de incumplimiento de servicios en rutap. 11
- Figura 2 Causas de incumplimiento, 5 ¿Por qué?p. 12
- Figura 3 Diagrama de Pareto, incumplimiento de servicios en rutap. 14
- Figura 4 Ejemplo solución VRPp. 20
- Figura 5 VRP con múltiples depósitosp. 23
- Figura 6 Estrategia de evolución para el VRPTWp. 27
- Figura 7 Distribución de velocidad y tiempo de viajep. 28
- Figura 8 Representación de ruteo con m periodos de tiempop. 29
- Figura 9 Ejemplo modelo VRP por zonas con ventanas de tiempop. 51
- Figura 10 Vehículo modelo de ruteo VRPTW Renault Traficp. 52
- Figura 11 Flujo del algoritmo genéticop. 59
- Figura 12 Diagrama de flujo detallado, algoritmo genético para el VRPTWp. 60
- Figura 13 Distribución y parámetros de probabilidad para variables paradasp. 62
- Figura 14 Distribución de probabilidad y parámetros de paradas diarias ajustadap. 63
- Figura 15 Análisis de Pareto clientesp. 64
- Figura 16 Conjunto de cliente, Bing Mapsp. 66
- Figura 17 Flujo macro funcionamiento “vrp_spreadsheet_solver_v3.72”p. 68
- Figura 18 Lectura de datos en Visual Code Pythonp. 72
- Figura 19 Población inicial generada en Visual Studio Codep. 72
- Figura 20 Representación de un individuop. 73
- Figura 21 Familia número 1, familia número 2p. 74
- Figura 22 Función para evaluar aptitud de cada individuop. 75
- Figura 23 Aptitud calculada de cada individuop. 76
- Figura 24 Función de adaptación vector hijos generadosp. 77
- Figura 25 Adaptación Población Inicialp. 77
- Figura 26 Representación de dos padres seleccionados, proceso OXp. 79
- Figura 27 Sub cadenas generadas de padres a hijosp. 79
- Figura 28 Hijos generados padre 1 y 2p. 80
- Figura 29 Función Python para reproducir individuosp. 81
- Figura 30 Técnica de Mutación por Intercambio Recíprocop. 82
- Figura 31 Función para procedimiento de mutaciónp. 83
- Figura 32 Rutas Infactibles Ventanas de tiempop. 84
- Figura 33 Rutas Reparadas VRPTWp. 84
- Figura 34 Función para procedimiento de Reparaciónp. 85
- Figura 35 Convergencia del AGp. 88
- Anexo 1 Pruebas estadísticas, distribución log normalp. 98
- Anexo 2 Matriz de Distanciasp. 98
- Anexo 3 Lista de ubicaciones Georreferenciadas con su Ventana de Atenciónp. 98
- Anexo 4 Ejemplo Base, Datos a Simularp. 98
- Anexo 5 Código y funciones Python VRPTW – AG – Visual Code Studiop. 99