Siguiente: Prototipo 4: Desarrollo de Subir: SMIV Anterior: Prototipo 2: Modelo de Índice General
PostGis es un módulo que añade soporte de objetos geográficos a la base de datos, convirtiéndola en una base de datos espacial para la utilización de un GIS.
PgRouting es una extensión para bases de datos geográficas que proporciona herramientas para servicios basados en la localización.
OpenLayers es una biblioteca de javascript de código abierto para mostrar mapas en un navegador web.
Se creará una serie de consultas a partir de una localización origen a una localización destino con los diferentes algoritmos que contiene el módulo de PgRouting.
-Shortest_path
PgRouting proporciona el algoritmo de Dijkstra en la forma de la función shortest_path, cuya especificación es:
CREATE OR REPLACE FUNCTION shortest_path( sql text, source_id integer target_id integer directed boolean, has_reverse_cost boolean ) RETURNS SET OF path_result;
Un ejemplo para este caso sería el siguiente.
SELECT * FROM shortest_path( 'SELECT the_geom, gid as id, source, target, x1, y1, x2, y2, length as cost, reverse_cost FROM ways', 405, 225, false, false);
-Dijkstra_sp
Dijkstra_sp son funciones contenedoras para el cálculo de rutas, es reducir el tiempo de respuesta de PgRouting. Dicho tiempo de respuesta se divide en dos partes: la primera de carga de datos, la segunda de cálculo de resultados. El tiempo de la primera parte depende del tamaño o la cantidad de datos existentes Para reducir este tiempo, el algoritmo debe reducir la cantidad de datos a cargar. Para conseguirlo, se reducen los datos de la carga a la información contenida en un cuadro delimitador, tomando como referencia las posiciones de nodo inicio y fin cuyo camino se pretende calcular. De esta manera, en la primera fase del algoritmo se cargan menos datos, reduciendo así el tiempo total de ejecución del algoritmo.
Es por eso que en pgRouting se concluye que las funciones contenedoras suelen ser siempre más rápidas a comparación del Algoritmo de Dijkstra.
La función dijkstra_sp es una función contenedora de shortest_path, tomando como cuadro delimitador los datos contenidos desde el origen hasta el destino. Esta función tiene mayor eficiencia que la función original shortest_path, aunque los resultados devueltos serán siempre los mismos.
CREATE OR REPLACE FUNCTION dijkstra_sp( geom_table character varying, source integer, target integer ) RETURNS SETOF geoms;
Un ejemplo para este caso sería el siguiente.
SELECT rt.gid, AsText(rt.the_geom) AS wkt, length(rt.the_geom) AS length,
ways.gid, ways.source, ways.target
FROM ways,
(SELECT gid, the_geom
FROM dijkstra_sp('ways',405,225)) as rt
WHERE ways.gid=rt.gid;
-Dijkstra_sp_delta
La función dijkstra_sp_delta consiste en una versión delta de la función dijkstra_sp. Las funciones delta son análogas a sus predecesoras, con la peculiaridad de que aceptan un parámetro más, llamado precisamente delta, que indica el margen a añadir un cuadro delimitador utilizado por la función. En resumidas cuentas consiste en un margen de error sobre los datos, para no descartar en el proceso alguna vía que de otro modo formaría parte del camino más corto entre los dos puntos. Si no se estableciera un margen correcto, los dos algoritmos podrían retornar resultados diferentes. La especificación de esta función es la siguiente.
CREATE OR REPLACE FUNCTION dijkstra_sp_delta( geom_table character varying, source integer, target integer, delta double precision ) RETURNS SETOF geoms;
Un ejemplo para este caso sería el siguiente.
SELECT rt.id, rt.gid, AsText(rt.the_geom) AS wkt, length(rt.the_geom) AS length, ways.gid,
ways.source, ways.target
FROM ways,
(SELECT id, gid, the_geom
FROM dijkstra_sp_delta('ways',405,225,3000)) AS rt
WHERE ways.gid=rt.gid;
El algoritmo Shortest Path A* es una extensión del algoritmo de Dijkstra usando heurística, con la ventaja de que consigue mejorar la velocidad de cálculo. Una heurística es una función matemática 42#42 que sirve como estimación del coste del camino más económico de un nodo origen hasta el nodo destino. La búsqueda escogerá el nodo que tiene el valor más bajo en la función heurística. La función 42#42 es admisible cuando no supera nunca los costes de encontrar el destino.
-Shortest_path_astar
PgRouting proporciona el algoritmo A* en la forma de la función shortest_path_astar, cuya especificación es la siguiente.
CREATE OR REPLACE FUNCTION shortest_path_astar( sql text, source_id integer, target_id integer, directed boolean, has_reverse_cost boolean ) RETURNS SETOF path_result;
Un ejemplo para este caso sería el siguiente.
SELECT * from shortest_path_astar( 'SELECT the_geom, gid AS id, source, target, x1, y1, x2, y2, length AS cost, reverse_cost FROM ways', 405, 225, false, false);
-Astar_sp_delta
La función astar_sp_delta es la equivalente a la función shortest_path_astar, en su versión contenedora y con parámetro delta. Su especificación es la siguiente.
CREATE OR REPLACE FUNCTION astar_sp_delta( geom_table character varying, source integer, target integer, delta double precision ) RETURNS SETOF geoms;
Un ejemplo para este caso sería el siguiente.
SELECT rt.id, rt.gid, AsText(rt.the_geom) AS wkt, length(rt.the_geom) AS length,
ways.gid, ways.source, ways.target
FROM ways,
(select id, gid, the_geom from astar_sp_delta('ways',405,225,3000)) AS rt
WHERE ways.gid=rt.gid;
El algoritmo Shooting Star calcula entre dos aristas, a diferencia de los dos algoritmos anteriores que realizan los cálculos de vértice a vértice. La ruta calculada mediante este algoritmo devuelve como punto de partida el nodo de inicio de la línea (origen). La particularidad de este algoritmo es que permite añadir restricciones a nivel de vía. Hasta ahora se calculaba el coste de una vía (cost) en función de su longitud (length), sin que por ello consten otras dificultades en el camino, como por ejemplo, semáforos, restricciones de giros prohibidos, etc. Shooting Star pretende tener en cuenta todos estos detalles para calcular las rutas teniendo en cuenta estos impedimentos presentes.
En la base de datos de PgRouting, no existe información alguna en los campos de ways.to_cost y ways.rule, por lo que el cálculo de ruta se está realizando sin tomar ninguna restricción.
-Shortest_path_shooting_star
PgRouting proporciona el algoritmo Shooting Star en la forma de la función
shortest_path_shooting_star, cuya especificación es la siguiente. CREATE OR REPLACE FUNCTION shortest_path_shooting_star( sql text, source_id integer, target_id integer, directed boolean, has_reverse_cost boolean ) RETURNS SETOF path_result;
La función devuelve un conjunto de filas, cada una de las cuales corresponde a una línea cruzada, además de una fila adicional que contiene el vértice terminal. La información devuelta por cada fila está formado de:
Un ejemplo para este caso sería el siguiente.
SELECT * from shortest_path_shooting_star( 'SELECT the_geom, gid AS id, source, target, x1, y1, x2, y2, length AS cost, rule, to_cost FROM ways', 405,225,false,false );
-Shootingstar_sp
La función shootingstar_sp es la equivalente a la función shortest_path_shooting_star, en su versión contenedora y con parámetro delta. Su especificación es la siguiente.
CREATE OR REPLACE FUNCTION shootingstar_sp( geom_table character varying, source integer, target integer, delta double precision, cost_field character varying, directed boolean, has_reverse_cost boolean ) RETURNS SETOF geoms;
Un ejemplo para este caso sería el siguiente.
SELECT rt.id, rt.gid, AsText(rt.the_geom) AS wkt, length(rt.the_geom) AS length,
ways.gid, ways.source, ways.target
FROM ways,
(SELECT id, gid, the_geom
FROM shootingstar_sp('ways',405,225,3000, 'length', false, false)) AS rt
WHERE ways.gid=rt.gid;
El Algoritmo Shooting Start, ocupa un costo y una heurística. Para el costo, será la longitud del segmento de calle y la heurística será el tiempo de trasladarse o cruzar dicho segmento de calle. Para obtener el tiempo de trasladarse (43#43) se requiere la longitud del segmento de la calle (44#44) y la velocidad promedio (45#45) que tiene registrado la base de datos. Quedando como fórmula:
Para el caso de las calles que sean bloqueados, el valor de la velocidad promedio de la calle, tendrá un valor negativo, entonces el tiempo promedio será un valor negativo.
Sí se requiere bloquear un segmento de calle, es decir, que esté transitable, el valor de la velocidad promedio deberá ser un valor negativo para obtener un tiempo promedio negativo. Cuando se calcule una ruta, y encuentre una calle con costo negativo, no se tomará la calle para formar el grafo con calles transitables.
En la figura 6.1 se muestra la arquitectura del prototipo, se agregó el módulo para la obtención de rutas.
El diagrama Entidad Relación de la figura 6.2 se modela en base a la documentación de PgRouting, extensión de PostgreSQL, para el cálculo de rutas.
En la figura 6.3 se muestra el diagrama de actividades que representa el procesamiento dinámico del cálculo de las rutas.
La figura 6.4 es una captura del desarrollo del prototipo cálculo de rutas.
En esta sección se muestran las gráficas de los resultados al aplicar los protocolos de pruebas que se encuentran en el anexo de este documento. Estos son los resultados de las iteraciones de cada título de prueba hasta cumplir con el 100% de aprobados (OK). Se suma el total OK y NOK de todas las iteraciones.
IPN - ESCOM
.
.