pgr_TSP

  • pgr_TSP - Aproximación usando el algoritmo*metrico*.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad:

  • Versión 3.2.1

    • Algoritmo Metrico de la Librería Boost

    • El algoritmo de recocido simulado ya no es utilizado

      • Se ignoran los parámetros relacionados con el algoritmo de recocido simulado: max_processing_time, tries_per_temperature, max_changes_per_temperature, max_consecutive_non_changes, initial_temperature, final_temperature, cooling_factor, randomize

  • Versión 2.3.0

    • Cambio de firma

      • Firma antigua ya no soportada

  • Versión 2.0.0

    • Función oficial

Descripción

Definición del Problema

En el problema del vendedor viajante (TSP) hace la siguiente pregunta:

Dada una lista de ciudades y las distancias entre cada par de ciudades, que corresponde con la ruta más corta posible que para visite cada ciudad exactamente una vez y regrese a la ciudad de origen?

Características

  • Este problema es un problema de optimización NP-duro.

  • Se utiliza el algoritmo métrico

  • La implementación genera soluciones que son el doble de largas que el recorrido óptimo en el peor de los casos cuando:

    • El grafo es no dirigido

    • El grafo está completamente conectado

    • Grafo donde los costos de viaje en los segmentos cumplen con la desigualdad del triángulo.

  • En un grafo no dirigido:

    • Los costos del viaje son simétricos:

    • Los costos del viaje de u a v son tanto como viajar de v a u

  • Se puede utilizar con funciones Cost Matrix - Categoría preferiblemente con directed => false.

    • Con directed => false

      • Generará un grafo que:

        • es no dirigido

        • está completamente conectado (siempre que el grafo tenga un componente)

        • todos los costos de viaje en los segmentos vumplen con la desigualdad del triángulo.

      • Cuando start_vid = 0 Ó end_vid = 0

        • Las soluciones generadas están garantizadas para ser el doble de largas que el recorrido óptimo en el peor de los casos

      • Cuando start_vid != 0 Y end_vid != 0 Y start_vid != end_vid

        • No está garantizado que la solución sea, en el peor de los casos, el doble de larga que el recorrido óptimo, debido al hecho de que end_vid se ve obligado a estar en una posición fija.

    • Con directed => true

      • No está garantizado que la solución sea, en el peor de los casos, el doble de larga que el recorrido óptimo

      • Generará un grafo que:

        • es dirigido

        • está completamente conectado (siempre que el grafo tenga un componente)

        • algunos (o todos) los costos de viaje en los segmentos podrían no obedecer a la desigualdad del triángulo.

      • Como se requiere un grafo no dirigido, el grafo dirigido se transforma de la siguiente manera:

        • los segmentos (u, v) y (v, u) se consideran el mismo segmentos (denotado (u, v)

        • Si “agg_cost difiere entre una o más instancias del segmento (u, v)

        • El valor mínimo de agg_cost en todas las instancias del segmento (u, v) se considera como el agg_cost de la arista (u, v)

        • Algunos (o todos) los costos de viaje en los segmentos aún podrían no obedecer a la desigualdad del triángulo.

  • Cuando los datos están incompletos, pero es un grafo conectado:

    • los datos están incompletos se calcularán con el algoritmo de Dijkstra.

Firmas

Resumen

pgr_TSP(SQL de martiz, [start_id, end_id])
REGRESA CONJUNTO DE (seq, node, cost, agg_cost)
OR EMTPY SET
Ejemplo:

Usando pgr_dijkstraCostMatrix para generar la información de la matriz

  • Línea 5 Los vértices \(\{2, 4, 13, 14\}\) no están incluidos porque no están conectados.

 1SELECT * FROM pgr_TSP(
 2  $$SELECT * FROM pgr_dijkstraCostMatrix(
 3    'SELECT id, source, target, cost, reverse_cost FROM edges',
 4    (SELECT array_agg(id) FROM vertices WHERE id NOT IN (2, 4, 13, 14)),
 5    directed => false) $$);
 6 seq | node | cost | agg_cost
 7-----+------+------+----------
 8   1 |    1 |    0 |        0
 9   2 |    3 |    1 |        1
10   3 |    7 |    1 |        2
11   4 |    6 |    1 |        3
12   5 |    5 |    1 |        4
13   6 |   10 |    2 |        6
14   7 |   11 |    1 |        7
15   8 |   12 |    1 |        8
16   9 |   16 |    2 |       10
17  10 |   15 |    1 |       11
18  11 |   17 |    2 |       13
19  12 |    9 |    3 |       16
20  13 |    8 |    1 |       17
21  14 |    1 |    3 |       20
22(14 rows)
23

Parámetros

Parámetro

Tipo

Descripción

SQL de matriz

TEXT

SQL de matriz como se describe más adelante

Parámetros opcionales de TSP

Columna

Tipo

x Defecto

Descripción

start_id

ENTEROS

0

El primer vértice visitado

  • Cuando 0 cualquier vértice puede convertirse en el primer vértice visitado.

end_id

ENTEROS

0

Último vértice visitado antes de regresar a start_vid.

  • Cuando 0 cualquier vértice puede convertirse en el último vértice visitado antes de regresar a start_vid.

  • Cuando NOT 0 y start_vid = 0 entonces es el primer y último vértice

Consultas Internas

SQL de matriz

Matrix SQL: an SQL query, which should return a set of rows with the following columns:

Columna

Tipo

Descripción

start_vid

ANY-INTEGER

Identificador del vértice de salida.

end_vid

ANY-INTEGER

Identificador del vértice destino.

agg_cost

ANY-NUMERICAL

Costo para pasar de start_vid a end_vid

Columnas de Resultados

Devuelve el CONJUNTO DE (seq, node, cost, agg_cost)

Columna

Tipo

Descripción

seq

INTEGER

Secuencia de filas.

node

BIGINT

Identificador del nodo/coordenada/punto.

costo

FLOAT

Coste que se debe recorrer desde el nodo al siguiente nodo en la secuencia de ruta.

  • 0 para la última fila en la secuencia del recorrido.

agg_cost

FLOAT

Costo agregado del nodo en seq = 1 hacia el nodo actual.

  • 0 para la primera fila en la secuencia del recorrido.

Ejemplos Adicionales

Inicio en el vértice \(1\)

  • Linea 6 start_vid => 1

 1SELECT * FROM pgr_TSP(
 2  $$SELECT * FROM pgr_dijkstraCostMatrix(
 3    'SELECT id, source, target, cost, reverse_cost FROM edges',
 4    (SELECT array_agg(id) FROM vertices WHERE id NOT IN (2, 4, 13, 14)),
 5    directed => false) $$,
 6  start_id => 1);
 7 seq | node | cost | agg_cost
 8-----+------+------+----------
 9   1 |    1 |    0 |        0
10   2 |    3 |    1 |        1
11   3 |    7 |    1 |        2
12   4 |    6 |    1 |        3
13   5 |    5 |    1 |        4
14   6 |   10 |    2 |        6
15   7 |   11 |    1 |        7
16   8 |   12 |    1 |        8
17   9 |   16 |    2 |       10
18  10 |   15 |    1 |       11
19  11 |   17 |    2 |       13
20  12 |    9 |    3 |       16
21  13 |    8 |    1 |       17
22  14 |    1 |    3 |       20
23(14 rows)
24

Uso de puntos de interés para generar una matriz asimétrica.

Para generar una matriz asimétrica:

  • Línea 4 La información side de pointsOfInterset se ignora al no incluirla en la consulta

  • Línea 6 Generación de una matriz asimétrica con directed => true

    • \(min(agg\_cost(u, v), agg\_cost(v, u))\) se considera como el agg_cost

    • La solución que puede ser mayor que el doble de larga que el tour óptimo porque:

      • La desigualdad del triángulo podría no estar satisfecha.

      • start_id != 0 Y end_id != 0

 1SELECT * FROM pgr_TSP(
 2  $$SELECT * FROM pgr_withPointsCostMatrix(
 3    'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
 4    'SELECT pid, edge_id, fraction from pointsOfInterest',
 5    array[-1, 10, 7, 11, -6],
 6    directed => true) $$,
 7  start_id => 7,
 8  end_id => 11);
 9 seq | node | cost | agg_cost
10-----+------+------+----------
11   1 |    7 |    0 |        0
12   2 |   -6 |  0.3 |      0.3
13   3 |   -1 |  1.3 |      1.6
14   4 |   10 |  1.6 |      3.2
15   5 |   11 |    1 |      4.2
16   6 |    7 |    1 |      5.2
17(6 rows)
18

Datos incompletos conectados

Usando aristas seleccionadas \(\{2, 4, 5, 8, 9, 15\}\) la matriz no es completa.

 1SELECT * FROM pgr_dijkstraCostMatrix(
 2  $q1$SELECT id, source, target, cost, reverse_cost FROM edges WHERE id IN (2, 4, 5, 8, 9, 15)$q1$,
 3  (SELECT ARRAY[6, 7, 10, 11, 16, 17]),
 4  directed => true);
 5 start_vid | end_vid | agg_cost
 6-----------+---------+----------
 7         6 |       7 |        1
 8         6 |      11 |        2
 9         6 |      16 |        3
10         6 |      17 |        4
11         7 |       6 |        1
12         7 |      11 |        1
13         7 |      16 |        2
14         7 |      17 |        3
15        10 |       6 |        1
16        10 |       7 |        2
17        10 |      11 |        1
18        10 |      16 |        2
19        10 |      17 |        3
20        11 |       6 |        2
21        11 |       7 |        1
22        11 |      16 |        1
23        11 |      17 |        2
24        16 |       6 |        3
25        16 |       7 |        2
26        16 |      11 |        1
27        16 |      17 |        1
28        17 |       6 |        4
29        17 |       7 |        3
30        17 |      11 |        2
31        17 |      16 |        1
32(25 rows)
33

Valor del cost para \(17 \rightarrow 10\) no existe en la matriz, pero el valor se toma de \(10 \rightarrow 17\).

 1SELECT * FROM pgr_TSP(
 2  $$SELECT * FROM pgr_dijkstraCostMatrix(
 3  $q1$SELECT id, source, target, cost, reverse_cost FROM edges WHERE id IN (2, 4, 5, 8, 9, 15)$q1$,
 4  (SELECT ARRAY[6, 7, 10, 11, 16, 17]),
 5  directed => true)$$);
 6 seq | node | cost | agg_cost
 7-----+------+------+----------
 8   1 |    6 |    0 |        0
 9   2 |    7 |    1 |        1
10   3 |   11 |    1 |        2
11   4 |   16 |    1 |        3
12   5 |   17 |    1 |        4
13   6 |   10 |    3 |        7
14   7 |    6 |    1 |        8
15(7 rows)
16

Ver también

Índices y tablas