Bin Postbote. Wie lässt sich der für mich effektivste Weg berechnen?
Wie oben gesagt, bin ich Postbote. Ich versuche natürlich, immer den effektivsten Weg zu laufen (was nicht immer der kürzeste sein muss ...). D. h., ich drehe, wenn möglich, Kreise oder Achten. Leider aber bleiben dabei einige Straßen auf der Strecke, weil sie nicht in dieses Schema reinpassen. Wie schaffe ich es, möglichst alle Straßen auf möglichst effektive Weise abzudecken?
12 Antworten
Aus Wikipedia
Das Problem des Handlungsreisenden (auch Rundreiseproblem, engl. Traveling Salesman Problem oder Traveling Salesperson Problem kurz TSP) ist ein kombinatorisches Optimierungsproblem des Operations Research und der theoretischen Informatik. Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die gesamte Reisestrecke des Handlungsreisenden nach der Rückkehr zum Ausgangsort möglichst kurz ist.
Seit seiner ersten Erwähnung als mathematisches Problem im Jahre 1930 haben sich viele Forscher damit befasst und neue Optimierungsverfahren daran entwickelt und erprobt, die momentan auch für andere Optimierungsprobleme eingesetzt werden. Heute steht eine Vielzahl von heuristischen und exakten Methoden zur Verfügung, mit denen auch schwierige Fälle mit mehreren tausend Städten optimal gelöst wurden.
Vermutlich willst du eine effiziente Lösung und keine effektive.
Da wir ja nicht den Bereich kennen, in dem zu zustellst, kann man kaum einen Rat geben. Es ist ja sicher ein Unterschied ob man z. B.im Stadtkern (mit geschlossener Blockrandbebauung) oder in einer zersiedelten ländlichen Gegend die Post zustellt.
Den effizientesten Weg durch (höhere) Mathematik zu finden, ist sicher schwieriger als durch ausprobieren.
Ich würde dir Google-Earth empfehlen, damit du die Tour gemütlich zuhause planen kannst. Bei Google-Earth gibt es in der Titelleiste ein Lineal. Eine Zusatzfunktion zum Lineal ist der "Pfad". Damit kannst du auf den Satellitenbildern deines Zustellbezirks Touren zeichnen. Die Länge des Weges wird dir auf Wunsch zentimetergenau angezeigt.
Du könntest solange rumprobieren, bis du das Optimum gefunden hast.
Na, da hast du dir was vorgenommen...
Dazu empfehle ich den Link in der Antwort von derBeobachter.
Ich glaub' dafür muss man erst studieren. ;-)
Du bekommst den Weg doch vorgeschrieben, oder???
Am besten du schaust bei GoogelMaps rein, gibst dort dein Zustellbezirk ein und arbeitest so die Strecke durch wie es für dich am günstigsten ist und auch keine Straßen vergessen werden können. Mach dir eine Art Karte dazu und trag dir deine Route die du gehen möchtest in Pfeilrichtung ein. Ich hab es damals so beim Zeitungaustragen von verschiedenen Bezirken gemacht. (Bsp. Bei einem Kreis mit Seitenstraße, den Kreis auf einer Seite beginnen, in die Seitenstraße rein und eine Seite rauf, die andre Seite auf dem Rückweg zum Kreis erledigen. Den Kreis im Rundgang abarbeiten.)
Versuch mal alle Wege, die dir gut erscheinen, achte auf die Zeit und nehme dann den, der am schnellsten ging :)
Entschuldige :) Aber effektiv bedeutet für mich auch Zeit sparend ^^ Wünsche viel Erfolg bei der Suche nach einer guten Lösung :)
Ja, aber das muss sich doch auch mathematisch lösen lassen!?