pgr_TSP¶
pgr_TSP
- Aproximación usando el algoritmo*metrico*.

Adentro: Boost Graph¶
Disponibilidad:
Versión 3.2.1
Algoritmo Metrico de la Librería Boost
El algoritmo de recocido simulado ya no es utilizado.
Se ignoran los parámetros relacionados con el algoritmo de recocido simulado: max_processing_time, tries_per_temperature, max_changes_per_temperature, max_consecutive_non_changes, initial_temperature, final_temperature, cooling_factor, randomize
Versión 2.3.0
Cambio de firma
Firma antigua ya no soportada
Versión 2.0.0
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 generales¶
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:
Los costos del viaje de
u
av
son tanto como viajar dev
au
Características¶
Se puede utilizar con funciones Cost Matrix - Categoría preferiblemente con directed => false.
Con
directed => false
Generará un grafo que:
es no dirigido
está completamente conectado (siempre que el grafo tenga un componente)
todos los costos de viaje en los segmentos vumplen con la desigualdad del triángulo.
Cuando
start_vid = 0 Ó end_vid = 0
Las soluciones generadas están garantizadas para ser el doble de largas que el recorrido óptimo en el peor de los casos
Cuando
start_vid != 0 Y end_vid != 0 Y start_vid != end_vid
No está garantizado que la solución sea, en el peor de los casos, el doble de larga que el recorrido óptimo, debido al hecho de que end_vid se ve obligado a estar en una posición fija.
Con
directed => true
No está garantizado que la solución sea, en el peor de los casos, el doble de larga que el recorrido óptimo.
Generará un grafo que:
es dirigido
está completamente conectado (siempre que el grafo tenga un componente)
algunos (o todos) los costos de viaje en los segmentos podrían no obedecer a la desigualdad del triángulo.
Como se requiere un grafo no dirigido, el grafo dirigido se transforma de la siguiente manera:
los segmentos (u, v) y (v, u) se consideran el mismo segmentos (denotado (u, v)
Si “
agg_cost
difiere entre una o más instancias del segmento (u, v)El valor mínimo de
agg_cost
en todas las instancias del segmento (u, v) se considera como elagg_cost
de la arista (u, v)Algunos (o todos) los costos de viaje en los segmentos aún podrían no obedecer a la desigualdad del triángulo.
Cuando los datos están incompletos, pero es un grafo conectado, los valores faltantes se calcularán con el algoritmo Dijkstra.
Firmas¶
Resumen
pgr_TSP(Matrix SQL, [start_id], [end_id])
RETURNS SETOF (seq, node, cost, agg_cost)
Ejemplo: Usando pgr_dijkstraCostMatrix para generar la información de la matriz
Línea 5 Los vértices 15 a 18 no están incluidos porque no están conectados.
1SELECT * FROM pgr_TSP(
2 $$
3 SELECT * FROM pgr_dijkstraCostMatrix(
4 'SELECT id, source, target, cost, reverse_cost FROM edge_table',
5 (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
6 directed => false)
7 $$);
8 seq | node | cost | agg_cost
9-----+------+------+----------
10 1 | 1 | 0 | 0
11 2 | 2 | 1 | 1
12 3 | 3 | 1 | 2
13 4 | 4 | 1 | 3
14 5 | 9 | 1 | 4
15 6 | 12 | 1 | 5
16 7 | 6 | 2 | 7
17 8 | 5 | 1 | 8
18 9 | 8 | 1 | 9
19 10 | 7 | 1 | 10
20 11 | 10 | 3 | 13
21 12 | 11 | 1 | 14
22 13 | 13 | 2 | 16
23 14 | 1 | 4 | 20
24(14 rows)
25
Parámetros¶
Parámetro |
Tipo |
Valores predeterminados |
Descripción |
---|---|---|---|
Matrix SQL |
|
Una consulta SQL, descrita en la sección Matrix SQL. |
|
start_vid |
|
|
El primer vértice visitado
|
end_vid |
|
|
Último vértice visitado antes de regresar a “
|
Consulta interna¶
Matriz SQL¶
Matrix SQL: una consulta SQL, que debe devolver un conjunto de filas con las siguientes columnas:
Columna |
Tipo |
Descripción |
---|---|---|
start_vid |
|
Identificador del vértice inicial. |
end_vid |
|
Identificador del vértice final. |
agg_cost |
|
Costo para pasar de start_vid a end_vid |
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
Inicio en el vértice \(7\)
Línea 9
start_vid => 7
1SELECT * FROM pgr_TSP(
2 $$
3 SELECT * FROM pgr_dijkstraCostMatrix(
4 'SELECT id, source, target, cost, reverse_cost FROM edge_table',
5 (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
6 directed => false
7 )
8 $$,
9 start_id => 7
10);
11 seq | node | cost | agg_cost
12-----+------+------+----------
13 1 | 7 | 0 | 0
14 2 | 8 | 1 | 1
15 3 | 5 | 1 | 2
16 4 | 2 | 1 | 3
17 5 | 1 | 1 | 4
18 6 | 3 | 2 | 6
19 7 | 4 | 1 | 7
20 8 | 9 | 1 | 8
21 9 | 12 | 1 | 9
22 10 | 11 | 1 | 10
23 11 | 6 | 1 | 11
24 12 | 10 | 2 | 13
25 13 | 13 | 1 | 14
26 14 | 7 | 4 | 18
27(14 rows)
28
- Ejemplo
Uso de puntos de interés para generar una matriz asimétrica.
Para generar una matriz asimétrica:
Línea 5 La información
side
depointsOfInterset
se ignora al no incluirla en la consultaLínea 7 Generación de una matriz asimétrica con directed => true`
\(min(agg\_cost(u, v), agg\_cost(v, u))\) se considera como el
agg_cost
La solución que puede ser mayor que el doble de larga que el tour óptimo porque:
La desigualdad del triángulo podría no estar satisfecha.
start_id != 0 Y end_id != 0
1SELECT * FROM pgr_TSP(
2 $$
3 SELECT * FROM pgr_withPointsCostMatrix(
4 'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
5 'SELECT pid, edge_id, fraction from pointsOfInterest',
6 array[-1, 3, 5, 6, -6],
7 directed => true)
8 $$,
9 start_id => 5,
10 end_id => 6
11);
12 seq | node | cost | agg_cost
13-----+------+------+----------
14 1 | 5 | 0 | 0
15 2 | -6 | 0.3 | 0.3
16 3 | -1 | 1.3 | 1.6
17 4 | 3 | 1.6 | 3.2
18 5 | 6 | 1 | 4.2
19 6 | 5 | 1 | 5.2
20(6 rows)
21
- Ejemplo
Datos incompletos conectados
Usando segmentos seleccionados (2, 4, 5, 8, 9, 15) la matriz no es completa pero está conectada
1SELECT source AS start_vid, target AS end_vid, 1 AS agg_cost
2FROM edge_table WHERE id IN (2, 4, 5, 8, 9, 15);
3 start_vid | end_vid | agg_cost
4-----------+---------+----------
5 2 | 3 | 1
6 2 | 5 | 1
7 3 | 6 | 1
8 5 | 6 | 1
9 6 | 9 | 1
10 9 | 12 | 1
11(6 rows)
12
El segmento (5, 12) no existe en los datos iniciales, pero se calcula internamente.
1SELECT * FROM pgr_TSP(
2 $$
3 SELECT source AS start_vid, target AS end_vid, 1 AS agg_cost
4 FROM edge_table WHERE id IN (2, 4, 5, 8, 9, 15)
5 $$);
6 seq | node | cost | agg_cost
7-----+------+------+----------
8 1 | 2 | 0 | 0
9 2 | 3 | 1 | 1
10 3 | 6 | 1 | 2
11 4 | 12 | 1 | 3
12 5 | 9 | 1 | 4
13 6 | 5 | 1 | 5
14 7 | 2 | 1 | 6
15(7 rows)
16
Las consultas utilizan la red Datos Muestra .
Ver también¶
Algoritmo Metrico de la Librería Boost
Índices y tablas