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

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

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 fintligt 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.

Spørgsmål og svar

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

Spørgsmål: Hvordan udtrykkes TSP?

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

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

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

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

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

Søg efter bogstav