Auf was Mathematik-Studenten aber auch so alles kommen: Die kürzeste Route in einem S-Bahnnetz, um alle Stationen anzufahren.

http://www.morgenpost.de/berlin-aktuell/...Stunden-ab.html

TSP - Travelling Salesman Problem. Eine altbekannte Aufgabe, die heutzutage am besten mit einem genetischen Algorithmus zu lösen ist. Genetische Algorithmen wurden erstmals in der Nachkriegszeit bekannt und haben erst seit den 70er und 80er Jahren Eingang in die Lösung praktischer Probleme erhalten. Genetische Algorithmen lösen Aufgaben, die zuvor als unlösbar oder nur mit riesigem Rechenaufwand als lösbar galten. Das Schöne an genetischen Algorithmen ist, dass sie schon sehr bald eine tatsächlich gangbare Lösung liefern, nicht unbedingt die optimale, aber ein Lösung, die zum Ziel führt. Um bessere Lösungen zu erhalten, muss man nur weiterrechnen lassen, irgendwann gibts keine besseren Lösungen mehr, dann hat man quasi optimiert. Optimierungslösungen auf Basis von Matrizen ('Lineare Optimierung') zielen nur auf das optimale Ergebnis (einen der Eckpunkte einer multidimensionalen Fläche) und können zuvor nicht abgebrochen werden, man lässt einenComputer daran oft tagelang rechnen, obwohl ein, wenn auch durchaus suboptiomales Ergebnis bereits nach wenigen Minuten nötig wäre, zB das übliche Fabriksteuerungsproblem.

schön. danke für die zusammenfaselung.

nein, spaß beiseite, hast du sehr anschaulich und einprägsam dargestellt.

es gibt jede menge software, die genau diese thematik für unternehmen mit großem außendienst bzw. werksverkehr löst.

in der praxis habe ich in stark abgeschwächter form bei ebay-abholfahrten ein ähnliches thema zu beantworten. da es aber meistens nur um maximal vier abholpunkte geht, ergibt sich die lösung bei einem blick auf die karte meist von alleine.