[OSM-talk-fr] Parcourir toutes les routes d'une commune
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
Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune
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
Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune
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 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
Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune
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 : > 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 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 > > > > _
Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune
Non, pas tout à fait, c'est le problème du postier chinois : https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_postier_chinois Le 04/10/2016 à 19:14, didier2020 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
Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune
Bonsoir, Le 04/10/2016 à 21:22, Frédéric Rodrigo a écrit : Le 04/10/2016 à 19:14, didier2020 a écrit : Le mardi 04 octobre 2016 à 19:01 +0200, Stéphane Péneau a écrit : 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. J'ai rencontré exactement ce problème en cherchant à parcourir toutes les rues de Clermont-Fd (en 2012). J'ai géré ça de façon artisanale (litote). J'ai divisé la ville en secteurs, globalement en prenant appui sur les grands axes. J'ai ensuite imprimé via Maposmatic chaque secteur séparément, sur du A4. Et j'ai composé ma tournée, sur une semaine, en balayant les secteurs un par un. Balayer signifiait : parcourir toutes les voies d'un secteur, en les raturant sur mon exemplaire papier pour identifier simplement le reste à faire. L'idée était de ne pas sortir d'un secteur tant que tous les axes n'étaient pas crayonnés. J'ai prévenu que c'était artisanal ;) Au final j'estime à facilement un quart du temps de la tournée le temps dédié, à l'arrêt, à décider des quelques prochaines rues à parcourir, avec en cible le souhait de minimiser les passages multiples sur un même axe. Un bon casse-tête ! Plus facile à traiter à Manhattan ou... Levallois-Perret : http://www.openstreetmap.org/relation/86985#map=15/48.8946/2.2874 Le première application pourrait se faire ce week-end pour l'opération libre de montreuil-en-touraine Ce WE Stéphane on bricolera ça en vélo ;) vincent ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr
Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune
Oui, c'est ça, c'est le problème du postier chinois !! Multiroute n'est pas adapté. J'ai essayé le plugin Qgis (le plugin est caché dans les plugs expérimentaux), et c'est mieux. Il m'indique à chaque fois un tracé de moins d'1km, mais je vois bien un parcours qui semble réaliste. En revanche, lorsque j'exporte en gpx, et que je l'ouvre dans OsmAnd, ce dernier ne me propose rien de cohérent, malgré les différents exports que j'ai tentés, route, waypoint, track, etc.. Je ne sais pas si c'est le plugin qui ne fonctionne pas correctement, mes choix d'exports qui sont mauvais, ou OsmAnd qui me fait des blagues. Vincent, Et bien, c'était courageux de faire ça de cette façon. On pourra regarder, mais j'en aurai besoin dès le vendredi, et en voiture je préfère de pas quitter la route des yeux pour regarder un plan papier. Le 04/10/2016 à 22:32, Vincent de Château-Thierry a écrit : Bonsoir, Le 04/10/2016 à 21:22, Frédéric Rodrigo a écrit : Le 04/10/2016 à 19:14, didier2020 a écrit : Le mardi 04 octobre 2016 à 19:01 +0200, Stéphane Péneau a écrit : 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. J'ai rencontré exactement ce problème en cherchant à parcourir toutes les rues de Clermont-Fd (en 2012). J'ai géré ça de façon artisanale (litote). J'ai divisé la ville en secteurs, globalement en prenant appui sur les grands axes. J'ai ensuite imprimé via Maposmatic chaque secteur séparément, sur du A4. Et j'ai composé ma tournée, sur une semaine, en balayant les secteurs un par un. Balayer signifiait : parcourir toutes les voies d'un secteur, en les raturant sur mon exemplaire papier pour identifier simplement le reste à faire. L'idée était de ne pas sortir d'un secteur tant que tous les axes n'étaient pas crayonnés. J'ai prévenu que c'était artisanal ;) Au final j'estime à facilement un quart du temps de la tournée le temps dédié, à l'arrêt, à décider des quelques prochaines rues à parcourir, avec en cible le souhait de minimiser les passages multiples sur un même axe. Un bon casse-tête ! Plus facile à traiter à Manhattan ou... Levallois-Perret : http://www.openstreetmap.org/relation/86985#map=15/48.8946/2.2874 Le première application pourrait se faire ce week-end pour l'opération libre de montreuil-en-touraine Ce WE Stéphane on bricolera ça en vélo ;) vincent ___ 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
Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune
Alors une version semi-artisanale ou semi-industrielle en fonction de vos intéressantes réponses. Tu ajoutes manuellement ou avec l'export dans l'ordre indiqué par QGis les points que tu auras réussi à exporter et tu laisses OSMAND faire le routage. C'est de la théorie, pas testé dans la pratique, actuellement mes trajets sont simples et non relatifs à OSM. Mais j'ai quand même répondu à mon client que pour son besoin il fallait utiliser OSM (JOSM en fait avec le greffon qui va bien) et que le résultat voulu il l'avait directement sur OpenSeaMap. Jean-Yvon Gesendet: Dienstag, 04. Oktober 2016 um 23:51 Uhr Von: "Stéphane Péneau - stephane.pen...@wanadoo.fr" An: "Discussions sur OSM en français" Betreff: Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune Oui, c'est ça, c'est le problème du postier chinois !! Multiroute n'est pas adapté. J'ai essayé le plugin Qgis (le plugin est caché dans les plugs expérimentaux), et c'est mieux. Il m'indique à chaque fois un tracé de moins d'1km, mais je vois bien un parcours qui semble réaliste. En revanche, lorsque j'exporte en gpx, et que je l'ouvre dans OsmAnd, ce dernier ne me propose rien de cohérent, malgré les différents exports que j'ai tentés, route, waypoint, track, etc.. Je ne sais pas si c'est le plugin qui ne fonctionne pas correctement, mes choix d'exports qui sont mauvais, ou OsmAnd qui me fait des blagues. Vincent, Et bien, c'était courageux de faire ça de cette façon. On pourra regarder, mais j'en aurai besoin dès le vendredi, et en voiture je préfère de pas quitter la route des yeux pour regarder un plan papier. Le 04/10/2016 à 22:32, Vincent de Château-Thierry a écrit : > Bonsoir, > > Le 04/10/2016 à 21:22, Frédéric Rodrigo a écrit : >> Le 04/10/2016 à 19:14, didier2020 a écrit : >>> Le mardi 04 octobre 2016 à 19:01 +0200, Stéphane Péneau a écrit : 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. > > J'ai rencontré exactement ce problème en cherchant à parcourir toutes > les rues de Clermont-Fd (en 2012). J'ai géré ça de façon artisanale > (litote). J'ai divisé la ville en secteurs, globalement en prenant > appui sur les grands axes. J'ai ensuite imprimé via Maposmatic chaque ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr