Redigerer Handelsreisendeproblemet

[[Fil:GLPK_solution_of_a_travelling_salesman_problem.svg|miniatyr|Løsning på et handelsreisendeproblem: den svarte linjen viser kortest mulig sløyfe som forbinder hver prikk.]]
'''Handelsreisendeproblemet '''(engelsk The travelling salesman problem eller TSP) stiller følgende spørsmål: «Gitt en liste over byer og avstanden mellom byene, hva er den kortest mulige ruten som besøker hver by nøyaktig en gang og returnerer til opprinnelsesbyen?» Det er et [[NP-hardt]] problem i kombinatorisk optimalisering, viktig i teoretisk informatikk og [[operasjonsanalyse]].

Problemet ble først formulert i 1930 og er et av de mest intensivt studerte problemene innen optimalisering. Den brukes som en referanse for mange optimaliseringsmetoder. Selv om problemet er beregningsmessig vanskelig, er mange heuristikker og nøyaktige algoritmer kjent, slik at noen forekomster med titusenvis av byer kan løses fullstendig, og til og med problemer med millioner av byer kan tilnærmes innen en liten brøkdel av 1 %.<ref>{{Kilde www|url=http://www.math.uwaterloo.ca/tsp/world/|tittel=World Traveling Salesman Problem|besøksdato=2021-01-16|verk=www.math.uwaterloo.ca}}</ref>

==Problemformulering==
Som et [[grafteori|graf]]-problem kan handelsreisendeproblemet modelleres som en ''urettet vektet graf'', der byene representeres av [[Node (grafteori)|nodene]], veiene imellom dem av [[Kant (grafteori)|kanter]] og avstandene imellom byene assosiert med en vei vekten til hver kant. Ofte settes grafen opp som [[komplett graf|komplett]], dvs. det finnes en kant mellom alle nodepar; eventuelt kan man gjøre grafen komplett ved å legge på kanter med høye verdier der de mangler. Problemet settes så opp som et [[optimaliseringsproblem]], der man starter og slutter på en gitt node etter å ha besøkt alle andre noder nøyaktig én gang, og man ønsker å minimere den totale kostnaden ved å reise denne ruten.

===Ulike versjoner===
Man kan klassifisere ulike versjoner av problemet basert på ulike betingelser.<ref name=matai>{{kilde artikkel
| forfatter1=Rajesh Matai
| forfatter2=Surya Prakash Singh
| forfatter3=Murari Lal Mittal
| tittel=Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches
| publikasjon=Traveling Salesman Problem, Theory and Applications
| år=2010
| url=https://www.intechopen.com/chapters/12736}}</ref>
* ''Symmetrisk TSP'' defineres som en graf der kanten <math>(n_1, n_2)</math> har lik vekt som kanten <math>(n_2, n_1)</math>, altså der det koster like mye å reise fra én by til en annen som motsatt vei
* ''Asymmetrisk TSP'' defineres som en graf der kanten <math>(n_1, n_2)</math> har ulik vekt som kanten <math>(n_2, n_1)</math>, altså der det å reise fra én by til en annen koster noe annet enn motsatt vei
* ''Multihandelsreisendeproblemt'' går ut på å finne en mengde sykler som tilsammen dekker hele grafen uten å besøke noen node mer enn én gang, altså der man lar flere handelsmenn reise ut fra samme by, hver sin vei, og fordeler det å besøke alle byene seg imellom. Versjoner av denne kan enten la alle starte i samme by, eller i hver sin, samt eventuelt med en kostnad assosiert pr handelsreisende som benyttes.

==Kompleksitetsanalyse==
I [[kompleksitetsteori]] tilhører [[avgjørelsesproblem|avgjørelsesversjonen]] av TSP (hvor lengden L er gitt, oppgaven å bestemme om grafen har en runde på høyst L) til klassen av [[NP-komplett]]e problemer. Dermed er det mulig at [[Det beste, verste og gjennomsnittlige tilfelle|beste tilfelle]] [[Tidskompleksitet|kjøretid]] for en hvilken som helst algoritme for TSP øker superpolynomielt (men ikke mer enn eksponentielt) med antall byer.

Avgjørelsesproblemet kan reduseres til spørsmålet om det finnes en [[Hamiltonvei|Hamiltonsyklus]] i grafen ved å la hver kant ha vekten én. I og med at Hamiltonsyklusproblemet er [[NP-hardt]], vil TSP være minst like vanskelig og er dermed også NP-hardt. På en annen side vil man, gitt en bestemt sti, verifisere at denne har en viss vekt og besøker alle noder nøyaktig én gang, hvilket gjør at det (i likhet med Hamiltonsyklusproblemet) er [[NP-komplett]].

==Generaliseringer==
Det reisende kjøperproblemet (TPP) og rutingen av kjøretøyet (VRP) er begge generaliseringer av TSP. Spesielt kan VRP sees på som multihandelsreisendeproblemet, men med begrensninger på tiden hver handelsreisende kan bruke samt på hvor mange byer (i form av kapasitet) hver kan besøke.<ref name=matai />

==Heltallsformulering==
Både det symmetriske handelsreisendeproblemet, det asymmetriske handelsreisendeproblemet og multihandelsreisendeproblemet kan settes opp som et problem som kan løses ved hjelp av [[heltallsprogrammering]]. Her knyttes det binære variabler <math>x_{ij}</math> til hver kant i grafen, gitt tilsvarende kostnad <math>c_{ij}</math>, der <math>x_{ij}</math> settes til 1 hvis kanten brukes og 0 ellers. Det symmetriske problemet kan settes opp som følger:<ref name="matai" /> Minimer

<math>
\sum_{i < j} c_{ij} x_{ij}
</math>

under forutsetning av at

<math>
\sum_{i < j} x_{ij} + \sum_{k > i} x_{ik} = 2
</math>

altså slik at det benyttes én vei inn til hver by, og én vei ut av hver by,

<math>
\sum_{i, j \in S} x_{ij} \leq |S| - 1 \qquad \forall S \subset V, 3 \leq |S| \leq n - 3  
</math>

der <math>S</math> er en subgraf av den underliggende grafen <math>V</math>; altså slik at det ikke dannes egne disjunkte sykler som tilsammen dekker hele grafen, og

<math>
x_{ij} = 0 \text{ eller } 1 \qquad \text{for alle kanter (i, j)}
</math>

Det asymmetriske handelsreisendeproblemet og multihandelsreisendeproblemet kan settes opp på en lignende måte.

==Anvendelser==
TSP har flere applikasjoner til og med i sin reneste formulering, for eksempel planlegging, [[logistikk]] og produksjon av [[integrert krets]]er. Litt modifisert ser det ut som et underproblem i mange områder, for eksempel [[DNA-sekvensering]]. I disse applikasjonene representerer konseptbyen for eksempel kunder, loddepunkter eller DNA-fragmenter, og konseptavstanden representerer reisetid eller kostnad, eller et likhetsmål mellom DNA-fragmenter. TSP vises også i astronomi, ettersom astronomer som observerer mange kilder vil ønske å minimere tiden brukt på å flytte teleskopet mellom kildene; i slike problemer kan TSP være innebygd i et optimalt kontrollproblem.<ref>{{Kilde artikkel|tittel=An Optimal Control Theory for the Traveling Salesman Problem and Its Variants|publikasjon=arXiv:2005.03186 [cs, math]|url=http://arxiv.org/abs/2005.03186|dato=2020-05-06|fornavn=I. M.|etternavn=Ross|etternavn2=Proulx|fornavn2=R. J.|etternavn3=Karpenko|fornavn3=M.|besøksdato=2021-01-16}}</ref><ref>{{Kilde artikkel|tittel=Autonomous UAV Sensor Planning, Scheduling and Maneuvering: An Obstacle Engagement Technique|publikasjon=2019 American Control Conference (ACC)|doi=10.23919/ACC.2019.8814474|url=https://ieeexplore.ieee.org/document/8814474/|dato=juli 2019|fornavn=I. M.|etternavn=Ross|etternavn2=Proulx|fornavn2=R. J.|etternavn3=Karpenko|fornavn3=M.|utgiver=IEEE|sider=65–70|isbn=978-1-5386-7926-5|besøksdato=2021-01-16}}</ref> I mange applikasjoner kan det pålegges ytterligere begrensninger som begrensede ressurser eller tidsvinduer.

== Referanser ==
<references />

{{Autoritetsdata}}

[[Kategori:Grafalgoritmer]]
[[Kategori:Matematiske problemer]]