Yleinen matkamyyjän ongelma

Yleistetty matkustava myyjä -ongelma on kombinatorinen optimointitehtävä, joka on yleistys tunnetusta matkustavamyyjä- ongelmasta . Ongelman lähtötietona on joukko pisteitä, tämän joukon osio niin sanotuiksi klustereiksi sekä matriisi siirtymäkustannuksista kärjestä toiseen. Ongelmana on löytää lyhin suljettu polku, joka vieraisi yhdessä kärjessä kussakin klusterissa (on myös muunnelma, kun polun täytyy käydä vähintään yhdessä kärjessä kussakin klusterissa).

Kustannusmatriisin ominaisuuksista riippuen ongelma voi olla symmetrinen, jos matriisi on symmetrinen, tai muuten epäsymmetrinen. Yksi yleisimmin käsitellyistä symmetrisen ongelman erikoistapauksista on euklidinen eli tasotehtävä, jolloin jokaisella kärjellä on omat koordinaattinsa avaruudessa ja pisteiden välillä liikkumisen hinta vastaa euklidista etäisyyttä vastaavien avaruuden pisteiden välillä.

Kuten matkustava myyjä -ongelma , yleinen matkustava myyjä -ongelma kuuluu NP-kovien ongelmien luokkaan . Sen todistamiseksi riittää, kun tarkastellaan ongelman erikoistapausta, jolloin jokainen klusteri sisältää täsmälleen yhden kärjen ja ongelma pelkistyy yksinkertaiseksi matkustava myyjätehtäväksi, joka on NP-kova.

Ratkaisumenetelmät

Tarkat menetelmät

Yleistyneen matkustavamyyjä-ongelman täsmälliseen ratkaisuun on olemassa kaksi tehokasta menetelmää: Brunch-and-Cut [1] sekä menetelmä yleistyneen ongelman pelkistämiseksi tavalliseksi matkustavamyyjä-ongelmaksi, jonka ratkaisumenetelmät ovat hyvin tutkittuja. [2] .

Vuonna 2002 osoitettiin [3] , että yleistetty matkustava myyjä -ongelma voidaan pelkistää samankokoiseksi tavalliseksi matkustava myyjä -ongelmaksi korvaamalla painomatriisi .

Heuristiset menetelmät

Yksinkertaiset heuristiset menetelmät

Yksinkertaisimpia heuristisia menetelmiä yleistyneen matkustavamyyjä-ongelman ratkaisemiseksi ovat ahne algoritmi , joka jokaisessa vaiheessa valitsee reunajoukosta edullisimman reunan, joka ei riko ratkaisun oikeellisuutta, sekä tehokkaamman Lähin naapurin. menetelmä, joka alkaa mielivaltaisesta kärjestä ja jokaisessa vaiheessa lisää ratkaisuun viimeistä lisättyä kärkipisteen. On myös muita heuristiikkaa, jotka ovat muunnelmia tavallisista matkustavamyyjä-ongelmasta tunnetuista heuristiikoista.

Erityisesti seuraavia paikallishakutyyppejä käytetään usein :

2-opt , jota käytetään laajasti monissa kombinatorisissa optimointiongelmissa, rajoittuu kahden reunan poistamiseen kiertueesta ja kahden uuden reunan lisäämiseen, jotka eivät riko ratkaisun oikeellisuutta (2-opt:n tapauksessa lisättävät reunat ovat yksilöllisesti määriteltyjä). Kierros katsotaan paikalliseksi minimiksi, jos siinä ei ole reunapareja, joiden korvaaminen johtaisi ratkaisun parantamiseen. Siten sekä naapuruston koko että heuristiikan monimutkaisuus ovat , missä on klusterien lukumäärä. $O(m^{2})$ $m$
3-opt on samanlainen kuin 2-opt, mutta kummastakin ei poisteta kahta, vaan kolme reunaa. 3-opt-tapauksessa on kahdeksan ei-triviaalia tapaa lisätä uusia reunoja kierroksen oikeellisuuden palauttamiseksi. Yksi näistä tavoista säilyttää jokaisen kiertueen fragmentin suunnan, mikä on tärkeä ominaisuus epäsymmetrisissä ongelmissa. Alueen koko ja heuristiikan monimutkaisuus ovat . $O(m^{3})$
2-opt- ja 3-opt-algoritmeissa on luonnollisia modifikaatioita, jotka lisäksi sisältävät optimaalisten kärkien etsimisen muuttuvista klustereista.
"Lisääminen" on 3-opt:n erikoistapaus. Jokaisessa iteraatiossa algoritmi poistaa kärjen ja yrittää löytää sille edullisemman paikan. Algoritmin monimutkaisuus on . Laajalti käytössä on muunnos, joka ei huomioi vain etäpisteen, vaan myös minkä tahansa muun vastaavan klusterin kärjen lisäämistä. $O(m^{2})$
Klusterioptimointi on paikallinen haku, joka liittyy yleiseen matkustavamyyjä-ongelmaan. Algoritmin ydin on löytää lyhin polku tietyn klusterisarjan läpi. Toisin sanoen algoritmin ympäristö sisältää kaikki matkat, jotka eroavat alkuperäisestä enintään kunkin klusterin kärkien valinnalla. Tutkitun kaupunginosan koko on:

$\prod _{i=1}^{m}|C_{i}|\,,$ missä on klusteri numeroitu . Käyttämällä lyhimmän polun hakua erityisesti rakennetussa graafissa, algoritmi löytää paikallisen minimin , jossa . Siten Cluster Optimization kuuluu paikallisten hakujen luokkaan, jolla on erittäin suuri naapurusto , eli se tutkii eksponentiaalista naapurustoa polynomiajassa. $C_{i}$ $i$ $O(ms^{3})$ $s=\max _{i}|C_{i}|$

Metaheuristiikka

Geneettisten algoritmien alaa, jotka ovat osoittaneet tehokkuutensa tähän tehtävään, on tutkittu hyvin. Ensimmäinen työ tällä alalla kuuluu Snyderille ja Duskinille [4] , myöhemmin tärkeitä tuloksia saavuttivat Silbergoltz ja Golden [5] , Gyuten ja Karapetyan [6] .

Muistiinpanot

↑ M. Fischetti, J. J. Salazar-Gonzalez ja P. Toth. Branch-and-Cut -algoritmi symmetriselle yleistetylle matkustavamyyjä-ongelmalle. Operations Research 45(3) (1997), 378-394.
↑ D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo ja A. Zverovitch. Yleistyneen ATSP:n muunnokset ATSP:ksi, Operations Research Letters 31 (2003), 357-365.
↑ 6. Arash Behzad, Mohammad Modarres (2002). Uusi tehokas muunnos yleisestä matkustavamyyjä-ongelmasta matkustavamyyjä-ongelmaksi
↑ LV Snyder ja MS Daskin. Satunnaisavaimen geneettinen algoritmi yleistyneelle matkustavamyyjä-ongelmalle. European Journal of Operational Research 174 (2006), 38-53.
↑ J. Silberholz ja B. Golden. Yleinen matkustava myyjäongelma: uusi geneettisen algoritmin lähestymistapa. Extending the Horisons: Advances in Computing, Optimization, and Decision Technologies, 2007, 165-181.
↑ G. Gutin ja D. Karapetyan. Gregory Gutin ja Daniel Karapetyan. Memeettinen algoritmi yleisen matkustavan myyjän ongelmaan. Natural Computing 9(1), sivut 47-60, Springer 2010. (linkki ei saatavilla)

NP-täydellisiä ongelmia
Pinoamisen (pakkauksen) maksimointiongelma	Pakkaus säiliöihin kaksiulotteinen pakkaus lineaarinen pakkaus pakkaus painon mukaan pakkaus arvon mukaan Reppu ongelma
graafiteorian joukkoteoria	Vertex-kannen ongelma Napsauta ongelma Itsenäisen joukon (joukon) ongelma Aseta peittoongelma Steinerin ongelma Matkamyyjän ongelma Yleinen matkamyyjän ongelma
Algoritmiset ongelmat	Boolen kaavojen tyydyttävyysongelma (konjunktiivisessa normaalimuodossa)
Logiikkapelejä ja pulmia	Yleiset tunnisteet (peli N 2 -1:ssä) lyhin ratkaisu ongelma Ongelmat, joiden ratkaisuja käytetään Tetrisissä Yleistynyt Sudoku-ongelma Latinalaisen neliön täyttöongelma Kakuron tehtävä
Vaikeusluokat Toimintatutkimus Optimointi Kombinatorinen optimointi Sovellettu matematiikka Algoritmien teoria Dynaaminen ohjelmointi 21 NP-täydellinen Karp-ongelma