Reizigersprobleem voor 3038 steden opgelost

Wat is de snelste manier om een heel rijtje steden te bezoeken? Dat is het klassieke probleem van de handelsreiziger, een probleem dat in moderne gedaante voortdurend opduikt.

Bijvoorbeeld in de elektronica-industrie, waar lasers de handigste volgorde moeten vinden om tienduizenden gaatjes te boren om gedrukte bedrading op condensatoren aan te brengen. Zulke optimaliseringsproblemen zijn in diverse technische en wetenschappelijke toepassingen aan de orde van de dag en daarom houdt het oudehandelsreizigersprobleem wiskundigen en computerexperts uit de hele wereld nog altijd volop bezig. Onderzoekers in de VS hebben nu een nieuw wereldrecord gevestigd. Zij hebben de snelste manier berekend om een groep van 3038 steden te bezoeken. Het vorige record, dat uit 1986 dateerde, stond op 2392 steden, wat al weer een hele vooruitgang was ten opzichte van het record dààrvoor dat 532 steden betrof.

Elke stad wordt eenmaal bezocht alvorens naar het uitgangspunt terug te keren. Voor een groep van vijf steden levert dat al 5x4x3x2x1=120 mogelijke routes op. Een computer berekent in een fractie van een seconde welke daarvan de korste is, maar naarmate het aantal steden toeneemt loopt het probleem al snel uit de hand. Bij 100 steden moet de computer 10¹5º opdrachten uitvoeren. Zelfs de snelste supercomputer ter wereld heeft daarvoor al 10¹²º jaar nodig, tenzij er een slimmere methode beschikbaar is.

De nieuwe wereldrecordhouders hebben vier jaar op het probleem zitten broeden en hadden voor het uitvoeren van de feitelijke recordberekening van 3038 steden naar schatting anderhalf jaar computertijd nodig. Overigens steekt dat nog tamelijk ongunstig af bij het vorige record dat in 27 uur computerrekentijd werd gevestigd.

Het vinden van oplossingen voor het handelsreizigersprobleem is van belang opdat onderzoekers daarmee efficiënte algorhitmen ("rekenvoorschriften') kunnen vinden voor een hele klasse soortgelijke optimaliseringsproblemen. Efficiënt wil in dit geval zeggen, dat er een redelijke verhouding moet bestaan tussen de omvang van het probleem en de tijd die een computer nodig heeft om het op te lossen.

Uit praktische overwegingen streven de meeste wiskundigen ernaar om oplossingen voor het handelsreizigersprobleem niet echt helemaal uit te rekenen, maar met de beste schattingen te benaderen. Zo kan At&T Bell Laboratories in New Jersey in minder dan drie uur een antwoord berekenen dat de juiste oplossing voor de kortste route tussen een miljoen steden tot op twee procent benadert, en voor 100.000 steden bedraagt de rekentijd nog maar tien minuten. De huidige recordhouders verklaarden tegenover New Scientist het hierbij voorlopig te zullen laten. Ze zijn namelijk bekaf. (New Scientist, 27 juni 1992)