SOLUCIÓN DEL PROBLEMA CVRP MEDIANTE EL ALGORITMO DE DESCOMPOSICIÓN DE DANTZIG WOLFE DANIEL ORLANDO MARTÍNEZ QUEZADA UNIVERSIDAD INDUSTRIAL DE SANTANDER FACULTAD DE INGENIERÍAS FISICOMECÁNICAS ESCUELA DE ESTUDIOS INDUSTRIALES Y EMPRESARIALES BUCARAMANGA 2014 1 SOLUCIÓN DEL PROBLEMA CVRP MEDIANTE EL ALGORITMO DE DESCOMPOSICIÓN DE DANTZIG WOLFE DANIEL ORLANDO MARTÍNEZ QUEZADA Trabajo de grado para optar al título de: Ingeniero Industrial Director: Henry Lamos Díaz Ph.D. Física - Matemática UNIVERSIDAD INDUSTRIAL DE SANTANDER FACULTAD DE INGENIERÍAS FISICOMECÁNICAS ESCUELA DE ESTUDIOS INDUSTRIALES Y EMPRESARIALES BUCARAMANGA 2014 2 3 4 AGRADECIMIENTOS Al Profesor Henry Lamos Díaz por su paciencia y esmero en la realización de este proyecto. A Silvia Galván Núñez y Miguel Ángel Beltrán Marín quienes me compartieron sus conocimientos y deseos por investigar. A familiares y amigos que me apoyaron de una u otra manera a lo largo de este proceso, especialmente a Silvia Juliana Serrano Flórez por su tiempo y dedicación. 5 CONTENIDO pág. INTRODUCCIÓN .................................................................................................. 13 1.PLANTEAMIENTO DEL PROBLEMA ................................................................ 16 2.JUSTIFICACIÓN ................................................................................................ 17 3.OBJETIVOS ....................................................................................................... 19 3.2.Objetivos Específicos ...................................................................................... 19 4.MARCO TEÓRICO ............................................................................................. 20 4.1.PROGRAMACIÓN LINEAL ............................................................................. 20 4.2.PROGRAMACIÓN ENTERA ........................................................................... 34 4.3.TEORÍA DE GRAFOS ..................................................................................... 43 4.4.PROBLEMA DE RUTEO DE VEHÍCULOS VRP ............................................. 45 4.5.PROBLEMA DE RUTEO DE VEHÍCULOS CON RESTRICCIONES DE CAPACIDAD (CVRP) ............................................................................................ 48 5.ESTADO DEL ARTE .......................................................................................... 50 5.1.PROBLEMAS CON ESTRUCTURA DE ESCALERA (STAIRCASE LINEAR PROGRAMS, SLPS) ............................................................................................. 50 5.2.PROBLEMA DE RUTEO DE VEHICULOS (CVRP) Y MÉTODOS EXACTOS 50 5.3.GAMS (GENERAL ALGEBRAIC MODELING SYMTEM) ................................ 56 6.DESARROLLO DE LA HERRAMIENTA............................................................. 59 6.1.PROGRAMACIÓN LINEAL ............................................................................. 59 6.2.PROBLEMA DUAL .......................................................................................... 59 6.3.DESCOMPOSICIÓN DE DANTZIG WOLFE ................................................... 60 6.4.ANÁLISIS DE INSTANCIAS PARA EL CVRP ................................................. 65 6 6.5.ARCHIVOS GAMS DATA EXCHANGE. .......................................................... 68 6.6.ALGORITMO DE DESCOMPOSICIÓN DE DANTZIG WOLFE APLICADO AL CVRP .................................................................................................................... 69 7.RESULTADOS OBTENIDOS ............................................................................. 71 8.CONCLUSIONES ............................................................................................... 78 9.RECOMENDACIONES ...................................................................................... 79 BIBLIOGRAFÍA ..................................................................................................... 81 ANEXOS ............................................................................................................... 92 7 LISTA DE FIGURAS pág. Figura 1. Estructura de Bloque .............................................................................. 31 Figura 2. Representación mediante un grafo del Problema de Transporte ........... 45 Figura 3. Variantes de los Problemas de Transporte ............................................ 47 Figura 4. Red de Shortest Path Problem ............................................................... 61 Figura 5. Seudocódigo de Dantzig-Wolfe a un SSP .............................................. 63 Figura 6. Estructura de un archivo GDX ................................................................ 68 Figura 7. Seudocódigo Dantzig-Wolfe aplicado al CVRP ...................................... 69 Figura 8. Tiempo en segundos vs máxima cardinalidad de S P_n16_k8 .............. 72 Figura 9. Tiempo en segundos vs máxima cardinalidad de S P_n19_k2 .............. 72 Figura 10. Tiempo en segundos vs máxima cardinalidad de S DW P_n16_k8 ..... 74 Figura 11. Tiempo en segundos vs máxima cardinalidad de S DW P_n19_k2 ..... 74 Figura 12. Comparación DW y la versión no descompuesta P_n16_k8 ................ 75 Figura 13. Comparación DW y la versión no descompuesta P_n19_k2 ................ 75 Figura 14. Red de Shorest Path Problem .............................................................. 92 8 LISTA DE TABLAS pág. Tabla 1. Resumen de operaciones entre simplex convencional y revisado .......... 26 Tabla 2. Iteración 0 de la solución del SPP ........................................................... 64 Tabla 3. Ramificaciones del SPP .......................................................................... 65 Tabla 4. Tiempos en segundos Exacto sin descomponer ..................................... 71 Tabla 5. Tiempo en segundos método exacto descompuesto .............................. 73 Tabla 6. Columna 1 ............................................................................................... 95 Tabla 7. Columna 2 ............................................................................................... 96 Tabla 8. Columna 3 ............................................................................................... 98 Tabla 9. Columna 4 ............................................................................................... 99 Tabla 10. Columna 1 rama 1 ............................................................................... 102 Tabla 11. Columna 2 rama 1 ............................................................................... 103 Tabla 12. Columna 3 rama 1 ............................................................................... 104 Tabla 13. Columna 1 Rama 2 .............................................................................. 106 Tabla 14. Columna 2 rama 2 ............................................................................... 108 Tabla 15. Columna 3 rama 2 ............................................................................... 109 Tabla 16. Columna 4 rama 2 ............................................................................... 110 Tabla 17. Columna 1 rama 3 ............................................................................... 112 Tabla 18. Columna 1 rama 4 ............................................................................... 114 Tabla 19. Columna 2 rama 4 ............................................................................... 115 9 LISTA DE ANEXOS pág. Anexo A. Solución aplicación Branch Bound and Pricing manual para un SPP .... 92 Anexo B. Guía de Ejecución de códigos ............................................................. 117 Anexo C. Script del método exacto completo sin descomponer.......................... 118 Anexo D. GMS del método exacto sin descomponer .......................................... 120 Anexo E. Script del método de descomposición D-W ......................................... 124 Anexo F. GMS del problema Maestro de la descomposición D-W ...................... 131 Anexo G. GMS del sub-problema de la descomposición D-W ............................ 133 Anexo H. Script para generar gráficas de las soluciones .................................... 137 Anexo I. Instancia P_n16_k8 ............................................................................... 138 Anexo J. Instancia P_n19_k2 .............................................................................. 139 Anexo K. Resultados P_n16_k8 sin descomponer .............................................. 140 Anexo L. Resultados P_n19_k2 sin descomponer .............................................. 154 Anexo M. Resultados P_n16_k8 descompuesto ................................................. 164 Anexo N. Resultados P_n19_k2 descompuesto ................................................. 178 10