Page 6 - Grafentheorie HS 5 Handelsreizigersprobleem

HS 5 Handelsreizigersprobleem

5.2 De TSP-wedloop

Het probleem van de handelsreiziger werd in 1832 voor de allereerste keer vermeld in een Duits
handboek “Der handlungsreisende” waarin een “Alte Commis-Voyageur” raad geeft aan zijn jongere
collega’s over hoe een geschikte route te plannen.
De allereerste keer dat naar het geformulariseerde probleem als “het handelsreizigersporbleem”, in het
Engels “Traveling Salesman Problem (TSP)” werd verwezen in het jaar 1930 aan de universiteit van
Princeton (USA).
In 1949 ontwikkelden wiskundigen waaronder George Dantzig een methode om het TSP-probleem voor
49 steden in de Verenigde Staten op te lossen.

In de loop der jaren zijn steeds grotere handelsreizigersproblemen opgelost. Zo vond Grötschel in 1977
de kortste rondreis langs 120 steden in Duitsland.

In 1987 vonden Padberg en Rinaldi de kortste route langs 2392 te boren gaatjes in een printplaat.
t
e
n
.
o
l
e
h
t
a
m
.
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 5