Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Ladungsverteilung auf Fahrzeuge
Druckversion
Druckversion
Antworten
Antworten
Autor
Beruf Ladungsverteilung auf Fahrzeuge
argonis
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.03.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-03-05


Hallo,

folgende Aufgabe stellt sich mir:

Ich habe unterschiedliche schwere Paletten, welche ich auf mehrere Fahrzeuge verteilen muss, die alle unterschiedliche Nutzlasten zuladen können.

Beispiel:

Paletten und deren Gewichte
Palette 1                350
Palette 2                426
Palette 3                352
Palette 4                281
Palette 5                220
Palette 6                226
Palette 7                378
Palette 8                465
Palette 9                382
Palette 10        198
Palette 11        212
Palette 12        184
Palette 13        181

Fahrzeuge und deren Nutzlast
Fahrzeug 1         1165 kg
Fahrzeug 2        1165 kg
Fahrzeug 3        1085 kg
Fahrzeug 4        1242 kg

Nun muss ich diese Lasten entsprechend auf die Fahrzeuge verteilen, sodass möglichst alle Paletten verteilt sind und kein Fahrzeug überladen, aber bestmöglich ausgelastet ist.

Das ganze ist teil einer Software die ich entwickeln soll. Ich finde dazu aber irgendwie keinen Ansatz, wie ich da ran gehen könnte.

Vielen Dank



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MontyPythagoras
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.05.2014
Mitteilungen: 2270
Aus: Hattingen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-03-05


Hallo argonis,
herzlich willkommen auf dem Matheplaneten.
Ich weiß nicht, ob es für so etwas fertige Algorithmen gibt. Ich vermute zwar, dass es kommerzielle Software für Speditionen gibt, aber das nützt hier ja nichts.
Wie würdest Du es denn machen, wenn Du es als Mensch, nicht als Computer lösen müsstest? Ich würde mir erst einmal eine menschliche Arbeitsweise überlegen, und die umsetzen. Vielleicht zeigen sich dann automatisch Optimierungsmöglichkeiten.
Als Mensch, der genau diese Paletten auf genau diese Fahrzeuge verteilen soll, würde ich wie folgt vorgehen:
1. Überprüfe, ob die Summe der Lasten die Summe der Nutzlasten übersteigt. Dann wäre es unlösbar.
2. Wenn 1. nicht der Fall ist, berechne die durchschnittliche Restnutzlast pro Fahrzeug. Warum, dazu kommen wir später.
3. Sortiere nach Größe. (Ein Computer bräuchte das nicht, aber ich als Mensch schon).
4. Belade nun ein Fahrzeug. Füge Palatten sinnvoll hinzu, z.B. von groß nach klein. Wenn der Wagen voll ist (die Einzelgewichte aller übrigen Paletten übersteigen die Restnutzlast des Fahrzeugs), dann prüfe, ob die aktuelle Restnutzlast des Fahrzeugs die durchschnittlich zulässige Restnutzlast übersteigt. Wenn ja, versuche eine andere Palettenzuordnung, denn wenn Dir das dreimal passiert, passen die restlichen Paletten möglicherweise nicht ins letzte Fahrzeug. Man sollte daher anstreben, die Nutzlast maximal auszunutzen und sich bei der Restnutzlast anfangs immer unter dem Durchschnitt zu bewegen. Aber das ist eine menschliche Strategie.

Man kann sich nun noch Gedanken darüber machen, wie man das Beladen sinnvoll durchprobiert. Du kannst allen Paletten den binären Zustand "Verladen in aktuelles Fahrzeug: ja/nein" zuordnen. Willst Du also alle möglichen Beladungszustände eines Fahrzeugs systematisch durchprobieren, gibt es in diesem Fall 2^13=8192 Möglichkeiten, denn eine Palette ist entweder im Fahrzeug, oder eben nicht. 8192 Möglichkeiten klingt für einen modernen PC sehr überschaubar. Probiere alle 8192 Zustände durch und suche den Beladungszustand, dessen Summe am knappsten unter der Nutzlast des betrachteten Fahrzeugs liegt. Im Idealfall hast Du eine Punktlandung. Dann hast Du dieses Fahrzeug schon einmal optimal bepackt.
Für das nächste Fahrzeug musst Du die verbliebenen Paletten neu sortieren, und der Algorithmus beginnt von vorn, allerdings sind es diesmal schon wesentlich weniger Möglichkeiten, weil es ja nicht mehr 13, sondern nur noch 8 oder 9 Paletten sind.

Das wären schon einmal ein paar Ansätze.

Ciao,

Thomas



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-03-05


Hallo,

2020-03-05 17:11 - MontyPythagoras in Beitrag No. 1 schreibt:
Man kann sich nun noch Gedanken darüber machen, wie man das Beladen sinnvoll durchprobiert. Du kannst allen Paletten den binären Zustand "Verladen in aktuelles Fahrzeug: ja/nein" zuordnen. Willst Du also alle möglichen Beladungszustände eines Fahrzeugs systematisch durchprobieren, gibt es in diesem Fall 2^13=8192 Möglichkeiten, denn eine Palette ist entweder im Fahrzeug, oder eben nicht. 8192 Möglichkeiten klingt für einen modernen PC sehr überschaubar.

Ich würde ja sogar jede Palette einem der vier Fahrzeuge zuordnen und für jede Zuordnung überprüfen, ob kein Fahrzeug überladen ist. Das ergibt 4^13 = 67 Mio Möglichkeiten. Auch das schafft ein Computer in einem Wimpernschlag.

Was sind denn die Obergrenzen der Anzahl der Fahrzeuge und der Anzahl der Paletten?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
MontyPythagoras
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 13.05.2014
Mitteilungen: 2270
Aus: Hattingen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-03-05


Hallo StrgAltEntf,
das wäre die Optimalvariante, die, wenn es eine Lösung gibt, diese auch garantiert findet. Das Problem dürfte sein, wenn es n Paletten und m Fahrzeuge gibt, das m^n Möglichkeiten ergibt, und das könnten sehr leicht deutlich zu viele sein. Bei 6 Fahrzeugen und 20 Paletten wäre größenordnungsmäßig schon Schicht im Schacht, wenn man den Rechner nicht jedesmal tagelang rechnen lassen will. Da bin ich als Mensch intuitiv schneller, wenn auch suboptimal... 🙂
Wenn die Palettengewichte sich immer in einem relativ engen Rahmen bewegen, und ebenso die Nutzlasten der Fahrzeuge, dann ist es in der Praxis vermutlich ausreichend, sobald man ein Fahrzeug "gut genug" beladen hat, zum nächsten Fahrzeug überzugehen. Denn selbst bei der binären Vorgehensweise (diese Palette in dieses Fahrzeug ja oder nein) könnte man schon bei einer überschaubaren Anzahl an Paletten an die Grenzen auch eines modernen Rechners kommen.
Der Algorithmus müsste somit sicher an die maximal möglichen Anzahlen an Paletten und Fahrzeugen angepasst werden. Ideen gibt es ja nun...

Ciao,

Thomas



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
argonis
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.03.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-03-05


Hallo,

erstmal vielen Dank für die tollen Antworten. Das hilft mir schon sehr weiter. Und in der Tat, führe ich diesen Prozess täglich "von Hand" durch. Da kann man aber auch schnell den Überblick verlieren.

Also eine feste Obergrenze an Paletten gibt es im Grunde nicht. Es können 8 Paletten sein (dementsprechend muss ich weniger Fahrzeuge einsetzten). Dann, können es aber auch 25 Paletten sein. Wobei ich dann eben zusätzliche Fahrzeuge einsetzen muss. Hier beschränkt es sich eben auf die Anzahl der Fahrzeuge, die wir insgesamt im Betrieb haben. Mehr können wir logischerweise nicht einsetzten. Die liegt bei 10 Fahrzeugen aktuell, die wir zu diesem Zweck nutzen können. 4 Fahrzeuge sind allerdings die Untergrenze. Die sind immer im Einsatz.

Ich hatte auch etwas über binary sort trees gelesen, was mir plausibel erschien in dem Zusammenhang. Allerdings sortieren diese einfach nur die Gewichte. Aber ich denke so etwas in der Art wird es wohl werden. Denn Diese sind recht effektiv und schnell.

Ich hatte gehofft, dass es eine Möglihckeit gäbe, ohne diese Vergleichsmethoden. Aber ich denke, das wird die beste Lösung sein.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-03-05


Hallo Monty,

2020-03-05 21:29 - MontyPythagoras in Beitrag No. 3 schreibt:
Bei 6 Fahrzeugen und 20 Paletten wäre größenordnungsmäßig schon Schicht im Schacht, wenn man den Rechner nicht jedesmal tagelang rechnen lassen will.

Deshalb meine Frage nach den Obergrenzen.

Ich fürchte ja, dass das allgemeine Problem in die Kategorie "Rucksackproblem" fällt, ohne das jetzt zu Ende gedacht zu haben, und damit NP-vollständig ist.

Grüße
StrgAltEntf

[Die Antwort wurde nach Beitrag No.3 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 5873
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-03-05


2020-03-05 21:47 - argonis in Beitrag No. 4 schreibt:
Und in der Tat, führe ich diesen Prozess täglich "von Hand" durch. Da kann man aber auch schnell den Überblick verlieren.

Du möchtest ein Programm dafür entwickeln? Welche Programmiersprache steht dir denn zur Verfügung?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
argonis
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.03.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2020-03-05



Du möchtest ein Programm dafür entwickeln? Welche Programmiersprache steht dir denn zur Verfügung?

Die ersten Versuche würde ich der Einfachheit halber, erstmal mit Python machen und dann sehen ob sich das auch effizient auf VBScript übertragen lässt ohne zu lange Rechenzeiten zu generieren (unsere Rechner sind im Schnitt 7 Jahre alt). Alternativ könnte ich noch auf Websprachen wie PHP oder JS zurückgreifen.

Letztlich wäre es aber optimal, ließe sich das in Excel implementieren. Dann würde ich mir das ganze Drumherum sparen. Python kann ich leider nur zu Versuchszwecken einsetzen, da auf den Firmenrechnern/-servern kein Python installiert ist und auch nicht installiert werden kann. sonst hätte ich das gerne mittels Python uns Panda gelöst.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
argonis
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.03.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-03-05


Das sieht doch für mich ganz sinnvoll aus, um mein Problem zu lösen.

pseudo-polynomialer Algorithmus:


Nun ich bin kein Mathematiker. Also muss ich mir dies Video sicher noch ein-zweimal ansehen. Aber das scheint die Lösung zu sein. die Logik dahinter kann ich verstehen.

Was ich nicht verstehe ist, der Wert, welcher den Objekten zugeordnet wird. Ich habe keine Idee, wie ich diese Werte erheben und zuordnen soll und ob diese Werte in Abhängigkeit zu den Gewichten erhoben werden.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.12.2009
Mitteilungen: 639
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-03-06


Hallo,

eine Frage wäre noch: Stehen eine feste Anzahl an Fahrzeugen zur Verfügung, die beladen werden MÜSSEN - oder ist ein zusätzliches Ziel möglichst wenige aber dafür vollbeladene Fahrzeuge zu erzielen?


Im ersteren Fall ist der Ansatz von MontyPythagoras keine schlechte Idee. Ich habe einen ähnlichen Algorithmus mal bei mir implementiert - ursprünglich war das nur als Startwert für einen Optimierungsalgorithmus geplant, aber die Lösung war so gut, dass ich das so gelassen habe.

Im zweitem Fall wird das ganze ein bisschen komplexer...


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
argonis
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 05.03.2020
Mitteilungen: 5
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2020-03-06


2020-03-06 14:47 - Carmageddon in Beitrag No. 9 schreibt:
Hallo,

eine Frage wäre noch: Stehen eine feste Anzahl an Fahrzeugen zur Verfügung, die beladen werden MÜSSEN - oder ist ein zusätzliches Ziel möglichst wenige aber dafür vollbeladene Fahrzeuge zu erzielen?


Im ersteren Fall ist der Ansatz von MontyPythagoras keine schlechte Idee. Ich habe einen ähnlichen Algorithmus mal bei mir implementiert - ursprünglich war das nur als Startwert für einen Optimierungsalgorithmus geplant, aber die Lösung war so gut, dass ich das so gelassen habe.

Im zweitem Fall wird das ganze ein bisschen komplexer...

Grundsätzlich sollen so wenig Fahrzeuge wie möglich beladen werden. Ich habe eben 3 Fahrzeuge zur Verfügung die in jedem Fall rausfahren. Ob nun beladen oder nicht. In aller Regel ist aber immer ausreichend Material zu fahren, dass mindestens 3 Fahrzeuge beladen werden. Was ich damit sagen will ist: das die Fahrzeuganzahl keine Konstante ist. Auch die Zuladungsgewichte variieren pro Fahrzeug.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1465
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-03-07


Hallo argonis!

Wenn ich die Aufgabe mathematisch angehen müsste, würde ich diskrete Optimierung und  wahrscheinlich lokale Suche benutzen. (Aber es gibt ja bereits gute Ansätze von anderen Usern.)

Falls sich die Gewichte der Ladungen wiederholen und auch die
LKW-Zuladungen gleich bleiben, könntest Du wohl auch mittels Papierstreifen (mit bestimmten Volumen oder Gewicht = Größe der Rechtecke) und bestimmten zu füllenden Flächen (LKW-Zuladungen) benutzen.
Vielleicht lässt sich die Aufgabe mit Millimeterpapier so lösen.
Dies könnte auch Spaß machen - so müsstest Du nicht jedes Mal den Computer bemühen!

Statt Millimeterpapier ginge wohl auch Holzmodelle(Quader) mit Volumen V1 bis V13.

Viele Grüße
Ronald



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.12.2009
Mitteilungen: 639
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-03-09


2020-03-06 22:44 - argonis in Beitrag No. 10 schreibt:
2020-03-06 14:47 - Carmageddon in Beitrag No. 9 schreibt:
Hallo,

eine Frage wäre noch: Stehen eine feste Anzahl an Fahrzeugen zur Verfügung, die beladen werden MÜSSEN - oder ist ein zusätzliches Ziel möglichst wenige aber dafür vollbeladene Fahrzeuge zu erzielen?


Im ersteren Fall ist der Ansatz von MontyPythagoras keine schlechte Idee. Ich habe einen ähnlichen Algorithmus mal bei mir implementiert - ursprünglich war das nur als Startwert für einen Optimierungsalgorithmus geplant, aber die Lösung war so gut, dass ich das so gelassen habe.

Im zweitem Fall wird das ganze ein bisschen komplexer...

Grundsätzlich sollen so wenig Fahrzeuge wie möglich beladen werden. Ich habe eben 3 Fahrzeuge zur Verfügung die in jedem Fall rausfahren. Ob nun beladen oder nicht. In aller Regel ist aber immer ausreichend Material zu fahren, dass mindestens 3 Fahrzeuge beladen werden. Was ich damit sagen will ist: das die Fahrzeuganzahl keine Konstante ist. Auch die Zuladungsgewichte variieren pro Fahrzeug.


Hallo,

bevor man sich hier mit diskreter Optimierung rumschlägt (😁) folgender Ad-Hoc Vorschlag:

1) Man trifft eine Vorauswahl aller möglichen und sinnvollen Fahrzeugkombinationen: Bei 6 Fahrzeugen und 3 sicher fahrenden Autos gibt es <math>\begin{pmatrix}6\\3 \end{pmatrix} + \begin{pmatrix}6\\4 \end{pmatrix} + \begin{pmatrix}6\\5 \end{pmatrix} +\begin{pmatrix}6\\6 \end{pmatrix} = 42</math> Möglichkeiten, für man prüft, ob die mögliche Gesamtzuladung der Fahrzeugkombination größer als das zu verladene Volumen ist.
Da du wahrscheinlich nicht so viele Fahrzeuge zur Verfügung hast, ist das kein Problem alle sinnvollen Kombinationen zu speichern.

2) Für jede dieser Kombinationen testest du nun die vorgeschlagene Verteilung von MontyPythagoras in Beitrag Nr.1 (immer schön von groß nach klein verteilen!)
Ich habe mir hier einen kleinen Algorithmus überlegt, der immer versucht den LKW zu finden, für den es am geschicktesten ist, das aktuelle Paket drauf zuladen.

3) Wähle die für dich günstigste Kombination der berechneten Verteilungen. Hier müsste man sich nun noch ein sinnvolles Kriterium überlegen (durchschnittliche Auslastung der LKWs, oder das Minimum an nicht genutzten Stauraum, ...)


Viele Grüße


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
argonis hat die Antworten auf ihre/seine Frage gesehen.
argonis wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]