pgr_TSPeuclidean
¶
pgr_TSPeuclidean
- Aproximación usando el algoritmo metric.

Boost Graph Inside¶
Disponibilidad:
Versión 3.2.1
Algoritmo Metrico de la Librería Boost
El algoritmo de recocido simulado ya no es utilizado.
The Simulated Annealing Algorithm related parameters are ignored: max_processing_time, tries_per_temperature, max_changes_per_temperature, max_consecutive_non_changes, initial_temperature, final_temperature, cooling_factor, randomize
Versión 3.0.0
Cambio de nombre de pgr_eucledianTSP
Versión 2.3.0
Nueva función Oficial
Descripción¶
Definición del Problema¶
En el problema del vendedor viajante (TSP) 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?
Características¶
Este problema es un problema de optimización NP-duro.
Se utiliza el algoritmo métrico
La implementación genera soluciones que son el doble de largas que el recorrido óptimo en el peor de los casos cuando:
El grafo es no dirigido
El grafo está completamente conectado
Grafo donde los costos de viaje en los segmentos cumplen con la desigualdad del triángulo.
En un grafo no dirigido:
Los costos del viaje son simétricos:
Traveling costs from
u
tov
are just as much as traveling fromv
tou
- Any duplicated identifier will be ignored. The coordinates that will be kept
is arbitrarly.
The coordinates are quite similar for the same identifier, for example
1, 3.5, 1 1, 3.499999999999 0.9999999
Las coordenadas son bastante diferentes para el mismo identificador, por ejemplo:
2 , 3.5, 1.0 2 , 3.6, 1.1
Firmas¶
Resumen
pgr_TSPeuclidean(Coordinates SQL, [start id], [end_id]) RETURNS SETOF (seq, node, cost, agg_cost)
- Ejemplo
Con valores predeterminados
SELECT * FROM pgr_TSPeuclidean(
$$
SELECT id, st_X(the_geom) AS x, st_Y(the_geom)AS y FROM edge_table_vertices_pgr
$$);
seq | node | cost | agg_cost
-----+------+----------------+---------------
1 | 1 | 0 | 0
2 | 2 | 1 | 1
3 | 8 | 1.41421356237 | 2.41421356237
4 | 7 | 1 | 3.41421356237
5 | 14 | 1.58113883008 | 4.99535239246
6 | 15 | 1.5 | 6.49535239246
7 | 13 | 0.5 | 6.99535239246
8 | 17 | 1.5 | 8.49535239246
9 | 12 | 1.11803398875 | 9.61338638121
10 | 9 | 1 | 10.6133863812
11 | 16 | 0.583095189485 | 11.1964815707
12 | 6 | 0.583095189485 | 11.7795767602
13 | 11 | 1 | 12.7795767602
14 | 10 | 1 | 13.7795767602
15 | 5 | 1 | 14.7795767602
16 | 4 | 2.2360679775 | 17.0156447377
17 | 3 | 1 | 18.0156447377
18 | 1 | 1.41421356237 | 19.4298583
(18 rows)
Parámetros¶
Parámetro |
Tipo |
Descripción |
---|---|---|
|
Coordinates SQL as described below |
TSP optional parameters¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ANY-INTEGER |
|
El primer vértice visitado
|
|
ANY-INTEGER |
|
Último vértice visitado antes de regresar a “
|
Inner queries¶
Coordenadas SQL¶
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador del vértice inicial. |
|
|
Valor X de la coordenada. |
|
|
Valor Y de la coordenada. |
Columnas de Resultados¶
Devuelve el CONJUNTO DE (seq, node, cost, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
seq |
|
Secuencia de filas. |
node |
|
Identificador del nodo/coordenada/punto. |
cost |
|
Coste que se debe recorrer desde el
|
agg_cost |
|
Costo agregado del
|
Ejemplos Adicionales¶
- Ejemplo
Prueba 29 ciudades del Sáhara Occidental
Este ejemplo muestra cómo hacer pruebas de rendimiento utilizando los datos de ejemplo de la Universidad de Waterloo utilizando el conjunto de datos de 29 ciudades del Sáhara Occidental
Creación de una tabla para datos y almacenamiento de los datos
CREATE TABLE wi29 (id BIGINT, x FLOAT, y FLOAT, geom geometry);
INSERT INTO wi29 (id, x, y) VALUES
(1,20833.3333,17100.0000),
(2,20900.0000,17066.6667),
(3,21300.0000,13016.6667),
(4,21600.0000,14150.0000),
(5,21600.0000,14966.6667),
(6,21600.0000,16500.0000),
(7,22183.3333,13133.3333),
(8,22583.3333,14300.0000),
(9,22683.3333,12716.6667),
(10,23616.6667,15866.6667),
(11,23700.0000,15933.3333),
(12,23883.3333,14533.3333),
(13,24166.6667,13250.0000),
(14,25149.1667,12365.8333),
(15,26133.3333,14500.0000),
(16,26150.0000,10550.0000),
(17,26283.3333,12766.6667),
(18,26433.3333,13433.3333),
(19,26550.0000,13850.0000),
(20,26733.3333,11683.3333),
(21,27026.1111,13051.9444),
(22,27096.1111,13415.8333),
(23,27153.6111,13203.3333),
(24,27166.6667,9833.3333),
(25,27233.3333,10450.0000),
(26,27233.3333,11783.3333),
(27,27266.6667,10383.3333),
(28,27433.3333,12400.0000),
(29,27462.5000,12992.2222);
Agregar una geometría (con fines visuales)
UPDATE wi29 SET geom = ST_makePoint(x,y);
Al obtener un costo total del recorrido, comparar el valor con la duración de un recorrido óptimo, que es 27603, dado en el conjunto de datos
SELECT *
FROM pgr_TSPeuclidean($$SELECT * FROM wi29$$)
WHERE seq = 30;
seq | node | cost | agg_cost
-----+------+---------------+---------------
30 | 1 | 2266.91173136 | 28777.4854127
(1 row)
Obtener una geometría del recorrido
WITH
tsp_results AS (SELECT seq, geom FROM pgr_TSPeuclidean($$SELECT * FROM wi29$$) JOIN wi29 ON (node = id))
SELECT ST_MakeLine(ARRAY(SELECT geom FROM tsp_results ORDER BY seq));
st_makeline
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
01020000001E000000F085C9545558D4400000000000B3D040000000000069D440107A36ABAAAAD040000000000018D54000000000001DD040107A36AB2A10D7401FF46C5655FDCE40000000000025D740E10B93A9AA1ECF40F085C954D552D740E10B93A9AA62CC40107A36ABAA99D7400000000000E1C940107A36AB4A8FD840E10B93A9EA26C840F085C954D5AAD9401FF46C5655EFC840F085C95455D0D940E10B93A9AA3CCA40F085C9545585D940000000000052CC400000000080EDD94000000000000DCB40A52C431C0776DA40E10B93A9EA33CA40A52C431C6784DA40E10B93A9AAC9C940A52C431C8764DA402C6519E2F87DC94000000000A0D1DA4096B20C711C60C940F085C95455CADA40000000000038C840F085C9545598DA40E10B93A9AA03C740F085C954551BDA40E10B93A9AAD1C640F085C9545598DA40000000000069C440107A36ABAAA0DA40E10B93A9AA47C440107A36ABAA87DA40E10B93A9AA34C340000000008089D94000000000009BC440F085C954D526D6401FF46C5655D6C840F085C954D5A9D540E10B93A9AAA6C9400000000000CDD4401FF46C56556CC940000000000018D5400000000000A3CB40F085C954D50DD6400000000000EECB40000000000018D5401FF46C56553BCD40F085C9545558D4400000000000B3D040
(1 row)
Visualmente, la primera imagen es la “solución óptima”<https://www.math.uwaterloo.ca/tsp/world/witour.html>`__ y la segunda imagen es la solución obtenida con pgr_TSPeuclidean
.


Ver también¶
Red Datos Muestra .
Índices y tablas