Deel dit artikel

handelsreizigers zouden maar wat graag kunnen berekenen wat het kortste parcours is tussen de klanten die ze moeten bezoeken. de vraag naar de kortste rondgang tussen verschillende punten lijkt eenvoudig, de oplossing is dat allerminst. het ‘handelsreizigersprobleem’ houdt wiskundigen en informatici al jaren in de ban. Maar ook in het dagelijkse leven kom je toepassingen van dit probleem tegen: van het uitsparen van behangpapier tot het organiseren van playlists op je mp3-speler.

Het probleem van de handelsreiziger

Bart Demoen

Een handelsreiziger wordt elke dag met het probleem geconfronteerd: hij bezoekt een aantal mogelijke klanten, keert ’s avonds terug waar hij ’s morgens vertrok en wil hierbij zo een klein mogelijke afstand afleggen. De benaming ‘handelsreizigersprobleem’ voor dit wiskundige vraagstuk ligt voor de hand. Algemener geformuleerd klinkt de vraagstelling als volgt: zoek voor een aantal knooppunten met daartussen verbindingen met hun lengte een kring die alle knooppunten juist één keer bevat en een minimale totale lengte heeft. In de wiskunde wordt een structuur die uit knooppunten (of knopen) en verbindingen bestaat een gewogen graaf genoemd. Een kring die alle knopen juist één keer bevat, heet een hamiltoniaanse kring (afgekort als HK). Sir W. Hamilton, een Ierse wiskundige uit de negentiende eeuw, was de eerste die het concept formaliseerde, bestudeerde en zelfs commercieel exploiteerde.

Ook niet-handelsreizigers kunnen met gelijkaardige problemen te maken krijgen. The Traveling Salesman Problem – A Computational Study van David Applegate en medewerkers beschrijft onder meer waar het probleem zoal voorkomt in de praktijk. Soms gaat het gewoon om variaties op de handelsreiziger: een toerist die op één dag zoveel mogelijk attracties wil bezoeken, een schoolbus die zo snel mogelijk alle kinderen wil afzetten of een postbode die zijn rondrit zo kort mogelijk wil maken. Andere toepassingen komen uit de productie, bijvoorbeeld van printplaten: in zo’n printplaat wordt een groot aantal gaten geboord door één boorkop, die zich boven de plaat van boorgat naar boorgat beweegt. Het productieproces kan worden verkort door een goede volgorde van de boorgaten te kiezen. Het verband met het reeds beschreven handelsreizigersprobleem is duidelijk: modelleer de boorgaten als de knopen van een graaf en neem de tijd nodig om de boorkop van het ene naar het andere boorgat te laten bewegen als de lengte van de verbinding tussen die twee knopen. Een kortste kring geeft nu een optimale volgorde waarin de boorgaten moeten worden gemaakt. Een gelijkaardige toepassing is te vinden in een sterrenobservatorium, waar tijdens één nacht een aantal sterren worden geobserveerd: ook hier wil men de bewegingen van de telescoop van de ene naar de andere ster het liefst beperken.

Toepassingen zijn in feite overal te vinden: van het reduceren van verlies bij behangpapier tot het organiseren van playlists op een mp3-speler. Dat het verlangen om de reisweg te optimaliseren van alle tijden is, blijkt onder meer uit een Duits handboek uit 1832, Der Handlungsreisende. Hierin geeft een ‘alte Commis-Voyageur’ raad aan zijn collega’s handelsreizigers over hoe ze een geschikte route kunnen plannen. In de jaren dertig van de vorige eeuw werd aan de universiteit van Princeton voor de eerste keer naar het geformaliseerde probleem verwezen als het ‘Traveling Salesman Problem’, afgekort het TSP. En die benaming is blijven hangen.

Voor twintig steden zijn er potentieel 60.822.550.204.416.000 kringen en die allemaal genereren ligt ver buiten onze rekencapaciteit

Het Traveling Salesman Problem kan zo makkelijk in één zin worden geformuleerd en het is zo makkelijk te vatten, dat men er allicht van uitgaat dat er ook een makkelijke oplossing voorhanden is. Voor een eindig aantal steden bestaat er inderdaad slechts een eindig aantal kringen: het is hierbij mogelijk om de lengte van elke kring te berekenen en de kortste kring te kiezen. Dit geeft een algoritme dat het TSP oplost … althans in principe. Voor vijf steden zijn er maximaal twaalf kringen. Een TSP met vijf steden kunnen we dus makkelijk met de hand oplossen. Voor tien steden zijn er hoogstens 181.440 kringen. Voor onze computer is dat nog een klein getal. Maar voor twintig steden zijn er potentieel 60.822.550.204.416.000 kringen en die allemaal genereren ligt ver buiten onze rekencapaciteit. Dit hoeft ons echter niet af te schrikken: misschien kan bovenstaand brutekrachtalgoritme worden verbeterd? Maar wat betekent het eigenlijk dat één algoritme beter is dan een ander?

De complexiteitstheorie bestudeert de kwaliteit van een algoritme en de intrinsieke moeilijkheid om bepaalde problemen op te lossen. In oorsprong gaat het om beslissingsproblemen, om vragen als: heeft een gegeven ding een bepaalde eigenschap? Bijvoorbeeld: is dit getal deelbaar door 9? Of: is deze rij getallen stijgend geordend? Of: heeft deze graaf een hamiltoniaanse kring? Er bestaat niet altijd een algoritme voor elk beslissingsprobleem. Zo bestaat er geen algoritme dat de vraag ‘stopt dit programma’ beantwoordt voor een willekeurig computerprogramma. Als een beslissingsprobleem echter een algoritme heeft, dan heeft het altijd veel algoritmen: zo kunnen we voor de deelbaarheid door 9 de deling echt uitvoeren en nagaan of de rest 0 is. Of we kunnen de som module 9 maken van de cijfers van het getal zoals in de negenproef.

Voor één vast algoritme kunnen we nu bestuderen hoeveel elementaire stappen het nodig heeft in functie van de grootte van de invoer. In het geval van deelbaarheid door 9 is de grootte van de invoer het aantal cijfers N. Het uitvoeren van de deling door 9 kost dan N delingen, een vermenigvuldiging en een aftrekking: het deel-door-9-algoritme noemen we dan ook lineair in N en we noteren dat door O(N). Die notatie verbergt de constante factor voor de N, maar die factor is voor de verdere discussie niet belangrijk. Vermenigvuldiging van twee getallen met elk N cijfers, zoals we het op school leerden, gebruikt een kwadratisch aantal bewerkingen: elk van de N cijfers van het ene getal wordt met elk van de N cijfers van het andere getal vermenigvuldigd. En dan zijn er nog wat optellingen: in het totaal O(N²). We zeggen dat het algoritme een kwadratische complexiteit heeft.

Elk algoritme heeft zijn eigen complexiteit en we vergelijken algoritmen door hun complexiteitsfunctie te vergelijken: zo vinden we een algoritme van orde N³ slechter dan een van orde N². Zo bestaat voor (bijna) elk beslissingsprobleem een best algoritme, ruwweg het algoritme met de complexiteitsfunctie die het minst snel stijgt. Een algoritme met een complexiteitsfunctie die een veelterm is in de grootte N, heet een polynomiaal algoritme. Een probleem met een polynomiaal algoritme noemen we een polynomiaal probleem. Zo is het vermenigvuldigen van twee getallen een polynomiaal probleem, en ook het sorteren van een rij getallen, of het bepalen van de kortste afstand tussen twee steden (iets dat routeplanners zoals ViaMichelin voortdurend doen). Polynomiale problemen hebben algoritmen die ook voor grote invoer (grote N) door computers snel kunnen worden beslist, tenminste als de graad van de polynoom niet te hoog is. De verzameling van polynomiale problemen noteert men door P.

Het naïeve algoritme dat van elke kring de lengte berekent, heeft complexiteit N!, waarbij N het aantal steden is

Terug naar de handelsreiziger: het naïeve algoritme dat van elke kring de lengte berekent, heeft complexiteit N!, waarbij N het aantal steden is. De faculteitsfunctie stijgt zeer snel met stijgende N. Bij het maken van printplaten is het aantal te boren gaten vaak groter dan honderd. Het naïeve algoritme is helemaal niet geschikt voor zulke waarden van N. We willen een goed, dus polynomiaal algoritme voor het TSP. En hier wringt het schoentje. De enorme inspanning van hordes wetenschappers heeft eigenlijk niets opgeleverd: geen polynomiaal algoritme voor het TSP, geen bewijs dat een polynomiaal algoritme voor het TSP bestaat en ook geen bewijs dat het niet bestaat. Voor we dit uitspitten, moeten we het verband bekijken tussen het TSP en het geassocieerde TSP-beslissingsprobleem. Bestaat er voor een gewogen graaf en een getal L een hamiltoniaanse kring die kleiner is dan L? Op die vraag kan alleen met ja of nee worden geantwoord: het is dus een beslissingsprobleem. Stel dat we een goed algoritme hadden om het TSP-beslissingsprobleem op te lossen, dan zouden we een algoritme voor het TSP als volgt kunnen bouwen: we lossen het TSP-beslissingsprobleem op voor L = 1, dan voor L = 2, dan voor L = 3 enzovoort – tot we een positief antwoord krijgen. Nu hebben we in ieder geval de lengte van de kleinste kring. Hiermee is het TSP nog niet opgelost, maar het is al een stap in de goede richting. Maar: voor het TSP-beslissingsprobleem hebben we geen goed algoritme: we weten niet of het in P zit.

Het TSP-beslissingsprobleem heeft wel een speciale eigenschap: als men ons wil overtuigen dat een gegeven gewogen graaf met N knopen een hamiltoniaanse kring heeft die kleiner is dan L, dan geeft men ons gewoon zo’n hamiltoniaanse kring. We kunnen dan heel eenvoudig nakijken of die kring inderdaad een hamiltoniaanse kring is en kleiner dan L. De hamiltoniaanse kring die men ons gaf, is een certificaat voor een ja-antwoord. Het certificaat is in dit geval een opeenvolging van N knopen, dus lineair in N, of O(N). Ons algoritme om dat certificaat na te kijken is eveneens lineair in N. Dus, voor het TSP-beslissingsprobleem bestaan polynomiale certificaten. De verzameling van alle beslissingsproblemen met een polynomiaal certificaat noteren we met NP, wat staat voor niet-deterministische polynomiaal, een terminologie die vanuit een equivalente alternatieve beschrijving van die verzameling komt. Als verzameling is P duidelijk een deel van NP.

De moeilijkste problemen in NP worden NP-compleet genoemd en één van de meest bekende NP-complete problemen is nu het TSP-beslissingsprobleem. Het is relatief gemakkelijk aan te tonen dat als het TSP-beslissingsprobleem tot P behoort, de verzameling P gelijk is aan de verzameling NP. De vraag of P = NP houdt wiskundigen en informatici echter al vele jaren in de ban en is zelfs één van de zeven ‘milleniumproblemen’, waarvoor het Clay Mathematics Institute of Cambridge, Massachusetts een prijs uitloofde van één miljoen US dollar. Het TSP zelf wordt NP-hard genoemd: elk NP-probleem kan ernaar worden gereduceerd. Het lijkt er dus op dat er niet snel een goed polynomiaal algoritme voor het TSP zal komen. Toch is het in de praktijk belangrijk dat voor netwerken met honderden steden optimale kringen worden gevonden. Het begon natuurlijk wat kleiner.

Proctor & Gamble schreef als reclamestunt een wedstrijd uit waarbij een TSP voor 33 steden in de Verenigde Staten moest worden opgelost

Het Traveling Salesman Problem werd waarschijnlijk bekend bij een breder publiek in het begin van de jaren zestig van de vorige eeuw, toen Proctor & 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. Daarvoor hadden in 1954 een aantal wiskundigen met behulp van technieken uit lineair programmeren al een TSP voor 49 steden opgelost. Het duurde zeventien jaar voor dit aantal op 57 steden kwam en het groeide gestaag naar 2.392 in 1987. Ondertussen heeft de gemeenschap van TSP-onderzoekers een hele testbatterij van gewogen grafen aangelegd. Die werden verzameld in een databank die bekendstaat als TSPLIB: elk nieuw idee om TSP sneller te implementeren wordt daarop uitgetest.

Sinds de jaren 1990 steekt één systeem boven alle andere uit: Concorde. De auteurs van het boek zijn ook de auteurs van dit systeem, dat overigens vrij kan worden gedownload voor academisch onderzoek. Intussen loste Concorde in 2004 een TSP op voor Zweden: het berekende de kortste kring door de 24.978 steden in Zweden. Die berekening gebruikte bijna 85 jaar computertijd, verdeeld over 96 machines. In 2006 werd zelfs een TSP met 85.900 ‘steden’ in een VLSI-toepassing opgelost. Zulke aantallen steden liggen ver buiten het bereik van het naïeve algoritme en zelfs van het meest bekende algoritme van Held en Karp, dat nog altijd van de orde N² 2^N is. Concorde combineert dan ook een aantal methoden en heuristieken en maakt bovendien gebruik van ondergrenzen op de gezochte kortste kring.

Het concept van de ondergrens is interessant, want die geeft aan dat geen enkele kring korter kan zijn en geeft daardoor greep op hoeveel een reeds gevonden oplossing nog van de optimale kan verschillen. Die krachtige ondergrenstechniek kan eenvoudig worden geïllustreerd. Bijgevoegde figuur laat zien hoe op de knopen van de graaf schijfjes zijn gelegd zodanig dat de schijfjes niet overlappen. De som van de diameters van de schijfjes is nu een ondergrens voor de lengte van elke hamiltoniaanse kring. Als we rond een groep schijfjes nu ook nog een gracht leggen (zoals in de rechterkant van de figuur) dan krijgen we in vele gevallen al een optimale ondergrens. Intussen zijn er voor verschillende landen optimale hamiltoniaanse kringen berekend. Ze zijn te vinden op http://www.tsp.gatech.edu/world/countries.html. De volgende uitdaging is een wereldtoer: een wereldkaart met 1.904.711 steden werd aan Concorde gegeven. Zelfs de auteurs van Concorde verwachten niet dat hun technieken voldoende zijn om een optimale hamiltoniaanse kring te vinden, maar het bestuderen van zulke grote problemen leidt tot nieuwe inzichten en algoritmen. Een benadering voor de wereldtoer tot op minder dan 0,06 procent is reeds gevonden.

Het TSP is zo moeilijk in het algemeen op te lossen dat het zin heeft om varianten van het TSP te onderzoeken, in de hoop dat die gemakkelijker zijn dan het oorspronkelijke probleem. Een eerste voor de hand liggende variant is die waarbij de steden meer dan eens mogen worden bezocht: die variante is nog altijd NP-hard. Misschien wordt het eenvoudiger als we veronderstellen dat de graaf in het vlak ligt en de afstanden euclidisch zijn? Dat helpt zeker om sommige kringen uit te sluiten, want met de driehoeksongelijkheid kunnen we aantonen dat een minimale hamiltoniaanse kring geen kruisende wegen heeft. Die variante is nog altijd NP-hard. Misschien kan er efficiënt een willekeurig dichte benadering van een optimale kring worden berekend: voor heel wat andere NP-complete problemen bestaan inderdaad polynomiale benaderingsalgoritmen, maar spijtig genoeg niet voor het TSP.

Het handelsreizigersprobleem is ook bestudeerd in andere contexten dan de complexiteitstheorie: zo hebben psychologen het gebruikt om de evolutie te bestuderen van perceptuele en cognitieve vaardigheden van kinderen tot volwassenen. Artiesten hebben het gebruikt om interessante tekeningen te produceren. En zelfs chimpansees en duiven hebben in experimenten mogen tonen hoe goed ze een TSP kunnen oplossen. Het ‘handelsreizigersprobleem’ blijkt een universele uitdagende inspiratie en zal dat nog lang blijven.

David L. Applegate, Robert E. Bixby, Vasek Chvátal en William J. Cook, The Traveling Salesman Problem. A Computational Study. (Princeton: Princeton University Press, 2007).

Bart Demoen is als informaticaonderzoeker verbonden aan de KU Leuven.

Deel dit artikel
Gerelateerde artikelen