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.1) 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.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 la Consulta interna

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.

Columna

Tipo

Descripción

BIGINT

(opcional) Identificador de la coordenada.

Cuando faltan las coordenadas recibirán un id a partir de 1, en el orden indicado.

FLOAT

Valor X de la coordenada.

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 .

Ver también¶

Índices y tablas