|
|
Het travelling salesman problem is een klassieker. Het betreft een verkoper die de kortste route wil bepalen waarbij hij toch al zijn klanten bezoekt. Dit probleem is de basis van alle transport-scheduling problemen in de logistieke wereld. Dit travelling salesman probleem is mathematisch niet oplosbaar, zonder alle mogelijkheden uit te rekenen (een zogenaamd NP-hard probleem). Er zijn geen 'slimme' algorithmes die eenvoudig de optimale route kunnen bepalen.
De hierboven weergegeven figuur is een voorbeeld van het travelling salesman probleem: de krantenbezorger in New York. In de figuur zijn het depot (het startpunt) en alle addressen weergegeven. De krantenjongen wil zo min mogelijk lopen, maar moet wel alle kranten bezorgen.
We zoeken nu naar een eenvoudige manier om tot een aanvaardbare oplossing te komen. De eerste vraag is natuurlijk wat aanvaardbaar is. Gesteld dat alle punten verdeeld zijn over twee uiterste punten (de hoeken) dan is de slechts mogelijke oplossing in de orde van 400.000. Als de punten gelijkmatig verdeeld zijn en de bezorger kan er eenvoudig langslopen is de afstand ca. 4000. Dus een oplossing die ver weg blijft van 400.000 en 4000 benaderd is alleszins aanvaardbaar. De interessante vraag blijft dan hoe we dat gaan doen.
Stelt u zich eens de positie van de krantenbezorger voor, bijvoorbeeld bij een nieuw adres. Wat zal deze krantenjongen doen. Waarschijnlijk zal hij het adres niet achteraan plakken, maar hij zal kijken tussen welke twee bestaande adressen het nieuwe adres het beste past. Dit kunnen we natuurlijk ook vanaf het begin doen. Dan ontstaat een simpele regel: Pak een willeurig punt (1). Kijk tussen welke twee punten dat punt het beste past. Ga door tot je alle punten hebt gedaan. Onthoudt het resultaat, en begin opnieuw. Dit kun je eindeloos blijven doen, of totdat het resultaat aanvaardbaar is.
Hiermee streven we niet naar de optimale oplossing, maar wel naar een goede oplossing in (vrij) korte tijd. In real life probleem situaties kan dit erg handig zijn, denk bv. aan koeriers die pas op het laatste moment nieuwe adressen krijgen, en dus hun route onmiddelijk moeten aanpassen.
De essentie van het voorbeeld is dat wederom een simpele regel tot een eenvoudige oplossing leidt. Het vinden van die regel kan erg moeilijk zijn. Meestal helpt het om op de stoel te gaan zitten van degene die dat nu dagelijks doen!
(1) Om te beginnen moeten dus twee willekeurige punten worden genomen. Het eerste punt kan immers nergens tussen.