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

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.41421356237 |             0
   2 |    3 |              1 | 1.41421356237
   3 |    4 |              1 | 2.41421356237
   4 |    9 | 0.583095189485 | 3.41421356237
   5 |   16 | 0.583095189485 | 3.99730875186
   6 |    6 |              1 | 4.58040394134
   7 |   11 |              1 | 5.58040394134
   8 |   12 |  1.11803398875 | 6.58040394134
   9 |   17 |            1.5 | 7.69843793009
  10 |   13 |            0.5 | 9.19843793009
  11 |   15 |            0.5 | 9.69843793009
  12 |   10 |  1.58113883008 | 10.1984379301
  13 |   14 |  1.58113883008 | 11.7795767602
  14 |    7 |              1 | 13.3607155903
  15 |    8 |              1 | 14.3607155903
  16 |    5 |              1 | 15.3607155903
  17 |    2 |              1 | 16.3607155903
  18 |    1 |              0 | 17.3607155903
(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.41421356237 |             0
   2 |    3 |              1 | 1.41421356237
   3 |    4 |              1 | 2.41421356237
   4 |    9 | 0.583095189485 | 3.41421356237
   5 |   16 | 0.583095189485 | 3.99730875186
   6 |    6 |              1 | 4.58040394134
   7 |    5 |              1 | 5.58040394134
   8 |    8 |              1 | 6.58040394134
   9 |    7 |  1.58113883008 | 7.58040394134
  10 |   14 |            1.5 | 9.16154277143
  11 |   15 |            0.5 | 10.6615427714
  12 |   13 |            1.5 | 11.1615427714
  13 |   17 |  1.11803398875 | 12.6615427714
  14 |   12 |              1 | 13.7795767602
  15 |   11 |              1 | 14.7795767602
  16 |   10 |              2 | 15.7795767602
  17 |    2 |              1 | 17.7795767602
  18 |    1 |              0 | 18.7795767602
(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.41421356237 |             0
   2 |    3 |              1 | 1.41421356237
   3 |    4 |              1 | 2.41421356237
   4 |    9 | 0.583095189485 | 3.41421356237
   5 |   16 | 0.583095189485 | 3.99730875186
   6 |    6 |              1 | 4.58040394134
   7 |    5 |              1 | 5.58040394134
   8 |    8 |              1 | 6.58040394134
   9 |    7 |  1.58113883008 | 7.58040394134
  10 |   14 |            1.5 | 9.16154277143
  11 |   15 |            0.5 | 10.6615427714
  12 |   13 |            1.5 | 11.1615427714
  13 |   17 |  1.11803398875 | 12.6615427714
  14 |   12 |              1 | 13.7795767602
  15 |   11 |              1 | 14.7795767602
  16 |   10 |              2 | 15.7795767602
  17 |    2 |              1 | 17.7795767602
  18 |    1 |              0 | 18.7795767602
(18 rows)

Las consultas utilizan la red Datos Muestra .