Motor de optimización de rutas para el mundo real: Python y otras bestias

Construir un motor de optimización para la planificación de rutas de vehículos de recogida de residuos, de reparto de mercancías, u otras muchas aplicaciones, no es tarea fácil por dos importantes motivos:

• La enorme cantidad de restricciones involucradas en el problema: restricciones a la hora de circular con los vehículos, puntos de parada que hay que visitar a cierta hora, conductores con horarios, camiones que se llenan y vacían, entregas y recogidas…
• Es un problema de optimización combinatoria bestial (NP-duro). Por ejemplo, para un sólo vehículo que tendría que visitar 100 localizaciones, existen 100! rutas posibles… 100! = 9.33 * 10^157. El número estimado de átomos en el universo visible es sólo 10^80, ¡casi nada!

Cayetano y Josema forman parte del equipo de Geographica que ha desarrollado una solución para resolver este tipo de problemas. Nos contarán como han montado este motor de optimización de rutas usando datos de OpenStreetMaps, PostgreSQL (con sus extensiones PostGIS y PgRouting) para ingestionarlos y procesarlos, las metaheuristicas de OR-Tools para darles sentido y Apache Airflow con Kuberntes para orquestar a estas bestias. Todo esto apoyado muy sólidamente con el SciPy ecosystem, lo mejor de Python para computación científica: Pandas, NumPy, Scikit-learn…