Paralelización en búsqueda de rutas en grafos

NICOLÁS JARES

Rio Cuarto

Congreso; VII Congreso de Matemática Aplicada Computacional e Industrial; 2019

Asociación Argentina de Matemática Aplicada, Computacional e Industria

En este trabajo se desarrollaron estrategias de paralelización aplicadas al modelo propuesto en [1] para diseñar un ruta de colectivo. Dicho modelo requiere conocer la demanda de pasajeros, descripta como un conjunto de pares Origen-Destino (OD) (p, q) que tienen asociadada una cantidad positiva. Luego, se necesita conocer todos los caminos que unen p con q para cada par. Con eso se construye un problema de asignación de tráfico y se resuelve con el método del gradiente proyectado. El minimizador de ese problema indica las aristas del grafo que debería usar la nueva línea de colectivo. Las etapas de mayor intensidad  computacional son el cálculo de todas las rutas posibles para cada par, y las proyecciones que se realizan durante la optimización.  Afortunadamente, ambas resultaron ser paralelizables. Se mostrarán las mejoras de tiempos obtenidos, y un análisis comparativo entre tres  clusters del CCAD-UNC.