Graph

Algoritmo A*

El algoritmo A* [24]es un algoritmo de búsqueda que puede ser empleado para el cálculo de caminos mínimos en una red. Se va a tratar de un algoritmo heurístico, ya que una de sus principales características es que hará uso de una función de evaluación heurística, mediante la cual etiquetará los diferentes nodos de la red y que servirá para determinar la probabilidad de dichos nodos de pertenecer al camino óptimo.

El problema del viajante

El problema del viajante o the traveling salesman problem (TSP), consiste en encontrar la ruta que lleva a cabo un vendedor, que comenzando por un origen visita un determinado y preestablecido conjunto de ciudades y vuelve a ese origen, de manera que la distancia recorrida total es mínima y cada ciudad sólo se visita una vez.

Si se desea expresar el problema de forma matemática utilizando la teoría de grafos, el TSP consistiría en encontrar en una red G el ciclo Hamiltoniano tal que la suma de los costes de las aristas que componen este ciclo sea lo más pequeña posible.

Ruteo en redes con restricciones en giros e intersecciones

Hasta ahora, todos los problemas de ruteo analizados tenían en cuenta los costes de los arcos de la red en la búsqueda de una ruta óptima, pero no diferentes costes en los nodos o intersecciones entre los arcos. Pero existen ciertos problemas en redes reales en los que será necesario tener en cuenta la naturaleza de los giros de la red, y diferenciar entre los tipos de intersecciones que aparecen en ella.

IDELabRoute: Librería para la gestión de grafos escalables.

Sistema de gestión de grafos dinámico que pueda manejar grandes modelos de redes de forma escalable, de forma que pueda utilizarse en entornos con pocos recursos o con un ciclo de trabajo bajo.

TSPEn experiencias previas con grandes sistemas de cálculos de rutas para servidores hemos encontrado que hay algunas carecias importantes en las librerías disponibles como OpenSource cuando se trata de manejar grandes redes con millones de nodos. Las librerías que conocemos usan un modelo de gestión de los grafos que generan una estructura mallada de objetos en memoria. Este modelo precisa grandes cantidades de memoria y unos tiempos de puesta en marcha elevados.

Este proyecto pretende desarrollar un sistema de gestión de grafos dinámico que pueda manejar grandes modelos de redes de forma escalable, de forma que pueda utilizarse en entornos con pocos recursos o con un ciclo de trabajo bajo.

El proyecto está en las primeras fases y aún ofrece limitadas prestaciones, aunque ya es funcional en muchas de sus características básicas.

Distribuir contenido