Tout pareil, mais en 2 liens : Problème du voyageur de commerce https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce C'est celui-là qui est abordé par le site indiqué par Didier https://www.multiroute.de/?locale=fr
Le problème indiqué par Stéphane est plus proche de: Problème du postier chinois https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_postier_chinois Je n'ai pas de solution toute prête, peut-être essayer un plugin de QGIS: https://plugins.qgis.org/plugins/chinesepostman/ (aucune idée si ça fonctionne) Benoît 2016-10-04 19:35 GMT+02:00 Philippe Verdy <verd...@wanadoo.fr>: > 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 > _______________________________________________ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr
