Thema: VBA Code zur Optimierung einer Zuordnung

Hallo Zusammen!
Ich versuche gerade die Verteilung von Gewichtseinheiten zu Optimieren und stecke fest.
Das Prinzip der Aufgabe ist recht simpel: Ein Kunde liefert Gewichtseinheiten an eine Spedition, wobei er nach Realgewicht bezahlt. Allerdings muss er für jede Einheit, welche unter dem Minimalgewicht bleibt, eine Strafe von 1,5 Euro/KG für das Untergewicht bezahlen. Um diese Strafe zu umgehen darf er Einheiten in Perioden zusammenfügen und kann so das Untergewicht einer Einheit mit dem Übergewicht einer anderen Einheit ausgleichen. Diese Perioden dürfen Einheiten von 5 oder weniger AUFEINANDER FOLGENDEN Tagen beinhalten, wobei sich die Perioden überlappen können. Sprich die verschiedenen Einheiten eines Tages können auf verschiedene Perioden verteilt werden, jedoch darf jede Einheit natürlich nur einer einzigen Periode angehören.
Ich habe das ganze in der angehängten Datei einmal dargestellt und Formeln eingesetzt, sodass man nur noch die Periodenzuordnung optimieren muss. Im linken Kasten sind die Daten der Einheiten zu finden, der rechte obere Kasten dient der Berechnung des Untergewichts und der rechte untere Kasten dient der Berechnung der Periodendauer.
Die gelben Felder sind also die änderbaren Variablenzellen, das grüne Feld zeigt das zu minimierende Untergewicht an und in rot sieht man die anfallende Strafzahlung.
Kann mir jemand einen VBA Code basteln, welcher die Optimierung der Einheitenzuordnung durchführt und dabei die Nebenbedingungen einhält? Mit dem Excel Solver habe ich es schon erfolglos versucht, diese Rechnung ist dafür zu komplex.
Vielen Dank schon mal und viele Grüße!
Matthias
https://www.herber.de/bbs/user/99025.xlsx

Hallo Matthias,
das ist vermutlich eine nur durch durch Kombinatorik berechenbare Kondition,
wäre es nicht praktischer, statt dessen jedes Übergewicht beliebig auf Untergewichte zu verteilen,
die bis zu 5 Tage vorher/nachher angefallen sind?
Gruß Coachyou

Hallo Coachyou,
die Perioden müssen nicht zwangsweise 5 Tage lang sein, sondern können im Extremfall sogar nur einen Tag beinhalten. Das schließt deine Lösung leider aus.
Hättest du denn eine Idee in Richtung Kombinatorik?
LG Matthias

Hallo Matthias,
ja, aber die ist wie gesagt nicht praktibel, weil es einfach zu viele Möglichkeiten gibt,
in Deinem Beispiel sind es, wenn man mal nur die jeweiligen Vorgänger der Einheiten betrachtet, 1*2*3*4*5*5*5*4*5*4*4*4*4*5*4*5*6*7*7*7*7*8*9*5*5*5*6*7*8*7 (ca 4,68E+20), weil es keine isolierten Gruppen gibt.
Wenn man mit Teiloptimierungen für die potentiell günstigsten Teilgruppen arbeitet und dabei deren Ränder "opfert", ist man deutlich schneller, siehe Screenshot
, die Lösung (Rest 2539) kommt bis auf 37 Stück an das Optimum (2502) heran, ist aber für einen Masseneinsatz immer noch zu langsam.
Wenn es an einem Tag mehr als eine Sendung gibt, funktioniert mein Lösungsansatz auch (der funktioniert sogar performant für beliebig lange Zeiten),
wenn es nur eine Sendung gibt, liefern bei dieser Bedingung beide Methoden keine Kompensation.
Gruß Coach

Hallo zusammen,
die Geschichte liegt mir irgendwie "quer im Hirn"; auf Anhieb kann ich Coachs Formeln nicht nachvollziehen. Könnten wir bitte die Datei samt Formeln haben?
Nur zur Illustration: es scheint sich hier um diese Problematik zu handeln:
https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
Exakte Lösungen sind quasi nicht berechenbar, und bei nicht exakten Lösungsverfahren weiß man nie, ob man das tatsächlich vorhandene Optimum errechnet hat: man kann sich nur entscheiden, ob man mit der Lösung zufrieden ist oder nicht.
Nur knapp 2% über dem Optimum ist auf alle Fälle klasse!
Schöne Grüße,
Michael

Hallo Coach, hallo Michael,
@Coach: Ich kann deine Berechnung leider auch nicht ganz nachvollziehen, was meinst du zB mit "Ränder opfern"? Vielleicht kannst du deinen Lösungsweg einfach kurz beschreiben und dein File hochladen.
Eins ist mir noch aufgefallen und zwar sind die Perioden bei dir zu lang(zB 5.-20.08). Das sind zwar 5 Tage Unterschied aber 6 Tage insgesamt ;)
@Michael: Guter Tipp mit dem Handlungsreisenden, ich werde mich mal schlau machen.
Viele Grüße
Matthias

Hallo Zusammen!
Ich versuche gerade die Verteilung von Gewichtseinheiten zu Optimieren und stecke fest.
Das Prinzip der Aufgabe ist recht simpel: Ein Kunde liefert Gewichtseinheiten an eine Spedition, wobei er nach Realgewicht bezahlt. Allerdings muss er für jede Einheit, welche unter dem Minimalgewicht bleibt, eine Strafe von 1,5 Euro/KG für das Untergewicht bezahlen. Um diese Strafe zu umgehen darf er Einheiten in Perioden zusammenfügen und kann so das Untergewicht einer Einheit mit dem Übergewicht einer anderen Einheit ausgleichen. Diese Perioden dürfen Einheiten von 5 oder weniger AUFEINANDER FOLGENDEN Tagen beinhalten, wobei sich die Perioden überlappen können. Sprich die verschiedenen Einheiten eines Tages können auf verschiedene Perioden verteilt werden, jedoch darf jede Einheit natürlich nur einer einzigen Periode angehören.
Ich habe das ganze in der angehängten Datei einmal dargestellt und Formeln eingesetzt, sodass man nur noch die Periodenzuordnung optimieren muss. Im linken Kasten sind die Daten der Einheiten zu finden, der rechte obere Kasten dient der Berechnung des Untergewichts und der rechte untere Kasten dient der Berechnung der Periodendauer.
Die gelben Felder sind also die änderbaren Variablenzellen, das grüne Feld zeigt das zu minimierende Untergewicht an und in rot sieht man die anfallende Strafzahlung.
Kann mir jemand einen VBA Code basteln, welcher die Optimierung der Einheitenzuordnung durchführt und dabei die Nebenbedingungen einhält? Mit dem Excel Solver habe ich es schon erfolglos versucht, diese Rechnung ist dafür zu komplex.
Vielen Dank schon mal und viele Grüße!
Matthias
https://www.herber.de/bbs/user/99025.xlsx

Hallo Matthias,
das ist vermutlich eine nur durch durch Kombinatorik berechenbare Kondition,
wäre es nicht praktischer, statt dessen jedes Übergewicht beliebig auf Untergewichte zu verteilen,
die bis zu 5 Tage vorher/nachher angefallen sind?
Gruß Coachyou

Hallo Coachyou,
die Perioden müssen nicht zwangsweise 5 Tage lang sein, sondern können im Extremfall sogar nur einen Tag beinhalten. Das schließt deine Lösung leider aus.
Hättest du denn eine Idee in Richtung Kombinatorik?
LG Matthias

Hallo Matthias,
ja, aber die ist wie gesagt nicht praktibel, weil es einfach zu viele Möglichkeiten gibt,
in Deinem Beispiel sind es, wenn man mal nur die jeweiligen Vorgänger der Einheiten betrachtet, 1*2*3*4*5*5*5*4*5*4*4*4*4*5*4*5*6*7*7*7*7*8*9*5*5*5*6*7*8*7 (ca 4,68E+20), weil es keine isolierten Gruppen gibt.
Wenn man mit Teiloptimierungen für die potentiell günstigsten Teilgruppen arbeitet und dabei deren Ränder "opfert", ist man deutlich schneller, siehe Screenshot
, die Lösung (Rest 2539) kommt bis auf 37 Stück an das Optimum (2502) heran, ist aber für einen Masseneinsatz immer noch zu langsam.
Wenn es an einem Tag mehr als eine Sendung gibt, funktioniert mein Lösungsansatz auch (der funktioniert sogar performant für beliebig lange Zeiten),
wenn es nur eine Sendung gibt, liefern bei dieser Bedingung beide Methoden keine Kompensation.
Gruß Coach

Hallo zusammen,
die Geschichte liegt mir irgendwie "quer im Hirn"; auf Anhieb kann ich Coachs Formeln nicht nachvollziehen. Könnten wir bitte die Datei samt Formeln haben?
Nur zur Illustration: es scheint sich hier um diese Problematik zu handeln:
https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden
Exakte Lösungen sind quasi nicht berechenbar, und bei nicht exakten Lösungsverfahren weiß man nie, ob man das tatsächlich vorhandene Optimum errechnet hat: man kann sich nur entscheiden, ob man mit der Lösung zufrieden ist oder nicht.
Nur knapp 2% über dem Optimum ist auf alle Fälle klasse!
Schöne Grüße,
Michael

Hallo Coach, hallo Michael,
@Coach: Ich kann deine Berechnung leider auch nicht ganz nachvollziehen, was meinst du zB mit "Ränder opfern"? Vielleicht kannst du deinen Lösungsweg einfach kurz beschreiben und dein File hochladen.
Eins ist mir noch aufgefallen und zwar sind die Perioden bei dir zu lang(zB 5.-20.08). Das sind zwar 5 Tage Unterschied aber 6 Tage insgesamt ;)
@Michael: Guter Tipp mit dem Handlungsreisenden, ich werde mich mal schlau machen.
Viele Grüße
Matthias