Das Rundreiseproblem und seine Lösung mit dem A*-Algorithmus

Illustration

Problemformulierung

Den Grundstein für das A*-Verfahren legten bereits 1980 HART et al. In dem hier behandelten Beispiel wird es auf die Aufgabe der Bildung einer Rundreise angewendet. Das Problem kann durch einen bewerteten Digraphen repräsentiert werden, bei dem die zu besuchenden Orte den Knoten, die Strecken zwischen je zwei Orten den Kanten und die Länge dieser Strecken der Kantenbewertung entsprechen. Das Problem der Bestimmung einer Rundreise minimaler Länge bezeichnet man als Traveling-Salesman-Problem (TSP).

 

Applet-Seite

Zum Kollektorproblem wurde von uns ein Applet programmiert, mit dem Sie für ein Hochregallager selbst die einzusammelnden Objekte und damit die Orte der Rundreise bestimmen können. Nach Ausführen des A*-Algorithmus werden die Fächer im Lager entsprechend angefahren.

Da die Unterstützung für alle NPAPI-Plugins außer Flash im März 2017 von Mozilla (ab Firefox 52) eingestellt wurde und in der 64-Bit-Version von Firefox dieses Plugin auch nicht unterstützt wird, können die Applets in Firefox leider nicht mehr ausgeführt werden.

13.08.2021