Page 2 - Grafentheorie HS 5 Handelsreizigersprobleem

HS 5 Handelsreizigersprobleem

5 Het handelsreizigersprobleem.

5.1 Handelsreizigersprobleem (Traveling Salesman Problem)

5.1.1 Inleiding

Een handelsreiziger wordt elke dag met het probleem geconfronteerd: hij moet een aantal mogelijke
klanten in verschillende steden bezoeken en ’s avonds terugkeren waar hij ’s morgens vertrok was.
Hierbij wil hij een zo klein mogelijke afstand afleggen. Er bestaan een aantal variaties van dit probleem
zoals een toerist die op één dag zoveel mogelijk attracties wil bezoeken, een schoolbus die zo snel
mogelijk alle kinderen wil afzetten, een pakjesdienst die een aantal pakjes moet leveren vertrekkend uit
een centraal depot en wel zodanig dat de kostprijs minimaal is.
Het handelsreizigersprobleem werd waarschijnlijk bekend bij een breder publiek in het begin van de
jaren zestig van de vorige eeuw, toen Procter & Gamble als reclamestunt een wedstrijd uitschreef
waarbij een TSP voor 33 steden in de Verenigde Staten moest worden opgelost. De prijs voor de
winnaar was 10.000 US dollar.

Men kan de vraagstelling van dit “handelreizigersprobleem” algemener formuleren met grafen.
Zoek voor een aantal knopen met daartussen bogen met een bepaalde afstand een kring die alle
knooppunten juist één keer bevat en een minimale totale lengte heeft. Omdat aan de bogen ook een
t
getal wordt toegekend noemt men dit gewogen grafen. e
n
Een kring die alle knopen juist één keer bevat, heet een Hamiltoncykel. .
o
Bij het handelsreizigersprobleem moet op zoek naar de kortste Hamiltoncykel. l
e
h
Dit handelsreizigersprobleem heeft ook talrijke andere toepassingen. Bij de fabricatie van printplaten
t
voor computers moet een laserstraal een aantal montagepuntjes aanbrengen, startend vanuit een vaste a
positie. Het productieproces kan aanzienlijk verkort worden door een goede volgorde van de m
.
montagepunten te kiezen. w
Een gelijkaardige toepassing is te vinden in een sterrenobservatorium, waar tijdens één nacht een aantal w
sterren worden geobserveerd en het aantal bewegingen van de telescoop van de ene naar de andere w
ster wil beperken.

© 2021 Ivan De Winne ivan@mathelo.net 1