Weg des Handlungsreisenden mit Laster und diversen Guetern

[voon]

Ich bin weder Programmierer, noch Algorithmierer, noch Mathemagier, noch sehr bewandert in solchen Dingen ... aber es interessiert mich.

Ein einfaches Problem: Ich hab X Staedte, die jeweils irgendwas an- und verkaufen. Mein Laster verbraucht Sprit und die Fahrt zudem Zeit. Ich moechte maximalen Profit.

Berlin verkauft also Berliner und Currywurst und sucht nach Flugplatzbauteilen und Steuer-CDs.
Zuerich mag Currywurst und Farben und verkauft seinerseits Steuer-CDs.
Mailand verkauft italienische Schuhe sowie Farben und kauft Uhren.

Usw. Die waren haben jeweils ein Volumen, mein Laster ebenfalls. Gewicht lassen wir einfach mal weg. Die Waren haben zudem einen Wert.

Es ist so eine Art Kombination aus dem Problem des Handlungsreisenden und dem Rucksackproblem:

Ich moechte maximalen Profit. Dazu soll irgendeine Route durch irgendwelche Staedte fuehren und Handel mit irgendwelchen Guetern getaetigt werden. Meine Spritkosten dabei moeglichst niedrig (werden vom Gewinn abgezogen) und natuerlich das Ladevolumen meines Lasters beruecksichtig werden.

Es kann also irgend eine Route sein. Staedte A, B C und Gueter X, Y Z. oder Staedte A, B, C, D, E und Gueter V, W, X, Y, Z oder irgendwas sonst beliebiges .. Staedte A, G, K und Gueter B, H, Z etc.

Staedte solls dabei so ca 100 - 200 geben. Handeslgueter vieleicht 200.

Ich hab nicht die geringste Ahnung, wie man sowas programmiert oder ob das schon jemand getan hat, ob das Problem ueberhaupt zeitnah geloest werden kann mit einem aktuellen PC usw.

Falls aber jemand mal sowas gemacht hat wuerd es mich interessieren.

 

[Nitschi66]

Puh, also ein Freund von mir hat sich dem mal für seine 5te PK im Abi angenommen und darüber referiert und ich weiß noch, dass er meinte, dafür gebe es keine Formel, das muss ausprobiert werden. Und er hat das auf seinem MacBook (Core2duo) für maximal 5 Städte NUR mit entfernungs-Optimum "berechnet" und selbst das hat paar Sekunden gedauert. Bei 100-200 Städten sind das immerhin 100! (Fakultät) bis 200 Fakultät Möglichkeiten...denke nicht dass das so ohne weiteres aufm normalen Rechner berechenbar ist.

Aber ich habe auch keine Ahnung ob nicht irgendwann mal eine Russe oder sonst wer ein geniales Programm geschrieben hat, möglich ist alles, ich bezweifel es aber.

"Die Vorgehensweise in der Praxis unterscheidet sich von der mathematischen Theorie dadurch, dass in der Regel nicht nach einer optimalen Lösung gesucht wird, sondern nur nach einer ausreichend guten. Denn schließlich muss der Gesamtaufwand betrachtet werden, also der Aufwand für Durchführung und Berechnung. Was dabei „gut“ bedeutet und welche Kriterien zum Tragen kommen, hängt dann sehr vom Kontext des Problems ab. So wird man sich für eine einmalige Liefertour weniger Mühe machen als für die Bestückungsplanung einer Leiterplatte, die in einer Millionenauflage hergestellt wird."
-Wikipedia

UPS FedEx etc benutzen auch solche "guten" Varianten. Die sind aber alles andere als optimal, als Beispiel: in Städten Werden seit ein paar Jahren Links-Abbiegungen von UPS (glaube ich ) vermieden und haben alleine dadurch 10-15% zeit einsparen können, da ist also noch einiges an Potential.

 

[Cr4y]

In folgendem Buch wurde das afaik auch (eher rudimentär) beschrieben:
"Die Intelligenz des Schwarms – was wir von Tieren für unser Leben in einer komplexen Welt lernen können"
Der Ansatz in dem Fall ist die Schwarmintelligenz - also selbstlernende Optimierung. Ich glaube in dem Fall basierte die Lösung auf der Funktionsweise von Ameisen-Kolonien.

Hab das Buch im Rahmen meiner BA-Thesis letztes Jahr gelesen (daher sind meine Erinnerungen etwas dunkel). Ist auch sonst recht interessant.

 

[Shimmy979]

Naja, schon alleine für 15 Städte gibt es im TSP über 40 Milliarden Möglichkeiten zur exakten Lösung.

Von daher wird es wohl bei deinen Zahlen schon sehr schwer, aber auch ich kenne mich nur mit den Grundlagen der Algorithmik aus (Informatikstudium).

Allerdings sollte klar sein, das für die NP-Probleme niemand einen wirklich effizienten Algorithmus entwickeln kann, was ja das Totschlagargument der Profs ist, etwas Algorithmik zu beherschen.

 

[cocosape]

Nach diesem Posting habe ich aus Verzweiflung mal wieder meine Schnapsflasche rausgeholt , und einen riesen Schluck genommen.Nach dem 2. oder 3. Schluck ,dachte ich mir: " Mann ,was manche Leute heutzutage ,um diese Uhrzeit für Probleme haben ... ?"
Was würde Einstein ,da wohl für einen schlauen Spruch verfassen ? " So ,jetzt gehe ich zu meier lieben Frau ins Bett und ........

Tschüss " Handlungsreisender " und immer schön fragen .

 

[estros]

In der realen Welt vereinfacht die Datumsangabe diese Berechnungen enorm.

 

[-Razzer-]

Normalerweise sucht man geeignete Heuristiken und kann somit das TSP relativ schnell lösen, wie gut das Ergebnis am Ende aber ist hängt von der Güte der Heuristik ab.

 

[maxwell-cs]

Wenn man Instanzen exakt lösen will, wird wohl Integer Programming das Mittel der Wahl sein.

 

[Ochse]

Puhh also bei den Größenordnungen, die du angegeben hast, glaube ich, du wirst in den meisten Fällen mit einem gewöhnlichen Heim-PC keine großen Chancen haben auch nur in die Nähe der optimalen Lösung zu kommen.

Darf man erfahren wozu du das brauchst?

 

[ryan_blackdrago]

Mir kommt die Problemstellung bekannt vor. Hatte mal eine Aufgabenstellung, die kürzeste Route/Knoten via Flughäfen zu berechnen. Hierzu wird der Dijkstra-Algorithmus genutzt. Laut google kann der auch in Excel eingebaut werden..

 

[ice-breaker]

Dijkstra löst das Problem des Handlungsreisenden nicht, der Algorithmus ist nur dafür da die optimale Route von einem Punkt zum nächsten Punkt mit x gegebenen Wegpunkten zu finden.

Für das angegebene Yproblemgibt es keinen richtig perfekten Algorithmus, da es für beide zugrunde liegenden Probleme keine gibt. Diese löst man (einzeln) dann mit Algorithmen die in annehmbarer Zeit eine gute Lösung finden (Tradeoff Rechenzeit vs. Genauigkeit).
Für das hier konstruierte Probleme wird das dann noch ne ganze Ecke schwerer, eine Aufgabe für die F&E-Abteilung.

 

[kuddlmuddl]

Wie bei Wiki ist: N = Anzahl Städte, M = Anzahl Kanten

-- edit: Hier stand erst mist, weil ich den Rückweg vergessen hatte.

Würdest du nur eine Strecke fahren wollen für maximal Profit ist das ganze in O(M) lösbar denn jede Strecke hat eine eindeutige und von der Umgebung unabhängige Größe "Gewinn pro Zeit" und die Strecke wo diese Größe maximal ist fährt man.
Der Algorithmus berechnet also einmal diese größe für alle Strecken (Kanten in einem Graphen) und gibt die maximal aus.

Da du aber einen geschlossenen Zyklus brauchst müsste man tatsächlich einen Routenplanungsalgorithmus nehmen (aber immernoch keinen NP Algorithmus bzw suboptimale Lösungen wie hier alle schreiben).
Dijkstra hat O(N*logN+m). Jetzt kommt allerdings jede Stadt als Start-/End-Knoten in betracht und nicht nur eine womit man dann bei O(N²*logN + NM) landet.

 

[voon]

Darf man erfahren wozu du das brauchst?

Klassisches Problem in vielen Computerspielen, die Handel einschliessen. Aber auch mal einfach aus interesse an der Sache. Ueber Bruteforce koennte man ja einfach jede erdenkliche Weg und Belademoeglichkeit ausrechnen, aber das wuerd wohl ewigs dauern.

Bei den fehlerhaften Annaeherungsalgorithmen faend ichs interessant zu wissen, wie genau die sein koennen, bzw was fuer Fehler man da in Kauf nimmt. Ich hab versucht die zugehoerigen Wikipages zu verstehen, aber ich glaub ich bin zu alt geworden fuer hoeheren Statistik- und Mathekram

 

[kuddlmuddl]

Ueber Bruteforce koennte man ja einfach jede erdenkliche Weg und Belademoeglichkeit ausrechnen, aber das wuerd wohl ewigs dauern.

Wie gesagt - das ist nicht nötig für eine optimale Lösung.
Wozu willst du überhaupt sub-optimale Güter einladen?
Du berechnest für jede "Kante" dh für jedes Gut und für jedes Paar an Städten zwischen denen dieses Gut gehandelt werden kannst die oben genannte Qualität. Das ist die Vorbereitung für den Wegfindungsalgorithmus und dauert nur genau so lange wie es Kanten gibt, also O(m).
So ergibt sich ein Graph von Städten als "Knoten" und Handelsgewinnen pro Zeit als Kanten.
Da man natürlich immer weiter handeln können will muss man zwingend mehrere Transaktionen aneinander Reihen die irgendwann wieder beim Start ankommen. Dh du brauchst einen geschlossenen Zyklus.

 

[Ochse]

@voon
Du hättest es noch ein wenig genauer formulieren können voon.
Kauft jede Stadt von jeder Ware beliebig viel auf und dann zu einem jeweils anderen Preis oder wie? Und ist alles überall verfügbar? Wann ist überhaupt Schluss; sobald das Benzin alle ist?

Das ganze Problem kommt mir schon bekannt, leider weiß ich im Moment nicht woher...

 

[Zweipunktnull]

Nicht nur können, sondern müssen. Bisher macht der Thread noch kaum Sinn, da jeder Poster wahrscheinlich ein anderes Problem im Kopf hat. Komplexität, NP-Vollständigkeit und letztlich auch Algorithmen sind mathematische Konzepte. Man kann unmöglich über die Komplexität eines Problems sprechen, ohne eine rigorose und hinreichend formale Definition des Problems zu haben.

Mir würden eine Menge Interpretationen des beschriebenen Problems einfallen, manche Interpretationen sind trivial lösbar, manche sind NP-schwer. Beispielsweise könnte man einfach einen Kreis im Graphen identifizieren, so dass man auf dem Kreis irgendeinen positiven "Profit" macht. Dann fahr ich einfach permanent im Kreis und mache unendlich viel "Profit". Ohne formale Definition des Problems werden wir hier nicht weit kommen.

Auf Basis der vagen Beschreibung würde ich aber schon mal vermuten, dass es nichts mit dem TSP zu tun hat. Da sind wohl einige auf das Schlüsselwort Handlungsreisender angesprungen. Beim TSP soll ja einfach ein kürzester Hamiltonkreis im Graph gefunden werden. Das hat auf den ersten Blick mal nichts mit hier dem Problem zu tun. Das Knappsack-Problem könnte schon eher eine Rolle spielen, aber da käme es halt darauf an, wie genau "das Ganze mit den Waren" laufen soll. Wie Ochse schon sagte, verkauft jede Stadt unendlich viel einer Ware, oder verkauft jede Stadt unterschiedliche und begrenzte Mengen? Wird potenziell unendlich viel angekauft? Auch ganz wichtig: Ist die Ware teilbar? Oder gibt es die Ware nur in diskreten "Blockgrößen"?

Das letzte ist vielleicht ein gutes Beispiel dafür, warum eine rigorose, formale Definition so wichtig ist: Erlaubt man im klassischen Knapsack-Problem, manche Objekte zu teilen, so erhält man das Continuous oder Fractional Knapsack Problem. Obwohl man relativ wenig an der Problemstellung geändert hat, ist das eine Problem extrem simpel (Continuous KP) und das andere NP-schwer (klassisches KP).

 

[voon]

Erstmal danke allen, die hier mitmachen. ich tu mich manchmal noch etwas schwer, alles zu verstehen, aber es ist spannend.

@voon
Du hättest es noch ein wenig genauer formulieren können voon.
Kauft jede Stadt von jeder Ware beliebig viel auf und dann zu einem jeweils anderen Preis oder wie? Und ist alles überall verfügbar? Wann ist überhaupt Schluss; sobald das Benzin alle ist?

Der Einfachheit halber: Jeder Ware wird in beliebigen Mengen gekauft und ist in beliebigen Mengen erhaeltlich. Aber jede Stadt bietet nur ein paar Typen Gueter an und kauft auch nur ein paar Gueter. Wieviele ... sagen wir mal je 3-5 Typen. Die Preise variieren zwischen den Staedte, zT drastisch.

Schluss ist nach einer gewissen Zeit .. zB 3 Stunden. Benzin gibts in jeder Stadt zum Einheitspreis.

 

[Ochse]

Schluss ist nach einer gewissen Zeit .. zB 3 Stunden. Benzin gibts in jeder Stadt zum Einheitspreis.

Nunja wenn man annimmt, dass der Benzinverbrauch zwischen zwei Städten proportional zu ihrer zeitlichen Entfernung ist und es keine direkte Verbindung zwischen zwei Städten gibt, die 'länger' als eine Tankfüllung ist, dann würde das Benzin praktisch keine Rolle spielen, denn in 3 Stunden hätte man immer gleich viel Benzin verbraucht egal wo man hinfährt. Falls man die Annahme aber weglässt (z.B. weil es Berge und Täler gibt, sodass der Verbrauch nicht allein von der Entfernung abhängt), wird es nochmal erheblich komplizierter

Noch ne Frage: Verbraucht der Aufenthalt/Handel in einer Stadt Zeit?

Kennst du das Spiel X3 Reunion? Darf man sich das Problem so vorstellen wie ein Universumshändler ohne Sprungantrieb?

 

[voon]

Stimmt, da fallen einem in Diskussionen Dinge auf, die gar keinen Einfluss mehr haben Danke. Ja, dann entspricht Benzin = Zeit momentan ... lassen wirs bei der Vereinfachung. Aufenthalt in der Stadt soll keine Rolle spielen, geht nur um die Fahrten.

X3 ... ja, ist mir bekannt ... das ist eigentlich ein ganz gutes Beispiel dafuer! Sprungantrieb ist ja auch nur eine definierte "Strasse" im Graphen? Ich geh davon aus, das man damit nicht jeden beliebigen Punkt anspringen kann, sondern auch einer definierten Anzahl Wege ausgesetzt ist.

 

[daemon777]

Angenommen es gibt n Städte und m Güter, weiterhin ist x der Einkaufspreis (mein Einkaufspreis) und y der Verkaufspreis . Dann setzen wir für jede Stadt x auf unendlich, falls sie das Gut nicht besitzt und y auf 0, falls sie das Gut nicht einkauft. Weiterhin habe ich den Graphen, der alle Städte miteinander verbindet und kann zwischen jedem 2-er Tupel aus Städten einen kürzesten Weg berechnen.
Dann kann ich mir auch für jedes 2er-Tupel aus Städten das Gut berechnen, das am meisten Profit für diesen Weg bringt. Hier wird kein Rucksackproblem benötigt, da ein Gut unendlich oft vorhanden und nur mein Laderaum begrenzt ist. Es gibt also eine triviale Lösung für das "Packproblem".
Kenne ich also Distanz und die optimale Ladung für diese Strecke, dann kann ich mir für jede Strecke das Optimum berechnen und im letzten Schritt ist max(Profit(ni, nj)) mit ni, nj sind Städte das gesuchte Optimum.

Das ist hier jetzt nur ein Greedy-Algorithmus für dieses Problem. Da ich aber davon ausgehe, dass die Pfade zwischen den Städten konstant ist, sowie in einer gegebenen Stadt der Einkaufs- bzw der Verkaufspreis immer gleich ist muss diese Berechnung lediglich einmal durchgeführt werden und dann hat man eben seine optimale Lösung.
Auf jeden Fall haben wir so schonmal ein Problem, das nicht mehr NP-vollständig ist (und schon gar keine 2 NP-vollständigen Probleme).

EDIT: Etwas zu schnell abgeschickt. Der Profit beim Rückweg muss natürlich mit berücksichtigt werden aber das ist auch eher eine kleine Anpassung.

EDIT2: Wieder etwas zu schnell gespostet. Wenn man natürlich einen optimalen Kreis sucht wird das Ganze wieder aufwendiger (wenn auch nicht NP-vollständig). Eine gute (aber nicht optimale) Lösung ist jedoch recht schnell gefunden.