Verfasst am: 04.12.2008, 11:19
Titel: warehouse location problem
Hallo zusammen,
sitze gerade an einem kniffligen Problem und beiss mir die Zähne aus. Vielleicht kann mir jemand von euch helfen!?
Das Problem:
Ich habe 600 Filialen, die mit Material versorgt werden müssen und habe alle Entfernungen zwischen den Filialen. (Filialen=z.B. alle Obi's die mit Spanplatten versorgt werden müssen)
Nun möchte ich 20 Filialen durch ein Lager erweitern.
Wie programmiere ich das, damit mein Programm mir sagt, welche der 600 möglichen Standort gewählt werden sollen. Zur Vereinfachung habe ich angenommen, dass jede Filiale einzeln vom Lager versorgt wird (also kein LKW der mit einer Fahrt vom Lager z.B. 2 Filialen versorgt).
Das ganze soll nun so gemacht werden, dass die Fahrtstrecken minimal sind.
Gut wäre noch, wenn man berücksichtgen könnte, dass die Filialen unterschiedlich oft angefahren werden müssen.
____________________
Ich weiss das ist nicht ganz einfach, aber bin mittlerweile einfach total ratlos und würde mich über jede Anregung freuen.
Ok ich bin nicht der Optimierungsexperte aber ich würde das erstmal in Matlab Form bringen. Ich schätze mal die Abstände sind in einer 600 mal 600 Matrix. Dann würde ich noch eine 2 mal 600 Matrix erstellen. Die erste Zeile für das Lager (1 oder 0) und die Zweite für die Besuche im Lager. Tja und dann brauchst du nen Optimierungsalgorithmus. Mir fällt da spontan nur hill climbing alg. oder A Stern ein. Aber Matlab hat ja auch optimierungsfunktionen. Da müsste nochmal jemand anderes was dazu schreiben.
Hallo boka, das hört sich nach einer Anfrage aus der Hochschulasubildung an. Für solche Probleme eignen sich genetische Algorithmen - ein faszinierendes Thema. Das Rechenzentrum der Uni hat auch bestimmt eine Lizenz für die "Genetic Algorithm and Direct Search Toolbox":
meiner Meinung nach ist das erstmal gar kein Matlab-Problem, sondern ein Modellierungs- und dann ein Optimierungsproblem. Für die Modellierung gibt es immer mehrere Möglichkeiten. Vielleicht kann man dies sogar linear modellieren, aber ich schaffe es (erstmal) als quadratisches Problem (quadratische Zielfunktion und quadratische und lineare Nebenbedingungen).
Ich würde binäre Entscheidungsvariable nehmen, also solche, die nur 0 oder 1 annehmen können.
Variable:
x_i = 1, wenn Filiale i zum Lager ausgebaut wird, sonst = 0
y_ij = 1, wenn Lager-Filiale i die Filiale j beliefert, sonst = 0
Konstanten: Entfernungen c_ij zwischen Filiale i und Filiale j
Zielfunktion: minimiere sum (x_i * sum (c_ij * y_ij) )
wobei die erste Summe über i geht und die zweite über j
Nebenbedingungen:
sum x_i = 20
sum x_i * y_ij = 1 für alle j (Summe über i)
x_i^2-x_i = 0 für alle i
y_ij^2-y_ij = 0 für alle i, für alle j
Damit hat man genau 20 Lager, jede Filiale wird genau einmal bedient und die Variablen sind entweder 1 oder 0 (Nachrechnen!).
Falls jedes Lager genau 30 Filialen bedienen soll, braucht man noch:
sum y_ij <= 30 für alle i (Summe über j)
Das wär's. Quadratische Probleme löst man im allgemeinen nicht mit genetischen Algorithmen. Letztere sind für schwierige Funktionen mit vielen lokalen Minima geeignet, die hier aber nicht vorliegen. Ich würde stattdessen fmincon aus der Optimization Toolbox verwenden.
Brauchst Du Hilfe bei der Implementierung? Einfach fragen.
ist ja super, vielen Dank für eure schnellen und ausführlichen Antworten!
Für die Implementierung der Idee von Bijick fällt mir spontan eine while Schleife ein. Minimiere die Zielfunktion solange die Randbedingungen gelten... ist das so von dir gedacht?
nein, ich dachte mir, dass Matlab die Optimierung übernimmt. Steht Dir denn die Optimization Toolbox zur Verfügung? Dann können wir fmincon nehmen und ist alles ganz leicht. Wenn nicht, müssen wir mit fminsearch tricksen, das geht auch.
Bei neuen Matlab-Versionen kann man (falls die Optimization Toolbox vorliegt) auch mit dem Optimization Tool arbeiten. Das ist eine grafische Oberfläche, bei der man sich dann alles zusammenklickern kann, ohne selbst programmieren zu müssen (außer die Zielfunktion und die Nebenbedingungen).
Sag doch mal, welche Version und welche Toolboxen Du hast.
Verfasst am: 08.12.2008, 10:25
Titel: Verwendete MatLAB Version
Hallo Bijick,
ich verwende die aktuelle Version von 2008 und habe zugang zu allen Toolboxen. Da ich mich nicht als versierten Programmierer bezeichnen würde finde ich deinen Vorschlag mit der graphischen Oberfläche ganz besonders interessant. Wie würde das denn dann aussehen?
ich hab das gerade mal für eine Testinstanz mit 6 Filialen und zwei Lagern ausprobiert und musste leider feststellen, dass es nicht so einfach ist. Der Optimierer hat Schwierigkeiten damit, die Ganzzahligkeit einzuhalten und findet daher nix Gescheites. Ich versuche nochmal, das ganze linear zu modellieren, denn mit bintprog ist die Ganzzahligkeit wieder kein Problem mehr. Schau Dir doch in der Zwischenzeit schon mal die Hilfe zum Optimierungstool (optimtool) an. Dann fällt es Dir später leichter, damit umzugehen.
vielen Dank für deine Hilfe. Ich bin sozusagen ein MatLAB Neuling und bin fast schon verzweifelt! Hoffentlich liefert dein lineares Modell ein Ergebnis! Falls ja kannst du mir das Modell dann per eMail schicken damit ich einen Anhaltspunkt habe wie das ganze aussehen könnte?
und wähle als "Solver" die Funktion bintprog aus. Dann schreibe in die Felder f, A, Aeq, b, beq genau diese Variablen hinein, also zum Beispiel in das Feld "f" schreibe f. Jetzt "Start" klicken und abwarten.
Im guten Fall erscheint die Meldung
Zitat:
Optimization running.
Optimization terminated.
Objective function value: xxx
Optimization terminated.
natürlich mit richtigem Optimalwert. Jetzt müssen wir nur noch aus der Tabelle "Final point" die Standorte der Lager ermitteln. Das geht so: Tabelle markieren, Strg + C drücken, im Workspace Strg +V drücken. Dann öffnet sich ein Fenster, "Next" und "Finish" klicken. Jetzt müssen wir aus A_pastespecial unseren Vektor x und unsere Matrix Y klauben:
Code:
z = A_pastespecial(:,2);
x = z(1:n);
Y = zeros(n);
Y(:) = z(n+1:end);
[ind1,ind2] = find(Y);
Lager = [ind1,ind2]
DAS ist ja SUPER! Vielen Dank Bijik. Ich war die letzten Tage krank aber ich werde es gleich morgen mal ausprobieren und melde mich dann nochmal hier im Forum und berichte.
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS