Continuamos la serie de artículos sobre la construcción de sistemas de enrutamiento con requisitos complejos basados en la base de datos de código abierto PostgreSQL y la extensión PgRouting en OpenStreetMap. Hoy hablaremos sobre cómo agregar soporte para carreteras de un solo sentido (indicaciones de manejo). A menudo, la falta de este soporte es la razón principal para cambiar PgRouting a un "motor" de enrutamiento diferente. Como de costumbre, todos los datos y resultados están disponibles en mi repositorio de GitHub de trucos de enrutamiento de OSM , que agrego a medida que publico.
Una ruta corta de 330 direcciones en OpenStreetMap.
¿Qué son las carreteras de un solo sentido y por qué son necesarias?
, , , . , . , , .
, , . , , — , .. , (, ) , ( , ), .
, — , ( , , ) , ( , — , PgRouting , ). , , .
PgRouting
PgRouting pgr_TSP — Using Simulated Annealing approximation algorithm :
If using directed := true, the resulting non symmetric matrix must be converted to symmetric by fixing the non symmetric values according to your application needs.
, , . , . , , Travelling salesman problem: Asymmetric:
Solving an asymmetric TSP graph can be somewhat complex. The following is a 3×3 matrix containing all possible path weights between the nodes A, B and C. One option is to turn an asymmetric matrix of size N into a symmetric matrix of size 2N.
, , ( ) . , PgRouting, , . . — , . . , ( , ).
:
A | B | C | |
---|---|---|---|
A | 1 | 2 | |
B | 6 | 3 | |
C | 5 | 4 |
:
A | B | C | A' | B' | C' | |
---|---|---|---|---|---|---|
A | -w | 6 | 5 | |||
B | 1 | -w | 4 | |||
C | 2 | 3 | -w | |||
A' | -w | 1 | 2 | |||
B' | 6 | -w | 3 | |||
C' | 5 | 4 | -w |
-w , ,
w=0 is not always low enough
- PgRouting. PgRouting , ( ) [] , PgRouting ( , , ).
CREATE OR REPLACE FUNCTION pgr_dijkstraSymmetrizeCostMatrix(matrix_cell_sql text,
OUT start_vid BIGINT, OUT end_vid BIGINT, OUT agg_cost float)
RETURNS SETOF RECORD AS
$BODY$
DECLARE
sql text;
r record;
BEGIN
sql := 'with edges as (' || matrix_cell_sql || ')
select 3e9+start_vid as start_vid, end_vid as end_vid, agg_cost from edges
union
select end_vid, 3e9+start_vid, agg_cost from edges
union
select 3e9+start_vid, start_vid, 0 from edges
union
select start_vid, 3e9+start_vid, 0 from edges
union
select start_vid, end_vid, 1e6 from edges
union
select 3e9+start_vid, 3e9+end_vid, 1e6 from edges
';
FOR r IN EXECUTE sql LOOP
start_vid := r.start_vid;
end_vid := r.end_vid;
agg_cost := r.agg_cost;
RETURN NEXT;
END LOOP;
END;
$BODY$
LANGUAGE plpgsql VOLATILE STRICT;
, . , PgRouting , ,
An Infinity value was found on the Matrix
- ( pgr_dijkstraSymmetrizeCostMatrix() , , , , ):
CREATE OR REPLACE FUNCTION pgr_dijkstraValidateCostMatrix(matrix_cell_sql text,
OUT start_vid BIGINT, OUT end_vid BIGINT, OUT agg_cost float)
RETURNS SETOF RECORD AS
$BODY$
DECLARE
sql text;
r record;
BEGIN
sql := 'WITH RECURSIVE src AS (' || matrix_cell_sql || '),
dst AS (
select
*
from src where start_vid =
(select
start_vid
from src
group by start_vid
order by count(*) desc
limit 1)
union
select
src.*
from src, dst
where src.start_vid=dst.end_vid
)
select * from dst';
FOR r IN EXECUTE sql LOOP
start_vid := r.start_vid;
end_vid := r.end_vid;
agg_cost := r.agg_cost;
RETURN NEXT;
END LOOP;
END;
$BODY$
LANGUAGE plpgsql VOLATILE STRICT;
PgRouting . , , , ( ).
, . load.sh PostgreSQL .
, , . , , . , ( ) . , (type='osm') (type='osmreverse') . , ( , , ). , (type='osm') — (type='osmreverse'). , :
case when (type='osmreverse' and oneway) then 1000000 else length end as cost,
case when type ilike 'osm%' then 1000000 else length end as reverse_cost,
length — . ( ), .
330 PgRouting pgr_TSP() pgr_dijkstraSymmetrizeCostMatrix() pgr_dijkstraValidateCostMatrix(). directed=true, pgr_TSP() (, , ). , SQL route.sql "route" , QGIS. QGIS , . route.qgs .
( ):
, , , . OpenStreetMap, :
OpenStreetMap, 329,330,331 :
( ) 72,73,74 ( ):
. (. ). , , pgr_TSP().
, , - . - .
PgRouting, . , , .
, , , pgr_TSP(). , — , PgRouting " " . , , , .
¿Es posible lograr un resultado similar con una numeración secuencial de edificios entre intersecciones de una manera diferente, sin aumentar la matriz de peso con la correspondiente desaceleración en la construcción de la ruta? Sí tu puedes. Además, también puede acelerar significativamente la construcción de la ruta (por ejemplo, en uno o dos órdenes decimales), incluso teniendo en cuenta las carreteras de un solo sentido. Hablaremos de esto la próxima vez.