Die optimierte Odyssee

Das Problem der k�rzesten Rundreise ist Prototyp einer gro�en Klasse praktisch bedeutsamer, komplexer Minimierungs- oder Maximierungsaufgaben. Sie sind so schwer, da� man sich h�ufig mit einer brauchbaren N�herung zufriedengeben mu�. Neue, listenreiche Verfahren liefern jedoch immer h�ufiger die nachweislich beste L�sung.

Martin Gr�tschel und Manfred Padberg

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