K�rzeste-Wege- und Rundreiseprobleme stellen typische Probleme mit breiten Anwendungsspektren in der Praxis dar. Einige Probleme liegen in der Komplexit�tsklasse P und k�nnen effizient in angemessener Zeit durch bekannte Algorithmen gel�st werden. Andere, meist NP-vollst�ndige, Problemstellungen erweisen sich als schwieriger, weshalb heuristische Verfahren wie Ant Colony Optimization [Dor02] zur Ermittlung approximativer L�sungen verwendet werden.

Es gibt einige Probleme, die bei Anwendung einer unikriteriellen Zielfunktion der Komplexit�tsklasse P zugeordnet werden k�nnen. Die mehrkriterielle Variante des Problems ist allerdings NP-vollst�ndig. Wir verwenden beispielhaft das mehrkriterielle K�rzeste-Wege-Problem in gerichteten, zyklenfreien Graphen. Die unikriterielle Variante dieses Problems geh�rt zu den Problemen in der Komplexit�tsklasse P und ist somit effizient l�sbar.Dijkstra entwickelte einen Algorithmus, der das Problem in einer Komplexit�t von O(n�) l�st [Dij59].

Das mehrkriterielle K�rzestete-Wege-Problem ist NP-vollst�ndig (vgl. [Hans80], [Sera87]). Insbesondere f�r grosse Probleminstanzen verbietet sich damit der Einsatz eines Algorithmus, der das Problem mit Sicherheit exakt l�st. Aus diesem Grund wird als L�sungsansatz ein heuristisches Verfahren, in diesem Fall ein mehrkriterieller Ansatz von Ant Colony Optimization, verwendet.

In unten verlinkten Beitrag, der in unserem Arbeitskreis entstanden ist, soll ein m�glicher Ansatz aufgezeigt werden, wie dieser Umstand der unikriteriellen effizienten L�sbarkeit zur Verbesserung des mehrkriteriellen Ameisenalgorithmus genutzt werden kann. F�r die unikriterielle L�sung kommt hierbei das Verfahren Dynamic Programming [Bel57] zum Einsatz.