Discussion :

[flamme34]

Bonjour,

Dans le cadre d’un projet ayant pour but de contrôler des moteurs, je souhaiterais avoir votre aide pour optimiser mes temps en mouvement.
Je vous explique.

Aujourd’hui je reçois une succession de trajectoire à effectuer sur des moteurs XY. Ces trajectoires n’ont pas besoin d’être exécutés dans un ordre précis. Et je souhaiterais réorganiser ces trajectoires pour que le temps de mouvement total soit le plus court possible.

Je vais vous imager ça. Voici un exemple de trajectoires que je peux recevoir.



Si je les écris dans l’ordre de réception voici ce que ça donne.



Et maintenant voici un exemple d’optimisation possible.



Donc vous le comprendrez la seconde façon est plus rapide que la première.
Je souhaiterais donc trouver un algorithme me permettant de faire cela. J’ai pensé à l’algorithme utilisant les graphes, mais j’avoue ne pas savoir si c’est la meilleure solution ni lequel utiliser.
Dans mes recherches j’ai pu voir l’algorithme de dijkstra qui recherche le plus court chemin entre deux sommets mais moi je cherche surtout la manière de faire en sorte que le parcours entre TOUS les sommets soit le plus court.
J’ai vu également que le terme de graphe hamiltonien pouvait correspondre à ma définition mais je n’ai rien vu concernant le parcours le plus rapide dans ce genre de graphe.

J’espère que vous pourrez m’aider, et je vous remercie d’avance pour cela.

[laurent_ott]

Bonjour.
Ça ressemble un peu au problème du voyageur de commerce.
Voir dans ma signature le tome 3 qui reprend certaines techniques.
Bonne continuation.

[flamme34]

En effet ça y ressemble beaucoup. Je vais regarder ça de plus prêt.

Je reviendrais ici après l'avoir lu si il me reste des questions.

Merci de ton aide ^^.

[dourouc05]

Ça ressemble effectivement à un cas très particulier du TSP : le cas euclidien, vu que tu travailles dans le monde "réel", les distances entre tes points correspondant à des distances au sens mathématique. Dans ce cas, l'algorithme de Chrystofides (https://fr.wikipedia.org/wiki/Algori...e_Christofides) semble tout adapté. Certes, tu n'auras pas de solution optimale à tous les coups, mais c'est raisonnablement facile à implémenter (utilise des bibliothèques de graphes comme Boost Graph Library, Lemon en C++ : la plupart des étapes correspond à des algorithmes classiques). Contrairement aux "algorithmes" évolutionnaires de Laurent, tu es sûr que tu auras une assez bonne solution, peu importe la forme de ton entrée. Si tu veux une solution réellement optimale, regarde Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html).

[valentin03]

Comme tu dois passer partout et dans le même sens, c'est pas ça le plus rapide ?

[Guesset]

Bonjour,

Quelle quantité de points de passage ?

Si la volumétrie est faible (de l'ordre d'une quarataine, par exemple, les solutions exactes restent accessibles car de l'ordre de l'heure).

Salutations

[dourouc05]

Si la volumétrie est faible (de l'ordre d'une quarataine, par exemple, les solutions exactes restent accessibles car de l'ordre de l'heure).

Pour un TSP classique, on peut atteindre une solution exacte pour une quarantaine de points en quelques secondes, pour des cas pathologiques, avec des machines et algorithmes d'avant 2000… (http://www.math.uwaterloo.ca/tsp/con...s/bench99.html)

[Guesset]

Bonsoir,

Pour un TSP classique, on peut atteindre une solution exacte pour une quarantaine de points en quelques secondes, pour des cas pathologiques, avec des machines et algorithmes d'avant 2000… (http://www.math.uwaterloo.ca/tsp/con...s/bench99.html)

J'ai été voir la page de ce lien mais je n'ai rien trouvé de tel mais je n'ai pas cherché outre cette page (il est tard).

Par ailleurs, travailler sur un seul coeur sur une machine moderne peut s'avérer moins efficace que sur une vieille machine mono coeur.

Salutations

[flamme34]

Désolé pour le retard pour les réponses. je viens tout juste de rentrer de congé.

Comme tu dois passer partout et dans le même sens, c'est pas ça le plus rapide ?

C'est possible. je t'avoue que j'ai fait ça a main lever sans aucun calcul.

Quelle quantité de points de passage ?

Tout dépend des motif. Ça peut aller de quelques un à quelques centaine de milliers.

En tout cas merci pour vos réponses et votre intérêt pour ma problématique