pgRouting Manual (2.0.0)

pgr_tsp - Voyageur du commerce

«  pgr_ksp - K-plus court chemin   ::   Contenu   ::   pgr_trsp - Plus court chemin avec restriction de virage (TRSP)  »

pgr_tsp - Voyageur du commerce

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.

sql:

une requête SQL, qui devrait retourner un ensemble de lignes avec les colonnes suivantes :

SELECT id, x, y FROM vertex_table
id:int4 identifiant du sommet
x:coordonnée x float8
y:coordonnée y float8
start_id:

int4 id du point de départ

end_id:

int4 id du point final, c’est OPTIONNEL, si inclure la route est optimisée d’un point de départ à la fin, sinon c’est supposé que le départ et la fin sont le même point.

La fonction retourne un ensemble de pgr_costResult[]:

seq:séquence de ligne
id1:index interne de la matrice de distance
id2:id du noeud
cost:coût pour traverser du nœud courant au prochain nœud

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:

dmatrix:float8[][] une distance symétrique euclidienne basée sur sql.
ids:integer[] un tableau d’ids comme ils sont ordonnés dans la matrice de distances.

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.

matrix:float[][] matrice de distances de points
start:int4 index du point de départ
end:int4 (optionnel) index du point final

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 ]:

seq:séquence de ligne
id:index dans la matrice

Notes de bas de page

[1]Il a été pensé que pré-calculer les distances de conduites entre les noeuds en utilisant Dijkstra, mais ensuite j’ai lu un papier (malheureusement je ne me rappelle plus qu’il l’a écrit), où il a été prouvé que la qualité de TSP avec la distance euclidienne est seulement légèrement moindre que celle avec la distance réelle dans le cas d’une couche de ville normale. Dans le cas d’un réseau très épars ou rivières et ponts ça devient plus imprécis, mais toujours pleinement satisfaisant. Bien sûr c’est mieux d’avoir une solution exacte, mais c’est un compromis entre la qualité et la vitesse (et le temps de développement aussi. Si vous avez besoin d’une solution précise, vous pouvez générer une matrice de distance et utiliser ce formulaire de la fonction pour obtenir vos résultats.

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.

«  pgr_ksp - K-plus court chemin   ::   Contenu   ::   pgr_trsp - Plus court chemin avec restriction de virage (TRSP)  »