OR-Labor

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

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.
Der A*-Algorithmus wird im multimedialen Lehrprogramm »Intelligente Strategien in Theorie und Praxis« mit weiteren Anwendungsmöglichkeiten behandelt.