Matkamyyjäongelma (usein TSP) on klassinen algoritminen ongelma tietojenkäsittelytieteen ja operaatiotutkimuksen alalla. Se keskittyy optimointiin. Tässä yhteydessä parempi ratkaisu tarkoittaa usein ratkaisua, joka on halvempi, lyhyempi tai nopeampi. TSP on matemaattinen ongelma. Se on helpointa ilmaista graafina, joka kuvaa solmujen joukon sijainteja.

Määritelmä

TSP voidaan muotoilla seuraavasti: annettu täydellinen painotettu graafi, jossa solmut vastaavat käyntikohteita ja kaarien painot edustavat välimatkoja tai kustannuksia, etsitään lyhin mahdollinen suljettu kiertokäynti (tour), joka käy jokaisessa solmussa täsmälleen kerran ja palaa lähtösolmuun. Erityistapauksia ovat:

  • Sykleihin liittyvä (symmetrinen) TSP: etäisyys i→j on sama kuin j→i.
  • Asymmetrinen TSP: etäydet voivat poiketa suunnasta riippuen.
  • Metristen tapausten: etäisyydet noudattavat kolmion epäyhtälöä (triangle inequality), mikä helpottaa approksimaatioita.

Kompleksisuus

TSP on laskennallisesti vaikea: optimointimuotona se on NP‑kovaa (NP-hard) eli ei tiedetä polynomiajassa ratkeavaa algoritmia yleiselle tapauk­selle. Päätösmuoto "onko kiertokäynti, jonka pituus ≤ K, olemassa?" on NP‑täydellinen. Tämän vuoksi tutkitaan sekä täsmällisiä menetelmiä, jotka sopivat vain pienempiin tai erityisrakenteisiin instanceihin, että heuristiikkoja ja approksimaatioita suurten tapausten käsittelyyn.

Ratkaisumenetelmät

Ratkaisut voidaan jakaa karkeasti täsmällisiin ja heuristisiin menetelmiin.

Täsmälliset menetelmät

  • Brute force: kaikki permutaatiot — toimii vain hyvin pienille n (kertaluvun kasvaessa factorialisesti).
  • Held–Karpin dynaaminen ohjelmointi: parantaa eksponenttiseen aikaan 2^n * n^2 luokkaan, käytännöllinen vain keskisuurille n.
  • Branch-and-bound ja leikkausmenetelmät (cutting planes): yhdistelmärakenne, jota käytetään suuren mittakaavan eksakteissa ratkaisuissa; Concorde on tunnettu käytännön optimointiohjelma, joka hyödyntää monia näistä tekniikoista.

Heuristiikat ja metaheuristiikat

  • Lähimmän naapurin heuristiikka (nearest neighbor) – nopea, mutta ei takaa hyvää tulosta.
  • Paikkausparannukset: 2-opt, 3-opt ja Lin–Kernighan – tehokkaita käytännössä ja usein tuottavat lähellä optimaalista ratkaisua.
  • Metaheuristiikat: simuloitu jäähdytys, geneettiset algoritmit, tabu search ja ant colony optimization — soveltuvat suurille reuna-arvoille ja reaalimaailman ongelmiin.

Approksimaatiot ja erikoistapaukset

  • Christofidesin algoritmi tarjoaa 1.5‑kertaiseen hyvyyteen takuun symmetrisessä metrisessä TSP:ssä.
  • Euclidean TSP (pisteet tasossa, euklidinen etäisyys) hyväksyy polynomiajassa toimivan PTAS:n (esimerkiksi Arora, Mitchell), eli voi löytää arbitrarily lähellä optimaalista ratkaisua annettuun tarkkuuteen.

Historia

Irlantilainen matemaatikko W. R. Hamilton ja brittiläinen matemaatikko Thomas Kirkman määrittelivät eräänlaisia kiertotehtäviä 1800‑luvulla. Hamiltonin Icosian-peli oli vapaa-ajan pulma, joka perustui Hamilton-syklin löytämiseen. Matemaatikot tutkivat TSP:n yleistä muotoa ensimmäisen kerran 1930‑luvulla Wienissä ja Harvardissa, erityisesti Karl Menger. Menger määrittelee ongelman, tarkastelee ilmeistä raa'an voiman algoritmia ja havaitsee, että lähimmän naapurin heuristiikka ei ole optimaalinen:

Kutsumme lähetti-ongelmaksi (koska käytännössä tämä kysymys pitäisi ratkaista jokaisen postinkantajan, joka tapauksessa myös monien matkustajien, toimesta) tehtävää löytää fihtyneelle määrälle pisteitä, joiden pareittaiset etäisyydet tunnetaan, lyhin reitti, joka yhdistää nämä pisteet. Tämä ongelma on tietenkin ratkaistavissa äärellisen monella kokeella. Sääntöjä, joiden avulla kokeilujen määrä olisi pienempi kuin annettujen pisteiden permutaatioiden määrä, ei tunneta. Sääntö, jonka mukaan lähtöpisteestä on ensin mentävä lähimpään pisteeseen, sitten tätä lähimpään pisteeseen jne., ei yleensä johda lyhimpään reittiin.

Hassler Whitney Princetonin yliopistossa esitteli pian tämän jälkeen kiertävän myyntimiehen ongelman. 1900‑luvulla ongelmaan kehitettiin sekä teoreettisia että käytännönläheisiä työkaluja: dynaaminen ohjelmointi (Held ja Karp), leikkausmenetelmät ja tehokkaat paikalliset parannusmenetelmät kuten Lin–Kernighan. Viime vuosikymmeninä on kehitetty huippuluokan optimointiohjelmistoja, jotka pystyvät ratkaisemaan erittäin suuria reaalimaailman instansseja eksaktisti tai lähes eksaktisti.

Sovellukset

TSP‑tyyppisiä ongelmia esiintyy monissa käytännön tilanteissa:

  • logistiikka ja reititys (pakettienjakelu, huoltokäynnit),
  • valmistusprosesseissa, esim. teollisuusporauksen ja leikkausreittien optimointi,
  • mikropiirien valmistuksessa rei'itysjärjestykset,
  • bioinformatiikassa, esimerkiksi tiettyjen järjestelyongelmien likimääräisissä mallinnuksissa,
  • astronomiassa ja kenttämittauksissa, missä on optimoitava havaintojärjestys.

Käytännön huomioita

Vaikka TSP on teoreettisesti haastava, käytännön instanssit usein ratkaistaan hyvin yhdistämällä heuristiikat, paikalliset parannukset ja eksaktit algoritmit. Usein riittää lähellä optimaalinen ratkaisu lyhyessä ajassa. Tutkijat ja insinöörit valitsevat menetelmän ongelman koon ja vaaditun ratkaisun tarkkuuden mukaan.