PolarDB:Model jalur

Pendahuluan

Model jalur adalah struktur graf yang terdiri dari titik dan sisi. Model ini digunakan untuk menyelesaikan permasalahan seperti perencanaan jalur berbasis jaringan jalan, navigasi GPS pada peta digital, dan routing. Model jalur sepenuhnya kompatibel dengan antarmuka PGRouting dan mendukung migrasi lancar aplikasi yang sudah ada. Data jalur membentuk graf jaringan geometris yang terdiri dari sisi dan node, yang terutama digunakan untuk membangun jaringan jalan dan lalu lintas.

GanosBase Networking adalah ekstensi mesin spasial-temporal untuk PolarDB for PostgreSQL. Ekstensi Networking menyediakan fungsi dan prosedur tersimpan untuk menemukan jalur tercepat, terpendek, atau optimal berdasarkan model biaya. Ekstensi ini menawarkan fitur routing geospasial dan mendukung berbagai algoritma analisis jalur dan jaringan, sehingga menambahkan kemampuan analisis jalur dan jaringan ke dalam database.

Ikhtisar fungsi

GanosBase Networking menyediakan serangkaian fungsi perencanaan jalur dan analisis jaringan:

• Algoritma Johnson.

• Algoritma Floyd-Warshall.

• Algoritma jalur terpendek A* dan A* dua arah.

• Algoritma jalur terpendek Dijkstra dan Dijkstra dua arah.

• Algoritma Traveling Salesperson.

• Algoritma Prim.

• Algoritma Kruskal.

• Algoritma K-jalur terpendek.

• Analisis aliran.

• Operasi topologi graf.

• Operasi komponen graf.

• Kontraksi graf.

• Algoritma Turn Restriction Shortest Path (TRSP).

Beberapa fungsi juga mendukung perhitungan menggunakan biaya atau matriks biaya.

Skenario bisnis utama

GanosBase Networking dapat digunakan dalam berbagai skenario:

• Perencanaan rute optimal

  Pada industri seperti logistik, pengiriman ekspres, dan layanan taksi, Anda dapat menggunakan GanosBase Networking untuk menghitung jalur terpendek atau tercepat antara dua titik guna perencanaan dan optimasi rute. Untuk jalur non-geografis, seperti koneksi antar node Internet, GanosBase Networking juga membantu menemukan topologi jaringan yang optimal.

• Analisis geospasial

  Anda dapat menggunakan GanosBase Networking untuk melakukan analisis berbasis jaringan jalan, seperti pencarian tetangga terdekat dan analisis wilayah layanan. Analisis ini membantu Anda memahami distribusi dan hubungan data geospasial guna meningkatkan pengambilan keputusan dan perencanaan.

• Manajemen arus lalu lintas

  Anda dapat menggabungkan GanosBase Networking dengan data arus lalu lintas untuk menganalisis traffic, memprediksi kemacetan, dan memperoleh saran optimasi. Hal ini bernilai tinggi untuk aplikasi seperti manajemen lalu lintas perkotaan dan sistem transportasi cerdas.

Komponen dasar

pgr_<name>(Inner_queries, Parameters, [ Optional_parameters ])

Struktur data kolom hasil

Kolom yang dikembalikan bervariasi tergantung fungsi yang digunakan.

Hasil untuk satu jalur

Berlaku untuk fungsi pgr_withPoints:

Berlaku untuk fungsi pgr_dijkstraNear:

Hasil untuk beberapa jalur

Berlaku untuk fungsi yang selektif terhadap beberapa jalur:

Berlaku untuk fungsi yang tidak selektif terhadap beberapa jalur:

Hasil untuk fungsi biaya

Berlaku untuk fungsi yang menggunakan biaya atau matriks biaya:

Pendahuluan

Panduan memulai cepat ini menjelaskan penggunaan dasar mesin GanosBase Networking, termasuk cara membuat ekstensi, membuat tabel, memasukkan data, memperbarui properti, membuat topologi, dan mengkueri jalur.

Penjelasan sintaks

• Buat ekstensi.

   CREATE Extension Ganos_Networking cascade;

  Catatan

  Instal ekstensi dalam skema public untuk menghindari masalah izin.

  CREATE extension Ganos_Networking WITH schema public cascade;

• Buat tabel.

   CREATE TABLE edge_table (
       id BIGSERIAL,
       dir character varying,
       source BIGINT,
       target BIGINT,
       cost FLOAT,
       reverse_cost FLOAT,
       capacity BIGINT,
       reverse_capacity BIGINT,
       category_id INTEGER,
       reverse_category_id INTEGER,
       x1 FLOAT,
       y1 FLOAT,
       x2 FLOAT,
       y2 FLOAT,
       the_geom geometry
   );

• Masukkan catatan.

   INSERT INTO edge_table (
       category_id, reverse_category_id,
       cost, reverse_cost,
       capacity, reverse_capacity,
       x1, y1,
       x2, y2) VALUES
   (3, 1,    1,  1,  80, 130,   2,   0,    2, 1),
   (3, 2,   -1,  1,  -1, 100,   2,   1,    3, 1),
   (2, 1,   -1,  1,  -1, 130,   3,   1,    4, 1),
   (2, 4,    1,  1, 100,  50,   2,   1,    2, 2),
   (1, 4,    1, -1, 130,  -1,   3,   1,    3, 2),
   (4, 2,    1,  1,  50, 100,   0,   2,    1, 2),
   (4, 1,    1,  1,  50, 130,   1,   2,    2, 2),
   (2, 1,    1,  1, 100, 130,   2,   2,    3, 2),
   (1, 3,    1,  1, 130,  80,   3,   2,    4, 2),
   (1, 4,    1,  1, 130,  50,   2,   2,    2, 3),
   (1, 2,    1, -1, 130,  -1,   3,   2,    3, 3),
   (2, 3,    1, -1, 100,  -1,   2,   3,    3, 3),
   (2, 4,    1, -1, 100,  -1,   3,   3,    4, 3),
   (3, 1,    1,  1,  80, 130,   2,   3,    2, 4),
   (3, 4,    1,  1,  80,  50,   4,   2,    4, 3),
   (3, 3,    1,  1,  80,  80,   4,   1,    4, 2),
   (1, 2,    1,  1, 130, 100,   0.5, 3.5,  1.999999999999,3.5),
   (4, 1,    1,  1,  50, 130,   3.5, 2.3,  3.5,4);

• Perbarui properti tabel.

   UPDATE edge_table SET the_geom = st_makeline(st_point(x1,y1),st_point(x2,y2)),
   dir = CASE WHEN (cost>0 AND reverse_cost>0) THEN 'B'   -- Both ways
              WHEN (cost>0 AND reverse_cost<0) THEN 'FT'  -- In the direction of the LINESTRING
              WHEN (cost<0 AND reverse_cost>0) THEN 'TF'  -- In the reverse direction of the LINESTRING
              ELSE '' END;

• Buat topologi.

   SELECT pgr_createTopology('edge_table',0.001);

• Kueri jalur terpendek.

   -- Dijkstra shortest path
   SELECT * FROM pgr_dijkstra(
       'SELECT id, source, target, cost, reverse_cost FROM edge_table',
       2, 3
   );
  
    seq | path_seq | node | edge | cost | agg_cost
   -----+----------+------+------+------+----------
      1 |        1 |    2 |    4 |    1 |        0
      2 |        2 |    5 |    8 |    1 |        1
      3 |        3 |    6 |    9 |    1 |        2
      4 |        4 |    9 |   16 |    1 |        3
      5 |        5 |    4 |    3 |    1 |        4
      6 |        6 |    3 |   -1 |    0 |        5
   (6 rows)
  
   -- A* path algorithm
   SELECT * FROM pgr_astar(
       'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
       2, 12,
       directed := false, heuristic := 2);
  
    seq | path_seq | node | edge | cost | agg_cost
   -----+----------+------+------+------+----------
      1 |        1 |    2 |    2 |    1 |        0
      2 |        2 |    3 |    3 |    1 |        1
      3 |        3 |    4 |   16 |    1 |        2
      4 |        4 |    9 |   15 |    1 |        3
      5 |        5 |   12 |   -1 |    0 |        4
   (5 rows)
  
   -- TRSP path algorithm
   SELECT * FROM pgr_trsp(
           'SELECT id::INTEGER, source::INTEGER, target::INTEGER, cost FROM edge_table',
           2, 7, false, false,
           'SELECT to_cost, target_id::int4,
           from_edge || coalesce('','' || via_path, '''') AS via_path
           FROM restrictions'
       );
  
    seq | id1 | id2 | cost
   -----+-----+-----+------
      0 |   2 |   4 |    1
      1 |   5 |  10 |    1
      2 |  10 |  12 |    1
      3 |  11 |  11 |    1
      4 |   6 |   8 |    1
      5 |   5 |   7 |    1
      6 |   8 |   6 |    1
      7 |   7 |  -1 |    0
   (8 rows)

• Hapus ekstensi (opsional).

   Drop Extension Ganos_Networking cascade;

Referensi SQL

Untuk manual SQL lengkap, lihat dokumentasi resmi pgRouting.