sehr gute Programmidee mit großem Potenzial

[samuel7]

Interessante Möglichkeit, Piktogramm, werde es auf jeden Fall speichern. Dankesehr ;-)

 

[kisser]

Was genau aus deinen eher wirren Ausführungen kann die von Speditionen eingesetzte Software nicht? Preise berechnen?

 

[samuel7]

Was genau aus deinen eher wirren Ausführungen kann die von Speditionen eingesetzte Software nicht? Preise berechnen?

haha sorry, habs nicht so mit schriftlichen Erklärungen, deshalb mach ich auch nie schriftlich Schluss :-P .
Ich möchte es aber nicht nochmal reinschreiben, habs gerade erst rausgenommen.

 

[gaunt]

Ich kann mir schon denken warums die Software nicht gibt. Optimierungsaufgaben sind extrem aufwändig deterministisch zu berechnen. Ein neuronales Netz wie ein Menchliches Gehirn kann das dagegen rel. gut.
Wenn ichs richtig verstehe willst du viele Transportaufträge eingeben, und die Software errechnet dir die optimale Betsückung der LKW und deren Routen.

Aber das ist eine erweiterung des TSP. Ähnlich verhält es sich mit Stundenplänen von Schulen, Rüstzeiten in Maschinenparks...
Die haben alle das selbe Problem. Es gibt übrigens einen Preis im Milionenhöhe für denjenigen der das TSP deterministisch löst.

Ein "guter" Plan, und wenn dus hinbekommst bist du unter garantie vielfacher Millionär. Das dumme ist nur: Tausende von Mathematikern und Informatikern arbeiten schon drann und bekommen es nicht hin.

Das Problem: Was dir einfach erscheint ist für einen Computer nahezu unmöglich zu berechenen. Es gibt für solche Aufgaben keinen Algorithmus der das Ergebnis wirklich optimal lösen kann. Also werden verschiedene Ansätze (Threshold, Simulated annealing, KI, Genetische Algorithmen...) verwendet um näherungsweise heranzu kommen. Ansonsten geht nur Try & Error. Und bei entsprechender Anzahl an Variablen... Vergiss es.

 

[titanskin]

Aber das ist eine erweiterung des TSP. Ähnlich verhält es sich mit Stundenplänen von Schulen, Rüstzeiten in Maschinenparks...
Die haben alle das selbe Problem. Es gibt übrigens einen Preis im Milionenhöhe für denjenigen der das TSP deterministisch löst.

Um es genauer zu sagen: das TSP ist NP-vollständig. Wer es deterministisch in polynomialzeit löst, hat das entscheidende Problem der theoretischen Informatik gelöst. Nur zum Glück ist man sich in der Fachwelt fast einig: P != NP.

Es gibt nicht nur diese Zwecke: In der Verschlüsslung wird es auch manchmal verwendet.

Entschuldige "die Verbesserung". Ich wollte nur die Tragweite etwas erhöhen.

Achso es gibt Löser für das TSP. Sie verwenden erschöpfende Suche etc.. Ein Verfahren, das theoretisch gar nicht so schwer ist, ist Branch&Bound, oder Branch&Cut. Diese finden meist in wenigen Minuten eine sehr gute Lösung. (aber können nicht zeigen, dass sie perfekt ist)

 

[gaunt]

Da der Threadersteller offensichtlich kein Informatiker ist wollte ich mich mit Fachbegriffen zurückhalten.

Aber so als Hinweis an was du dich da drann wagst:
Das ganze Zählt zu den Millenium Problemen!
http://de.wikipedia.org/wiki/Millennium-Probleme
Von denen ist bis dato nur eins gelöst wurde und bei einem weiteren hat ein Kasache (oder sonst was ab von Schuss) einen Lösungsvorschlag eingereicht, der aber noch nicht geprüft ist.


Aber von dem ganzen mal abgesehen:
Weiche Algorithmen die Näherungslösungen ermittlen sind in der Praxis oftmals garnicht schlecht!

 

[Daaron]

Wir reden hier doch von Routenfindung... Da fällt mir doch spontan Dijkstra ein. Wenn das Ding bei Netzwerkknoten funktioniert, dann auch bei Straßen.

 

[gaunt]

Dijkstra und Abwandlungen sind bereits die Standard Routing Algorithmen für Navis (Soweit ich weiß).
Was du hier aber beachten müsstest:
1. Die Summe aller anzufahrenden Orte (standard TSP)
2. Die Anzahl der zur Verfügung stehenden LKW ist variabel
3. Die Bestückung der LKW muss ermittelt werden

Auf das TSP setzt du zwei weitere Fragestellungen auf welche wiederum ähnlich komplex sind. Auch mit weichen Algorithmen ist das nicht ohne. Denn ob du mehr oder weniger LKW einsetzt verändert sowohl die Routen als auch die Bestückung der LKW. In jeder Optimierungsrunde für eines der drei Elemente müsstest du also wieder alle Optimierungen der anderen beiden durchführen. Danach beginnt das spiel von vorne. Bestimmt machbar, aber zum einen Aufwändig und es wird definitiv nicht die Optimale Lösung ermittelt werden können.
Das dumme ist: Jetzt kommt ein Menschliches Gehirn daher und schaut sich die Lösung an. Mit hoher Wahrscheinlichkeit wird ein erfahrener Speditionsplaner sich den Plan ansehen und weiter Optimierungen erkennen. Für den Informatiker vorhersehbar und OK, für den BWL'er ist damit aber die gesamt Lösung kompromitiert.

 

[Grantig]

Wenn ich mir das hier durchlese...

Ich weiß nicht, ob ich die Frage richtig verstehe, tatsächlicherweise geht das so vonstatten:
-> Der User gibt PLZ "A" bis "B" nach "C" bis "D" ein. zB PLZ D-20*** - D-29*** nach IT-60*** bis IT-80*** und es werden alle Relationen berechnet.
In diesem Fall wäre das A nach C, A nach D, B nach C und B nach D

...würde ich auch sagen, dass es sich hier nicht um ein traveling salesman problem handelt.
Er will ja keine Rundreise planen, sondern nur den optimalen Weg von A nach B, wobei A und B variabel sind.
Für n verschiedene A und m verschiedene B müsste man also nur n * m Routen berechnen.

Edit: wobei - beim 2. mal lesen könnte es auch anders gemeint sein, evtl. irre ich mich bzw. habe die Aussage da falsch interpretiert
Edit2: nach dem 3. mal lesen bin ich doch der Meinung, dass ich die Aussage beim 1. mal lesen richtig verstanden habe xD

Es würde mich aber wundern, wenn tatsächlich keine Software existiert die dieses Problem angeht, bzw. wenn die Problemstellung tatsächlich so simpel wäre.

Dijkstra und Abwandlungen sind bereits die Standard Routing Algorithmen für Navis (Soweit ich weiß).

Nicht A-Star? Darauf hätte ich jetzt spontan getippt.
Ist der verallgemeinerte Dijkstra + Heuristik.

 

[Daaron]

Eben, ich versteh das Problem so wie Grantig:
Du hast n Startpunkte und m Ziele. Für jede n:m-Verbindung ermittelst du über einen brauchbaren Routing-Algorithmus die optimale Strecke. Da ein Logistikunternehmen eine recht begrenzte Anzahl Lager hat, von denen aus Lieferungen abgehen bzw. zu denen Lieferungen erfolgen, ist einer der beiden Faktoren also arg begrenzt. Gerade wenn man den Mittelstand als Zielgruppe ansieht reden wir hier vielleicht von einem Dutzend Startpunkte.

Ich habe, außer bei lokalen Kurierfahrern, noch nie erlebt, dass Traveling Salesman wirklich zur Anwendung kommt. Und selbst bei denen kommen ganz andere Optimierungen zum Tragen. Die Mythbusters hatten dazu mal ne interessante Folge: Warum fahren Kurierdienste in San Francisco immer nur rechts herum?
Tatsächlich war eine Route, bei der nie nach links abgebogen wird, zwar etwas länger, dafür signifikant schneller abgearbeitet. Es widerspricht allen offensichtlichen Ansichten, dass 3x rechts rum tatsächlich besser als 1x links rum ist.

 

[gaunt]

@grantig
ist doch wurscht obs im Kreis geht oder von A nach B. Entscheidend ist das es vermutlich mehr als 2-3 Zwischenstationen gibt und die sind vermutlich auch nicht schön hintereinander gelegt sondern wirr über ein Gebiet verteilt. Und vermutlich exitiert auch nicht nur ein Fahrzeug sondern mehrere. Und jetzt kommt dazu das die Stationen nicht an den Fahrzeugen sondern den Waren liegen.

Es würde mich aber wundern, wenn tatsächlich keine Software existiert die dieses Problem angeht, bzw. wenn die Problemstellung tatsächlich so simpel wäre.

Versucht man ja auch. Aber ich könnte mir gut vorstellen das man die Entwicklung der Software vereinfacht indem man einen Speditionskauf z.B. die Stationen und die Fahrzeuge vorgeben lässt. Das reduziert die Komplexität enorm.

Ich sage ja auch nicht das es nicht möglich ist. Über weiche Algorithmen (welche auch immer) geht das bestimmt. Aber die Berechnung dürfte dennoch aufwändig sein. Optimiere nur mal Stationen und LKW und frage dafür die Routen bei Google ab. Als kommerzieller Nutzer und entsprechend vielen Abfragen wird das richtig teuer!
Man kann hier bestimmt viel optimieren. Aber das ist nix für ein kleines Projekt was man mal eben nebenbei nach der Arbeit macht. Das richt nach richtig Arbeit!

Warum fahren Kurierdienste in San Francisco immer nur rechts herum?

Das liegt aber nur daran dass man sich im stark befahrenen SF das Linksabbiegen und damit das queren des Gegegnverkehrs spart.

Du hast n Startpunkte und m Ziele.

Jein. Du hast eine überschaubare Anzahl an Startpunkten, aber viele Zielpunkte. Und die wiederum kannst du von verschiedenen Punkten aus anfahren und auch die gesamtzahl der Routen ist variabel. Z.B. kann ein LKW weiter fahren und eine weitere Station anfahren, dafür sparst du dir aber vielleicht eine komplette LKW Tour von einem anderen Lager aus.

Nicht A-Star? Darauf hätte ich jetzt spontan getippt.
Ist der verallgemeinerte Dijkstra + Heuristik.

Ist doch eine Abwadnlung von Dijkstra oder?

 

[Daaron]

Ohne ein paar klare Anwendungsbeispiele spielen wir hier nur Rätselraten.
Eine lokal agierende Möbelkette wird z.B. sehr wohl nur eine Lieferung in einen Transport packen. Eine DHL-Tour hingegen hat x-wieviele Zwischenstationen, ausgehend vom zentralen Verteilerpunkt.

 

[Grantig]

Entscheidend ist das es vermutlich mehr als 2-3 Zwischenstationen gibt und die sind vermutlich auch nicht schön hintereinander gelegt sondern wirr über ein Gebiet verteilt. Und vermutlich exitiert auch nicht nur ein Fahrzeug sondern mehrere. Und jetzt kommt dazu das die Stationen nicht an den Fahrzeugen sondern den Waren liegen.

So wies der TE schreibt ist das imho nicht der Fall.
Deswegen habe ich ja geschrieben:

Es würde mich aber wundern, [...] wenn die Problemstellung tatsächlich so simpel wäre.

Wahrscheinlich hat der TE das Proble einfach nur zu sehr vereinfacht dargestellt und du hast recht damit, dass er eigentlich doch ein TSP meint. Ohne weitere Infos vom TE artet das jetzt in Spekulation aus.

Ist doch eine Abwadnlung von Dijkstra oder?

Ja klar ist es das - meine Frage war dämlich gestellt.
Worauf ich eigentlich hinaus wollte war, welche Abwandlungen von Dijkstra denn genau gemeint sind und wo ich evtl. was darüber nachlesen kann. (am besten speziell auf den Straßenverkehr bezogen).
Würd mich grad brennend interessieren.

 

[gaunt]

Würd mich grad brennend interessieren.

Wenn dich Routing interessiert und du Java kannst dann schau dir doch mal das OSMAnd Projekt an. Ist eine Android Routing Software welche auf Open Streetmap Vector Karten basiert und da eine echte Offline Navigation möglich ist muss auch der Routing Algorithmus implementiert sein. Aus eigener Erfahrung kann ich sagen das er recht ordentlich funktioniert. Und wie der Name schon vermuten lässt ist es Open Source:
http://code.google.com/p/osmand/


Wie ihr schon sagt. Muss der Starter der Diskussion was dazu sagen...

 

[Grantig]

Vielen Dank ich schaus mir mal an.

 

[maxwell-cs]

Entschuldige "die Verbesserung". Ich wollte nur die Tragweite etwas erhöhen.

Achso es gibt Löser für das TSP. Sie verwenden erschöpfende Suche etc.. Ein Verfahren, das theoretisch gar nicht so schwer ist, ist Branch&Bound, oder Branch&Cut. Diese finden meist in wenigen Minuten eine sehr gute Lösung. (aber können nicht zeigen, dass sie perfekt ist)

natürlich können b&b/b&c-basierte verfahren optimalität beweisen. das zeichnet sie ja erst überhaupt als exakte verfahren aus. eine hauptanwendung von b&c beim tsp besteht darin, die optimalität von gegebenen touren, die in der regel von heuristiken gefunden werden, zu verifizieren.

 

[asdfman]

Wenn ein offensichtlicher Amateur mit "habe eine bahnbrechende Idee" ankommt und sich schon seinen baldigen Reichtum ausrechnet, habe ich wenig Vertrauen in beides.
Ein wenig Bescheidenheit und realistische Selbsteinschätzung kann hier nur förderlich sein. Kennste die Geschichte mit dem Milchmädchen?

 

[gaunt]

Hm, ein bisschen Naivität und Mut braucht man aber auch um sich an so Themen herann zu trauen.
Ich sage ja auch nicht dass es unmöglich ist eine solche Software zu schreiben. Nur ist es eben nicht in nem Nachmittag gemacht. Wenn der Bedarf bei den Speditionen aber da ist kann sich eine Investition evtl. doch lohnen.
Ist doch oft so. Ein Brachenkenner erkennt eine Bedarf und sucht nach einer Lösung. Was er jetzt machen muss ist den Aufwand genau zu schätzen und den zu erwarteneden Umsätzen gegenüber zu stellen. Weißt der BC einen Gewinn aus kann man sich überlegen ob man die nicht unerheblichen Risiken eingeht.
Vielleicht haben die Hersteller der Speditionssoftware wenig Know How im Bereich weicher Algorithmen und sich deshalb nie rann getraut. Kann schon sein dass sich hier eine Geschäftsidde versteckt. Aber wie gesagt: Das kann nur ein Bracheninsider wisssen.

Wenn ich eine Zahl in den Raum werfen müsste... vielleicht zwei PJ. Also ~500PT (Könnte auch weniger sein). Legt man für einen guten normalen Coder 600€ zugrunde und für einen Experten für weiche Algorithmen 1200€ (je 50/50) käme man auf ~500k€. Dazu ~100PT Projektmanagement mit 1000€ 100k€ und 50PT a 700€ fürs initiale Anforderungsmanagement also 35000€.
Stehen unterm Strich 635k€.
Da kämen evtl. noch Kosten für die Kartenzulieferer hinzu und auch juritischer Support für die Vertragsgestaltungen. Sollte aber im Rahmen bleiben.

 

[titanskin]

natürlich können b&b/b&c-basierte verfahren optimalität beweisen. das zeichnet sie ja erst überhaupt als exakte verfahren aus. eine hauptanwendung von b&c beim tsp besteht darin, die optimalität von gegebenen touren, die in der regel von heuristiken gefunden werden, zu verifizieren.

Danke deiner Verbesserung . Ich habe manches etwas schwammig dargestellt.

1. B&B/B&C laufen häufig, wenn man den ganzen Suchraum abgeht, sehr lange bei großen Probleminstanzen.
2. Man kann, während das Problem durchläuft, auch schon die bisher gefundene Optimallösung betrachtet werden. Natürlich ist dann die Lösung noch nicht verifiziert optimal, kann aber ein gutes Maß sein.

Zu Heuristiken: eine Verifizierung einer Lösung aus einer Heuristik ist sinnlos, so könnte man auch gleich das "Ungetüm" starten und hätte wenn nur theoretischen Wert (Abschätzung über die Güte), oder man würde sehen, dass diese nicht optimal ist und dann die neue Lösung nehmen. Daraus schließe ich: Wenn würde ich die Lösung als neuen Start-Wert nehmen ;-).

@maxwell-cs: genügt dir jetzt die Aussage?

 

[samuel7]

Wenn ein offensichtlicher Amateur mit "habe eine bahnbrechende Idee" ankommt und sich schon seinen baldigen Reichtum ausrechnet, habe ich wenig Vertrauen in beides.
Ein wenig Bescheidenheit und realistische Selbsteinschätzung kann hier nur förderlich sein. Kennste die Geschichte mit dem Milchmädchen?

Hi asdfman, danke für deinen recht sinnfreien Kommentar (ich frage mich, in welchem Bereich ich ein Amateur bin? Ich glaube ja nicht sowas selber programmieren zu können? In meiner Branche bin ich bei Weitem kein Amateur ;-) ) , wenn wir alle so denken würden, wäre die Menschheit nicht da, wo sie heute ist, und gute Programmierer brauchen glaube ich auch etwas Wagemut und sehr viel Kreativität, um sensationelle Programme zu schaffen. Um Reichtum geht's da nicht ((was soll ich denn bitte mit so viel Geld privat??)), sondern darum, dass eine Lösung für das Problem eine Riesenerleichterung wäre! Das Rechenbeispiel war als Veranschaulichung, dass sich eine mögliche sehr hohe Investition auch rechnen könnte - und wie Gaunt (danke Gaunt für deine intelligente Antwort) gesagt hat, wenn man Kosten mit Risiko gegenüber möglichem Gewinn vergleicht, könnte es sich ja rentieren. Du glaubst hoffentlich nicht, ich komme in ein Forum und bitte um Hilfe, weil ich glaube ich bin morgen Milliardär? Aaaber, ich weiß, Querdenker wurden immer als Lächerlich hingestellt, bis es dann doch funktionierte... und an euch Querdenker richtete ich meine Fragen und ich bedanke mich für die hilfreichen Postings!!!

Ich habe mitverfolgt was Ihr diskutiert habt über mögliche Lösungen, und beim besten Willen, ich versteh nur Bahnhof, ihr seid richtige Profis, darum weiß ich auch, dass ich hier richtig bin. Das Konzept wird in den nächsten paar Wochen intensiv ausgearbeitet und ich werde es dann mehreren Programmierfirmen präsentieren. Wenn ihr wollt, kann ich euch dann mitteilen, was sich diese dabei gedacht haben, wie man das lösen kann, inkl. Entwicklerzeit und Kosten.

Ich schreibe Euch jetzt einfach einmal, was ich mir gedacht habe, wegen den optimalen Routen, sagt mir einfach, warum das nicht programmierbar ist.

Ich möchte folgende Routenpreise in 1 Schritt mit dem möglichen Programm berechnen:

München -> Asti (PLZ IT-14)
München -> Alessandria (PLZ IT-15)
München -> Genova (PLZ IT-16)
.

1. Das Programm greift wie ein normaler Routenplaner auf die Map zu und berechnet mögliche Routen.
-> mögliche Routen: Schnellste Route ohne Mautstraßen | Schnellste mögliche Route | Schnellste Route Schweiz vermeiden | ..
-> Mit oder ohne Mautraßen muss der Benutzer im Vorhinein festlegen, dh. es berechnet in diesem Fall 1 bzw 2 verschiedene Routen

2. Das Programm vergleicht die 1 oder 2 Möglichkeiten und nimmt die km der günstigeren Variante als Berechnungsgrundlage
-> Schnellste Route Schweiz KM + 235 = Wert A ; Schnellste Route Schweiz vermeiden KM = Wert B
-> (If-variable?) Wert A > Wert B == Ausgabewert ist Wert B, sonst Ausgabewert ist Wert A
-> Wert x + Aufschlag y = Ergebnis z

3. Das Programm speichert Ergebnis z in Zelle München-> Asti (und gibt es wenn gewünscht in eine Tabelle aus)


Denke ich da zu einfach ?

ps: es freut mich dass so eine Fachdiskussion entstanden ist, dann ist das Ganze wenistens für mehrere lernreich