Comment calculer un trajet optimal entre point gpx ?

bonsoir,


j’ai un fichier avec 1100 point différents et j’aimerai savoir si il existe une méthode pour calculer un chemin optimum passant par tout les point.

l’idéal serai un calcul routier mais je ne pense pas qu’il soit possible de traiter autant de point. Un tracé indiquant le trajet à vol d’oiseau me suffirai et j’aurai plus qu’a adapter le trajet proposé en l’adaptant au terrain et rue une fois sur place.

Bonjour,
C’est le problème bien connu du Voyageur de Commerce. Déjà OSRM prévoit cette fonctionnalité, mais elle n’est pas encore en place.

L’article Wikipédia indique que le nombre de possibilité pour 71 villes est déjà un nombre de 100 chiffres. En visant une solution “itinéraire” (càd l’optimum via le réseau routier d’OSM), il parait délicat d’explorer les possibilités via des requêtes à OSRM (aussi rapides soient-elles).

En visant une solution simple, en se basant sur une distance à vol d’oiseau, il y a des algo pour obtenir une solution approchée en un temps raisonnable. Regardes tsplib, et le mot clé tsp.
Pour améliorer la solution selon le réseau routier, on doit pouvoir (?) pondérer les arrêtes avec les distances (ou durées de parcours) fournis par OSRM pour les n points les plus proches de chaque points…

Bruno

Salut,

ton problème est connu depuis longtemps, il y a même des algorithmes spécialement conçus pour :wink:
voir http://fr.wikipedia.org/wiki/Problème_du_voyageur_de_commerce

il y a par exemple pgRouting (http://www.davidgis.fr/documentation/win32/html/apa.html#id2518043)
un tutoriel sur l’utilisaiton de pgRouting tellement frais que c’est daté du jour : http://www.postgis.fr/chrome/site/docs/workshop-routing-foss4g/docs/pgRoutingWorkshop.pdf

mais également GRASS : http://grass.osgeo.org/grass64/manuals/v.net.salesman.html

Ah oui il y a pgRouting!

Tu pourras nous faire un retour sur tes résultats, surtout concernant les temps de réponse avec autant de points ?
bruno

Nickel la coïncidence entre ma demande et la date du tutoriel est étonnante. J’en profite pour indiquer que l’installation avec Ubuntu trusty est légèrement différente en ce qui concerne le nom des paquets :

gaul-devel n’existe pas
postgresql-8.4-pgrouting est à remplacer par postgresql-9.3-pgrouting
postgresql-8.4-pgrouting-dd n’existe pas
postgresql-8.4-pgrouting-tsp n’existe pas

Ce qui donne sudo apt-get install postgresql-9.3-pgrouting posm2pgrouting pgrouting-workshop


Pour les travaux pratique, peut être est il préférable d’utiliser la racine du dossier utilisateur au lieu de ~/home/Desktop qui est valable seulement si la session démarre en anglais. Je suis en train de suivre différent tuto en parallèle pour adapter le tout à ma config mais ça à l’air bien intéressant