Rundlaufoptimierung < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es existiert ein Depot welches eine bestimmte Menge von Gütern innerhalb von einer Woche an Kunden ausliefern soll.
Es existieren Kundenorte die jeweils eine bestimmte Menge von Gütern am Ende dieser Woche erhalten haben sollen, diese Güter werden mit Fahrzeugen (beschränkte Kapazität) in jeweils einem Rundlauf transportiert.
Die Entfernungen zu den Kundenorten, die Fahrtkosten und die Fahrtdauer sind gegeben.
Nun ist die Frage, wie viele Fahrzeuge im Depot stationiert werden müssen, um alle diese Kunden innerhalb von einer Woche abzudecken. |
Ich hoffe das Problem ist verständlich gemacht. Nun suche ich einen Algorithmus/Verfahren/Heuristik mit welcher man die geringsten Kosten und die daraus resultierende Anzahl der Fahrzeuge bestimmen kann. Ich suche keine Lösung, nur einen Hinweis mit welchem Verfahren man das Problem angehen könnte.
Beispiel:
Das Depot muss 2 Kunden beliefern. Kunde 1 erhalt 500 Mengeneinheiten(ME), Kunde 2 300 ME. Kunde 1 ist 500 Km entfernt, Kunde 2 150 Km, daraus resultieren Fahrtkosten und Dauer. Fahrergehalt und Fahrzeugabschreibung fallen pro Tag an.
Ein Fahrzeug kann aber mit einer Fahrt nur 15 ME transportieren. Nun sollen beide Depos nach 5 Tagen günstig abgedeckt sein.
Desto mehr Fahrzeuge, desto schneller geht es natürlich, doch desto mehr Kosten (Fahrergehalt, Abschreibung).
Für jeden Vorschlag wäre ich dankbar!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:12 So 06.06.2010 | | Autor: | max3000 |
Bevor du dir Gedanken über den Algorithmus machst brauchst du doch erstmal ein vernünftiges mathematisches Modell. Da dies in dem Fall doch recht schwierig ist würde ich sagen dass man auf jeden Fall erstmal nach guten Heuristiken suchen sollte. Alles andere wäre für dieses Beispiel zu komplex um es mit gewöhnlichen Verfahren zu lösen.
Da du hier viele Zielgrößen hast (Minimale Fahrzeugzahl, Maximale Erfüllung der Kundenaufträge, Minimaler Weg der einzelnen Fahrzeuge, etc...) musst du eine Heuristische Funktion finden, die eine Bewertung unter all diesen Kriterien zusammen abgibt. Also simpelsten Weg würde ich die Zielgrößen einfach mit Gewichten als Verfahrensparameter aufsummieren und in jedem Schritt irgendwie die Stellgrößen ändern. Also irgendwas in Richtung Simmulated Annealing, Threshold Accepting oder Genetischen Algorithmen.
Wo hast du die Aufgabe eigentlich her? Was genau sollst du machen?
Geht es darum ein Lösungsverfahren zu implementieren oder mehr um die Theorie?
|
|
|
| |
|
Danke für deine Antwort und die Vorschläge erstmal!
"Minimale Fahrzeugzahl, Maximale Erfüllung der Kundenaufträge, Minimaler Weg der einzelnen Fahrzeuge."
Es ist lediglich Ziel, die gewünschten Kundenmengen innerhalb eines Zeitfensters auszuliefern. Die Fahrzeuganzahl soll nicht minimiert werden und minimaler Weg ist nicht möglich, da pro Ablieferort genau ein Weg gegeben ist der immer wieder abgefahren wird. Aber du hast Recht, zu erst bräuchte ich eine gültige Ausgangslösung um Anhand dieser zu Optimieren. Nachher möchte ich durch Abändern verschiedener Anfangsparameter mit dem Ergebnis "spielen" können.
Die Aufgabe habe ich aus der Praxis, beschäftige mich gerade mit derartigen Problemen von Speditionen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:42 Mi 09.06.2010 | | Autor: | max3000 |
Das ist schon ein sehr komplexes Modell und durch deine diskrete Größe drin (Fahrzeuganzahl), wird das auch sehr aufwendig mit direkten Verfahren zu lösen. Darum würde ich Heuristische Suchverfahren vorschlagen.
Was du als erstes brauchst ist eine Art simulation, die zu gegebener Fahrzeuganzahl und route der einzelnen Fahrzeuge deine Zeilgrößen (Überschreitung der vorgeschriebenen Lieferzeit, Fahrzeuganzahl, etc.) zu gegebenen Stellgrößen (Route für jedes Fahrzeug, etc.) berechnet. Ich denke mit Genetischen Algorithmen könnte man das ganz gut lösen.
Da es sicherlich sehr aufwendig wird eine eigene Simulationsanwendung zu schreiben und dann noch einen passenden Algorithmus zu implementieren denke ich wirst du nicht um eine Simulationssoftware drum herum kommen. Vielleicht solltest du dich mal über "ereignisdiskrete Simulationssoftware" informieren. Ich bearbeite grad etwas ähnliches und habe dazu "simcron MODELLER" verwendet. Das ist aber eher dazu da um Produktionsprozesse zu simulieren. Aber vielleicht findest du etwas ähnliches, was im Logistikbereich eingesetzt wird.
Grüße
Max
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Mi 16.06.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
