Durchschnittliche Entfernung & optimale Route

[Sven (Gast)]

Hallo,
wir suchen eine Software (oder Online-Tool) welches ermöglicht die 
durchschnittliche Entfernung & optimale Fahrstrecke zwischen mehreren 
Standorten (aktuell 1.134 Stück) zu bestimmen. Kann jemand helfen?
Danke

[Niklas G. (erlkoenig)]

Bei 1134 Standorten hast du 1134! Routen, also ca.

$$2.3 * 10^{2973}$$

Routen. Wenn das Berechnen jeder Route 1 Nanosekunde dauert, dauert das 
Berechnen aller Routen

$$7.5 * 10^{2959}$$

Jahre. Das ist

$$5.4 * 10^{2949}$$

mal so lange, wie das Alter des Universums.

[der Toni (Gast)]

in der Mathematik ist das ein recht großes Thema, nennt sich "Problem 
des Handlungsreisenden"
https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden

Vorweg: es gibt bei willkürlich, unsymmetrischen Zwischen- und 
Zielpunkten keine perfekte Lösung, nur Annäherungen an das Ideal.
Die Schlussfolgerung ist, dass die Komplexität des Problems mit 
zunehmender Zahl an Zwischenstopps exponentiell zunimmt.

Meine Vermutung bei 1200 Stopps: Male es auf einer Karte auf und schaue 
mit "menschlicher Intuition" nach einer geeigneten Route - eine KI ist 
da (vom Zeitaufwand her betrachtet) dem menschlichen Logikverständnis 
maßlos unterlegen...

[Niklas G. (erlkoenig)]

Ich bin übrigens blöd, ist ist natürlich die Summe und nicht das 
Produkt, d.h. lediglich 642411 Routen. Ich brauch erstmal nen Tee.

der Toni schrieb:
> in der Mathematik ist das ein recht großes Thema, nennt sich "Problem
> des Handlungsreisenden"

Wenn man eine Route durch alle Punkte will, ich war jetzt von allen 
Routen zwischen allen Standorten ausgegangen

[Georg (Gast)]

Sven schrieb:
> durchschnittliche Entfernung & optimale Fahrstrecke

Nur so nebenbei: das sind zwei ganz verschiedene Fragen, selbst wenn ihr 
die optimale Route finden könntet (was erwiesenermassen in akzeptabler 
Zeit unmöglich ist) sagt das nichts über die durchschnittliche 
Entfernung aus - die Entfernung zu einem anderen Standort ist ja i.A. 
kein Bestandteil der optimalen Route. Wobei sich die Frage erhebt, was 
ihr überhaupt unter "durchschnittlicher" Entfernung versteht. 
Mathematisch korrekte Begriffe sind wohl nicht so euer Ding.

Am besten beschäftigt ihr euch die nächsten Monate oder Jahre mit dem 
Problem des Handelsreisenden, da gibt es Unmegen Literatur, und mit 
Näherungsmethoden, die keine optimale, aber ausreichend gute Lösungen 
liefern. Reicht euch das nicht könnt ihr das ganze sofort aufgeben.

Georg

[Gunnar F. (gufi36)]

Sven schrieb:
> optimale Fahrstrecke

definiere optimal!

[Rüdiger B. (rbruns)]

Map und Guide konnte das damals, ob es heute noch ein Produkt gibt weiss 
ich nicht.

[der Toni (Gast)]

Gunnar F. schrieb:
> definiere optimal!


Optimal wäre in der Logistbranche wohl der kürzeste Weg in Km auf alle 
1134 Wegpunkte verteilt, wobei nur der jeweils kürzeste Weg vom Wegpunkt 
zur Autobahn eben nicht Autobahn sein darf...

Zusatzquest: Eine Software welche die Touren der vorhandenen 100 LKWs 
und die zu bewegenden 10.000 Pakete zwischen den 1134 Wegpunkten 
selbstständig plant und verteilt. Wäre wohl ein Millionengeschäft....

[Gunnar F. (gufi36)]

der Toni schrieb:
> Wäre wohl ein Millionengeschäft....

dann bist du ja quasi schon steinreich?

[Dago (Gast)]

Niklas G. schrieb:
> 642411

wie kommst du auf die Zahl? Laut meiner Berechnung sollten 486.090.990 
Routen existieren

[Dago (Gast)]

Dago schrieb:
> Niklas G. schrieb:
>> 642411
>
> wie kommst du auf die Zahl? Laut meiner Berechnung sollten 486.090.990
> Routen existieren

sorry, Denkfehler. 642411 stimmtnatürlich

[Niklas G. (erlkoenig)]

Dago schrieb:
> wie kommst du auf die Zahl

$$\sum_{k=1}^{1133}k=\frac{1133*1134}{2}=642411$$

Es sei denn ich habe wieder gepennt 🤔