Variante voyageur itinérant

Extraire des données OSM, créer sa carte, uMap, utiliser sur un GPS ou un smartphone...
02e26e4022
Messages : 10
Inscription : dim. juin 04, 2017 11:18 am

Variante voyageur itinérant

Message par 02e26e4022 » mar. mars 13, 2018 10:01 pm

Bonjour,

Une problématique que j'aimerai résoudre depuis un moment, mais je n'ai pas trouvé à ce jour.

J'ai un certain nombre de tronçons de route à parcourir. J'aimerais obtenir (en GPX par exemple) le chemin le plus court passant par l'intégralité de ces tronçons au moins une fois en tenant compte des sens interdits. Idéalement en passant une fois dans chaque sens sur toutes les routes à double sens, mais ça c'est secondaire.

Des idées ou des outils (de préférence libres) à proposer ? J'ai essayé sous QGis, mais pas réussi à obtenir quoi que ce soit jusqu'à présent.

Merci d'avance.

Avatar de l’utilisateur
cquest
Messages : 1775
Inscription : ven. avr. 16, 2010 12:22 am
Localisation : Val de Marne
Contact :

Re: Variante voyageur itinérant

Message par cquest » mer. mars 14, 2018 9:39 am

C'est le problème du postier "chinois"... ;)

https://en.wikipedia.org/wiki/Route_inspection_problem
https://fr.wikipedia.org/wiki/Probl%C3% ... er_chinois

Je ne connais pas d'outil pour le traiter, mais ça m'intéresse !
Connaître le nom donné à ce problème va permettre de mieux cibler les recherches...

Avatar de l’utilisateur
cquest
Messages : 1775
Inscription : ven. avr. 16, 2010 12:22 am
Localisation : Val de Marne
Contact :

Re: Variante voyageur itinérant

Message par cquest » mer. mars 14, 2018 10:35 am

Une vidéo youtube explique assez bien le principe pour le résoudre et quelques variantes: https://www.youtube.com/watch?v=JCSmxUO0v3k

02e26e4022
Messages : 10
Inscription : dim. juin 04, 2017 11:18 am

Re: Variante voyageur itinérant

Message par 02e26e4022 » mer. mars 14, 2018 12:50 pm

Merci.
Je ne savais pas que c’était considéré comme un autre problème à part entière.

Et accessoirement QGis vient de lancer la version 3.0, et ils ont ajouté une catégorie "analyse réseaux". Va y avoir matière fouiller un peu.

Avatar de l’utilisateur
cquest
Messages : 1775
Inscription : ven. avr. 16, 2010 12:22 am
Localisation : Val de Marne
Contact :

Re: Variante voyageur itinérant

Message par cquest » mer. mars 14, 2018 3:00 pm

Les traitements proposés sont basiques et n'intègrent pas le "postier chinois"

02e26e4022
Messages : 10
Inscription : dim. juin 04, 2017 11:18 am

Re: Variante voyageur itinérant

Message par 02e26e4022 » mer. mars 14, 2018 9:00 pm

Effectivement, j'ai testé (très rapidement) aujourd'hui, c'est pas encore ça…
J'ai aussi trouvé un module "chinese postman" dans les dépôts expérimentaux de QGis 2.18 (tout de suite, avec le bon nom, c'est plus facile). Il a l'air de fonctionner. Pas moyen de tenir compte des sens uniques ou des vitesses de circulation en revanche. Mais c'est un bon début.

Avatar de l’utilisateur
cquest
Messages : 1775
Inscription : ven. avr. 16, 2010 12:22 am
Localisation : Val de Marne
Contact :

Re: Variante voyageur itinérant

Message par cquest » jeu. mars 15, 2018 8:55 am

Et oui, le coup du nom j'ai vécu ça en voulant colorier une carte avec les 4 couleurs... il fallait chercher "coloration de graphe" et comme je n'avais rien trouvé je m'étais recodé un algo naïf mais qui fonctionnait plutôt bien ;)

Répondre

Qui est en ligne ?

Utilisateurs parcourant ce forum : Aucun utilisateur inscrit et 2 invités