PolarDB:Modelo de caminho

Introdução

O modelo de caminho é uma estrutura de grafo composta por pontos e arestas. Ele resolve problemas como planejamento de rotas em redes viárias, navegação GPS para mapas eletrônicos e roteamento. Esse modelo é totalmente compatível com as interfaces do PGRouting e permite a migração tranquila de aplicações existentes. Os dados de caminho formam um grafo de rede geométrica de arestas e nós, utilizado principalmente para construir redes rodoviárias e de tráfego.

GanosBase Networking é uma extensão de engine espaço-temporal para PolarDB for PostgreSQL. A extensão Networking fornece funções e stored procedures para encontrar o caminho mais rápido, mais curto ou ideal com base em um modelo de custo. Ela oferece recursos de roteamento geoespacial e suporta diversos algoritmos de análise de caminhos e redes, adicionando capacidades de análise de rotas e redes ao banco de dados.

Visão geral das funções

GanosBase Networking oferece uma série de funções para planejamento de rotas e análise de redes:

• Algoritmo de Johnson.

• Algoritmo Floyd-Warshall.

• Algoritmos de caminho mais curto A e A bidirecional.

• Algoritmos de caminho mais curto Dijkstra e Dijkstra bidirecional.

• Algoritmo do Caixeiro Viajante.

• Algoritmo de Prim.

• Algoritmo de Kruskal.

• Algoritmo de K-caminhos mais curtos.

• Análise de fluxo.

• Operações de topologia de grafo.

• Operações de componentes de grafo.

• Contração de grafo.

• Algoritmo de Caminho Mais Curto com Restrição de Conversão (TRSP).

Algumas funções também suportam cálculos usando um custo ou uma matriz de custos.

Principais cenários de negócios

GanosBase Networking atende a uma ampla variedade de cenários:

• Planejamento de rota ideal

  Em setores como logística, entregas expressas e serviços de táxi, utilize o GanosBase Networking para calcular o caminho mais curto ou mais rápido entre dois pontos, otimizando o planejamento de rotas. Para caminhos não geográficos, como conexões entre nós da Internet, o GanosBase Networking também auxilia na identificação de uma topologia de rede ideal.

• Análise geoespacial

  Utilize o GanosBase Networking para executar análises baseadas em redes viárias, como buscas de vizinhos mais próximos e análise de áreas de service. Essas análises ajudam a compreender a distribuição e as relações dos dados geoespaciais, melhorando a tomada de decisão e o planejamento.

• Gestão de fluxo de tráfego

  Combine o GanosBase Networking com dados de fluxo de tráfego para analisar o trânsito, prever congestionamentos e obter sugestões de otimização. Essa funcionalidade é valiosa para aplicações como gestão de tráfego urbano e sistemas inteligentes de transporte.

Componentes básicos

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

Estruturas de dados das colunas de resultado

As colunas retornadas variam dependendo da função.

Resultado para um único caminho

Aplica-se à função pgr_withPoints:

Aplica-se à função pgr_dijkstraNear:

Resultado para múltiplos caminhos

Aplica-se a funções seletivas para múltiplos caminhos:

Aplica-se a funções não seletivas para múltiplos caminhos:

Resultado para funções de custo

Aplica-se a funções que utilizam um custo ou matriz de custos:

Introdução

Este guia de início rápido descreve o uso básico da engine GanosBase Networking, incluindo como crie uma extensão, crie uma tabela, inserir dados, atualize propriedades, crie uma topologia e consultar caminhos.

Descrição da sintaxe

• Crie a extensão.

   CREATE Extension Ganos_Networking cascade;

  Nota

  Instale a extensão no schema public para evitar problemas de permissão.

  CREATE extension Ganos_Networking WITH schema public cascade;

• Crie uma tabela.

   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
   );

• Insira registros.

   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);

• Atualize as propriedades da tabela.

   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;

• Crie uma topologia.

   SELECT pgr_createTopology('edge_table',0.001);

• Consulte o caminho mais curto.

   -- 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)

• Remova a extensão (opcional).

   Drop Extension Ganos_Networking cascade;

Referência SQL

Para obter um manual SQL detalhado, consulte a documentação oficial do pgRouting.