Reisijate müügimehe probleem (sageli ka TSP) on klassikaline algoritmiline probleem arvutiteaduse ja operatsioonide uurimise valdkonnas. See keskendub optimeerimisele. Selles kontekstis tähendab parem lahendus sageli lahendust, mis on odavam, lühem või kiirem. TSP on matemaatiline probleem. Seda on kõige lihtsam väljendada graafina, mis kirjeldab sõlmede hulga asukohti ja servasid nende vahel – tavaliselt iga kahe sõlme vahel on määratud kaugus või maksumus ja eesmärk on leida kõige odavam sulgev teekond, mis külastab iga sõlme täpselt üks kord ja naaseb alguspunkti.

Määratlus ja variandid

Põhivormis: antud n punkti (sõlme) ja paariskaugused, leida lühim ühemine tsükkel, mis läbib kõik punktid täpselt üks kord. TSP-l on mitu levinud varianti:

  • Sümmeetriline TSP: kaugus i→j on sama kui j→i.
  • Asümmeetriline TSP (ATSP): suundade kaupa erinevad kulud; oluline logistikaprobleemides ja marsruutide planeerimisel, kus teed võivad olla ühesuunalised.
  • Metric / euclidean TSP: kaugused rahuldavad kolmnurga ebavõrdsust (triangle inequality); vastavas ruumis (nt Eukleidese ruumis) on eraldi teoreetilised tulemused ja heuristikatel paremad garantiid.

Ajalugu ja tähendused

Reisijate probleemi määratlesid 1800. aastatel iiri matemaatik W. R. Hamilton ja briti matemaatik Thomas Kirkman. Hamiltoni Icosian Game oli meelelahutuslik mõistatus, mis põhines Hamiltoni tsükli leidmisel. TSP üldvormi näib olevat esimest korda uurinud matemaatikud 1930. aastatel Viinis ja Harvardis, eelkõige Karl Menger. Menger määratleb probleemi, kaalub ilmset toorest algoritmi ja täheldab lähima naabri heuristika mitteoptimaalsust:

Tähistame sõnumitooja probleemiga (kuna praktikas peaks seda küsimust lahendama iga postiljon, igatahes ka paljud reisijad) ülesannet leida fintsele hulgale punktidele, mille paariskaugused on teada, kõige lühem marsruut, mis ühendab neid punkte. Loomulikult on see ülesanne lahendatav lõplikult paljude katsetega. Reeglid, mis viiksid katsete arvu alla antud punktide permutatsioonide arvu, ei ole teada. Reegel, et kõigepealt tuleb minna alguspunktist lähimasse punkti, seejärel sellele lähimasse punkti jne, ei anna üldiselt lühimat marsruuti.

Hassler Whitney Princetoni ülikoolis võttis varsti pärast seda kasutusele rändmüüja probleemi. Alates 1950.–1960. aastatest hakkas TSPist huvi tundma ka operatsioonide uurimise ja lineaarprogrammeerimise uurijad, sest probleemi optimeerimiseks arendati efektiivseid täisarvulise programmeerimise ja lõikemenetlustega lahendeid.

Kompleksus ja teoreetilised tulemused

TSP optimeerimisvariant on NP‑raske (NP-hard) ning otsustusvariant — kas leidub teekond, mille pikkus on ≤ K — on NP‑täielik (NP-complete). See tähendab, et ühegi teadaoleva polünoomse aja algoritmi abil ei saa lahendada kõiki juhte efektiivselt (kui eeldada, et P ≠ NP). Siiski on mitmeid olulisi teoreetilisi ja praktilisi saavutusi:

  • Täpsed algoritmid: otsin läbi kõik permutatsioonid annab O(n!) keerukuse; Held–Karp dünaamiline programmeerimine lahendab probleemi ajas O(n^2 2^n) ja ruumis O(n 2^n).
  • Approximation ja PTAS: metric TSP puhul on olemas Christofidesi algoritm, mis annab 1.5‑kordse lähenduse sümmeetrilisele metric TSP‑le. Euclidese TSP jaoks on olemas polünomiaalse aja lähendusskeemid (PTAS), mille töötasid välja näiteks Arora ja Mitchell.

Praktilised lahendused ja heuristikad

Enamiku praktiliste rakenduste puhul on eesmärk saada hea (kui mitte absoluutne optimaalsus) lahendus kiirelt. Levinud lähenemised:

  • Brute force ja täpsed meetodid: lõikemenetlus (branch-and-cut), lõiketehnikaid ja täisarvulist programmeerimist kombineerivad lahendajad (nt Concorde) leiavad optimaalseid lahendusi paljude reaalse maailma ja testandmete puhul.
  • Dünaamiline programmeerimine: Held–Karp annab täpse lahendi väiksemate n‑i puhul ja kasutatakse ka teoreetilise aluspõhjana.
  • Simplistlikud heuristikad: lähima naabri (nearest neighbor), greedy, erinevad sisestusheuristikad — kiireid ja lihtsaid, kuid mitte alati kvaliteetseid.
  • Paigutuseparandused (local search): 2‑opt, 3‑opt, k‑opt, Lin–Kernighan ja nende hübriidid on väga tõhusad praktiliselt: algne marsruut parandatakse korduvate kohalike muutustega.
  • METAHEURISTIKAD: geneetilised algoritmid, simuleeritud annealing, tabu search ja ant colony optimization annavad sageli väga häid lahendusi suurtele instantsidele.

Rakendused

TSP ja selle variandid ilmnevad mitmes reaalse elu ülesandes:

  • transport ja logistika (pakkide kättetoimetamine, teenindusretked),
  • tööstus (laua- ja trükkplaadi tootmine, paigutusprobleemid),
  • robotite marsruudiplaneerimine ja marsruutide optimeerimine,
  • genoomika (DNA järjestuste kokkupanek kui järjestamise ülesanne),
  • võrgustike ja graafianalüüsi testjuhtumid.

Praktilised näpunäited

  • Kui probleem on väike (n kuni paar kümmet), võivad täpsed meetodid olla teostatavad.
  • Keskmise ja suurema suuruse puhul kombineeritakse heuristikat ja lokaalset parandust, et saada kiiresti kõrge kvaliteediga vastuseid.
  • Kui andmed rahuldavad kolmnurga tingimust või on Eukleidese kaugused, tasub kasutada Christofidesi või PTAS‑lähenemisi ning Lin–Kernighani tüüpi parandusmeetodeid.

TSP on nii teoreetiliselt huvitav kui ka praktiliselt väga kasulik uurimisvaldkond, sest see ühendab kombinatoorse optimeerimise, algorütmide uurimise ja praktilised rakendused logistikas ning inseneriteaduses. Uued lähenemised, kiiremad arvutid ja spetsiaalsed lahendajad võimaldavad lahendada järjest keerukamaid juhtumeid, kuid üldine probleemi raskus muudkui inspireerib uusi meetodeid ja teooriaid.