AlegsaOnline.com

Rejsendesælgerproblemet (TSP): Definition, algoritmer og optimering

TSP: Definition, algoritmer og optimering — få forståelse, heuristikker og metoder til at finde korteste ruter.

Forfatter: Leandro Alegsa

12-03-2026

Traveling Salesman-problemet (ofte kaldet TSP) er et klassisk algoritmisk problem inden for datalogi og operationsforskning. Det er fokuseret på optimering. I denne sammenhæng betyder en bedre løsning ofte en løsning, der er billigere, kortere eller hurtigere. TSP er et matematisk problem. Det udtrykkes lettest som en graf, der beskriver placeringen af et sæt knudepunkter. Formelt: givet n byer og afstande d(i,j) mellem hver par af byer, skal man finde en permutation π af byerne, som minimerer den samlede rejserute

c(π) = Σ_{k=1}^{n-1} d(π(k),π(k+1)) + d(π(n),π(1)), altså den korteste Hamilton-cyklus, som besøger hver by præcis én gang og vender tilbage til start.

Historie og tidlige observationer

Det rejsende sælgerproblem blev defineret i 1800-tallet af den irske matematiker W. R. Hamilton og den britiske matematiker Thomas Kirkman. Hamiltons Icosian Game var et fritidspuslespil, der var baseret på at finde en Hamilton-cyklus. Den generelle form af TSP synes først at være blevet undersøgt af matematikere i 1930'erne i Wien og på Harvard, især af Karl Menger. Menger definerer problemet, overvejer den indlysende brute-force-algoritme og konstaterer, at den nærmeste nabo heuristik ikke er optimal:

Vi betegner som messenger-problem (da dette spørgsmål i praksis skal løses af hvert enkelt postbud, men også af mange rejsende) opgaven med at finde den korteste rute, der forbinder punkterne, for ﬁntligt mange punkter, hvis parvise afstande er kendt. Selvfølgelig kan dette problem løses ved endeligt mange forsøg. Regler, som ville presse antallet af forsøg ned under antallet af permutationer af de givne punkter, er ikke kendt. Reglen om, at man først skal gå fra startpunktet til det nærmeste punkt, derefter til det punkt, der ligger tættest på dette punkt osv. giver i almindelighed ikke den korteste rute.

Hassler Whitney fra Princeton University introducerede kort efter navnet traveling salesman problem. Siden da er TSP blevet et af de mest studerede problemer inden for algoritmeteori, kompleksitetsteori og praktisk optimering.

Varianter af problemet

Symmetrisk TSP (STSP): d(i,j) = d(j,i). Typisk når afstande er euklidiske eller målt på en vejnet.
Asymmetrisk TSP (ATSP): d(i,j) ≠ d(j,i). Forekommer fx ved envejsgader eller forskellig rejsetid i hver retning.
Metric TSP: afstanden opfylder trekantsuligheden d(i,k) ≤ d(i,j)+d(j,k). Dette gør nogle approximationer mulige.
Euclidisk TSP: punkter i planen med euklidiske afstande. Har særlige strukturer og metoder.
Generaliserede varianter: multiple tours, kapacitetsbegrænsninger (VRP), præferencer, tidsvinduer osv.

Kompleksitet

TSP er et svært problem i beregningsmæssig forstand. Den beslutningsmæssige version ("er der en tur af længde ≤ K?") er NP‑komplet, og optimeringsversionen er NP‑hård. En simpel brute-force-løsning kræver at undersøge alle permutationer (n!), hvilket bliver uoverkommeligt hurtigt når n vokser. Derfor udvikles både eksakte algoritmer med bedre (men stadig eksponentiel) køretid og heuristikker til store instance.

Eksakte algoritmer

Brute force: enumerer alle permutationer — kun praktisk for meget små n.
Dynamic programming (Held–Karp): bruger bitmasker og har tidskompleksitet O(n^2 2^n) og plads O(n 2^n). Denne metode er brugbar op til moderate n (typisk n ≲ 30–40 afhængigt af ressourcer).
Branch-and-bound: træstruktur med øvre og nedre grænser for at udelukke store dele af søgeområdet.
Integer linear programming (ILP), subtour-elimination: formulering med binære variabler x_ij for at angive om kant (i,j) er med i turen. Løsning sker via branch-and-cut, hvor man løbende tilføjer subtour-elimination-cutting planes.
Kraftfulde kommercielle/forskningstools: fx Concorde (en velkendt eksakt solver til store instanser), som kombinerer cutting planes, branch-and-bound og specialiserede heuristikker.

Approximationer og begrænsninger

For den generelle (ikke-metriske) TSP findes ingen god polytime-approximation (med konstant faktor) medmindre P = NP. For metric (især symmetrisk) TSP findes der derimod væsentlige approximationer:

MST-baseret 2-approximation: Konstruer et mindste spændtræ (MST), dobbelt hver kant og forkort turen til en Hamilton-cyklus — giver faktor 2 i metriske tilfælde.
Christofides-algoritmen: kombinerer MST, minimum perfekt matchning på odd-degree-knuder og sammensmeltning; giver en 1,5-approksimation for metrisk symmetrisk TSP.
Forskning i bedre approximationer er aktiv for særlige versioner (fx graf-TSP), men Christofides' 1,5-grænse er stadig en central reference i mange sammenhænge.

Heuristikker og metaheuristikker

I praksis bruges ofte heuristikker, der hurtigt finder gode (om end ikke garanteret optimale) løsninger for store n:

Nærmeste nabo: start et sted og gå altid til den nærmeste uudforskede by — meget hurtig, men kan være langt fra optimal (Menger bemærkede dette tidligt).
2‑opt / 3‑opt: lokale forbedringer der bytter to eller tre kanter for at reducere totalafstand; meget effektive i praksis.
Lin–Kernighan (LK) og LKH: adaptive og kraftfulde lokale søgestrategier; LKH‑implementeringen er en af de mest brugte til store instanser.
Metaheuristikker: simulated annealing, genetiske algoritmer, ant colony optimisation (ACO) — bruges til at undgå lokale minima og finde bedre løsninger over tid.

Praktisk optimering og implementeringstips

Vælg algoritme efter størrelse og struktur: for n < ~12–15 kan brute-force være acceptabelt; Held–Karp er realistisk for moderate n; for hundreder til tusinder af knudepunkter anvendes heuristikker som LKH.
Udnyt problemstruktur: euklidiske og metriske tilfælde tillader stærke heuristikker og approximationer.
Præprocessering og rensning af data (fjerne overflødige knuder, symmetrisering i tilfælde af små asymmetrier) kan hjælpe.
Benchmark og test på standarddatasæt (fx TSPLIB) for at sammenligne metoder.

Anvendelser

TSP er mere end et akademisk puslespil: det bruges som model eller delkomponent i adskillige praktiske problemer:

Ruteplanlægning og logistik
Produktionsopsætning og boresekvenser i fabrikation
Planlægning af inspektioner eller vedligeholdelsesruter
Genom-sammenkædning / DNA-sekventering (nær beslægtede problemer)
Robotnavigation og dronetilstrømning

Afsluttende bemærkninger

TSP illustrerer et vigtigt princip i optimering: selv simple formuleringer kan føre til store beregningsmæssige udfordringer. Kombinationen af teoretisk indsigt (kompleksitetsresultater, approximationsteori) og praktiske metoder (heuristikker, branch‑and‑cut, specialiserede solvere) gør TSP til en central case i både forskning og industri.

En sælger ønsker at besøge alle byerne A, B, C og D. Hvad er den bedste måde at gøre dette på (billigste flybilletter og minimal rejsetid)?

Optimal rute for en sælger, der besøger de 15 største byer i Tyskland. Den viste rute er den korteste af de 43.589.145.600 mulige ruter.

Angivelse af problemet

Problemet med den rejsende sælger beskriver en sælger, der skal rejse mellem N byer. I hvilken rækkefølge han gør det, er han ligeglad med, så længe han besøger hver by én gang i løbet af sin rejse og slutter der, hvor han var først. Hver by er forbundet med andre nærliggende byer, eller knudepunkter, med fly, vej eller jernbane. Hver af disse forbindelser mellem byerne har en eller flere vægte (eller omkostninger) tilknyttet. Omkostningerne beskriver, hvor "vanskeligt" det er at krydse denne kant i grafen, og kan f.eks. angives ved prisen på en flybillet eller en togbillet, eller måske ved længden af kanten eller den tid, der kræves for at gennemføre gennemkørslen. Sælgeren ønsker at holde både rejseomkostningerne og den tilbagelagte afstand så lav som muligt.

Traveling Salesman-problemet er typisk for en stor klasse af "svære" optimeringsproblemer, som har fascineret matematikere og dataloger i årevis. Det vigtigste er, at det har anvendelser inden for videnskab og teknik. Ved fremstillingen af et printkort er det f.eks. vigtigt at bestemme den bedste rækkefølge, i hvilken en laser skal bore tusindvis af huller. En effektiv løsning på dette problem reducerer produktionsomkostningerne for producenten.

Sværhedsgrad

Generelt er problemet med den omrejsende sælger svært at løse. Hvis der findes en måde at opdele problemet i mindre delproblemer, vil disse delproblemer være mindst lige så komplekse som det oprindelige problem. Det er det, som dataloger kalder NP-hårde problemer.

Mange mennesker har undersøgt dette problem. Den nemmeste (og dyreste løsning) er at prøve alle muligheder. Problemet med dette er, at man for N byer har (N-1) faktorielle muligheder. Det betyder, at der for kun 10 byer er over 180.000 kombinationer at prøve (da startbyen er defineret, kan der være permutationer på de resterende ni). Vi tæller kun halvdelen, da hver rute har en tilsvarende rute i omvendt retning med samme længde eller omkostninger. 9! / 2 = 181 440

Der kan findes nøjagtige løsninger på problemet ved hjælp af branch and bound-algoritmer. Dette er i øjeblikket muligt for op til 85 900 byer.
Heuristiske metoder anvender et sæt vejledende regler for valg af det næste knudepunkt. Men da heuristikker resulterer i tilnærmelser, vil de ikke altid give den optimale løsning, selv om tilladelige heuristikker af høj kvalitet kan finde en brugbar løsning på en brøkdel af den tid, der kræves til en fuldstændig brute force-analyse af problemet. Et eksempel på en heuristik for et knudepunkt kunne være en summering af, hvor mange ubesøgte knudepunkter der er "tæt på" et forbundet knudepunkt. Dette kunne tilskynde sælgeren til at besøge en gruppe af knuder i nærheden af hinanden, inden han går videre til en anden naturlig klynge i grafen. Se Monte Carlo-algoritmer og Las Vegas-algoritmer

Spørgsmål og svar

Spørgsmål: Hvad er det rejsende sælgerproblem?

A: Traveling Salesman Problem (TSP) er et klassisk algoritmisk problem inden for datalogi og operationsforskning. Det fokuserer på optimering, hvor bedre løsninger ofte betyder billigere, kortere eller hurtigere løsninger.

Spørgsmål: Hvordan udtrykkes TSP?

Svar: TSP udtrykkes lettest som en graf, der beskriver placeringen af et sæt knudepunkter.

Spørgsmål: Hvem definerede først TSP?

Svar: Traveling Salesman-problemet blev defineret i 1800-tallet af den irske matematiker W. R. Hamilton og af den britiske matematiker Thomas Kirkman.

Spørgsmål: Hvem undersøgte det yderligere i 1930'erne?

Svar: I 1930'erne studerede matematikerne Karl Menger i Wien og Harvard det yderligere.

Spørgsmål: Hvad introducerede Hassler Whitney kort efter?

Svar: Hassler Whitney på Princeton University introducerede navnet "traveling salesman problem" kort efter definitionen af det.

Spørgsmål: Hvad betyder "bedre løsning" i denne sammenhæng?

A: I denne sammenhæng betyder bedre løsning ofte en løsning, der er billigere, kortere eller hurtigere.

Spørgsmål: Hvilken algoritme blev af Menger betragtet som indlysende, da han studerede TSP?

Svar: Menger betragtede en indlysende brute-force-algoritme som indlysende, da han studerede TSP, og bemærkede, at brugen af nærmeste nabo heuristik ikke altid giver optimale resultater.