Ist das Handlungsreisenden-Problem praxisrelevant?

Nun kann man natürlich kritisch anführen, dass Handlungsreisende in den Zeiten des Internet-Vertriebs rar geworden sind. Aber ist es wirklich so, dass das Beispiel lediglich von akademischem Wert ist?

Bei der Chip-Produktion müssen Hunderttausende von Arbeitsgängen an den einzelnen Chips von Automaten vollzogen werden. Beim Positionswechsel des Automaten muss eine Strecke überwunden werden, die durchaus einen gewissen Zeitbedarf erfordert. Gelingt es, die Positionswechsel auf Grundlage einer kürzesten Route zu vollziehen, so wird dadurch die Produktionsdauer pro Stück minimiert. Bei den hohen Fixkosten der Chip-Produktion und den immensen Stückzahlen, die auf einer Anlage produziert werden, können dabei schnell sehr hohe Einsparungen realisiert werden.

Schleifmittelproduktion

Ähnliche Voraussetzungen finden sich bei der Produktion von Schleifmitteln. Nun ist es nicht so, dass ein Roboter die einzelnen Körner auf dem Schleifpapier ablegt und dabei eine kürzeste Route wählen sollte. Vielmehr vollzieht sich die Produktion wie folgt: Zunächst wird eine Textilie in lange Streifen geschnitten und in ein Fließsystem eingespannt. Anschließend wird ein Klebstoff aufgetragen, so dass ein Sieb passiert werden kann, woraus die Schleifkörner auf den Grund rieseln und durch den Klebstoff fixiert werden. Beim Wechsel von Schleifmittel der einen Körnung auf eine andere müssen die Maschinen gereinigt werden (Umrüsten). Wurde nun zunächst ein Schleifmittel mit feiner Körnung gefertigt und es soll jetzt eines mit grober Körnung folgen, so muss der Kessel mit den Schleifkörnern nicht so ausgiebig gereinigt werden. Anders verhält es sich bei einer umgekehrten Fertigungsfolge. Fällt nur ein grobes Korn auf den Grund, so wird das Schleifmittel später bei seiner Anwendung Kratzer hinterlassen. Da die Umrüstungen mitunter mehrere Stunden erfordern können, ist sofort ersichtlich, dass sich durch eine günstige Fertigungsfolge Kosten einsparen lassen.

Ersetzt man nun Orte durch unterschiedliche Schleifmittel-Aufträge und Entfernungen durch Umrüstzeiten, so findet sich hier unser Handlungsreisenden-Problem.

Entsprechende Problemstellungen finden sich in der Zigarettenproduktion, wo die Tabaksorten mit unterschiedlicher Schwere und unterschiedlichem Parfümierungsgrad erheblichen Reinigungsaufwand der Anlagen bedingen, und beim Lackieren in der Automobilindustrie. Dort erfordert der Wechsel von schwarzen auf weiße Autos einen größeren Umrüstaufwand als anders herum.

Andere Optimierungsprobleme

Das Handlungsreisenden-Problem und seine erläuterten Abarten stellen lediglich ein Anwendungsbeispiel für den Ameisenalgorithmus dar. Prinzipiell lässt sich ein Ameisenalgorithmus auf jedes kombinatorische Optimierungsproblem übertragen. Weitere Beispiele, in denen wir den Ameisenalgorithmus erfolgreich eingesetzt haben, sind etwa die Abstimmung von Fließbändern und das optimale Verstauen von Paketen in Containern.