Solución del problema cvrp mediante el algoritmo de descomposición de Dantzig Wolfe

Abstract

En el siguiente trabajo se presenta la aplicación de un algoritmo de descomposición de Dantzig-Wolfe aplicado a dos instancias del benchmark para el CVRP, limitando la enumeración de las restricciones de sub-tours o ciclo hamiltonianos y a la vez comparándolo con una formulación sin descomponer usando como entorno de programación Matlab y GAMS de forma simultánea mediante el uso de archivos y librerias gdx (GAMS data exchange) mostrando los resultados obtenidos, analizando la factibilidad de las respuestas generadas por cada limite en la cardinalidad del conjunto de restricciones de eliminación de sub-tours enumerados, encontrándose que los límites de memoria de los ordenadores comerciales son insuficientes para formular por completo un CVRP superior a 16 nodos en sistemas operativos de 32bits, pero también que en algunas instancias no es necesario formular el CVRP en su totalidad solo para llegar a una solución factible u óptima. Además se encuentra que en una formulación de descomposición converge más rápido que una formulación completa para algunos casos, finalmente se sugiere una formulación descompuesta para implementar con algoritmos mixtos entre estocásticos y determinísticos limitando el conjunto de sub-tours y evitar formularlo en su totalidad, viéndolo como un posible nuevo campo de investigación en problemas de optimización combinatoria junto con la aplicación de la herramienta de parallel pool de las nuevas versiones de Matlab para aplicaciones de computación en paralelo.