[OSM-talk-fr] Nouvelles bornes Trilib'

[Julien Coupey]

Re,

Si je comprends ton usage, le respect des sens uniques est important 
(vélo, voiture) mais pas forcément le sens de parcours des chemins pour 
lesquels il y a le choix ? En particulier tu n'a pas forcément besoin de 
passer dans les deux sens sur les chemins qui le permettent ?

Si c'est bien le cas, il y a peut-être un bricolage à tenter pour faire 
quelque chose sans rien développer. Mettons que tu veuilles prendre une 
photo tous les x mètres. Tu transformes alors ton problème en TSP en 
disant que tu souhaites visiter un paquet de nœuds par chemin (voire 
peut-être tous les nœuds de chaque chemin). On peut penser qu'une 
solution raisonnable à ce problème te fera parcourir les chemins en une 
seule fois dans la plupart des cas. Limitations :

- sans garantie d'absence de demi-tour au milieu en fonction de 
l'espacement des nœuds OSM)
- explosion de la taille du TSP (peut-être gérable quand même)
- c'est clairement une façon un peu moche de chercher quelque chose 
d'utilisable sans résoudre le problème initial ;-)

Si tu veux tenter quelque chose dans ce goût-là, n'hésite pas à me 
contacter en direct, je serais curieux de voir si ça peut donner quelque 
chose d'exploitable.

À+
Julien

Le 12/01/2017 à 14:05, Stéphane Péneau a écrit :
> Le 11/01/2017 à 17:14, Julien Coupey a écrit :
>> Salut
>>
>> Les problèmes de tournées consistent à passer par tous les nœuds d'un
>> certain graphe (avec éventuellement des contraintes additionnelles).
>> La nature du problème du postier chinois est différente puisqu'il
>> s'agit de visiter tous les arcs d'un graphe, donc malheureusement la
>> réponse à ta question est non. ;-)
>>
>> Concrètement, si le sens de visite des chemins n'a pas d'importance et
>> s'il n'y a pas à tenir compte de sens uniques (par exemple à pied),
>> alors le graphe est non orienté et il existe des méthodes
>> réalistes/efficaces en temps de calcul pour trouver la solution optimale.
>> Par contre, si tu dois tenir compte des sens uniques et/ou si le sens
>> de visite a de l'importance (par exemple tu veux passer dans les rues
>> une fois dans chaque sens), alors là le problème se complique nettement !
>>
>> À +
>> Julien
>>
> C'est dommage, et mon usage potentiel (passer partout, à vélo ou en
> voiture pour prendre des photos) rentre dans le cas des situations qui
> sont plus compliquées. (gestion des sens unique, gros gros malus sur les
> demi-tour, etc..)
>
> Stf
>
> _______________________________________________
> Talk-fr mailing list
> Talk-fr at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/talk-fr