BECAS
JARES NicolÁs
congresos y reuniones científicas
Título:
Paralelización en búsqueda de rutas en grafos
Autor/es:
NICOLÁS JARES
Lugar:
Lleida
Reunión:
Congreso; Escuela Latinoamericana de Verano en Investigación Operativa ? XXIII ELAVIO; 2019
Institución organizadora:
Universitat de Lleida
Resumen:
En este trabajo se desarrollaron estrategias de paralelización aplicadas al modelo propuesto en mi trabajo final de licenciatura. Dicho modelo fue pensado para diseñar un ruta de colectivo y requiere conocer la demanda de transporte público de pasajeros, descripta como un conjunto de pares Origen-Destino (OD) (p, q) los que a su vez tienen asociadados una cantidad de personas que desean desplazarse desde p hasta q . Esos desplazamientos se realizan dentro de un grafo dirigido pesado que representa las calles de la ciudad y las lineas de colectivos existentes. Una vez conocida la demanda, es necesario conocer todos los caminos que tienen inicio p y n q , para cada par OD.A continuación, con todos los caminos encontrados para cada par OD se construyen dos matrices que caracterizan un problema de asignación de tráco. Este problema es resuelto con el método del gradiente proyectado. Su minimizador es un vector que contiene determinados ujos óptimos para cada arista del grafo. Los valores de esos ujos indican las aristas que debería usar la nueva linea de colectivo que se desea diseñar, donde a mayor flujo, mejor sería que la nueva linea utilice esa arista en su recorrido.Dentro de todo este proceso, las dos etapas de mayor intensidad computacional son el cálculo de todas las rutas posibles para cada par, y las proyecciones que se realizan en la etapa de optimización (gradiente proyectado). A su vez, ambas etapas están relacionadas pues si bien es deseable encontrar la mayor cantidad de rutas posibles en el menor tiempo, la cantidad de rutas encontradas determina la dicultad de las proyecciones que deberán realizarse (la dimensión del espacio sobre el que se realizan las proyecciones). Afortunadamente, las dos etapas más pesadas resultaron ser las que mayor posibilidad de paralelización tenían. Se mostrarán las mejoras de tiempos obtenidos, y un análisis comparativo de performance entre tres clusters del CCAD-UNC.
