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 |    3 |        0
   2 |    4 |    1 |        3
   3 |    9 |    1 |        4
   4 |   12 |    1 |        5
   5 |   11 |    2 |        6
   6 |   13 |    1 |        8
   7 |   10 |    1 |        9
   8 |    5 |    2 |       10
   9 |    7 |    1 |       12
  10 |    8 |    2 |       13
  11 |    6 |    1 |       15
  12 |    3 |    1 |       16
  13 |    2 |    1 |       17
  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 |    1 |        0
   2 |    6 |    1 |        1
   3 |    3 |  1.6 |        2
   4 |   -1 |  1.3 |      3.6
   5 |   -6 |  0.3 |      4.9
   6 |    5 |    0 |      5.2
(6 rows)

Las consultas utilizan la red Datos Muestra .