AlegsaOnline.com

Problemet med den resande säljaren (TSP) – definition, historia och optimering

Lär dig TSP: definition, historik från Hamilton till Menger och moderna optimeringsmetoder för kortaste rutter, algoritmer och praktiska lösningar.

Författare: Leandro Alegsa

11-03-2026

Traveling Salesman Problem (ofta kallat TSP) är ett klassiskt algoritmiskt problem inom datavetenskap och operationsforskning. Det handlar om optimering — att hitta den bästa möjliga rutten enligt något mått, oftast kortaste totala avstånd, lägsta kostnad eller kortast total tid. Formellt kan TSP beskrivas som en viktad graf som representerar platser (noder) och avstånd eller kostnader mellan dem (kanter): målet är att hitta en slinga som besöker varje nod exakt en gång och återvänder till startpunkten, med minimal total vikt.

Problemet med den resande säljaren definierades på 1800-talet av den irländska matematikern W. R. Hamilton och den brittiska matematikern Thomas Kirkman. Hamiltons Icosian Game var ett fritidspussel som byggde på att hitta en Hamiltons cykel. Den allmänna formen av TSP verkar ha studerats för första gången av matematiker under 1930-talet i Wien och på Harvard, särskilt av Karl Menger. Menger definierar problemet, överväger den uppenbara brutala algoritmen och observerar att den närmaste granne-heuristiken inte är optimal:

Vi betecknar budbärarproblemet (eftersom denna fråga i praktiken bör lösas av varje brevbärare, men också av många resenärer) som en uppgift att för ﬁnantilt många punkter vars parvisa avstånd är kända, hitta den kortaste vägen som förbinder dessa punkter. Naturligtvis kan detta problem lösas genom ändligt många försök. Regler som skulle få antalet försök att understiga antalet permutationer av de givna punkterna är inte kända. Regeln att man först ska gå från startpunkten till den närmaste punkten, sedan till den punkt som ligger närmast denna punkt osv. ger i allmänhet inte den kortaste vägen.

Hassler Whitney vid Princeton University introducerade kort därefter namnet "traveling salesman problem".

Matematisk formulering och varianter

Vanligtvis formuleras TSP på en komplett riktad eller oriktig graf med viktade kanter. Vanliga varianter:

Symmetriskt TSP: avståndet från A till B = avståndet från B till A.
Asymmetriskt TSP: avstånden är riktade (olika i olika riktningar).
Metiskt (triangelolikhet) TSP: avstånden uppfyller triangelolikheten (direkt väg är aldrig längre än via en tredje punkt). Detta gör att vissa approximationer fungerar.
Varianten med krav: exempelvis tidsfönster, kapacitetsbegränsningar — leder vidare till problem som Vehicle Routing Problem (VRP).

Komplexitet

TSP är beräkningsmässigt svårt. Beslutsvarianten ("finns en rundresa med kostnad ≤ K?") är NP-komplett, och optimeringsvarianten är NP‑hård. Det innebär att inga kända polynomal tidsalgoritmer garanterar optimala lösningar för alla instanser, och för stora n blir brutalt sökande över alla permutationer (n!) omöjligt i praktiken. För vissa specialfall finns dock bättre metoder och approximationsresultat — t.ex. en 1,5-approximation för symmetriskt metriskt TSP (Christofides' algoritm) och PTAS i fasta dimensioner för euklidiskt TSP (Arora/ Mitchell).

Lösningsmetoder

Man skiljer grovt mellan exakta algoritmer (garanterar optimalitet) och heuristiker/approximativa metoder (snabba men utan garanti på optimalitet för alla instanser).

Exakta metoder

Bruteforce: pröva alla permutationer — O(n!) tid; praktiskt endast för mycket små n.
Held–Karp (dynamisk programmering): O(n^2 2^n) tid och O(n 2^n) minne — förbättring jämfört med n!, gör exakta lösningar möjliga för mellanstora n.
Branch-and-bound / branch-and-cut: kombinerar sökträd med gränsberäkningar och linjärprogrammering (cutting planes). Dantzig–Fulkerson–Johnson var tidiga banbrytare. Moderna kraftfulla verktyg (Concorde, LKH för heuristisk förbättring) används i praktiken.

Approximationer och teoretiska resultat

Christofides' algoritm: ger för symmetriskt metriskt TSP en lösning med kostnad ≤ 1.5 × optimal.
PTAS för euklidiskt TSP: i fasta dimensioner finns algoritmer som, för varje ε>0, hittar en (1+ε)-approx i polynomtid (Arora, Mitchell).

Heuristiker och metaheuristiker

I praktiska tillämpningar används ofta heuristiker som snabbt hittar mycket bra (om än inte alltid optimala) rundor:

Närmaste granne — enkel men kan ge dåliga resultat (Menger noterade detta tidigt).
2-opt, 3-opt — lokala förbättringsmetoder som byter kanter för att minska längden.
Lin–Kernighan och Lin–Kernighan–Helsgaun (LKH) — avancerade lokalsökningsmetoder som ofta ger mycket nära optimala lösningar i praktiken.
Simulated annealing, genetiska algoritmer, ant colony optimization — metaheuristiker som används för stora eller svårstrukturade instanser.

Praktiska tillämpningar

TSP och dess varianter dyker upp i många områden:

Logistik och ruttplanering (distributionsnätverk, bud- och leveransrutter).
Tillverkning (t.ex. optimering av borr- eller skärjobb där ett verktyg ska besöka många punkter).
Telekommunikation och databussoptimization.
Biologi och bioinformatik (t.ex. vissa varianter av sekvenssammansättning kan formuleras med liknande grafproblem).
Planering av turist- eller försäljningsrutter och andra realtidsapplikationer.

Praktiska begränsningar och storlek

Den storlek av problemländer (n) som kan lösas exakt beror på metod och maskinkraft. Enkel implementering av Held–Karp skalar till några tiotal noder i rimlig tid; branch-and-cut med kraftfulla implementationer kan lösa hundratals till tusentals noder för speciella instanser, och heuristiker kan hantera mycket större problem (tusentals–miljoner) med god kvalitet på lösningen.

Sammanfattning

TSP är ett enkelt att beskriva men djupt och mångsidigt problem: det är centralt både i teori (komplexitetsteori, approximationsalgoritmer) och i praktisk optimering (logistik, produktion). Valet av metod beror på instansens storlek, krav på optimalitet och problemets struktur (t.ex. euklidiskt vs. allmänt viktat). Moderne forskning och mjukvara kombinerar exakta metoder med kraftfulla heuristiker för att lösa riktiga problem effektivt.

En försäljare vill besöka alla städerna A, B, C och D. Vilket är det bästa sättet att göra detta (billigaste flygbiljetter och minsta möjliga restid)?

Optimal rutt för en försäljare som besöker de 15 största städerna i Tyskland. Den visade rutten är den kortaste av de 43 589 145 600 möjliga rutterna.

Problemet är tydligt formulerat.

Problemet med den resande försäljaren beskriver en försäljare som måste resa mellan N städer. Han bryr sig inte om i vilken ordning han gör det, så länge han besöker varje stad en gång under resan och slutar där han var i början. Varje stad är förbunden med andra närliggande städer, eller noder, med flyg, väg eller järnväg. Varje länk mellan städerna har en eller flera vikter (eller kostnader). Kostnaden beskriver hur "svårt" det är att korsa denna kant i grafen, och kan till exempel anges genom kostnaden för en flygbiljett eller tågbiljett, eller kanske genom längden på kanten, eller den tid som krävs för att genomföra korsningen. Försäljaren vill hålla både resekostnaderna och den sträcka han reser så låg som möjligt.

Traveling Salesman-problemet är typiskt för en stor klass av "svåra" optimeringsproblem som har fascinerat matematiker och datavetare i åratal. Det viktigaste är att det har tillämpningar inom vetenskap och teknik. Vid tillverkningen av ett kretskort är det till exempel viktigt att bestämma den bästa ordningen i vilken en laser ska borra tusentals hål. En effektiv lösning på detta problem minskar tillverkarens produktionskostnader.

Svårighetsgrad

Generellt sett är problemet med den resande säljaren svårt att lösa. Om det finns ett sätt att dela upp problemet i mindre problemkomponenter, kommer dessa komponenter att vara minst lika komplexa som det ursprungliga problemet. Detta är vad datavetare kallar NP-hårda problem.

Många har studerat detta problem. Den enklaste (och dyraste) lösningen är att helt enkelt prova alla möjligheter. Problemet med detta är att man för N städer har (N-1) faktoriella möjligheter. Detta innebär att det för endast 10 städer finns över 180 000 kombinationer att prova (eftersom startstaden är definierad kan det finnas permutationer för de återstående nio). Vi räknar bara hälften eftersom varje rutt har en likvärdig rutt i motsatt riktning med samma längd eller kostnad. 9! / 2 = 181 440

Exakta lösningar på problemet kan hittas med hjälp av algoritmer för grenar och gränser. Detta är för närvarande möjligt för upp till 85 900 städer.
Heuristiska metoder använder en uppsättning vägledande regler för att välja nästa nod. Men eftersom heuristiker ger approximationer ger de inte alltid den optimala lösningen, även om godtagbara heuristiker av hög kvalitet kan hitta en användbar lösning på en bråkdel av den tid som krävs för en fullständig brute force-analys av problemet. Ett exempel på en heuristik för en nod skulle vara en summering av hur många obesökta noder som ligger "nära" en ansluten nod. Detta skulle kunna uppmuntra försäljaren att besöka en grupp av nära knutar som är grupperade tillsammans innan han går vidare till ett annat naturligt kluster i grafen. Se Monte Carlo-algoritmer och Las Vegas-algoritmer.

Frågor och svar

Fråga: Vad är problemet med den resande säljaren?

S: Traveling Salesman Problem (TSP) är ett klassiskt algoritmiskt problem inom datavetenskap och operationsforskning. Det fokuserar på optimering, där bättre lösningar ofta innebär billigare, kortare eller snabbare lösningar.

F: Hur uttrycks TSP?

S: TSP uttrycks lättast som en graf som beskriver var en uppsättning noder befinner sig.

F: Vem definierade först TSP?

Svar: Problemet med den resande säljaren definierades på 1800-talet av den irländske matematikern W. R. Hamilton och den brittiske matematikern Thomas Kirkman.

F: Vem studerade det vidare under 1930-talet?

Svar: Under 1930-talet studerade matematikerna Karl Menger i Wien och på Harvard det vidare.

F: Vad introducerade Hassler Whitney kort därefter?

S: Hassler Whitney vid Princeton University införde namnet "traveling salesman problem" strax efter att det definierats.

F: Vad betyder "bättre lösning" i detta sammanhang?

S: I detta sammanhang betyder bättre lösning ofta en lösning som är billigare, kortare eller snabbare.

F: Vilken algoritm ansåg Menger vara självklar när han studerade TSP?

S: Menger ansåg att en självklar brute-force-algoritm var en självklar algoritm när han studerade TSP och konstaterade att användningen av heuristiken för närmaste granne inte alltid ger optimala resultat.