Transportproblem - Welche Methode anwenden?

Wissenschaft Mathematik
#1

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 mit folgender Situation:
Es gibt mehrere Punkte, 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 bestimmte Mengen mit einem Stapler zu transportieren, sodass die Wegstrecke minimal ist.
z.B.
Von A nach B 2 Stück
Von B nach A 1 Stück
Von C nach B 2 Stück
von A nach C 1 Stück

Von der prinzipiellen Einordnung handelt es sich ja um NP-Problemstellungen?

super wäre es, wenn zeitliche Restriktionen auch berücksichtig werden können ( A nach B hat innerhalb der nächsten Stunde zu erfolgen,…)

Ich hoffe ihr könnt mir helfen!
Mit bestem Dank im Voraus
David

#2

Hallo David,
so richtig helfen kann ich dir nicht. Dazu müsste ich wissen wie das Netzwerk (A, B, C, D) „aufgebaut“ ist.

Zu deiner Frage wo man dieses Problem von der Komplexität her einordnen kann, würde ich es als P (http://en.wikipedia.org/wiki/P_(complexity)) was zur „Menge“ der NP gehört, da ich davon ausgehen, dass die Routen vorgegeben sind. Also handelt es sich um ein Netzwerkfluss-Problem, dass mittels Algorithmus gelöst werden kann.
Noch zu den zeitlichen Restriktion: da würde ich gleich vorgehen wie bei den Mengen. Den Algorithmus dann so definieren, dass er entsprechend diesen Restriktion entscheidet.
Grüsse,
GeazMoan

#3

Hallo,
vielen Dank für die Antwort!

Jede Verbindung zwischen A, B, C und D ist erlaubt/vorhanden.
Die Wegzeiten zwischen den Stationen kannst du für eine mögliche Erklärung annehmen wie du willst, schließtlich kann man die ja sowieso ausbessern wie man sie dann wirklich hat!

#4

Hallo David,
für die Weiterbearbeitung müsste ich schon einbisschen mehr wissen, vor allem wie dein „Background“ diesbzgl. ist. Zudem geht es - meiner Meinung nach - über den Horizont einer gewöhnlichen Beantwortung einer Frage hinaus.
Grüsse, GeazMoan