Rändmüüja probleem (TSP): definitsioon, ajalugu ja lahendused

Rändmüüja probleem (TSP): definitsioon, ajalugu ja lahendused — ülevaade algoritmidest, heuristikast ja praktilistest optimeerimislahendustest.

Autor: Leandro Alegsa

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.

Müügimees soovib külastada kõiki linnu A, B, C ja D. Milline on parim viis seda teha (kõige odavamad lennupiletid ja minimaalne sõiduaeg)?Zoom
Müügimees soovib külastada kõiki linnu A, B, C ja D. Milline on parim viis seda teha (kõige odavamad lennupiletid ja minimaalne sõiduaeg)?

Müügimehe optimaalne marsruut, mis külastab Saksamaa 15 suurimat linna. Näidatud marsruut on 43 589 145 600 võimalikust marsruudist kõige lühem.Zoom
Müügimehe optimaalne marsruut, mis külastab Saksamaa 15 suurimat linna. Näidatud marsruut on 43 589 145 600 võimalikust marsruudist kõige lühem.

William Rowan HamiltonZoom
William Rowan Hamilton

Probleemi esitamine

Müügimehe probleem kirjeldab müügimeest, kes peab reisima N linna vahel. See, millises järjekorras ta seda teeb, ei ole talle oluline, kui ta külastab iga linna üks kord oma reisi jooksul ja lõpetab seal, kus ta alguses oli. Iga linn on ühendatud teiste lähedalasuvate linnadega ehk sõlmpunktidega kas lennuki, maantee või raudtee kaudu. Igale linnade vahelisele ühendusele on lisatud üks või mitu kaalu (või kulu). Kulu kirjeldab, kui "raske" on seda serva graafil läbida, ja see võib olla antud näiteks lennupileti või rongipileti maksumuse, ehk siis serva pikkuse või läbimiseks vajaliku aja järgi. Müügimees soovib hoida nii reisikulud kui ka läbitud vahemaa võimalikult madalad.

Reisiv müügimehe probleem on tüüpiline suurest klassist "rasketest" optimeerimisprobleemidest, mis on matemaatikuid ja arvutiteadlasi juba aastaid intrigeerinud. Kõige tähtsam on see, et sellel on rakendusi teaduses ja tehnikas. Näiteks trükkplaadi valmistamisel on oluline määrata parim järjekord, milles laser puurib tuhandeid auke. Selle probleemi tõhus lahendus vähendab tootja tootmiskulusid.

Raskusaste

Üldiselt on rändmüüja probleemi raske lahendada. Kui seda probleemi on võimalik jagada väiksemateks komponentprobleemideks, siis on need komponendid vähemalt sama keerulised kui algne probleem. Seda nimetavad arvutiteadlased NP-raskeks probleemiks.

Paljud inimesed on seda probleemi uurinud. Kõige lihtsam (ja kõige kallim) lahendus on lihtsalt proovida kõiki võimalusi. Probleemiks on see, et N linna puhul on (N-1) faktoriaalset võimalust. See tähendab, et ainult 10 linna puhul on üle 180 tuhande kombinatsiooni, mida proovida (kuna alguslinn on määratud, võib ülejäänud üheksa linna kohta olla permutatsioone). Me loeme ainult pooled, sest igal marsruudil on tagurpidi sama pikk või sama maksumusega võrdne marsruut. 9! / 2 = 181 440

  • Probleemi täpseid lahendusi saab leida, kasutades haru ja piirangute algoritme. Praegu on see võimalik kuni 85 900 linna puhul.
  • Heuristilised lähenemisviisid kasutavad järgmise sõlme valimiseks suunavaid reegleid. Kuid kuna heuristikud on ligikaudsed, ei anna nad alati optimaalset lahendust, kuigi kvaliteetsed vastuvõetavad heuristikud võivad leida kasuliku lahenduse murdosa ajast, mis on vajalik probleemi täielikuks jõhkraks lahendamiseks. Üks näide heuristikast oleks näiteks summeerimine selle kohta, mitu külastamata sõlme on seotud sõlme "lähedal". See võiks julgustada müüjat külastama koos klastrisse koondatud lähedaste sõlmede rühma, enne kui ta liigub graafi teise loomuliku klastri juurde. Vt Monte Carlo algoritmid ja Las Vegase algoritmid.

Küsimused ja vastused

K: Mis on rändkaupmehe probleem?


V: Reisijate müügimehe probleem (TSP) on klassikaline algoritmiline probleem arvutiteaduse ja operatsioonide uurimise valdkonnas. See keskendub optimeerimisele, kusjuures paremad lahendused tähendavad sageli odavamaid, lühemaid või kiiremaid lahendusi.

K: Kuidas on TSP väljendatud?


V: TSP on kõige lihtsamini väljendatav graafina, mis kirjeldab sõlmede kogumi asukohti.

K: Kes määratles esimesena TSP?


V: Reisivate müügimeeste probleemi defineerisid 1800. aastatel iiri matemaatik W. R. Hamilton ja briti matemaatik Thomas Kirkman.

K: Kes uuris seda 1930. aastatel edasi?


V: 1930. aastatel uurisid seda edasi Viinis ja Harvardis töötanud matemaatikud Karl Menger.

K: Mida tutvustas Hassler Whitney varsti pärast seda?


V: Hassler Whitney Princetoni ülikoolis võttis varsti pärast selle määratlust kasutusele nime "rändmüüja probleem".

K: Mida tähendab selles kontekstis "parem lahendus"?


V: Selles kontekstis tähendab parem lahendus sageli lahendust, mis on odavam, lühem või kiirem.

K: Millist algoritmi pidas Menger TSP-d uurides ilmselgeks?


V: Menger pidas TSP-i uurides ilmselget toorest algoritmi ja täheldas, et lähima naabri heuristika kasutamine ei anna alati optimaalset tulemust.


Otsige
AlegsaOnline.com - 2020 / 2025 - License CC3