mercredi 25 avril 2007
PgRouting: Nouvelle version 1.0.0.a et utilisation de la fonctionnalité TSP
Par david techer, mercredi 25 avril 2007 à 03:13 :: PostGIS et PostgreSQL
Nouvelle version 1.0.0a
Anton A. Patrushev annonçait aujourd'hui que la version 1.0.0a de PgRouting était disponible sur le site http://www.postlbs.org/. Je l'ai compilé aujourd'hui, pas de problème particulier sous Ubuntu Dapper.
fonction TSP
Dans ma doc pour le moment, je m'étais arrêté à  l'utilisation de la fonctionnalité shortest_path_astar()
- qui utilise l'algorythme A* -. Ce soir, j'ai essayé la fonctionnalité tsp(). TSP signifie Traveling Salesman Problem, désignant ainsi le problème du voyageur du commerce. Pour une définition plus profane, il s'agit du problème du père Noël, ou de l'agent commercial qui doit visiter des clients dans un trajet professionnel en essayant d'optimiser son parcours - un peu de théorie des graphes, celà  ne fait pas de mal que les puristes de la discipline m'excusent -.
Exemple
Pour rappel dans ma doc, j'ai le graphe avec les noeuds
Fig 1. Noeuds de mon graphe.

Fig 2. Noeuds par lesquels je souhaite passer en commençant par le noeud 41.
routing=# SELECT * from tsp('select distinct source as source_id, x1::double precision as x, y1::double precision as y from troncon_route_edges where source in (43,30,18,41,1,13)','43,30,18,41,1,13',41); vertex_id | edge_id | cost -----------+-----------+----------------------- 41 | 138321080 | 0 30 | 0 | 2.12199579047121e-314 1 | 8 | 6.84394238386657e-316 18 | 16 | 2.12199611507234e-314 13 | 138523056 | 6.79720117142741e-313 43 | 406 | 1.23516411460312e-322 (6 lignes)Les colonnes
edge_id
et cost
n'ont pas d'importance. Seul compte la colonne vertex_id
. Selon l'ordre énuméré des valeurs des lignes de la colonne de vertex_id, il me faudra donc pour optimiser mon parcours aller de 41 à  30, puis de 30 à  1, puis de 1 à  18, de 18 à  13 et de 13 à  43. Pour la suite, pour trouver le parcours finale, il suffira par exemple d'appliquer de proche en proche la fonction shortest_path_astar() sur les couples (source,target) avec dans l'ordre d'énumération (41,30), puis (30,1), puis (1,18) etc...
Et on obtiendra par exemple le parcours suivant

Fig 3. Parcours à  effectuer dans l'ordre 41,30,1,18,13,43 en partant du noeud 41.

TODO: A ajouter dans la doc