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@openstreetmap.org
https://lists.openstreetmap.org/listinfo/talk-fr
_______________________________________________
Talk-fr mailing list
Talk-fr@openstreetmap.org
https://lists.openstreetmap.org/listinfo/talk-fr
