Die Lösung des Rundreiseproblems
Problemformulierung
Ein in der OR-Literatur häufig beschriebenes Problem behandelt die Bildung einer Rundreise. Auch bei Domschke et al. (2015, S.130) ist zu lesen, dass man dabei die Vorstellung hat, dass ein Handelsreisender Kunden in einer bestimmten Anzahl von Städten besuchen muss und am Ende wieder zum Ausgangsort zurückkehren möchte. Das Problem kann durch einen bewerteten Graphen oder Digraphen repräsentiert werden, bei dem die zu besuchenden Orte den Knoten, die Strecken zwischen je zwei Orten den Kanten (bzw. Pfeilen) und die Länge dieser Strecken der Kanten- bzw. Pfeilbewertung entsprechen. Das Problem der Bestimmung einer Rundreise minimaler Länge bezeichnet man als Traveling-Salesman-Problem (TSP).
Domschke, W., A. Drexl, R. Klein und A. Scholl: Einführung in Operations Research (9. Aufl., Springer Gabler, 2015).
JavaScript-Applikation zum Verfahren »Nächster Nachbar« und »A*«
Zum Drillingproblem wurde von uns eine JS-Applikation programmiert, mit der Sie für ein (konfigurierbares) Werkstück nachvollziehen können, wie die Verfahren »Nächster Nachbar« und »A*« die Route anzufahrender Bohrlöcher generieren.
Applet-Seite zum A*-Algorithmus
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.
