Criando um aplicativo de rotas com pgRouting – Parte 3

Além de ter uma conexão de rede, precisamos saber o “custo” de viajar sobre qualquer uma das estações. O custo depende da aplicação: Pode ser um manipulador de custo real (tal como um medidor de tarifa); a distância total percorrida; tempo; ou qualquer outra métrica quando se desloca de um ponto a outro.

Em nossa aplicação, vamos suportar tanto a distância quanto o tempo como métrica de custos. Para melhorar o desempenho, vamos pré-calcular o tempo para viajar de carro em todas as nossas entradas na tabela edges_noded. O tempo será calculado com base no tipo de estrada; consultando nosso banco de dados ele nos mostra os diferentes tipos de rodovias cadastradas.

SELECT DISTINCT(type) from edges_noded;
    type
----------------
 motorway
 motorway_link
 steps
 secondary
 tertiary
 trunk
 secondary_link
 path
 unclassified
 proposed
 cycleway
 trunk_link
 primary
 track
 tertiary_link
 raceway
 residential
 construction
 primary_link
 service
 footway

Alguns deles (steps, path, footway, cycleway, proposed and construction) claramente não são adequados para veículos por isso para estes vamos setar um custo de -1 (números negativos o pgRouting interpreta como sendo segmentos intransitáveis). Para o restante, vamos precisar atribuir uma velocidade média e usar esse tempo para preencher uma nova coluna na nossa tabela. Nós vamos adicionar uma coluna distância para economizar no cálculo do comprimento dos nossos segmentos em cada solicitação.

ALTER TABLE edges_noded ADD distance FLOAT8;
ALTER TABLE edges_noded ADD time FLOAT8;
UPDATE edges_noded SET distance = ST_Length(ST_Transform(the_geom, 4326)::geography) / 1000;

Com base na distância, tipo e a superfície agora pode-se estimar a quantidade de tempo necessário para percorrer cada aresta. O site OpenStreetMap nos dá alguma indicação sobre a velocidade relativa para vários tipos de rodovia.

UPDATE edges_noded SET
  time =
  CASE type
    WHEN 'steps' THEN -1
    WHEN 'path' THEN -1
    WHEN 'footway' THEN -1
    WHEN 'cycleway' THEN -1
    WHEN 'proposed' THEN -1
    WHEN 'construction' THEN -1
    WHEN 'raceway' THEN distance / 100
    WHEN 'motorway' THEN distance / 70
    WHEN 'motorway_link' THEN distance / 70
    WHEN 'trunk' THEN distance / 60
    WHEN 'trunk_link' THEN distance / 60
    WHEN 'primary' THEN distance / 55
    WHEN 'primary_link' THEN distance / 55
    WHEN 'secondary' THEN distance / 45
    WHEN 'secondary_link' THEN distance / 45
    WHEN 'tertiary' THEN distance / 45
    WHEN 'tertiary_link' THEN distance / 40
    WHEN 'unclassified' THEN distance / 35
    WHEN 'residential' THEN distance / 30
    WHEN 'living_street' THEN distance / 30
    WHEN 'service' THEN distance / 30
    WHEN 'track' THEN distance / 20
    ELSE distance / 20
  END;

Dividindo a distância por nossas estimativas de velocidade para cada estrada digite o número de horas necessárias para viajar ao longo desse segmento. Vamos também definir a distância para o valor especial de -1 aos tipos de arestas que não queremos que os veículos circulem.

UPDATE edges_noded SET
  distance =
  CASE type
    WHEN 'steps' THEN -1
    WHEN 'path' THEN -1
    WHEN 'footway' THEN -1
    WHEN 'cycleway' THEN -1
    WHEN 'proposed' THEN -1
    WHEN 'construction' THEN -1
    ELSE distance
  END;

Podemos testar o funcionamento da rota usando a função pgr_dijkstra (que implementa o algoritmo Dijkstra) para encontrar o caminho mais curto entre quaisquer dois vértices da rede. Vértices são identificados pela coluna id na tabela edges_noded_vertices_pgr, gerada automaticamente. Selecione quaisquer dois números do ID de tabela e execute a seguinte consulta. Iremos utilizar neste exemplo os vértices 757 e 1000.

SELECT
  id1 AS vertex,
  id2 AS edge,
  cost
FROM pgr_dijkstra('SELECT id, source::INT4, target::INT4, time AS cost FROM edges_noded', 1000, 757, false, false)
ORDER BY seq;

 vertex | edge  |        cost
--------+-------+---------------------
   1000 |   873 | 0.00862449481177354
   1001 | 11469 |  0.0946329838309096
  11548 | 11468 |  0.0411391925170661
  11510 | 11418 |  0.0130258077805629
  11511 | 11452 |   0.010555359038939
  11536 | 11453 |  0.0500946880163133
  11537 | 11454 |  0.0128158392635584
  11538 | 11455 |   0.225115465905455
    757 |    -1 |                   0

Note como passamos uma sub-consulta como um argumento para pgr_dijkstra. Isto é, estamos dizendo para o pgRouting qual rede usar quando procurar a rota, e é um SQL, que podemos refinar o tipo de rota a procurar. Poderíamos, por exemplo, dizer ao pgRouting para ignorar todas as highways ao procurar uma rota, adicionando a seguinte cláusula WHERE: WHERE type = ‘highway’. O melhor de tudo, isso pode ser feito de forma dinâmica, para que possamos mudar os parâmetros de roteamento com cada solicitação.

Para nossos propósitos, devemos notar que, se substituirmos o tempo pela distância na sub-consulta, isto dirá ao pgRouting para encontrar a rota mais curta, em vez da rota mais rápida (lembre-se que você terá de viajar mais lento em determinados tipos de estradas).

Até agora não temos estradas de sentido único. O mesmo algoritmo pode lidar com estradas de sentido único se somarmos a coluna reverse_cost. Como antes, precisamos definir o custo -1 quando não queremos permitir que uma aresta seja usada; Portanto, vamos usar -1 como o reverse_cost quando o atributo de sentido único for sim. Se a estrada não for unidirecional, usamos o mesmo custo na direção de avanço e reversão.

SELECT
  id1 AS vertex,
  id2 AS edge,
  cost
FROM pgr_dijkstra('SELECT id, source::INT4, target::INT4, time AS cost, CASE oneway WHEN ''yes'' THEN -1 ELSE time END AS reverse_cost FROM edges_noded', 1000, 757, true, true)
ORDER BY seq;

Juntando os resultados dos nós da consulta com os da tabela, podemos obter a informação completa acerca da rota que deve ser tomada, em vez de apenas os números de pontos e vértices.

SELECT
  e.old_id AS id,
  e.name, e.type,
  e.oneway,
  sum(e.time) AS time,
  sum(e.distance) AS distance
FROM
  pgr_dijkstra('SELECT id, source::INT4, target::INT4, time AS cost, CASE oneway WHEN ''yes'' THEN -1 ELSE time END AS reverse_cost FROM edges_noded', 753, 756, true, true) AS r,
  edges_noded AS e
WHERE r.id2 = e.id
GROUP BY e.old_id, e.name, e.type, e.oneway;

 id  |        name         |    type     | oneway |  time   | distance
-----+---------------------+-------------+--------+--------------------+
 203 | Bunker Hill Terrace | residential |        | 0.00790 | 0.23713
 210 | Two Rod Road        | residential |        | 0.00537 | 0.16137
 225 | Heritage Lane       | residential |        | 0.01131 | 0.33932
 224 | Plymouth Drive      | residential |        | 0.00230 | 0.06914
 201 | Colonial Drive      | residential |        | 0.00794 | 0.23829