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

Aller au contenu | Aller au menu | Aller à la recherche


< 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 >

mercredi 25 avril 2007

PgRouting: Nouvelle version 1.0.0.a et utilisation de la fonctionnalité TSP

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

mardi 24 avril 2007

Journées du Libre à Montpellier - ALL - 14 au 16 juin 2007

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/

La WishList pour PostGIS 2.0

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.

lundi 23 avril 2007

Guide de l'utilisateur PostgreSQL/PostGIS, version 11.1: annexe sur dblink

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.