Un algoritmo exacto para el problema de recogida y entrega con ventanas de tiempo

El problema de recogida y entrega con ventanas de tiempo (PDPTW) es una generalización del problema de enrutamiento de vehículos con ventanas de tiempo. En el PDPTW, un conjunto de vehículos idénticos ubicados en un depósito central debe ser enrutado óptimamente para atender un conjunto de solicitudes de transporte sujeto a restricciones de capacidad, ventanas de tiempo, emparejamiento y precedencia. En este documento, presentamos un nuevo algoritmo exacto para el PDPTW basado en una formulación entera similar a la partición de conjuntos, y describimos un procedimiento de acotación que encuentra una solución dual casi óptima de la relajación LP de la formulación al combinar dos heurísticas de ascenso dual y un procedimiento de generación de corte y columna. La solución dual final se utiliza para generar un problema reducido que contiene solo las rutas cuyos costos reducidos son menores que la brecha entre un límite superior conocido y el límite inferior alcanzado. Si el problema resultante tiene un tamaño moderado, se resuelve mediante un solver de programación entera; de lo contrario, se utiliza un algoritmo de ramificación-corte-precio para cerrar la brecha de integridad. Resultados computacionales extensivos sobre las principales instancias de la literatura muestran la efectividad del método exacto propuesto.