Algorithmus für Transportoptimierung
-
Allgemeine Frage: Welche bekannten Algos existieren für die Optimierung von Transporten für Waren oder Personen in einem begrenzten Areal mit einer bestimmten Anzahl gleichartiger Fahrzeuge (nicht verfügbar, bereit und leer/teilbeladen/voll), vlt. auch einiger Spezialfahrzeuge (besonders groß, spezielle Ausrüstung)?
Es geht nicht vorwiegend um die Suche nach kürzesten Wegen (das schaffen heute die Navis - unterstützt durch aktuelle Verkehrsinfos - in den Fahrzeugen), sondern um den jeweils optimalen (und energiesparenden) Einsatz von Fahrzeugen (mit und später ohne Fahrer).
Überwacht/regelt/steuert man ein solches System eher zentral oder verteilt/kommunikativ? Vorbilder?
Passt hier auch bei vielen Fahrzeugen, die verschiedene Routen abdecken sollen der Ameisen-Algo? https://de.wikipedia.org/wiki/Ameisenalgorithmus
Es geht also nicht um einen "Handlungsreisenden", sondern um viele Handlungsreisende. Entscheidend ist nicht das Anfahren von A, sondern der Transport von A nach B usw. Optimierung des Fahrzeugeinsatzes, der Warte- und Transportzeiten. Gibt es für dieses komplexere System bereits eine theoretische Lösung?
-
Bevor es eine theoretische Lösung geben kann, muss es eine formale Problembeschreibung geben, aber genau die fehlt in deinem Post.
-
Klingt nach einem guten Einsatzgebiet für einen Genetischen Algorithmus.
-
Du meinst nicht zufaellig sowas?
https://de.wikipedia.org/wiki/Ungarische_Methode
-
@TGGC: Danke, diesen Begriff kannte ich bisher nicht. Genau diese "Verkupplung" zu idealen Bedingungen (nicht nur Geld, sondern vor allem Kundenzufriedenheit) will ich lösen.
-
Such mal nach "airline scheduling" oder "crew scheduling", das dürfte in die Richtung gehen. Da gibt es massenhaft Literatur und Forscher.
Ich glaube die Standardmethode in der Praxis ist bei den Airlines immer noch Vorverarbeitung mit Linearer Programmierung und dann finden einer möglichst optimalen Lösung mit einer Heuristik (Tabu Search, Simulated Annealing, usw.)
-
Danke für die Hinweise!
-
Der Vollständigkeit halber würde ich noch die Verbindung zu Fluss- und Matchingproblemen erwähnen.
-
Ich suche ein C++ Beispiel für https://de.wikipedia.org/wiki/Ungarische_Methode
finde erstaunlicherweise keines. Bitte um Hilfe.
-
Und das musstest du jetzt in den alten Thread schreiben?
-
manni66 schrieb:
Und das musstest du jetzt in den alten Thread schreiben?
Wieso, passt doch alles zusammen. Erhard hat ursprünglich gefragt, ihm ist die ungarische Methode vorgeschlagen worden, und jetzt erkundigt er sich nach einer Beispielimplementation. Was stört es, wenn da ein paar Monate seitdem vergangen sind?
-
Mr X schrieb:
Was stört es, wenn da ein paar Monate seitdem vergangen sind?
Sehe ich auch so. OPs dürfen ihre Threads i.d.R. stets erwecken, gerade wenn eine so relativ kurze Zeitspanne dazwischen liegt.
-
Diese Apriltrolle
-
Könnte jemand auch mal sachdienliche Hinweise geben?
Ich habe mit "Ungarische ..." gesucht. MrX hat mit "Hungarian Method C++" sofort das hier u.a. gefunden: https://github.com/saebyn/munkres-cpp usw.
-
In der LEDA Bibliothek sollte auch eine Implementation dazu enthalten sein.