Disponibilidad: 2.0.0
Soporte
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
Resumen
pgr_TSP(Matrix 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_TSP(
$$
SELECT * FROM pgr_dijkstraCostMatrix(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
(SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
directed := false)
$$,
randomize := false);
seq | node | cost | agg_cost
-----+------+------+----------
1 | 1 | 1 | 0
2 | 2 | 1 | 1
3 | 3 | 1 | 2
4 | 4 | 1 | 3
5 | 9 | 1 | 4
6 | 6 | 1 | 5
7 | 11 | 1 | 6
8 | 12 | 2 | 7
9 | 10 | 1 | 9
10 | 13 | 4 | 10
11 | 7 | 1 | 14
12 | 8 | 1 | 15
13 | 5 | 2 | 16
14 | 1 | 0 | 18
(14 rows)
Parámetro | Descripción |
---|---|
Matrix SQL | una consulta SQL, descrita en Inner query |
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
|
Matrix SQL: una consulta SQL, que debe devolver un conjunto de filas con las siguientes columnas:
Columna | Tipo | Descripción |
---|---|---|
start_vid | BIGINT |
Identificador del vértice inicial. |
end_vid | BIGINT |
Identificador del vértice final. |
agg_cost | FLOAT |
Costo para pasar de start_vid a end_vid |
Se puede utilizar con las funciones Cost Matrix - Categoría, con el valor directed := false.
Si se utiliza directed := true, la matriz no simétrica resultante debe convertirse a simétrica mediante la corrección de los valores no simétricos de acuerdo con las necesidades de la aplicación.
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 |
|
agg_cost | FLOAT |
|
Ejemplo: | Inicio en el vértice \(7\) |
---|
SELECT * FROM pgr_TSP(
$$
SELECT * FROM pgr_dijkstraCostMatrix(
'SELECT id, source, target, cost, reverse_cost FROM edge_table',
(SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
directed := false
)
$$,
start_id := 7,
randomize := false
);
seq | node | cost | agg_cost
-----+------+------+----------
1 | 7 | 1 | 0
2 | 8 | 1 | 1
3 | 5 | 1 | 2
4 | 2 | 1 | 3
5 | 1 | 2 | 4
6 | 3 | 1 | 6
7 | 4 | 1 | 7
8 | 9 | 1 | 8
9 | 12 | 1 | 9
10 | 11 | 1 | 10
11 | 10 | 1 | 11
12 | 13 | 3 | 12
13 | 6 | 3 | 15
14 | 7 | 0 | 18
(14 rows)
Ejemplo: | Uso con puntos de interés. |
---|
Para generar una matriz simétrica:
SELECT * FROM pgr_TSP(
$$
SELECT * FROM pgr_withPointsCostMatrix(
'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
'SELECT pid, edge_id, fraction from pointsOfInterest',
array[-1, 3, 5, 6, -6], directed := false)
$$,
start_id := 5,
randomize := false
);
seq | node | cost | agg_cost
-----+------+------+----------
1 | 5 | 0.3 | 0
2 | -6 | 1.3 | 0.3
3 | -1 | 1.6 | 1.6
4 | 3 | 1 | 3.2
5 | 6 | 1 | 4.2
6 | 5 | 0 | 5.2
(6 rows)
Las consultas utilizan la red Datos Muestra .
Índices y tablas