Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune

[Stéphane Péneau]

Bon, ce ne fut pas un grand succès de ce côté-là.

Si je disais à OsmAnd de suivre impérativement la trace, je me 
retrouvais à faire des demi-tours assez bizarres. Et si je laissais 
OsmAnd faire comme il le sent, il me supprimait d'importantes parties du 
parcours.


Je rattrape mon retard sur ma todo list (dont le traitement des presque 
100 000 photos du week-end), et je m'y remets.


Stf

Le 07/10/2016 à 10:40, Etienne Trimaille a écrit :
Tout depend du nettoyage que tu fais dans JOSM, mais tu peux 
directement interroger l'overpass depuis QGIS avec le plugin QuickOSM 
: highway in nomdelacommune, linestring uniquement.


Le 7 octobre 2016 à 03:38, Stéphane Péneau > a écrit :


Je suis sur une bonne piste.

Overpass Turbo -> highway=* in nomdelacommune
Josm, un peu de nettoyage puis export en geojson
import dans Qgis (linestring uniquement)
Application du plugin chinese postman
Export GPX avec force track/route activé, et en ne prenant que les
linestrings.

Crash test demain à Montreuil-en-Touraine pour l'OPL.

Stf


Le 04/10/2016 à 22:51, Stéphane Péneau a écrit :

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 

Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune

[Etienne Trimaille]

Tout depend du nettoyage que tu fais dans JOSM, mais tu peux directement
interroger l'overpass depuis QGIS avec le plugin QuickOSM : highway in
nomdelacommune, linestring uniquement.

Le 7 octobre 2016 à 03:38, Stéphane Péneau  a
écrit :

> Je suis sur une bonne piste.
>
> Overpass Turbo -> highway=* in nomdelacommune
> Josm, un peu de nettoyage puis export en geojson
> import dans Qgis (linestring uniquement)
> Application du plugin chinese postman
> Export GPX avec force track/route activé, et en ne prenant que les
> linestrings.
>
> Crash test demain à Montreuil-en-Touraine pour l'OPL.
>
> Stf
>
>
> Le 04/10/2016 à 22:51, Stéphane Péneau a écrit :
>
>> 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
>>
>
>
>
> ___
> 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

[Stéphane Péneau]

Je suis sur une bonne piste.

Overpass Turbo -> highway=* in nomdelacommune
Josm, un peu de nettoyage puis export en geojson
import dans Qgis (linestring uniquement)
Application du plugin chinese postman
Export GPX avec force track/route activé, et en ne prenant que les 
linestrings.


Crash test demain à Montreuil-en-Touraine pour l'OPL.

Stf

Le 04/10/2016 à 22:51, Stéphane Péneau a écrit :

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




___
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

[osm . sanspourriel]

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" <talk-fr@openstreetmap.org>
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

Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune

[Stéphane Péneau]

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

[Vincent de Château-Thierry]

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

[Frédéric Rodrigo]

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

[Benoit Fournier]

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

Re: [OSM-talk-fr] Parcourir toutes les routes d'une commune

[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
>
___
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

[didier2020]

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