نقوم بالتوجيه (التوجيه) على OpenStreetMap. إضافة دعم للطرق ذات الاتجاه الواحد

نواصل سلسلة المقالات حول إنشاء أنظمة توجيه ذات متطلبات معقدة بناءً على قاعدة بيانات PostgreSQL مفتوحة المصدر وامتداد PgRouting على OpenStreetMap. سنتحدث اليوم عن كيفية إضافة دعم للطرق ذات الاتجاه الواحد (اتجاهات القيادة). غالبًا ما يكون نقص هذا الدعم هو السبب الرئيسي لتحويل PgRouting إلى "محرك" توجيه مختلف. كالعادة ، تتوفر جميع البيانات والنتائج في مستودع GitHub الخاص بخدع توجيه OSM ، والذي أقوم بإضافته أثناء النشر.

طريق صغير من 330 عنوانًا على OpenStreetMap.

ما هي الطرق ذات الاتجاه الواحد ولماذا هناك حاجة إليها

, , , . , . , , .

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

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

هل من الممكن تحقيق نتيجة مماثلة مع الترقيم التسلسلي للمباني بين التقاطعات بطريقة مختلفة ، دون زيادة مصفوفة الوزن مع تباطؤ مماثل في إنشاء المسار؟ نعم تستطيع. علاوة على ذلك ، يمكنك أيضًا تسريع إنشاء المسار بشكل كبير (على سبيل المثال ، بواحد أو اثنين من الأوامر العشرية) ، بما في ذلك مراعاة الطرق ذات الاتجاه الواحد. سنتحدث عن هذا في المرة القادمة.