Excel Solver Transportproblem Optimierung

[anro9383]

Hallo zusammen,
ich versuche mich gerade an der Lösung eines klassischen Transportproblems über den Solver mit Simplex LP. 
Ich habe auch eine Lösung, aber denke dass man das besser lösen kann und würde mich sehr über Input freuen. (Datei mit aktuellem Stand ist angehängt)

Folgende Problemstellung:

- Die Bedarfe von D1-D8 sollen durch die Anbieter KL1-KL5 gedeckt werden
- Bedarfs,- und Angebotsmengen sowie Entfernungen sind gegeben
- alle Fzg. fahren je Tour immer nur ein D an und fahren anschließend zurück zu dem KL von dem sie gekommen sind (keine Kombination von Anfahrten zu verschiedenen D auf einer Tour)
- jedes Fzg. fährt tgl. nur 1 Tour
- an Kosten entstehen 0,35€/km
- jedes Fzg. hat max. Kapazität von 10
- je Fzg. fallen 190€ Fixkosten an
- jedes Fzg. hat eine max. Kapazität von 10 ME je Tour 
- je Fzg. fallen 190€ Fixkosten an

Ist also soweit ja erstmal ein klassisches TPP.
Ich habe es so gelöst, dass ich über den Solver die optimalen Transportmengen (also das auch als Zielfunktion definiert) ermittelt habe, dann durch die Kapazität geteilt und für die nötige Anzahl an Fzg. aufgerundet und darüber dann die Kosten ermittelt.
Also eigentlich nur den 1. Teil modelliert und den Rest danach berechnet. 

Ich denke, dass wird auch grob passen.
Meine Überlegung war aber, dass die Bedingung mit der Kapazitätsgrenzen ja schon in die optimalen Mengen einfließen sollte, da man dann vielleicht Mengen auf "schlechte KM-Relationen legt", um ggf. an anderer Stelle einen ganzen Transport zu sparen und einen besseren Kostennutzen zu haben.
Allerdings würde sich bei meiner Endlösung eh nichts sinnvoll verschieben lassen, dass man einen Transport sparen könnte.

Wie ist eure Meinung dazu? Sollte ich es dabei belassen oder kann man alle Bedingungen in der Modellierung vereinen? 
Und wenn ja, wie gehe ich da vor?

Vielen Dank schon mal fürs Mitdenken :)
Lg

[Ego]

Hallo a...,

zu

Sollte ich es dabei belassen

Wenn ich die Bedingungen richtig verstanden habe, kannst du es so lassen.

zu

Ich habe auch eine Lösung, aber denke dass man das besser lösen kann

Aber nur wenn du bei der Bedarfsprüfung auch das Kühllager 5 berücksichtigst.

[Ego]

Hallo a...,

nach nochmaligem Lesen der Bedingungen ist mir aufgefallen, dass das Gesamtproblem durch die Begrenzung der ME je Tour und die Kosten pro Fahrt und Fahrzeug nicht mehr linear ist. Und für die Gesamtkosten mit diesem Vorgehen nicht immer eine optimale Lösung gefunden wird.

Du kannst in deinem Beispiel das Angebot in Kl4 auf 82 erhöhen. Eigentlich sollte ein erhöhtes Angebot die Kosten nicht erhöhen, was es aber bei deinem Vorgehen macht.

[anro9383]

Hallo Helmut, 

ups da ist die letzte Zeile wohl durchgerutscht. Hab ich korrigiert - danke für den Hinweis.

Also wüsstest du auch keine Möglichkeit, wie ich die Kapazitätsbegrenzung von 10ME je Fzg. und/oder den Fixkostenbetrag je Fzg. bereits in die Modellierung einfließen lassen kann, um so vielleicht sogar eine Optimallösung zu erhalten.

Mh ja.. ich verstehe was du meinst, ich kann also hier nur eine gute Lösung finden und nicht garantieren, dass es die Optimallösung ist. Hab es noch mit anderen Beispielzahlen in KL4 versucht und sogar immer andere Ergebnisse. Das dürfte ja bei der Optimallösung nicht passieren.

Hast du eine Idee, mit welchem Verfahren man sonst zu einer optimalen Lösung kommen könnte? 

Lg
Anne

[anro9383]

Hat vielleicht noch jemand eine Idee?? 
Ich habe nun einen Ansatz verfolgt, wie ich die Fixkosten und Kapazitätsbegrenzung doch mit in die Zielfunktion des Solvers einbauen kann.
Ich habe aus der Entfernungsmatrix die Kosten je Fzg. ermittelt und dann das Summenprodukt aus Entscheidungsvariablen (bzw. die aus den Mengen resultierenden Ganztransporte) und Kostenmatrix gebildet. 

Soweit so gut. Die Berechnung klappt, aber mein Ergebnis ist um ca. 10.000€ schlechter als meine "naive" anfängliche Herangehensweise.
Das kommt daher, dass der Solver auf Biegen und Brechen versucht, dass jedes KL möglichst auch jedes D beliefert (was ja eher kontraproduktiv ist).

Ich verstehe, dass durch Solver hier keine optimale Lösung garantiert werden kann - aber diese Lösung scheint ja meilenweit weg von optimal.

Wäre für jede Hilfe und Ansatz dankbar, um das Thema irgendwie zu verstehen.

Lg und Danke 
Anne

[Ego]

Hallo Anne,


A) Probleme bei den Solver-Methoden

1. Methode Simplex
Deine Zielfunktion ist nicht linear. Daher liefert der Solver eine Fehlermeldung.

2. Methode GRG
Deine Zielfunktion ist nicht stetig. Daher liefert der Solver nur eine zufällig gefundene gültige Lösung.

3. Methode EA
Diese Methode ist theoretisch möglich. Hierbei wird über zufällige Änderungen von bestehenden Lösungen versucht eine Verbesserung zu erhalten. Bevorzugt werden Änderungen die ähnlich schon gefundener guter Lösungen sind.
a) Wenn ich das Problem wie in der Datei mit 40 Variablen (Mengen von Lager nach Lieferort) erstelle muss der Algorithmus immer wieder erst über zufällige kleine Änderungen dieser Variablen eine gültige Lösung finden die sowohl die Angebotsgrenzen als auch die Nachfragegrenzen einhält. Dies ist (wenn überhaupt möglich) sehr sehr sehr zeitaufwändig, also nicht machbar.
b) Für diese Methode würde man für jede angefragte ME eine Variable anlegen in der festgelegt wird aus welchem Lager sie beliefert wird. Dann müste man "nur" noch das Einhalten der Angebotsgrenzen prüfen. Das sind aber in deinem Beispiel mehr als 600 Variablen, was im Excel-Solver die Begrenzung weit überschreitet.
c) Eventuell könnte man über geschickte Zusammenfassung der ME die Anzahl der Variablen reduzieren. ZB. könnte man an jedem Lieferort 1/5 der ME zusammenfassen da ja mindestens einer der Lager 1/5 liefern muss. Ob man mit solchen Zusammenfassungen die Anzahl der Variablen allgemeingültig auf die Grenzen des Excel-Solvers reduzieren kann und ob dann in angemessener Zeit eine gute Lösung gefunden werden kann ist unwahrscheinlich.

B) manuelle Anpassung der zweistufigen Lösung.
Du kannst versuchen, wenn die aktuell Anzahl der Fahrzeuge an einem Lieferort grösser ist als das theretische Minimum, die Restmengen aus zwei Lagern wenn möglich anders aufzuteilen oder einem Lager mit noch freien Mengen zuzuordnen.
In deinem Beispel wird für D7 (wenn du die Zeile 19 auch in den Nebenbedingungen berücksichtigt hast ) aus "0;0;13;0;75" "0;8;10;0;70"

[anro9383]

Hallo Helmut, 
danke für die Antwort :)
Also ich habe ja schon eine Lösung mit dem Solver erreicht, die auch ganz gut zu sein scheint - habe dabei aber die Fixkosten einfach rausgelassen und nur am Ende aufgeschlagen. So ist die Kostenfunktion linear und geht mit Simplex-LP. 

Die Ideen das händisch noch auf Verbesserung zu prüfen sind sicher ganz gute Ansätze aber der Anspruch bei der Aufgabe bzw. der meines Professors ist das Problem über ein exaktes Verfahren eine optimale Lösung nach linearem Optimierungsmodell zu finden, sprich simplex-LP. Irgendwie muss es also gehen..

Da die Zielfunktion allerdings nicht linear ist, war meine Idee alles auf Ganztransporte umzumünzen und gar nicht mehr die einzelnen Mengen zu betrachten. So wäre ja Linearität gegeben oder? Je weiteres Fzg. steigen die Kosten in gleichem Maße. 
Ich mache mir also eine Kostenmatrix je Relation für ein Fzg. 
So das wäre also der erste Teil der Zielfunktion: Summe über alle (Anzahl der Transporte je Relation*Kosten je Fahrzeug)- das bekomme ich über den Solver ja gut abgebildet. 

Dazu müsste ich denke ich noch eine Art Binärvariable einführen, die angibt ob auf der Relation ein Transport stattfindet oder nicht.
Aber eigentlich eben nicht nur ob oder ob nicht sondern auch wenn ja, wie oft?
ls Nebenbedingung wäre mir dazu noch eingefallen, dass wenn diese Binärvariable 0 ist, muss xij auch 0 sein. 

Also ich denke ich habe eine Grundidee zu dem Ganzen, aber leider ist es ganz schön verfahren in meinem Kopf und ich fürchte ich kann meine Gedankengänge auch nicht so gut darstellen. 

Ich bin etwas ratlos, vielleicht hast du noch Muse :)
Würde mich freuen.
Lg 
Anne

---

Ich habe Literatur dazu gefunden, die zu meinen Überlegungen aber einigermaßen passt (aber eben auch nur fast) - siehe Bilder unten
Vielleicht könnte man das anwenden, wenn man für das Zeichen eta die 10 Kapazität nimmt?