pgr_TSP

  • “”pgr_TSP”” - Uso del algoritmo de aproximación Simulated Annealing

Disponibilidad: 2.0.0

  • Versión 2.3.0
    • Cambio de firma
      • Firma antigua ya no soportada
  • Versión 2.0.0
    • Función oficial

Soporte

Descripción

En el problema del vendedor viajante (TSP) se 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?

Consulte Algoritmo de Recocido Simulado para obtener una descripción completa de esta implementación

Firmas

Resumen

pgr_TSP(Matrix SQL,
    [start_id], [end_id],
    [max_processing_time],
    [tries_per_temperature], [max_changes_per_temperature], [max_consecutive_non_changes],
    [initial_temperature], [final_temperature], [cooling_factor],
    [randomize])
RETURNS SETOF (seq, node, cost, agg_cost)
Ejemplo:No tener una ejecución aleatoria 
SELECT * FROM pgr_TSP(
    $$
    SELECT * FROM pgr_dijkstraCostMatrix(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
        directed := false)
    $$,
    randomize := false);
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    1 |    1 |        0
   2 |    2 |    1 |        1
   3 |    3 |    1 |        2
   4 |    4 |    1 |        3
   5 |    9 |    1 |        4
   6 |    6 |    1 |        5
   7 |   11 |    1 |        6
   8 |   12 |    2 |        7
   9 |   10 |    1 |        9
  10 |   13 |    4 |       10
  11 |    7 |    1 |       14
  12 |    8 |    1 |       15
  13 |    5 |    2 |       16
  14 |    1 |    0 |       18
(14 rows)

Parámetros

Parámetro Descripción
Matrix SQL una consulta SQL, descrita en Inner query

Parámetros opcionales

Parámetro Tipo Valores predeterminados Descripción
start_vid BIGINT 0 La parte ambiciosa de la implementación utilizará este identificador.
end_vid BIGINT 0 El último vértice de visita antes de volver a start_vid.
max_processing_time FLOAT +infinity Detenga el proceso de recocido cuando se alcance el valor.
tries_per_temperature INTEGER 500 Número máximo de veces que se busca a un(os) vecino(s) en cada temperatura.
max_changes_per_temperature INTEGER 60 Número máximo de veces que se cambia la solución en cada temperatura.
max_consecutive_non_changes INTEGER 100 Número máximo de veces consecutivas que la solución no cambia en cada temperatura.
initial_temperature FLOAT 100 Temperatura de inicio.
temperatura_final FLOAT 0.1 Temperatura final.
factor_de_enfriamiento FLOAT 0.9 Valor entre 0 y 1 (sin incluir) utilizado para calcular la siguiente temperatura.
aleatorizar BOOLEAN true

Elija la semilla aleatoria

  • true: Utilice el tiempo actual como semilla
  • falso: Use 1 como semilla. Usando este valor obtendrá los mismos resultados con los mismos datos en cada ejecución.

Consulta interna

Matrix SQL: una consulta SQL, que debe devolver un conjunto de filas con las siguientes columnas:

Columna Tipo Descripción
start_vid BIGINT Identificador del vértice inicial.
end_vid BIGINT Identificador del vértice final.
agg_cost FLOAT Costo para pasar de start_vid a end_vid

Se puede utilizar con las funciones Cost Matrix - Categoría, con el valor directed := false.

Si se utiliza directed := true, la matriz no simétrica resultante debe convertirse a simétrica mediante la corrección de los valores no simétricos de acuerdo con las necesidades de la aplicación.

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.
cost FLOAT
Coste que se debe recorrer desde el nodo al siguiente nodo en la secuencia de ruta.
  • 0 para la última fila de la secuencia de ruta.
agg_cost FLOAT
Costo agregado del nodo en seq = 1 hacia el nodo actual.
  • 0 para la primera fila de la secuencia de ruta.

Ejemplos Adicionales

Ejemplo:Inicio en el vértice \(7\) 
SELECT * FROM pgr_TSP(
    $$
    SELECT * FROM pgr_dijkstraCostMatrix(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table',
        (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
        directed := false
    )
    $$,
    start_id := 7,
    randomize := false
);
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    7 |    1 |        0
   2 |    8 |    1 |        1
   3 |    5 |    1 |        2
   4 |    2 |    1 |        3
   5 |    1 |    2 |        4
   6 |    3 |    1 |        6
   7 |    4 |    1 |        7
   8 |    9 |    1 |        8
   9 |   12 |    1 |        9
  10 |   11 |    1 |       10
  11 |   10 |    1 |       11
  12 |   13 |    3 |       12
  13 |    6 |    3 |       15
  14 |    7 |    0 |       18
(14 rows)
Ejemplo:Uso con puntos de interés.

Para generar una matriz simétrica:

  • la información del lado de pointsOfInterset se omite al no incluirla en la consulta
  • y directed := false
SELECT * FROM pgr_TSP(
    $$
    SELECT * FROM pgr_withPointsCostMatrix(
        'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
        'SELECT pid, edge_id, fraction from pointsOfInterest',
        array[-1, 3, 5, 6, -6], directed := false)
    $$,
    start_id := 5,
    randomize := false
);
 seq | node | cost | agg_cost
-----+------+------+----------
   1 |    5 |  0.3 |        0
   2 |   -6 |  1.3 |      0.3
   3 |   -1 |  1.6 |      1.6
   4 |    3 |    1 |      3.2
   5 |    6 |    1 |      4.2
   6 |    5 |    0 |      5.2
(6 rows)

Las consultas utilizan la red Datos Muestra .