Problem in OR einordnen < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 22:44 Sa 29.09.2012 | | Autor: | bsty |
| Aufgabe | | Wo ist die Problemstellung im OR anzusiedeln? |
Hallo,
ich habe eine Frage bzgl. Einordnung/Methodik in Operations Research für eine bestimmte Aufgabenstellung die wäre:
Es handelt sich um ein "Transportproblem" folgender Situation:
Es gibt mehrere Stationen, die sowohl als Quelle oder Senke auftreten können.
Z.B.
4 Stationen A,B,C & D( Jeweils Quelle und Senke zugleich) und jetzt sind zwischen diesen Stationen genau bestimmte Mengen mit einem Stapler zu transportieren, sodass die Wegstrecke minimal ist.
z.B.
2 Stück von A müssen nach B
3 Stück von D müssen nach B
1 Stück von C müssen nach A
2 Stück von C müssen nach B
Von der prinzipiellen Einordnung handelt es sich ja um NP-Problemstellungen?
Mir sind einfache Tourenprobleme ( 3 Quellen sollen Kosten/Wegoptimal 5 Senken beliefern etc.) bekannt, aber irgendwie komm ich mit diesem Beispiel überhaupt nicht klar, oder ich kann die bisherigen Lösungsansätze nicht richtig auf das Problem übersetzen.
Außerdem sollte der Algorithmus auch einen Zeitfaktor berücksichtigen. ( 1 Stück von A nach B muss innerhalb einer Stunde abgearbeitet sein)
EDIT:
Jede Verbindung zwischen A, B, C und D ist erlaubt/vorhanden.
Die Wegzeiten zwischen den Stationen kann man für eine mögliche Erklärung annehmen wie man will, schließtlich sind die Zeiten in dem Modell jederzeit änderbar.
Ich hoffe ihr könnt mir helfen!
Mit bestem Dank im Voraus
David
PS
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.wer-weiss-was.de/app/query/send?queryid=1190391
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:06 So 30.09.2012 | | Autor: | Infinit |
Hallo bsty,
willkommen hier bei der Vorhilfe.
Die Aufgabenbeschreibung ist noch nicht so komplett, dass man damit direkt was anfangen kann. Wo sind die Freiheitsgrade, an denen Du herumschrauben kannst? Wenn die Orte festliegen und auch die zwischen diesen Orten zu transportierenden Waren, dann sehe ich da keine große Chance, etwas zu optimieren. Wo kannst Du also in Deinem Modell ab und zu geben?
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 12:06 So 30.09.2012 | | Autor: | bsty |
Hallo Infinit,
vielen Dank für deine rasche Rückmeldung.
Die Freiheitsgrade sind ( wenn ich deine Antwort in https://matheraum.de/forum/Optimierung_-_Freiheitsgrade/t812758 richtig verstanden habe):
1)Wegzeiten/strecke zwischen den Stationen können beliebg geändert werden & die Wegstrecke kann ohne bedenken in Wegzeiten umgerechnet werden
2) Es kommen immer neue Produkte die von unterschiedlichen Stationen zu unterschiedlichen Stationen transportiert werden müssen hinzu. ( für Problem jetzt weniger relevant, da es sich dann einfach um Berechnungen zu unterschiedlichen Zeitpunkten handelt - Es wird einfach immer das optmimiert, was gerade im System ist
3)Es können mehrere Stationen als 4 in dem Modell berücksichtigt werden ( ohne jetzt (anfangs) weiter auf Laufzeitprobleme bei der Lösungsfindung zu achten
Restriktionen wären:
1)Es gibt einen Stapler, 1 Stapler kann immer nur ein Stück pro Transport zwischen zwei Stationen transportieren
2)Für jeden Transport gibt es einen spätesten Zeitpunkt, an dem er durchgeführt werden muss
Ich sehe die Chance die gesamte Wegstrecke/Wegzeit für alle Transporte zu minimieren, also in welcher Reihenfolge sollen die Transporte realisiert werden. Zwischen den Transporten kann es ja dann auch zu "Leerwegen/Leerzeiten", die der Stapler aufwenden muss um das nächste Produkt abzuholen und wieder zu einer Station zu bringen.
Vielleicht hilft es bei der Problemdefinition:
Prinzipiell handelt es sich um ein Staplerleitsystem. Wann holt der Stapler von wo was ab und bringt es (über welche Route) wohin, so dass die Wegstrecke/Zeit minimal ist.
Bsp. (A,B,C)
AB,BA Wegzeit 1
AC,CA Wegzeit 1
BC,CB Wegzeit 1
Transportanforderungen jeweils 1 Stk von
A nach B
B nach C
A nach C
dann gibt es ja mehrere Möglichkeiten mit unterschiedlichen Wegzeiten: ( _= Transport von nach ; ohne _ = Leerfahrt (CB)
[mm] A_B; B_C; [/mm] CB, BA; [mm] A_C; [/mm] Wegzeit gesamt = 5
[mm] A_B; B_C; [/mm] CA; [mm] A_C; [/mm] Wegzeit gesamt =4
Also jenachdem in welcher Reihenfolge man die Transportaufträge abbarbeitet und welche Wege man dabei zurücklegt bekommt man eine kürzere Wegstrecke.
Prinzipiell muss es sich ja mal irgendwie um ganzzahlige Optimierung handeln, weil ich ja eigentlich nur irgendwelche Transportbeziehungen nach der Reihe "aktiviere". Und über alle aktivierten Beziehungen muss sich dann ein Minimum ergeben.
Bin grad etwas verwirrt, mach ich´s komplizierter als das Problem ist?
PS: Den Zeitfaktor kann man z.B so berücksichtigen, dass man die Restriktionen mit der Zeit einfach ganz hoch bestraft, sodass der Zeitfaktor vor jedem Transport schlagend wird?
Ich hoffe die Rückmeldung ist verständlich, wenn nicht bitte einfach sagen!
LG
bsty
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:02 Mi 03.10.2012 | | Autor: | Infinit |
Hallo bsty,
danke für die Beschreibung, jetzt ist mir einiges klarer, wenn ich auch nicht eine Musterstrategie aus dem Ärmel schütteln kann. Die Zeit spielt hier eine wichtige Rolle und die Bewertung der Gegenstände, die zum Transport eingesetzt werden oder auch tranportiert werden sollen. Eine kontinuierliche Beschreibung als Funktion der Zeit macht wohl keinen Sinn, sondern es muss eine Strategie entwickelt werden, um herauszubekommen, welche Aktion zum nächsten Zeitpunkt am zielversprechensten ist. Mit OR habe ich mich nie beschäftigt, nur ein bisschen BWL mal gemacht, wo allerdings ähnliche Probleme auftreten. Eine Bewertung in Form einer Übergangsmatrix könnte hier weiterhelfen, denn zu einem gegebenen Zeitpunkt muss ich ja entscheiden, was als nächstes durchgeführt werden soll. Hierbei muss eine Zielfunktion minimiert werden, wobei der Transport von Gütern positiv eingeht, die Transportkosten selbst aber negativ. Es gibt hier sicherlich Restriktionen, die man beachten muss, zu denen ich aber eben nichts weiter sagen kann. Macht es beispielsweise Sinn ein Gut zunächst komplett von der Quelle zum Ziel zu transportieren, kann man es zwischenlagern und eine negative Bewertung in Kauf nehmen, da ein Stapler auch mal leer fährt? Das sind solche Fragen, die mir durch den Kopf gehen, wo ich aber dediziert nicht weiterhelfen kann.
Gehen diese Überlegungen in Deine Richtung oder siehst Du vollkommen andere Ansätze?
Viele Grüße,
Infinit
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:20 Mi 03.10.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:20 So 07.10.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
