Este trabajo considera una variante del Problema de Enrutamiento de Vehículos con Ventanas de Tiempo, con dependencias de sitios, múltiples depósitos y costos de externalización. Este problema es la base para muchos problemas de enrutamiento de técnicos. Tener tanto dependencias de sitios como restricciones de ventana de tiempo resulta en dificultades para encontrar soluciones factibles e induce instancias altamente restringidas. En primer lugar, se diseñan matheurísticas basadas en formulaciones compactas de Programación Lineal Entera Mixta. Luego se describen matheurísticas de Generación de Columnas utilizando técnicas previas de matheurísticas y aprendizaje automático para estabilizar y acelerar la convergencia del algoritmo de Generación de Columnas. Los experimentos computacionales se analizan en instancias públicas con dificultades graduales para analizar la precisión de los algoritmos para garantizar la viabilidad y la calidad de las soluciones para instancias débilmente a altamente restringidas. Los resultados enfatizan el interés de los múltiples tipos de hibridación entre programación matemática, aprendizaje automático y heurísticas dentro del marco de Generación de Columnas. Este trabajo ofrece perspectivas para muchas extensiones de problemas de enrutamiento de técnicos.