OpenStreetMapでルーティング（ルーティング）を行います。片道のサポートを追加

Open Source PostgreSQLデータベースとOpenStreetMapのPgRouting拡張機能に基づいて、複雑な要件を持つルーティングシステムの構築に関する一連の記事を続けます。今日は、片道（運転ルート）のサポートを追加する方法について説明します。多くの場合、このサポートの欠如が、PgRoutingを別のルーティング「エンジン」に切り替える主な理由です。いつものように、すべてのデータと結果は、公開時に追​​加するOSM Routing TricksGitHubリポジトリで利用できます。

OpenStreetMap上の330アドレスの短いルート。

片道とは何ですか？なぜ必要なのですか

, , , . , . , , .

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

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

ルートの構築に対応する速度低下を伴う重みマトリックスを増やすことなく、異なる方法で交差点間の建物に順番に番号を付けることで同様の結果を達成することは可能ですか？はい、できます。さらに、片道を考慮に入れることを含めて、ルートの構築を大幅にスピードアップすることもできます（たとえば、10進数で1つまたは2つ）。これについては次回お話します。