pgr_TSPeuclidean

pgr_TSPeuclidean - Uso del algoritmo de aproximación Simulated Annealing

Disponibilidad

  • Versión 3.0.0
    • Cambio de nombre de pgr_eucledianTSP
  • Versión 2.3.0
    • Nueva función Oficial

Soporte

  • Versiones soportadas: actual(3.0) 2.6
  • Versiones no soportadas: 2.5 2.4 2.3

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_TSPeuclidean(Coordinates 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_TSPeuclidean(
    $$
    SELECT id, st_X(the_geom) AS x, st_Y(the_geom)AS y  FROM edge_table_vertices_pgr
    $$,
    randomize := false);
 seq | node |       cost        |     agg_cost
-----+------+-------------------+------------------
   1 |    1 |   1.4142135623731 |                0
   2 |    3 |                 1 |  1.4142135623731
   3 |    4 |                 1 | 2.41421356237309
   4 |    9 |                 1 | 3.41421356237309
   5 |    6 |  0.58309518948453 | 4.41421356237309
   6 |   16 | 0.860232526704263 | 4.99730875185763
   7 |   12 |  1.11803398874989 | 5.85754127856189
   8 |   17 |  1.11803398874989 | 6.97557526731178
   9 |   11 |                 1 | 8.09360925606168
  10 |   10 |               0.5 | 9.09360925606168
  11 |   15 |               0.5 | 9.59360925606168
  12 |   13 |  1.58113883008419 | 10.0936092560617
  13 |   14 |  1.58113883008419 | 11.6747480861459
  14 |    7 |                 1 | 13.2558869162301
  15 |    8 |                 1 | 14.2558869162301
  16 |    5 |                 1 | 15.2558869162301
  17 |    2 |                 1 | 16.2558869162301
  18 |    1 |                 0 | 17.2558869162301
(18 rows)

Parámetros

Parámetro Descripción
Coordenadas 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

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

Columna Tipo Descripción
id BIGINT

(opcional) Identificador de la coordenada.

  • Cuando faltan las coordenadas recibirán un id a partir de 1, en el orden indicado.
x FLOAT Valor X de la coordenada.
y FLOAT Valor Y de la coordenada.

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:Prueba \(3\) veces por temperatura con factor de enfriamiento de \(0.5\), sin tener una ejecución aleatoria
SELECT* from pgr_TSPeuclidean(
    $$
    SELECT id, st_X(the_geom) AS x, st_Y(the_geom) AS y FROM edge_table_vertices_pgr
    $$,
    tries_per_temperature := 3,
    cooling_factor := 0.5,
    randomize := false);
 seq | node |       cost       |     agg_cost
-----+------+------------------+------------------
   1 |    1 |  1.4142135623731 |                0
   2 |    3 |                1 |  1.4142135623731
   3 |    4 |                1 | 2.41421356237309
   4 |    9 | 0.58309518948453 | 3.41421356237309
   5 |   16 | 0.58309518948453 | 3.99730875185762
   6 |    6 |                1 | 4.58040394134215
   7 |    5 |                1 | 5.58040394134215
   8 |    8 |                1 | 6.58040394134215
   9 |    7 | 1.58113883008419 | 7.58040394134215
  10 |   14 |   1.499999999999 | 9.16154277142634
  11 |   15 |              0.5 | 10.6615427714253
  12 |   13 |              1.5 | 11.1615427714253
  13 |   17 | 1.11803398874989 | 12.6615427714253
  14 |   12 |                1 | 13.7795767601752
  15 |   11 |                1 | 14.7795767601752
  16 |   10 |                2 | 15.7795767601752
  17 |    2 |                1 | 17.7795767601752
  18 |    1 |                0 | 18.7795767601752
(18 rows)

Ejemplo:Omitir el Recocido Simulado y mostrar información del proceso
SET client_min_messages TO DEBUG1;
SET
SELECT* from pgr_TSPeuclidean(
    $$
    SELECT id, st_X(the_geom) AS x, st_Y(the_geom) AS y FROM edge_table_vertices_pgr
    $$,
    tries_per_temperature := 0,
    randomize := false);
DEBUG:  Processing Information
Initializing tsp class ---> tsp.greedyInitial ---> tsp.annealing ---> OK

Cycle(100) 	total changes =0	0 were because  delta energy < 0
Total swaps: 3
Total slides: 0
Total reverses: 0
Times best tour changed: 4
Best cost reached = 18.7796
 seq | node |       cost       |     agg_cost
-----+------+------------------+------------------
   1 |    1 |  1.4142135623731 |                0
   2 |    3 |                1 |  1.4142135623731
   3 |    4 |                1 | 2.41421356237309
   4 |    9 | 0.58309518948453 | 3.41421356237309
   5 |   16 | 0.58309518948453 | 3.99730875185762
   6 |    6 |                1 | 4.58040394134215
   7 |    5 |                1 | 5.58040394134215
   8 |    8 |                1 | 6.58040394134215
   9 |    7 | 1.58113883008419 | 7.58040394134215
  10 |   14 |   1.499999999999 | 9.16154277142634
  11 |   15 |              0.5 | 10.6615427714253
  12 |   13 |              1.5 | 11.1615427714253
  13 |   17 | 1.11803398874989 | 12.6615427714253
  14 |   12 |                1 | 13.7795767601752
  15 |   11 |                1 | 14.7795767601752
  16 |   10 |                2 | 15.7795767601752
  17 |    2 |                1 | 17.7795767601752
  18 |    1 |                0 | 18.7795767601752
(18 rows)

Las consultas utilizan la red Datos Muestra .