Algorithme de chargements camionsRésolu

Question

Bonjour 

Je cherche un algorithme pour chercher le plan chargement de camions.Voici mon problème:

J'ai un camion avec 6 cuves qui ont comme capacités :
   1ere cuve 2500 kg maxi
   2eme cuve 1500 kg maxi
   3eme cuve 1500 kg maxi
   4eme cuve 2500 kg maxi
   5eme cuve 2000 kg maxi
   6eme cuve 2000 kg maxi

J'ai une commande par exemple 
   1ere ligne  Client1 Produit 1 2200 Kg
   2eme ligne Client2 Produit 2 3000 Kg
   3eme ligne Client3 Produit 3 4500 Kg
   4eme ligne Client4 Produit 4 1000 Kg
Les bases de ce problèmes sont les suivantes on ne peut pas mélanger les produits et on ne peut pas mélanger les commandes.

L'algorithme devra me trouver la solution suivante:
      le Produit 1 ira dans la cuve 1
      le Produit 2 ira dans les cuves 2 et 3
      le Produit 3 ira dans les cuves 4 et 5
      le Produit 4 ira  dans la cuve 6 

Merci à celui ou celle qui poura me répondre
Eric H

poy20 · Accepted Answer

Salut,
Je suppose que le but est d'utiliser la plus petite cuve possible à chaque ligne de commande ...?
Par contre y-a-t-il un paramètre "date" ? Histoire de savoir si une cuve est déjà prise par une autre commande le même jour, et qui serait donc indisponible.

Sinon voici une première idée qui permettra d'ouvrir le débat :

Dim Cuve1 as integer =2500
Dim Cuve2 as integer = 1500
Dim Cuve3 as integer = 1500
Dim Cuve4 as integer = 2500
Dim Cuve5 as integer = 2000
Dim Cuve6 as integer = 2000
Dim CuveUtilise as String = ""

'KilosProduit correspond à la charge de la première commande

Private Function RechercheCuve (KilosProduit as integer) as String
   If KilosProduit <= 1500 then
      CuveUtilise &= "Cuve 2 "
   ElseIf KilosProduit <= 2000 then
      CuveUtilise &= "Cuve 5 "
   Elseif KilosProduit <= 2500 then
      CuveUtilise &= "Cuve 4 "
   ElseIf  KilosProduit > 2500 then 'compare à la plus grande cuve
      CuveUtilise &= "Cuve 4 "
      RechercheCuve(kilosProduit - 2500)
   End If

   Return(CuveUtilse)
End Function

Bon je sais bien, s'il boucle 2 fois il peut utiliser plusieurs fois la même cuve, mais avant d'approfondir la chose avec des booléens pour vérifier la dispo des cuves, je laisse Eric répondre pour savoir si c'est bien ce qu'il cherche....

Espérant avoir compris le problème ...

cs_eric89 · Answer

Cela ressemble à ce que je veux mais effectivement on peut utiliser une cuve plusieurs fois.Il faudra aussi pouvoir retrouver où auront été mises les commandes.

Eric H

poy20 · Answer

Je pense que le mieux est de passer par des class :

Class Cuve :

Public

ClassCuve

PublicNomCuveAsString

PublicCapaciteCuveAsInteger

PublicDispoCuveAsBoolean

   PublicSubNew(ByValNomAsString, ByValCapaciteAsInteger)      NomCuve = Nom

      CapaciteCuve = Capacite

      DispoCuve =

True

      DimtailleAsInteger'ajout de la cuve au tableau

      IfIsNothing(Form1.TabloCuve)Then         taille = 0

      Else         taille = UBound(Form1.TabloCuve) + 1

      EndIf

      ReDimPreserveForm1.TabloCuve(taille)
      Form1.TabloCuve(taille) =

Me

   EndSubEnd

Class

poy20 · Answer

Class Commande :
Public

Class
 Commande

   Public NomCommande 
As

String

   Public Produits()() 
As

String

   Public CuveUtilise() 
As
 Cuve

   
   Public
Sub

New
(
ByVal
 NomCommande 
As

String
)

      Me.NomCommande = NomCommande

   End
Sub

   Public
Sub
 AddProduit(
ByVal
 NomProduit 
As

String
, 
ByVal
 ChargeProduit 
As

Integer
)

      Dim taille 
As

Integer

      If IsNothing(Produits) 
Then
         taille = 0

      Else         taille = UBound(Produits) + 1

      EndIf

      ReDimPreserveProduits(taille)

      ReDimPreserveProduits(taille)(1)      Produits(taille)(0) = NomProduit

      Produits(taille)(1) = ChargeProduit

      RechercheCuve(ChargeProduit)

   EndSub

   PrivateSubRechercheCuve(ByVal ChargeProduit 
As

Integer
)

   DimiAsInteger= 0

   DimCuveTrouveAsBoolean = False

   IfIsNothing(CuveUtilise)Then

      ReDimPreserveCuveUtilise(0)

   Else

      ReDimPreserveCuveUtilise(UBound(CuveUtilise) + 1)

   EndIf
   While(i <UBound(Form1.TabloCuve) And CuveTrouve 
False
)

      If ChargeProduit < Form1.TabloCuve(i).CapaciteCuve 
Then
      CuveUtilise(UBound(CuveUtilise)) = Form1.TabloCuve(i) 

'attribution de la cuve
      Form1.TabloCuve(i).DispoCuve = 

False
      CuveTrouve =

True

      EndIf   i += 1

   EndWhile

   IfCuveTrouve =FalseThen      i = 0

      WhileForm1.TabloCuve(i).DispoCuve =False         i += 1

      EndWhile      CuveUtilise(UBound(CuveUtilise)) = Form1.TabloCuve(i) 

'attribution de la 1ere cuve dispo
      Form1.TabloCuve(i).DispoCuve =

False      RechercheCuve(ChargeProduit - Form1.TabloCuve(i).CapaciteCuve)

   EndIf

EndSub

End

Class

poy20 · Answer

Et enfin le form1 :
Public

Class
 Form1

Public TabloCuve() 
As
 Cuve

Private
Sub
 Form1_Load(
ByVal
 sender 
As
 System.Object, 
ByVal
 e 
As
 System.EventArgs) 
Handles

MyBase
.Load

Dim cuve1 
As

New
 Cuve(
"Cuve 1"
, 2500) 'Veillez a insérer les cuves en ordre décroissant de capacité

Dim cuve2 
As

New
 Cuve(
"Cuve 4"
, 2500)

Dim cuve3 
As

New
 Cuve(
"Cuve 5"
, 2000)

Dim cuve4 
As

New
 Cuve(
"Cuve 6"
, 2000)

Dim cuve5 
As

New
 Cuve(
"Cuve 2"
, 1500)

Dim cuve6 
As

New
 Cuve(
"Cuve 3"
, 1500)

EndSub

Private
Sub
 ClickButtonChargement()

Dim Client1 
As

New
 Commande(
"Client1"
)Client1.AddProduit(

"Produit 1", 2200)

Dim Client2 
As

New
 Commande(
"Client2"
)Client1.AddProduit(

"Produit 2", 3000)

Dim Client3 
As

New
 Commande(
"Client3"
)Client1.AddProduit(

"Produit 3", 4500)

Dim Client4 
As

New
 Commande(
"Client4"
)Client1.AddProduit(

"Produit 4", 1000)

EndSubEnd

Class

cs_eric89 · Answer

Je vais essayer 

Merci de ton aide 

Eric H

poy20 · Answer

Private





Sub
 RechercheCuve(
ByVal
 ChargeProduit 
As


Integer
)


Dim
 i 
As


Integer
 = 0


Dim
 CuveTrouve 
As


Boolean
 = 
False





If
 IsNothing(CuveUtilise) 
Then





ReDim


Preserve
 CuveUtilise(0)


Else





ReDim


Preserve
 CuveUtilise(UBound(CuveUtilise) + 1)


End


If





While
 (i <= UBound(Form1.TabloCuve) 
And
 CuveTrouve = 
False
)


If
 Form1.TabloCuve(i).CapaciteCuve > ChargeProduit 
Then

CuveUtilise(UBound(CuveUtilise)) = Form1.TabloCuve(i) 



'attribution de la cuve

Form1.TabloCuve(i).DispoCuve = 



False

CuveTrouve = 



True





End


If

i += 1






End


While





If
 CuveTrouve = 
False


Then

i = UBound(Form1.TabloCuve)






While
 Form1.TabloCuve(i).DispoCuve = 
False

i -= 1






End


While

CuveUtilise(UBound(CuveUtilise)) = Form1.TabloCuve(i) 



'attribution de la 1ere cuve dispo

Form1.TabloCuve(i).DispoCuve = 



False

RechercheCuve(ChargeProduit - 



CType
(Form1.TabloCuve(i).CapaciteCuve, 
Integer
))


End


If





End


Sub

J'ai fait une petite erreur dans l'algo de recherche des cuves dispo, en voici la correction.
Par contre il faut désormais classer les cuve dans ton form1 dans l'oredre inverse ...

Dim cuve6 AsNew Cuve("Cuve 3", 1500)

Dim cuve5 AsNew Cuve("Cuve 2", 1500)

Dim cuve4 AsNew Cuve("Cuve 6", 2000)

Dim cuve3 AsNew Cuve("Cuve 5", 2000)

Dim cuve2 AsNew Cuve("Cuve 4", 2500)

Dim cuve1 AsNew Cuve("Cuve 1", 2500)

J'ai un petit test, ça à l'air de fonctionner correctement, ar contre ça ne gère pas la possibilité qu'il n'y ait 
plus de cuve dispo... Mais ça doit pas être sorcier.
N'hésite pas !

poy20 · Answer

Wahou, c'est quoi ce formatage !!!

j'arrive pas à éditer ma réponse pour corriger

cs_eric89 · Answer

Le seul problème est que tu m'as donné la réponse en VB.net alors que moi je suis en VB6

Eric H

poy20 · Answer

Aïe ! 
Je connais pas assez vb6 pour traduire ...

Désolé

jmfmarques · Answer

Euh...
Toujours de passage... et de bien loin...

Voyons donc : ton problème de cuves ressemble tout simplement à celui d'un monnayeur (une caisse, des billets et pièces.
... une somme à faire verser par la caisse le plus "adroitement" possible... je ne vois aucune différence de raisonnement....)!
Remplace donc tes cuves par des valeurs faciales...
un véritable jeu d'enfant, ma foi ... (juste un peu de réflexion et l'utilisation astucieuse de l'opérateur Mod (aide en ligne)...


Tu veux bien t'y mettre, s'il te plait ?


On verra après (si tu as bien voulu d'abord y mettre un peu du tien  ...)

cs_eric89 · Answer

Je ne vois pas trop comment faire !

Eric H

jmfmarques · Answer

Tu me fais travailler de bon matin (et avant ce soir !) sans VB sous la main....

Voilà un monnayeur (gaffe : je n'ai pas VB sous la main et je peux avoir fait une erreur en codant à "main levée")

une Form avec un bouton de commande command1 et une listbox List1

Regarde bien (surtout les arrays notes et dispo (ce sont tes citernes)... et le montant  (c'est ce que tu as à mettre dans tes citernes...)

Tu as là le principe d'une répartition la mieux organisée pour utiliser au mieux tes billets/pièces (tes citernes, donc)...
Il te suffit de comprendre ce mécanisme et d'adapter à ton cas...

Private notes, dispo, dispo1


Private Sub Command1_Click()
  Dim rep As Double, arep As Double, montant As Double, i As Integer, combien As Double
  arep = 3127.98
  montant = CDbl(arep) 'ici le montant à sortir (analogie : la commande d'u client)
  List1.Clear
  For i = 0 To UBound(notes)
    combien = Int(CDbl(montant) / CDbl(notes(i)))
    If combien > dispo(i) Then combien = dispo(i)
    dispo(i) = dispo(i) - combien
    montant = montant - (combien * CDbl(notes(i)))
    rep = rep + (combien * CDbl(notes(i)))
    If combien > 0 Then List1.AddItem combien & " * " & notes(i)
  Next
  If arep > rep Then
    Dim avoir As Double
    For i = 0 To UBound(notes)
      avoir = avoir + (dispo(i) * notes(i))
    Next
    If avoir > (arep - rep) Then
       MsgBox " pas de quoi faire appoint "
    Else
      MsgBox " pas assez et bous devez encore " & arep - rep
    End If
    List1.Clear
    Let dispo = dispo1
  Else
    Let dispo1 = dispo
  End If
End Sub




Private Sub Form_Activate()
  'ici les valeurs faciales de tes billets et pièces (analogie : la contenance de tes citernes)
  notes = Array(500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01)
'ici ce qu'il te reste à chaque sortie comme billets et pièces (analogie : ce qu'il te reste dans chaque citerne)
' au départ (stock encore non entamé) on dit ce dont on dispose (la capacité de tes citernes vides, donc)
  dispo = Array(3, 50, 20, 30, 100, 150, 300, 280, 100, 200, 190, 160, 200, 110, 10)
End Sub

Attention : comme je ne peux vérifier ma syntaxe (sans VB sous la main), elle comportre peut-être une erreur ou deux à corriger ici ou là ... mais ce doit alors être insignifiant et facile à corriger...

cs_eric89 · Answer

Cela ne va pas marcher car on ne peut pas mélanger les commandes ni les produits 

Eric H

jmfmarques · Answer

Oui ?

Et quelle est donc la petite modif à apporter ? (tu ne la vois pas ?)
Il te suffit de dire que ta cuve est indisponible dès que tu l'as utilisée, même en partie...
Tu as pour cela la Array dispo, non ? (si cuve utilisée, même en partie,  le dispo correspondant estr mis à zéro ...)
Ton problème est autre, en réalité : contrairement au monnayeur pur (qui ne distribue un billet que si la valeur restant à distribuer est supérieure ou égale à la valeur faciale de ce billet), il te faut faire un peu le contraire (rechercher la cuve de capacité égale ou, à défaut,  immédiatement supérieure... c'est tout !!).
Tu as donc un exemple de répartition (monnayeur) et il te convient de l'adapter un tout petit peu...et cette adaptation réclamera moins de code (que tu as déjà) que de l'utilisation de ton intelligence ! Fais donc un petit algorithme d'abord (tu me parais avoir surtout besoin de réfléchir et d'organiser ta p)ensée...) Une autre fois : en ce qui concerne le code de répart(ition... tu l'as déjà !!!
En d'autres termes : ne pas confondre le raisonnement avant de coder et le code à proprement parler .. Tu me parais ne pas avoir encore terminé ton étape de raisonnement avant même de coder.

jmfmarques · Answer

Bon...
Me voilà enfin devant une machine "équipée" comme il le faut...
Et d'excellente humeur, je dois dire...

Je vais donc m'occuper de toi et on va faire autrement...

Tu vas commencer par ceci :

un petit projet et sur ta Form :

1) à gauche, un au dessous de l'autre et dans cet ordre là :
- une textbox nommée matiere
- une textbox nommée quantité
-un bouton de commande nommé Command1
- une listbox nommée listcommande et avec sa propriété Sorted à True

2) à la droite de cette "colonne" et toujours de haut en bas:

- une textbox nommée citerne
- un bouton de commande nommé Compmand2
- une listbox nommée listeciternes, avec sa propriété Sorted = True

3) à la droite de ces deux colonnes :
 une textbox nommée Resultat et avec sa propriété Multiline = True

4) quelque part en dessous de ces trois colonnes : un bouton de commande nommé Command3

Tu as tout deviné, nous sommes partis pour faire un petit truc polyvalent, qui te permettra de défrinir tes commandes et tes citernes....

Quand tu seras prêt, fais-le moi savoir... le reste sera un jeu d'enfant et nous nous amuserons ensemble, si tu le souhaites....
(tu as de la chance : je suis vraiment de bonne humeur  )

Tu dis...

cs_eric89 · Answer

Ok tout est prêt .

Eric H

jmfmarques · Answer

Bon.
... (je ne t'attendais plus)

Voilà donc ce que je viens de faire rapidement

Tu dois :
- d'abord enregistrer toutes tes commandes (matiere et quantité puis click sur command1 pour chaque commande)
- enregistrer toutes tes citernes (contenance puis click sur command2 pour chaque citerne)

puis : clique sur command3 pour obtenir la répartition de tes commandes

Essaye déjà celà, que je perfectionnerai ensuite (j'ai fait à toute allure et n'ai que peu testé jusqu'à présent)
Dis-moi si ce chemin te parait bon, dékà...
Je continuerai cet après-midi en fonction de ta réponse

Private Sub Command1_Click()
  If quantite.Text = "" Then quantite.SetFocus: Exit Sub
  If matiere.Text = "" Then matiere.SetFocus: Exit Sub
  listcommande.AddItem quantite.Text & " litres de  " & matiere.Text
  quantite.Text = ""
  matiere.Text = ""
End Sub


Private Sub Command2_Click()
  If citerne.Text = "" Then Exit Sub
  listeciternes.AddItem citerne.Text
  citerne.Text = ""
End Sub


Private Sub Command3_Click()
  resultat.Text = ""
  total_commandes = faire_total(listcommande)
  total_citernes = faire_total(listeciternes)
  If total_commandes > total_citernes Then
    MsgBox "pas bon ( " & total_commandes & " > " & total_citernes & ")": Exit Sub
  End If
  While listcommande.ListCount > 0
    traitercommande listcommande.ListCount - 1
    
    'MsgBox listcommande.ListCount - 1
  Wend
End Sub


Private Sub Form_Activate()
  listcommande.Clear
  listeciternes.Clear
  quantite.Text = ""
  matiere.Text = ""
  citerne.Text = ""
End Sub


Private Function faire_total(ctrl As ListBox)
  For i = 0 To ctrl.ListCount - 1
    faire_total = faire_total + Val(ctrl.List(i))
  Next
End Function


Private Sub traitercommande(j)
  resultat.Text = resultat.Text & "traitement de la commande de " & listcommande.List(j)
  acaser = Val(listcommande.List(j))
  While acaser > 0
    For i = listeciternes.ListCount - 1 To 0 Step -1
      If acaser <= Val(listeciternes.List(i)) Then
        quelle_citerne = i
        resultat.Text = resultat.Text & vbCrLf & acaser & " litres dans citerne de " & listeciternes.List(i) & " litres"
        listeciternes.RemoveItem (i)
        acaser = 0
        Exit For
      End If
    Next
    If acaser > 0 Then resultat.Text = resultat.Text & vbCrLf & Val(listeciternes.List(quelle_citerne)) & " litres dans citerne de " & listeciternes.List(quelle_citerne) & " litres"
    acaser = acaser - Val(listeciternes.List(quelle_citerne))
    If acaser > 0 Then listeciternes.RemoveItem (quelle_citerne)
    DoEvents
  Wend
  listcommande.RemoveItem (j)
End Sub

cs_eric89 · Answer

Cela me semble pas mal .Par contre si pour une raison la commande quelconque la commande n'est pas casable on va boucler sans arrêt.Exemple


3 produits 


produit 1 30


produit 2 25


produit 3 10

quatre citernes 
   15
   10
   20
   20

Eric H

jmfmarques · Answer

On va régler celà cet après midi (ce sera assez facile, ne t'inquiète pas)...
Mais déjà, je viens de voir un petit truc qui m'embête :

Modifie ceci (remplace l'ancienne ligne par celle en rouge ici) :

Private Sub Command1_Click()
  If quantite.Text = "" Then quantite.SetFocus: Exit Sub
  If matiere.Text = "" Then matiere.SetFocus: Exit Sub
  listcommande.AddItem Format(quantite.Text, "000000") & " litres de  " & matiere.Text
  quantite.Text = ""
  matiere.Text = ""
End Sub

Voilà pour l'instant .
Le reste cet après-midi car je dois m'absenter.
tu verras...

jmfmarques · Answer

Bon...
Jer me suis finalement débarraser d'une tâche qui m'appelait à l'extérieur et me revoilà donc.

J'ai apporté les modifications nécessaires (traitement des incasables) et suis même allé un peu plus loin ...
Amélioration : je traite en priorité les grosses commandes. Si une commande importante n'est pas casable, je cherche quand même à placer une autre commande (immédiatement inférieure en importance, etc...) ce qui fait que j'optimise l'utilisation de mes citernes.
Dans le rapport (textbox resultat), je signale bien évidemment les commandes qui n'ont pu être casées..

Il t'appartient maintenant d'arranger au mieux ton interface, notamment en donnant la meilleure largeur possible à la textbox resultat, c'est tout 
Tu devrais en profiter, dans la foulée, pour contrôler la cohérence de saisie des numériques (les exemples ne manques pas sur ce forum...)

Option Explicit
Private dispo As Long, toto As String
Private Sub Command1_Click()
  If quantite.Text = "" Then quantite.SetFocus: Exit Sub
  If matiere.Text = "" Then matiere.SetFocus: Exit Sub
  listcommande.AddItem Format(quantite.Text, "000000") & " litres de  " & matiere.Text  quantite.Text "": matiere.Text ""
End Sub


Private Sub Command2_Click()
  If citerne.Text = "" Then Exit Sub
  listeciternes.AddItem citerne.Text
  citerne.Text = ""
End Sub


Private Sub Command3_Click()
  Dim total_commandes As Long, total_citernes As Long
  resultat.Text = ""
  total_commandes = faire_total(listcommande)
  total_citernes = faire_total(listeciternes)
  dispo = total_citernes
  If total_commandes > total_citernes Then
    MsgBox "pas bon ( " & total_commandes & " > " & total_citernes & ")": Exit Sub
  End If
  While listcommande.ListCount > 0
    traitercommande listcommande.ListCount - 1
  Wend
End Sub


Private Sub Form_Activate()
  listcommande.Clear
  listeciternes.Clear  quantite.Text "":   matiere.Text "": citerne.Text = ""
End Sub


Private Function faire_total(ctrl As ListBox) As Long
  Dim i As Integer
  For i = 0 To ctrl.ListCount - 1
    faire_total = faire_total + Val(ctrl.List(i))
  Next
End Function


Private Sub traitercommande(j)
  Dim acaser As Long, i As Integer, quelle_citerne As Integer
  resultat.Text = resultat.Text & vbCrLf & "traitement de la commande de " & listcommande.List(j)
  acaser = Val(listcommande.List(j))
  If acaser > dispo Then
    resultat.Text = resultat.Text & vbCrLf & "non staisfaisable"
    DoEvents
    listcommande.RemoveItem (j)
    Exit Sub
  End If
  While acaser > 0
    For i = listeciternes.ListCount - 1 To 0 Step -1
      If acaser <= Val(listeciternes.List(i)) Then
        quelle_citerne = i
        resultat.Text = resultat.Text & vbCrLf & acaser & " litres dans citerne de " & listeciternes.List(i) & " litres"
        dispo = dispo - Val(listeciternes.List(quelle_citerne))
        listeciternes.RemoveItem (i)
        acaser = 0
        Exit For
      End If
    Next
    If acaser > 0 Then resultat.Text = resultat.Text & vbCrLf & Val(listeciternes.List(quelle_citerne)) & " litres dans citerne de " & listeciternes.List(quelle_citerne) & " litres"
    acaser = acaser - Val(listeciternes.List(quelle_citerne))
    If acaser > 0 Then
      dispo = dispo - Val(listeciternes.List(quelle_citerne))
      listeciternes.RemoveItem (quelle_citerne)
    End If
    DoEvents
  Wend
  listcommande.RemoveItem (j)
End Sub


Voilà...
Si satisfait, tu dis...
J'ai fait pour toi une exception (j'évite en général de développer un ensemble de choses... préférant laisser travailler...).
Tu me ferais plaisir si, t'inspirant dse ce que j'ai écrit ici à "la va vite", tu y ajoutais un travail personnel de perfectionnement et d'optimisation.

A +

cs_eric89 · Answer

Merci de ton aide !
Je ne voyais vraiment pas comment j'allais m'en sortir.

Eric H

cs_eric89 · Answer

Bonjour

Je me suis remis à mon problème de chargement.Je ne comprend pas pourquoi cela ne marche pas :
Exemple Camion 
   Cuve1 capacite :15
   Cuve2 capacite :15
   Cuve3 capacite:20
   Cuve4 capacite:20
   Cuve5 capacite:25
   Cuve6 capacite:25

Commande :
   Produit1:10
   Produit2:22
   Produit3:30
   Produit4:45

Voila le résultat:
   
   produit 4 dans CUVE1,CUVE2,CUV5
   produit 3 dans CUVE4,CUVE6
   produit 2:non satisfait
   produit1 dans CUVE3

Il y avait une solution:
   produit 4 dans CUVE3 et CUVE5
   produit 3 dans CUVE1 et CUVE4
   produit 2 dans CUVE6
   produit 1 dans CUVE2
Eric H

Algorithme de chargements camions

23 réponses

Votre réponse

Discussions similaires