Discussion :

[Avatar36]

Bonjour,

Je cherche à faire un algorithme (en Matlab mais peu importe) pour modéliser l'enroulement de tuyaux sur une roue. Je ne suis pas sûr qu'il y ai un solution simple (voire même une solution tout court).

Concernant les tuyaux à enrouler:
- Il y en a plusieurs avec des diamètres extérieurs qui peuvent être différents
- Je veux pouvoir spécifier lequel je veux dérouler en premier (donc celui qui doit être sur l'extérieur de la roue).
- Ils ont une longueurs Lng qui leur est propre.

Concernant la roue:
- L'enroulement débute à un rayon r
- L'enroulement termine à un rayon R. R>r.
- Attention, la roue à une forme trapézoïdale! Donc au rayon r, la largeur pour enrouler est de l et est de L au rayon R, avec l<L.

J'ai fait un algorithme qui me permet d'enrouler les tuyaux en commençant par la bas (au rayon r). Mais dans mon cas, il faudrait que je commence à enrouler par le haut vu que que je veux spécifier le premier tuyau déroulable.
L'enroulement est forcément fait par couches à un même rayon. Quand le rayon est plein, on démarre une couche suivante.
Bien sûr, il y a des contraintes:
- Les tuyaux ne peuvent pas continuer à être enroulés sur une roue si cela signifie dépasser le rayon R.
- Les tuyaux ayants une masse linéique propre, il ne faut pas que le poids de la roue dépasse un poids Pmax.

Ce que je cherche à faire c'est un algorithme qui me permettrait d'optimiser l'ordre d'enroulement des tuyaux pour remplir le moins de roues possibles. Au point où j'en suis, à part tester tous les remplissages possible un par un et de les comparer je ne vois pas. Sauf que si j'ai un grand nombre de tuyaux, disons une dizaine, il y a beaucoup trop de combinaisons possibles. J'ai regardé l'algorithme du sac à dos, etc... Mais ça ne me semble pas applicable dans mon cas.
Merci de votre aide.

Cordialement

[Flodelarab]

Bonjour

si j'ai un grand nombre de tuyaux, disons une dizaine,

Tu n'as pas 10 tuyaux, mais 10 types de tuyaux. N'est-ce pas ?

Ce n'est pas grand. Si tu as 10 tuyaux (cette fois-ci) enroulés, tu as 10^10 possibilités, soit 10 milliards de cas. Facile à traiter pour un ordinateur.
Quel est l'ordre de grandeur du nombre de tuyau par bobine ?

Au point où j'en suis, à part tester tous les remplissages possible un par un et de les comparer je ne vois pas.

Ce n'est pas forcément une mauvaise idée.
Tu peux considérer un arbre des possibilités et faire un parcours en largeur pour créer de nouvelles branches.
Tu as calculé la formule qui te donne le nouveau rayon extérieur quand tu as enroulé un tuyau donné ?

Les tuyaux ayants une masse linéique propre, il ne faut pas que le poids de la roue dépasse un poids Pmax.

Ça, c'est pratiquement le plus simple.
Un tuyau enroulé fait le même poids qu'un tuyau non-enroulé.
Donc les combinaisons trop lourdes sont détectables instantanément.

[Avatar36]

Tu n'as pas 10 tuyaux, mais 10 types de tuyaux. N'est-ce pas ?

Oui c'est ça. Ils peuvent être de diamètres différents, de longueur différentes,...

Si tu as 10 tuyaux (cette fois-ci) enroulés, tu as 10^10 possibilités, soit 10 milliards de cas. Facile à traiter pour un ordinateur.

Ce serait vrai si l'algorithme qui me permet de packer les tuyaux sur la roue était quasiment instantané. Ce n'est pas le cas. Pour 280 cas, il me faut environ 2 minutes. Alors pour plus d'1 milliard...
En effet, prenons une tranche de cette roue avec les tuyaux dessus. Il s'agit de placer des cercles dans une surface trapézoïdale. Donc on remplit la roue avec des couches en résolvant pour chaque tour une équation donnant la position du cercle. Il n'est pas rare que j'ai une centaine de tours pour chaque roue, donc 100 équations à résoudre, etc... D'où l'idée d'utiliser une approche plus intelligente que la force brute.

Ce n'est pas forcément une mauvaise idée.
Tu peux considérer un arbre des possibilités et faire un parcours en largeur pour créer de nouvelles branches.

D'après la réponse si-dessus, ce n'est pas applicable car c'est déjà ce que je voulais faire, sans que ça ne convienne.

Tu as calculé la formule qui te donne le nouveau rayon extérieur quand tu as enroulé un tuyau donné ?

Je ne pense pas qu'il soit possible de formuler ce rayon. En effet, il dépend entièrement de comment va se positionner le tuyau lors du dernier enroulement d'une ligne.
Je n'ai peut-être pas été assez clair dans mon énoncé. Je ne cherche pas à placer les différentes couches à un diamètre les unes des autres. Cette distance dépend entièrement d'où tombe le dernier tuyau d'une ligne.
Distance qui est de plus influencé par le potentiel changement de diamètre entre 2 tuyaux ainsi que par la forme trapézoïdale de la roue.

Ça, c'est pratiquement le plus simple.
Un tuyau enroulé fait le même poids qu'un tuyau non-enroulé.
Donc les combinaisons trop lourdes sont détectables instantanément.

Je suis d'accord, c'est une simple condition.

[Jipété]

Bonsoir,

ainsi que par la forme trapézoïdale de la roue.

Il m'arrive d'enrouler des tuyaux dans mon jardin dans la vraie vie.

Et je pense que quelle que soit la forme trapézoïdale plus ou moins biscornue de ta roue, ça va se terminer par à chaque tour une certaine longueur de tuyau enroulée dessus, longueur que tu pourrais ensuite ramener à la circonférence d'un cercle, ce qui te simplifierait grandement la vie.
Et les algorithmes,

[tbc92]

Il faut faire quelques impasses/approximations. Plutôt que cumuler le déroulement du tuyau sur une roue, tu peux plus simplement calculer une fois pour toutes le volume disponible sur une roue. ( en gros, surface du trapèze * périmètre de la roue... qu'il faut certainement affiner par un calcul d'intégrale si l'écart entre r et R est important).
A partir du volume, en question, tu peux estimer assez bien la quantité de tuyaux que tu peux enrouler. Volume de la roue >= somme des volumes des tuyaux.
En appliquant probablement un coefficient, car il y a du volume perdu : quand on dessine plusieurs cercles sur une feuille de papier, la surface remplie est égale à k * surface disponible, avec k = environ 0.9 (tiens ... question intéressante, combien vaut ce taux de remplissage).
Du coup, pour chaque roue, tu as :
- volume disponible
- poids maximum
Et pour chaque tuyau :
- volume nécessaire
- poids du tuyau.

C'est tout, le fait qu'on traite des tuyaux à enrouler sur des roues, ou des bonbons à mettre dans des boites... peu importe.

[Avatar36]

Et je pense que quelle que soit la forme trapézoïdale plus ou moins biscornue de ta roue, ça va se terminer par à chaque tour une certaine longueur de tuyau enroulée dessus, longueur que tu pourrais ensuite ramener à la circonférence d'un cercle, ce qui te simplifierait grandement la vie.
Et les algorithmes,

Oui c'est déjà l'approximation que je fais. Toute la difficulté réside dans la manière dont les tuyaux s'agencent sur une tranche de la roue.

Il faut faire quelques impasses/approximations.

C'est un peu ce que je cherche à éviter mais ça peut être une bonne approche pour faire une première estimation puis s'approcher de la solution idéale avec un minimum d'itérations par la suite.

En appliquant probablement un coefficient

C'est un peu ce que j'avais dans l'idée aussi mais j'ai peur que ce coefficient soit très variable car il dépend de pas mal de paramètres que je ne peux pas quantifier: position du dernier tuyau sur une ligne, changement de diamètre durant l'enroulement... Je pourrais surement lancer des tas de combinaisons différentes et quantifier ce k mais j'espérais que ce soit plus simple. Et le problème est le même. Avec ce k, j'aurais uniquement une estimation de la quantité de tuyau que je peux mettre sur une roue. Moi je ne recherche pas une estimation mais la quantité exacte.