Versiones soportadas: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Versiones no soportadas:2.6 2.5 2.4 2.3 2.2 2.1 2.0

pgr_TSP

• pgr_TSP - Aproximación usando el algoritmo métrico.

Disponibilidad:

Versión 4.0.0

• Simulated Annealing signature removed

• Results change depending on input order

• Only for undirected graphs

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

• Implementation generates solutions that are twice as long as the optimal tour in the worst case:

• Graph characteristics for best performance:

  • 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.

  • Los costos del viaje son simétricos:

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

• Results change depending on input order of the Matrix SQL

• Negative costs are ignored.

• 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

      • The solutions generated are guaranteed to be twice as long as the optimal tour in the worst case

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

      • It is not guaranteed that the solution will be, in the worst case, twice as long as the optimal tour, due to the fact that end_vid is forced to be in a fixed position.

  • Con directed => true

    • It is not guaranteed that the solution will be, in the worst case, twice as long as the optimal tour

    • 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.

• When the data does not come from an undirected graph or its not fully connected:

  • Missing values will be calculated with dijkstra algorithm.

  • When the graph has more than one component:

    • start_vid or end_vid are defined and are on the same component: the TSP tour will happen on that component.

    • start_vid or end_vid are defined and are not on the same component: the TSP tour will propose a tour that has both components where connecting costs are estimated.

    • start_vid or end_vid are not defined: the starting point could be on any component and will include data only from that component.

• One cycle attempt to remove crossing edges is done to the TSP results.

Adentro: Boost Graph

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)

O CONJUNTO VACÍO

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)

Using points of interest to generate an asymmetric matrix.

Para generar una matriz asimétrica:

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

• Line 6 Generating an asymmetric matrix with directed => true

  • $min(agg\mathrm{\_}cost(u,v),agg\mathrm{\_}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\to 10$ no existe en la matriz, pero el valor se toma de $10\to 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

• Boost: aproximación métrica de TSP

• Wikipedia: Problema del viajante

Índices y tablas

• Índice

• Página de Búsqueda