pgr_tsp - Vendedor Viajante¶
Nombre¶
- pgr_tsp - Devuelve la mejor ruta desde un nodo inicial vía un lista de nodos.
- pgr_tsp - Devuelve el mejor orden de la ruta cuando se le introduce una matriz de distancias
- pgr_makeDistanceMatrix - Devuelve una matriz de distancias Euclidiana desde los puntos que le provee la consulta sql.
Sinopsis¶
En el problema del vendedor viajante (TSP) o problema del vendedor se hace la siguiente pregunta: dada una lista de las ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y vuelve a la ciudad de origen. Este algoritmo hace simulaciones para devolver una solución aproximada de alta calidad. Devuelve un conjunto de registros pgr_costResult (seq, id1, id2, cost) que conforman un camino.
pgr_costResult[] pgr_tsp(sql text, start_id integer);
pgr_costResult[] pgr_tsp(sql text, start_id integer, end_id integer);
Devuelve un conjunto de (seq integer, integer id1, id2 integer, cost float8) que representa el mejor orden para visitar los nodos en la matriz. id1 es el índice en la matriz de distancia. id2 es el identificador del punto de la consulta sql.
Si no se suministra el identificador de un punto de llegada end_id o si es -1 o si es el mismo que al identificador del punto de partida start_id, TSP supone que se regresa al punto de partida. Si se suministra un punto de llegada end_id entonces se supone que la ruta inicia y termina en los identificadores designados.
record[] pgr_tsp(matrix float[][], start integer)
record[] pgr_tsp(matrix float[][], start integer, end integer)
Descripción¶
Con distancias Euclidianas
El evaluador TSP se basa en los puntos ordenados utilizando la línea recta (euclidiana) de distancias [] entre nodos. La aplicación utiliza un algoritmo de aproximación que es muy rápido. No es una solución exacta, pero se garantiza que una solución se devuelve después de cierta cantidad de iteraciones.
| sql: | Consulta SQL que debe proporcionar un conjunto de registros con los siguientes campos: SELECT id, x, y FROM vertex_table
|
||||||
|---|---|---|---|---|---|---|---|
| start_id: | int4 Identificador del punto de partida |
||||||
| end_id: | int4 identificador del punto de llegada, esto es opcional, si se incluye la ruta será optimizada desde la partida hasta la llegada, de lo contrario se supone que la partida y la llegada son el mismo punto. |
La función devuelve el conjunto de pgr_costResult[]:
| seq: | Secuencia de registros |
|---|---|
| id1: | índice interno de la matriz de distancias |
| id2: | int4 identificador del nodo |
| cost: | costo para atravesar desde el nodo actual hasta el siguiente nodo. |
Crear una matriz de distancias
Para usuarios necesitan una matriz de distancias tenemos una función simple que toma consultas SQL en sql como se describe anteriormente y devuelve un registro con dmatrix e ids.
SELECT dmatrix, ids from pgr_makeDistanceMatrix('SELECT id, x, y FROM vertex_table');
La función devuelve un registro de dmatrix, `` ids``:
| dmatrix: | float8[][] una matriz de distancia euclidiana simétrica basado en la consulta sql. |
|---|---|
| ids: | integer[] una matriz de identificadores basados en el orden de la matriz de distancias. |
Con la matriz de distancia
Para los usuarios, que no requieren utilizar distancias euclidianas, tenemos también la posibilidad de pasar una matriz de distancia que resuelve y devuelve una lista ordenada de nodos con el mejor orden visita de cada nodo. Es el usuario debe llenar completamente la matriz de distancia.
| matrix: | float[][] matriz de distancia de puntos |
|---|---|
| start: | int4 índice del punto de inicio |
| end: | int4 (opcional) índice del nodo final |
El nodo final end es un parámetro opcional, se puede omitir cuando se requiere un bucle donde el principio start es un depósito y la ruta debe regresar de vuelta al depósito. Al incluir el parámetro final end, se optimiza el camino de principio start al final end y se reduce al mínimo la distancia de la ruta al ir incluyendo los puntos restantes.
La matriz de distancias es un array de PostgreSQL multidimensional que debe ser de tamaño N x N.
El resultado será de N registros de [ seq, id ]:
| seq: | Secuencia de registros |
|---|---|
| id: | índice dentro de la matriz |
Notas al pie
| [1] | Se ha pensado sobre precalcular las distancias de manejo entre los nodos usando Dijkstra, pero después de leer un artículo (por desgracia no recuerdo quién lo escribió), en el cuál se comprobó que la calidad del TSP con distancia euclidiana es sólo ligeramente peor que uno con las distancias reales en el caso de la distribución normal de una ciudad. En caso de una escasa red o ríos y puentes se vuelve todavía más inexacta, pero es una solución enteramente satisfactoria. Claro que es bueno tener la solución exacta, pero hay un compromiso entre la calidad y la velocidad (y el tiempo de desarrollo también). Si usted necesita una solución más precisa, puede generar una matriz de distancias y usarla para obtener los resultados. |
Historia
- Renombrado en la versión 2.0.0
- Dependencia de la GAUL eliminada en la versión 2.0.0
Ejemplos¶
- Usando el parámetro SQL (todos los puntos de la tabla, comenzando en 6 y terminando en 5). En este ejemplo, hemos enumerado dos consultas, la primera puede variar de sistema a sistema porque hay varias respuestas equivalentes. La segunda consulta debe ser estable en que la ruta óptima ya que la longitud debe ser la misma independientemente del orden.
SELECT seq, id1, id2, round(cost::numeric, 2) AS cost
FROM pgr_tsp('SELECT id, x, y FROM vertex_table ORDER BY id', 6, 5);
seq | id1 | id2 | cost
-----+-----+-----+------
0 | 5 | 6 | 1.00
1 | 6 | 7 | 1.00
2 | 7 | 8 | 1.41
3 | 1 | 2 | 1.00
4 | 0 | 1 | 1.41
5 | 2 | 3 | 1.00
6 | 3 | 4 | 1.00
7 | 8 | 9 | 1.00
8 | 11 | 12 | 1.00
9 | 10 | 11 | 1.41
10 | 12 | 13 | 1.00
11 | 9 | 10 | 2.24
12 | 4 | 5 | 1.00
(13 rows)
SELECT round(sum(cost)::numeric, 4) as cost
FROM pgr_tsp('SELECT id, x, y FROM vertex_table ORDER BY id', 6, 5);
cost
---------
15.4787
(1 row)
- Utilizando la matriz de distancia (un circuito a partir de 1)
Cuando se utiliza sólo el nodo de inicio, entoces se tiene un bucle que comienza, en este caso, con 1 y viaja a través de los otros nodos y se sobreentiende que regresa al nodo inicial desde el último nodo de la lista. Puesto que esto es un bucle, hay al menos dos posibles caminos, uno hacia la derecha y otro en sentido opuesto que tienen la misma longitud y ambos son igualmente válidos. Así que en el ejemplo siguiente también es posible recuperar una secuencia de identificadores = {1,0,3,2} en vez de la secuencia {1,2,3,0} que se obtiene a continuación.
SELECT seq, id FROM pgr_tsp('{{0,1,2,3},{1,0,4,5},{2,4,0,6},{3,5,6,0}}'::float8[],1);
seq | id
-----+----
0 | 1
1 | 2
2 | 3
3 | 0
(4 rows)
- Utilizando la matriz de distancia (a partir de 1, terminando en 2)
SELECT seq, id FROM pgr_tsp('{{0,1,2,3},{1,0,4,5},{2,4,0,6},{3,5,6,0}}'::float8[],1,2);
seq | id
-----+----
0 | 1
1 | 0
2 | 3
3 | 2
(4 rows)
- Usando la tabla de vértices edge_table_vertices_pgr generada por pgr_createTopology. De nuevo tenemos dos consultas donde la primera puede variar y la segunda se basa en la longitud total del camino.
SELECT seq, id1, id2, round(cost::numeric, 2) AS cost
FROM pgr_tsp('SELECT id::integer, st_x(the_geom) as x,st_x(the_geom) as y FROM edge_table_vertices_pgr ORDER BY id', 6, 5);
seq | id1 | id2 | cost
-----+-----+-----+------
0 | 5 | 6 | 0.00
1 | 10 | 11 | 0.00
2 | 2 | 3 | 1.41
3 | 3 | 4 | 0.00
4 | 11 | 12 | 0.00
5 | 8 | 9 | 0.71
6 | 15 | 16 | 0.00
7 | 16 | 17 | 2.12
8 | 1 | 2 | 0.00
9 | 14 | 15 | 1.41
10 | 7 | 8 | 1.41
11 | 6 | 7 | 0.71
12 | 13 | 14 | 2.12
13 | 0 | 1 | 0.00
14 | 9 | 10 | 0.00
15 | 12 | 13 | 0.00
16 | 4 | 5 | 1.41
(17 rows)
SELECT round(sum(cost)::numeric, 4) as cost
FROM pgr_tsp('SELECT id::integer, st_x(the_geom) as x,st_x(the_geom) as y FROM edge_table_vertices_pgr ORDER BY id', 6, 5);
cost
---------
11.3137
(1 row)
Las consultas usan la red de ejemplo Datos Muestra