Nous faisons du routage (routage) sur OpenStreetMap. Ajout de la prise en charge des routes à sens unique

Nous continuons la série d'articles sur la construction de systèmes de routage avec des exigences complexes basées sur la base de données Open Source PostgreSQL et l'extension PgRouting sur OpenStreetMap. Aujourd'hui, nous allons parler de la façon d'ajouter la prise en charge des routes à sens unique (itinéraires routiers). Souvent, l'absence de ce support est la principale raison pour laquelle PgRouting est basculé vers un autre "moteur" de routage. Comme d'habitude, toutes les données et résultats sont disponibles dans mon référentiel GitHub OSM Routing Tricks , que j'ajoute au fur et à mesure que je publie.

Un petit parcours de 330 adresses sur OpenStreetMap.

Que sont les routes à sens unique et pourquoi sont-elles nécessaires

, , , . , . , , .

, , . , , — , .. , (, ) , ( , ), .

, — , ( , , ) , ( , — , 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, , . . — , . . , ( , ).

:

:

-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 " " . , , , .

Est-il possible d'obtenir un résultat similaire avec une numérotation séquentielle des bâtiments entre les intersections d'une manière différente, sans augmenter la matrice de poids avec un ralentissement correspondant dans la construction de l'itinéraire? Oui, vous pouvez. De plus, vous pouvez également accélérer considérablement la construction de l'itinéraire (par exemple, d'un ou deux ordres décimaux), y compris en tenant compte des routes à sens unique. Nous en parlerons la prochaine fois.