Die optimierte Odyssee

Odysseus, der sagenhafte König von der griechischen Insel Ithaka, hatte eine lange Reise hinter sich, als er nach 20 Jahren seine Penelope endlich wieder in die Arme schließen konnte – Stoff für ein ganzes Epos, die "Odyssee" des antiken Dichters Homer. Moderne Interpreten haben aus ihr 16 Orte im Mittelmeerraum herausgelesen, die er besucht haben soll (kleines Bild unten).

Er hätte es zweifellos kürzer haben können, wären da nicht das Schicksal, die Launen des Meeres, die Mißgunst der Götter und vor allem der mangelnde Überblick über die Geographie gewesen. Versetzen wir Odysseus in die moderne Zeit: Stellen wir uns einen Topmanager oder – prosaischer – Handelsvertreter (travelling salesman) vor. Er will alle 16 Städte in beliebiger Reihenfolge besuchen, und zwar auf dem kürzestmöglichen Wege – Zeit ist Geld. Das ist das berühmte travelling salesman problem (TSP): schnell formuliert, höchst praxisrelevant, scheinbar harmlos, in Wirklichkeit aber – für große Städteanzahlen – so schwer, daß die Mathematiker sich auch nach Jahrzehnten harter Arbeit die Zähne daran ausbeißen.

Mehr noch: Das TSP ist nur das einleuchtendste Beispiel aus einer ganzen Klasse von Problemen. Sie finden sich überall da, wo es gilt, unter Kombinationen von sehr vielen Möglichkeiten die günstigste zu finden. Beispielhaft für die unübersehbar vielen Anwendungen seien genannt:

• Zuweisung von Ladung und Personal an Lastwagen oder Frachtflugzeuge,

• Maschinenbelegung,

• Fahrplangestaltung,

• Entwurf von Mikrochips,

• Kapitalanlageplanung und

• die Gestaltung von Kommunikations-

netzen.

Für das Problem des Odysseus ergibt sich als kürzeste Rundreise eine Tour von 6859 Kilometern Länge (Kasten Seite 84 rechts unten). Die Entfernungen zwischen je zwei Städten haben wir in Luftlinie gemessen (und auf ganze Kilometer gerundet); aber selbst mit dem Flugzeug hätte Odysseus in der von ihm gewählten Reihenfolge 9913 Kilometer zu