Desempeño de la descomposición de Benders basada en lógica en la escalabilidad de un problema VRP con ventanas temporales

Resumen

El problema de planificación del transporte de larga distancia abordado en este trabajo consiste en decidir el orden de visitas a los destinos, así como los horarios de carga y descarga. Estas decisiones deben permitir satisfacer una demanda semanal bajo diversas restricciones operativas, con el objetivo de minimizar el tamaño de la flota requerida y lograr su máximo aprovechamiento. Inicialmente se desarrolló una formulación monolítica que representaba fielmente el problema, resolviendo instancias pequeñas satisfactoriamente. Sin embargo esta formulación presenta un desafío significativo para instancias realistas, pues requería excesivos recursos computacionales. En estos casos, el tamaño de la región factible crece rápidamente, lo que incrementa de manera considerable la dificultad para la convergencia del modelo. En este trabajo se analizan dos estrategias orientadas a mejorar su escalabilidad. Como el modelo presentaba un alto nivel de simetría, la primera estrategia consistió en eliminar algunas soluciones equivalentes con restricciones específicas. Por último, la mas efectiva, resultó ser una técnica conocida como descomposición de Benders basada en lógica ( ´ Logic-Based Benders Decomposition, LBBD), la cual permite mejorar la escalabilidad del modelo sin perder la garantía de optimalidad. Los resultados obtenidos indican que esta estrategia de LBBD resulta beneficiosa, ya que permite resolver instancias de escala real utilizando una cantidad de recursos computacionales aceptable.