Variante voyageur itinérant

[02e26e4022]

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.

[cquest]

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...

[cquest]

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

[02e26e4022]

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.

[cquest]

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

[02e26e4022]

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.

[cquest]

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