Le problème du voyageur de commerce n'est PAS de parcourir toutes les routes, mais de passer par toutes les villes par le plus court chemin et revenir au point de départ (une variante étant de ne pas non plus croiser un chemin déjà parcouru, de façon à former un "anneau" sans auto-intersection). Ce problème est le classique problème du routage de circuits imprimés ou circuits intégrés (la contrainte de ne pas croiser un chemin parcouru est résolue en utilisant au moins 2 couches de gravures, mais on a un résultat plus compact avec 4 ou 6 couches, comme on le voit sur les cartes mères de nos PC).
Passer par toutes les routes est impossible sans repasser plusieurs fois par certaines, notamment s'il y a des intersections avec un nombre impair de routes/rues connectées (par exemple on devra nécessairement parcourir les impasses en faisant demi-tour par le même chemin) : la contrainte étant seulement de trouver le chemin total le plus court. Les heuristiques existent pour ce problème, mais sont beaucoup plus complexes pour ce problème que pour le problème classique consistant à ne passer qu'une seule fois dans chaque ville. Il n'y a pas d'algorithme en temps non exponentiel, les heuristiques en temps logarithmique sont possibles, celles considérées comme bonnes. Pour OSM je pense qu'on a aussi les contraintes des sens uniques (à moins que le parcours soit à faire à pied) et on peut se demander s'il faut ou non parcourir chacune des branches des Y de raccordement aux ronds-points (non nécessaire si la but est de parcourir tout ce qui est à portée de vue sans obstacle obstruant ce qu'on voit sur une autre voie proche (mais là OSM ne fournit pas toujours de données sur la visibilité réelle et si on est au volant il n'est pas facile de voir non plus les panneaux orientés de l'autre côté de la route en sens inverse. D'autres contraintes sont liées au mode de transport utilisé (une voiture ne pourra pas aller sur les chemins piétons ou cyclistes). Je pense que pour planifier un parcours il vaut mieux se limiter au problème classique du voyageur de commerce: passer par un certain nombre de points reliés par des chemins autorisés, et formant un graphe connexe. Ensuite pour compléter la visite, autoriser le stationnement et parcourir les alentours à pied si nécessaire. Alors peu importe la distance et si on emprunte un chemin plusieurs fois, que ce soit à pied, à vélo ou en voiture. Autour de chaque point de stationnement, établir ensuite la liste des chemins supplémentaires à visiter en faisant une boucle pouvant revenir plusieurs fois au point de départ et tenter de minimiser les parcours à pied. Là il n'y aura pas trop de combinaisons à tester autour de chaque point d'arrêt, et on peut faire une recherche en temps exponentiel sur chaque petit secteur. Ce qu'on obtient alors c'est la "tournée du facteur". Le 4 octobre 2016 à 19:14, didier2020 <didier2...@free.fr> a écrit : > c'est le fameu probleme du voyageur de commerce mais ramené a une > ville ... > > tu peu essayé ca : > https://www.multiroute.de/?locale=fr > > > Le mardi 04 octobre 2016 à 19:01 +0200, Stéphane Péneau a écrit : > > Bonsoir tout le monde, > > > > Si vous deviez parcourir toutes les routes d'une commune, comment est-ce > > que vous vous y prendriez ? > > > > On part du principe qu'on met de côté tout ce qui est highway=path ou > > track pour conserver les routes adaptées aux voitures. > > > > Je peux facilement récupérer ces routes dans Josm avec un requête > > overpass, puis faire quelques corrections, comme ajouter les routes qui > > sont très légèrement au-delà des limites admin, mais ensuite, comment > > trouver le parcours le plus court et être guidé, depuis OsmAnd par > exemple. > > > > J'avoue que je sèche. > > > > Le première application pourrait se faire ce week-end pour l'opération > > libre de montreuil-en-touraine > > > > http://www.openstreetmap.org/relation/171408 > > > > Stf > > > > > > _______________________________________________ > > Talk-fr mailing list > > Talk-fr@openstreetmap.org > > https://lists.openstreetmap.org/listinfo/talk-fr > > > > _______________________________________________ > Talk-fr mailing list > Talk-fr@openstreetmap.org > https://lists.openstreetmap.org/listinfo/talk-fr >
_______________________________________________ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr
