Kauppamatkustajan ongelma

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.

Irlantilainen matemaatikko W. R. Hamilton ja brittiläinen matemaatikko Thomas Kirkman määrittelivät kiertävän myyntimiehen ongelman 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ää ﬁhtyneelle 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.

William Rowan Hamilton

Myyjä haluaa vierailla kaikissa kaupungeissa A, B, C ja D. Mikä on paras tapa tehdä tämä (halvimmat lentoliput ja mahdollisimman lyhyt matka-aika)?

Saksan 15 suurimmassa kaupungissa vierailevan myyntimiehen optimaalinen reitti. Näytetty reitti on lyhin 43 589 145 600 mahdollisesta reitistä.

Ongelman toteaminen

Matkamyyjäongelma kuvaa myyntimiestä, jonka on matkustettava N kaupungin välillä. Hän ei välitä siitä, missä järjestyksessä hän matkustaa, kunhan hän käy jokaisessa kaupungissa kerran matkansa aikana ja päätyy sinne, missä hän oli aluksi. Kukin kaupunki on yhteydessä muihin läheisiin kaupunkeihin eli solmukohtiin lentokoneella tai maanteitse tai rautateitse. Jokaiseen kaupunkien väliseen yhteyteen liittyy yksi tai useampi paino (tai kustannus). Kustannus kuvaa sitä, kuinka "vaikeaa" on kulkea kyseisen reunan kautta graafissa, ja se voidaan antaa esimerkiksi lento- tai junalipun hinnan, reunan pituuden tai kulkemiseen kuluvan ajan perusteella. Myyjä haluaa pitää sekä matkakustannukset että matkan pituuden mahdollisimman pieninä.

Matkamyyjäongelma on tyypillinen lukuisa joukko "vaikeita" optimointiongelmia, jotka ovat kiehtoneet matemaatikkoja ja tietojenkäsittelytieteilijöitä jo vuosia. Tärkeintä on, että sillä on sovelluksia luonnontieteissä ja tekniikassa. Esimerkiksi piirilevyn valmistuksessa on tärkeää määrittää paras järjestys, jossa laser poraa tuhansia reikiä. Tehokas ratkaisu tähän ongelmaan vähentää valmistajan tuotantokustannuksia.

Vaikeusaste

Yleisesti ottaen kiertävän myyntimiehen ongelma on vaikea ratkaista. Jos ongelma voidaan jakaa pienempiin osaongelmiin, osaongelmat ovat vähintään yhtä monimutkaisia kuin alkuperäinen ongelma. Tietojenkäsittelytieteilijät kutsuvat tätä NP-vaikeaksi ongelmaksi.

Monet ihmiset ovat tutkineet tätä ongelmaa. Helpoin (ja kallein) ratkaisu on yksinkertaisesti kokeilla kaikkia mahdollisuuksia. Ongelmana tässä on se, että N kaupungilla on (N-1) faktoriaalisia mahdollisuuksia. Tämä tarkoittaa sitä, että vain 10 kaupungille on yli 180 tuhatta yhdistelmää kokeiltavana (koska aloittava kaupunki on määritelty, jäljellä oleville yhdeksälle kaupungille voi olla permutaatioita). Laskemme vain puolet, koska jokaisella reitillä on yhtä pitkä tai samanhintainen reitti toisinpäin. 9! / 2 = 181 440

Ongelmaan voidaan löytää täsmällisiä ratkaisuja käyttämällä haarautumisalgoritmeja. Tämä on tällä hetkellä mahdollista jopa 85 900 kaupungille.
Heuristiikkalähestymistavat käyttävät joukon ohjaavia sääntöjä seuraavan solmun valintaan. Koska heuristiikat ovat kuitenkin likiarvoja, ne eivät aina anna optimaalista ratkaisua, vaikka laadukkaat hyväksyttävät heuristiikat voivat löytää käyttökelpoisen ratkaisun murto-osassa ajasta, joka tarvitaan ongelman täydelliseen raa'an voiman käyttöön. Esimerkki heuristiikasta solmulle olisi yhteenlasku siitä, kuinka monta vierailematonta solmua on "lähellä" yhdistettyä solmua. Tämä voisi kannustaa myyntimiestä vierailemaan ryhmässä lähekkäin olevia solmuja, jotka on klusteroitu yhteen, ennen kuin hän siirtyy graafin toiseen luonnolliseen klusteriin. Katso Monte Carlo -algoritmit ja Las Vegas -algoritmit.

Kysymyksiä ja vastauksia

K: Mikä on kiertävän myyntimiehen ongelma?

V: Traveling Salesman Problem (TSP) on klassinen algoritminen ongelma tietojenkäsittelytieteen ja operaatiotutkimuksen alalla. Siinä keskitytään optimointiin, jossa paremmat ratkaisut tarkoittavat usein halvempia, lyhyempiä tai nopeampia ratkaisuja.

K: Miten TSP ilmaistaan?

V: TSP on helpointa ilmaista graafina, joka kuvaa solmujen sijainteja.

K: Kuka määritteli ensimmäisenä TSP:n?

V: Irlantilainen matemaatikko W. R. Hamilton ja brittiläinen matemaatikko Thomas Kirkman määrittelivät kiertävän myyntimiehen ongelman 1800-luvulla.

K: Kuka tutki sitä tarkemmin 1930-luvulla?

V: 1930-luvulla matemaatikot Karl Menger Wienissä ja Harvardissa tutkivat sitä tarkemmin.

K: Mitä Hassler Whitney esitteli pian sen jälkeen?

V: Hassler Whitney Princetonin yliopistossa otti käyttöön nimen "travelling salesman problem" pian sen määrittelyn jälkeen.

K: Mitä "parempi ratkaisu" tarkoittaa tässä yhteydessä?

V: Tässä yhteydessä parempi ratkaisu tarkoittaa usein ratkaisua, joka on halvempi, lyhyempi tai nopeampi.

K: Mitä algoritmia Menger piti ilmeisenä tutkiessaan TSP:tä?

V: Menger piti TSP:tä tutkiessaan ilmeisenä raakaa algoritmia ja havaitsi, että lähimmän naapurin heuristiikan käyttäminen ei aina tuota optimaalisia tuloksia.