Evolutionäre Metaheuristiken als Problemlösungsmethoden für kombinatorische Optimierungsprobleme - dargestellt am Beispiel des Standardproblems der Tourenplanung mit Zeitfensterrestriktionen

Metaheuristiken stellen approximative Problemlösungsmethoden dar, mit denen sich komplexe kombinatorische Optimierungsprobleme effektiv lösen lassen. Im folgenden Beitrag wird aufgezeigt, wie Evolutionsstrategien als evolutionäre Metaheuristiken konzipiert werden können. Dies geschieht am Beispiel des Standardproblems der Tourenplanung mit Zeitfensterrestriktionen. Konkret werden zwei Evolutionsstrategien entwickelt. Ihr Ziel ist die Berechnung eines optimalen Tourenplans, der die vollständige Bedienung der Kunden ermöglicht und die Problemrestriktionen − insbesondere die Zeitfensterrestriktionen − erfüllt. Die Zielfunktion besteht aus der Kombination der Minimierung der Fahrzeuganzahl (primäres Zielkriterium) und der Minimierung der Gesamtentfernung (sekundäres Zielkriterium). Die beiden entwickelten Evolutionsstrategien werden anhand von 58 Problembeispielen aus der Literatur gestest. Die Problemgrößen varieren von 100 bis 417 Kunden und von 2 bis 58 Fahrzeugen. Die berechneten besten Lösungen deuten darauf hin, daß Evolutionsstrategien geeignet sind, sowohl die Fahrzeuganzahl als auch die Gesamtentfernung zu minimieren.