pgr_TSP

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

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 de la arista (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 el conjunto de (seq, path_id, path_seq, start_vid, end_vid, node, edge, 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.

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

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

Columna	Tipo	Descripción
start_vid	ANY-INTEGER	Identificador del vértice de salida.
end_vid	ANY-INTEGER	Identificador del vértice final.
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

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

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

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

Datos incompletos conectados

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

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

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

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

Ver también

• Vendedor Viajante - Familia de funciones

• Datos Muestra

• Algoritmo Métrico de la Librería Boost

• Wikipedia: Problema del viajante

Índices y tablas

• Índice

• Página de Búsqueda