Kami melakukan perutean (routing) di OpenStreetMap. Menambahkan dukungan untuk jalan satu arah

Kami melanjutkan rangkaian artikel tentang membangun sistem perutean dengan persyaratan kompleks berdasarkan basis data PostgreSQL Open Source dan ekstensi PgRouting di OpenStreetMap. Hari ini kita akan berbicara tentang cara menambahkan dukungan untuk jalan satu arah (petunjuk arah mengemudi). Seringkali, kurangnya dukungan ini adalah alasan utama untuk mengalihkan PgRouting ke "mesin" perutean yang berbeda. Seperti biasa, semua data dan hasil tersedia di repositori GitHub Trik Perutean OSM saya , yang saya tambahkan saat saya publikasikan.

Rute kecil 330 alamat di OpenStreetMap.

Apa itu jalan satu arah dan mengapa itu dibutuhkan

, , , . , . , , .

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

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

Apakah mungkin untuk mencapai hasil yang sama dengan penomoran berurutan bangunan antara persimpangan dengan cara yang berbeda, tanpa meningkatkan matriks bobot dengan perlambatan yang sesuai dalam pembangunan rute? Ya kamu bisa. Selain itu, Anda juga dapat mempercepat pembangunan rute secara signifikan (misalnya, dengan satu atau dua urutan desimal), termasuk dengan mempertimbangkan jalan satu arah. Kami akan membicarakannya lain kali.