Handelsreisendeproblemet

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.

Det reisende kjøperproblemet (TPP) og rutingen av kjøretøyet (VRP) er begge generaliseringer av TSP.

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

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

TSP har flere applikasjoner til og med i sin reneste formulering, for eksempel planlegging, logistikk og produksjon av integrert kretser. 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. I mange applikasjoner kan det pålegges ytterligere begrensninger som begrensede ressurser eller tidsvinduer.