Nom¶

• pgr_tsp - Retourne la meilleure route à partir d’un point de départ via une liste de nœuds.
• pgr_tsp - Retourne le meilleur ordre de route quand passée une matrice de distance.
• pgr_makeDistanceMatrix - Retourne une matrice de distance Euclidienne à partir de points fournis par le résultat sql.

Synopsis¶

Le problème du voyageur du commerce (TSP) demande la question suivante : étant donnée une liste de villes et les distances entre chaque paire de villes, quelle est la route la plus courte possible qui visite chaque ville exactement une fois et retourne à la ville originale ? Cet algorithme utilise un recuit simulé pour retourner une solution approximative de haute qualité. Retourne un ensemble de lignes pgr_costResult (seq, id1, id2, cost), qui constituent un chemin.

pgr_costResult[] pgr_tsp(sql text, start_id integer);
pgr_costResult[] pgr_tsp(sql text, start_id integer, end_id integer);

Retourne un ensemble de (seq integer, id1 integer, id2 integer, cost float8) qui est le meilleur ordre pour visiter les noeuds dans la matrice. id1 est l’index dans la matrice de distance. id2 est l’id du point à partir du sql.

Si aucun end_id est donné ou est -1 ou égal au start_id alors le résultat TSP est supposé être une boucle circulaire retournant au départ. Si end_id est fourni alors la route est supposée commencer et finir aux ids désignés.

record[] pgr_tsp(matrix float[][], start integer)
record[] pgr_tsp(matrix float[][], start integer, end integer)

Description¶

Avec distances euclidiennes

Le solveur TSP est basé sur l’ordonnancement des points en utilisant la distance (euclidienne) de ligne droite [] entre les noeuds. L’implémentation est utilisé un algorithme d’approximation qui est très rapide. Ce n’est pas une solution exacte, mais il est garanti qu’une solution est retournée après un certain nombre d’itérations.

SELECT id, x, y FROM vertex_table

La fonction retourne un ensemble de pgr_costResult[]:

Créer une matrice de distance

Pour les utilisateurs qui ont besoin d’une matrice de distance, nous avons une fonction simple qui prend le SQL dans sql comme décrit au-dessus et retourne avec dmatrix et ids.

SELECT dmatrix, ids from pgr_makeDistanceMatrix('SELECT id, x, y FROM vertex_table');

La fonction retourne un enregistrement de dmatrix, ids:

Avec matrice de distance

Pour les utilisateurs, qui ne veulent pas utiliser les distances euclidiennes, nous fournissons aussi la capacité de passer une matrice de distances et retourne une liste ordonnée de nœuds pour le meilleur ordre pour visiter chacun. C’est à l’utilisateur de remplir complètement la matrice de distances.

Le noeud end est un paramètre optionnel, vous pouvez juste le laisser ainsi si vous voulez une boucle où start``est le dépôt et la route retourne au dépôt. Si vous incluez le paramètre ``end, nous optimisons le chemin de start à end et minimisons la distance de la route en incluant les points restants.

La matrice de distances est un tableau multidimensionnel PostgreSQL array type qui doit être de taille N x N.

Le résultat sera de N enregistrements de [ seq, id ]:

Notes de bas de page

Histoire

• Renommé depuis la version 2.0.0
• dépendance GAUL supprimée depuis la version 2.0.0

Exemples¶

• Using SQL parameter (all points from the table, atarting from 6 and ending at 5). We have listed two queries in this example, the first might vary from system to system because there are multiple equivalent answers. The second query should be stable in that the length optimal route should be the same regardless of order.

 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)

• Utiliser la matrice de distances (boucle A en partant de 1)

When using just the start node you are getting a loop that starts with 1, in this case, and travels through the other nodes and is implied to return to the start node from the last one in the list. Since this is a circle there are at least two possible paths, one clockwise and one counter-clockwise that will have the same length and be equall valid. So in the following example it is also possible to get back a sequence of ids = {1,0,3,2} instead of the {1,2,3,0} sequence listed below.

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)

• Utiliser la matrice de distance (en partant de 1, jusqu’à 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)

• Using the vertices table edge_table_vertices_pgr generated by pgr_createTopology. Again we have two queries where the first might vary and the second is based on the overal path length.

     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)

Les requêtes utilisent le réseau Données d’échantillon.

Voir aussi¶

• pgr_costResult[]
• http://en.wikipedia.org/wiki/Traveling_salesman_problem
• http://en.wikipedia.org/wiki/Simulated_annealing