WPS

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.

RouteEngine: WPS

Implantación de un servicio WPS e OpenLS para RouteEngine

La librería RouteEngine permite realizar algunas operaciones sobre grafos. Una de las aplicaciones más populares es la obtención de rutas óptimas en redes de comunicación. Una forma de fomentar el uso de esta información es permitir el acceso a estos servicios mediante interfaces estándar como el WPS del OGC.
Objetivos principales:

Objetivos indirectos:

  • FeatureResolver: Implementar el interfaz ya iniciado para transformar los grafos en features geográficas.
  • Path descriptions: Implementar un API para generar descripciones amigables sobre los resultados de lo algoritmos.
      [ADJUDICADO]

Para ver la descripción detallada del PFC ponte en contacto con Dr. Juan Pablo de Castro.

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