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.

[tbc92]

Je pense que l'approximation est nécessaire. Si la largeur de ta roue est le 30cm, et que les tuyaux ont 4cm de diamètre, tu vas pouvoir disposer 7 passages côte à côte. Mais comment disposer nos 7 passages : tous serrés contre l'un des côtés, et ainsi , on libère un peu d'espace sur l'autre côté ? Ou bien, les 7 passages peuvent être répartis :
1er passage de tuyau : entre 0 et 4cm
2ème passage de tuyau : entre 4.3cm et 8.3cm
3ème pasage de tuyau : entre 8.6cm et 12.6cm ...
Ainsi, le tour suivant pourra mieux s'intercaler, et le rayon du tour suivant sera optimisé.

Si tu dois entrer à ce niveau de détail, je te souhaite bon courage, c'est très compliqué. Mais dans ce cas, il y a certainement un premier chantier à mener avant le chantier que tu as proposé : avec une roue, avec 2 ou 3 tuyaux de section X et de masse linéique Y, quelle est la longueur de tuyaux que l'on peut disposer. Faire cet exercice, et s'assurer que les résultats que l'on obtient par un calcul poussé sont meilleurs que ceux que l'on obtient par approximation. Ou en tout cas, il faut bâtir une fonction efficace qui dit si oui ou non, sur une roue, on peut mettre x mètres de tuyau a+y mètres de tuyau b.

[Avatar36]

tous serrés contre l'un des côtés, et ainsi , on libère un peu d'espace sur l'autre côté ? Ou bien, les 7 passages peuvent être répartis

Ils doivent être serrés. Donc on libère de l'espace d'un côté et le tuyau qui vient s'intercaler n'est ni vraiment sur la ligne d'en bas, ni vraiment sur la ligne du dessus. Ceci créant un décalage qui va conditionner la manière dont la suite des tuyaux vont s'enrouler.

Si la largeur de ta roue est le 30cm

Pour rappel, la section de la roue est trapézoïdale donc la largeur varie avec le rayon. Complexité supplémentaire j'en ai bien peur.

Si tu dois entrer à ce niveau de détail, je te souhaite bon courage, c'est très compliqué.

Je me doute, c'est pour ça que je viens ici. J'arriverai toujours à m'en sortir d'une manière ou d'une autre mais je vais faire un code qui va demander du temps à tourner.

Mais dans ce cas, il y a certainement un premier chantier à mener avant le chantier que tu as proposé : avec une roue, avec 2 ou 3 tuyaux de section X et de masse linéique Y, quelle est la longueur de tuyaux que l'on peut disposer. Faire cet exercice, et s'assurer que les résultats que l'on obtient par un calcul poussé sont meilleurs que ceux que l'on obtient par approximation. Ou en tout cas, il faut bâtir une fonction efficace qui dit si oui ou non, sur une roue, on peut mettre x mètres de tuyau a+y mètres de tuyau b.

Cela va même plus loin. En effet, j'ai le droit de couper le dernier tuyau pour le mettre sur la bobine suivante. C'est à dire que dans tous les cas l'enroulement proposé est possible. Pour le moment j'ai une fonction capable de me dire comment sont répartis les tuyaux sur les bobines (on coupe dès que la bobine est pleine, etc...). Cependant cette fonction ne remplit que depuis le bas de la bobine. Or dans mon cas il faudrait que je puisse la remplir d'abord en haut pour spécifier le premier tuyau déroulé.
La fonction que tu propose serait plutôt pour un ordre de tuyau donné: Combien de bobines est-ce que j'ai rempli? Est-ce qu'il n'y a pas un autre ordre qui serait mieux?
Le genre de fonction que tu propose est exactement le genre de chose que je cherche mais il faut en plus que je m'assure que le résultat est conservatif. En gros, il faut pas qu'elle m'écarte des solutions plus optimales, écartées à cause de l'approximation faite.

[tbc92]

Cela va même plus loin. En effet, j'ai le droit de couper le dernier tuyau pour le mettre sur la bobine suivante. C'est à dire que dans tous les cas l'enroulement proposé est possible. Pour le moment j'ai une fonction capable de me dire comment sont répartis les tuyaux sur les bobines (on coupe dès que la bobine est pleine, etc...). Cependant cette fonction ne remplit que depuis le bas de la bobine. Or dans mon cas il faudrait que je puisse la remplir d'abord en haut pour spécifier le premier tuyau déroulé.

Si tu as cette fonction, alors tu as déjà une élément essentiel !

Le fait que cette fonction remplisse à partir du centre n'est pas un problème. Aujourd'hui, tu formules ton besoin en disant : le premier tuyau déroulé est x, le 2ème est y etc etc. Tu peux tout simplement inverser cette liste, et du coup, tu as tes tuyaux dans l'ordre de remplissage, et non plus dans l'ordre de déroulage.

[Avatar36]

Oui c'est déjà ce que je fait. Maintenant mon problème c'est que la première bobine doit être pleine. Si j'inverse l'ordre et que je commence par le dernier tuyau, alors ma première bobine n'est pas pleine.

En réalité il y a 2 problèmes ici:
1/ Je ne peux pas remplir la première bobine à dérouler en premier, en tout cas pas avec mon code actuel
2/ Je n'ai pas de solution pour optimiser le déroulement sans calculer tous les cas avec ma fonction lourde