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.
Variante voyageur itinérant
- cquest
- Messages : 1748
- Inscription : ven. avr. 16, 2010 12:22 am
- Localisation : Val de Marne
- Contact :
Re: Variante voyageur itinérant
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...

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...
- cquest
- Messages : 1748
- Inscription : ven. avr. 16, 2010 12:22 am
- Localisation : Val de Marne
- Contact :
Re: Variante voyageur itinérant
Une vidéo youtube explique assez bien le principe pour le résoudre et quelques variantes: https://www.youtube.com/watch?v=JCSmxUO0v3k
-
- Messages : 10
- Inscription : dim. juin 04, 2017 11:18 am
Re: Variante voyageur itinérant
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.
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.
- cquest
- Messages : 1748
- Inscription : ven. avr. 16, 2010 12:22 am
- Localisation : Val de Marne
- Contact :
Re: Variante voyageur itinérant
Les traitements proposés sont basiques et n'intègrent pas le "postier chinois"
-
- Messages : 10
- Inscription : dim. juin 04, 2017 11:18 am
Re: Variante voyageur itinérant
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.
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.
- cquest
- Messages : 1748
- Inscription : ven. avr. 16, 2010 12:22 am
- Localisation : Val de Marne
- Contact :
Re: Variante voyageur itinérant
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 

Qui est en ligne ?
Utilisateurs parcourant ce forum : Aucun utilisateur inscrit et 2 invités