Le blog de Jean David TECHER, un Réunionnais à Saint-Priest/Lyon

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. Supposons que je veuille trouver le chemin de longueur totale minimale passant par les noeuds 43,30,18,41,1,13. Mon point de départ sera le noeud 41.
Fig 2. Noeuds par lesquels je souhaite passer en commençant par le noeud 41. La requête sera tout simplement

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. Je m'excuse si l'exemple n'est pas des + convaincants mais c'est juste pour le fun .

TODO: A ajouter dans la doc

La news n'est pas nouvelle mais je me permets quand même de la faire apparaà®tre sur mon blog. Comme chaque année ALL - Association pour le Logiciel Libre - organise la 6ème édition des Journées du Logiciel Libre à  Montpellier. Répartie sur 3 journées, elle se décline sur 3 journées dédiée chacune à  un public et un thème différent:

1. Jeudi 14 : journée collectivités - le poste de travail libre;
2. Vendredi 15 : journée entreprises - enjeux, migration et sécurité;
3. Samedi 16 : journée grand public - citoyenneté, éducation et jeux.

Je me souviens quand 2005, j'avais tenu un stand avec Gérald. On a reçu des contacts très intéressants cette année-là . Un des liens possibles à  consulter est http://www.all.asso.fr/Realisations/2007/jlm07/

Ayé, Paul a publié la liste des souhaits pour PostGIS 2.0 disponible à  http://docs.google.com/Doc?id=dg99qr76_2dgt26j. Le moins que l'on puisse dire est que la liste est des plus intéressantes. A mon sens chaque point a été passé en revue: geocoding, routing/réseau, conformité au SFSQL2, amélioration de la documentation, faire de geometry_columns une vue ou autre manipulation.

Je ne passerais pas ici tout en revue mais je citerais par exemple quelques points qui ont attiré mon attention:

1. renommer les fonctions et les préfixer: Use ST_ for SQL/MM, SE_ for ESRI, SP_ for PostGIS specific. Comme souligné dans ce passage, celà  peut porter à  la plus grande confusion. Personnellement, je ne me suis pas encore penché sur le cas du SQL/MM qui apparaà®t comme un sur-ensemble des «objets» de PostGIS. Lire les spécifications c'est long!
2. que faire de geometry_columns? comme dit le résumé, il faudra attendre que PostgreSQL supporte les triggers sur les tables-système. A quand? A voir!

Il semblerait que la route soit assez longue avant de voir apparaà®tre une première ébauche d'une 2.0 mais la liste des souhaits me semble plus que correcte.

Suite à  mon précédent billet sur dblink, j'ai mis ce billet en forme en tant qu'annexe dans ma documentation. On peut ainsi le retrouver à  l'URL http://www.davidgis.fr/documentation/win32/html/apc.html. Contrairement à  ce que j'avais annoncé vendredi vu que je n'ai pas eu le temps, j'incluerais l'annexe sur tsearch2 au cours de cette semaine.