Problemă generalizată a vânzătorului ambulant

Problema generalizată a vânzătorului călător este o problemă de optimizare combinatorie care este o generalizare a binecunoscutei probleme ale vânzătorului călător . Datele inițiale ale problemei sunt un set de vârfuri, o partiție a acestui set în așa-numitele clustere, precum și o matrice a costurilor de tranziție de la un vârf la altul. Problema este de a găsi cea mai scurtă cale închisă care ar vizita un vârf în fiecare cluster (există și o modificare când calea trebuie să viziteze cel puțin un vârf în fiecare cluster).

În funcție de proprietățile matricei de cost, problema poate fi simetrică dacă matricea este simetrică sau asimetrică în caz contrar. Unul dintre cele mai frecvent considerate cazuri speciale ale unei probleme simetrice este problema euclidiană sau plană, când fiecare vârf are propriile coordonate în spațiu, iar costul deplasării între vârfuri corespunde distanței euclidiene dintre punctele corespunzătoare din spațiu.

La fel ca problema vânzătorului călător , problema generalizată a vânzătorului ambulant aparține clasei de probleme NP-hard . Pentru a dovedi, este suficient să luăm în considerare un caz special al problemei, când fiecare cluster conține exact un vârf, iar problema se reduce la o simplă problemă de vânzător ambulant, care este NP-hard.

Metode de rezolvare

Metode exacte

Există două metode eficiente pentru rezolvarea exactă a problemei generalizate ale vânzătorului ambulant: Brunch-and-Cut [1] , precum și o metodă de reducere a problemei generalizate la problema obișnuită a vânzătorului călător, metodele de rezolvare care sunt bine studiate. [2] .

În 2002, s-a arătat [3] că problema generalizată a vânzătorului ambulant poate fi redusă la o problemă obișnuită a vânzătorului călător de aceeași dimensiune prin înlocuirea matricei de greutate. .

Metode euristice

Metode euristice simple

Cele mai simple metode euristice pentru rezolvarea problemei generalizate ale vânzătorului ambulant includ algoritmul lacom , care la fiecare pas selectează marginea celui mai mic cost din setul de muchii care nu încalcă corectitudinea soluției, precum și cel mai eficient Nearest Neighbor. metoda, care pleacă de la un vârf arbitrar și la fiecare pas se adaugă la soluție, vârful cel mai apropiat de ultimul adăugat. Există, de asemenea, alte euristici care sunt modificări ale euristicilor binecunoscute pentru problema obișnuită a vânzătorului călători.

În special, sunt adesea folosite următoarele tipuri de căutare locală :

2-opt , care este utilizat pe scară largă în multe probleme de optimizare combinatorie, se reduce la eliminarea a două muchii din tur și la inserarea a două noi muchii care nu încalcă corectitudinea soluției (în cazul 2-opt, muchiile care trebuie introduse sunt determinate în mod unic). Un tur este considerat un minim local dacă nu există perechi de margini în el a căror înlocuire ar duce la o îmbunătățire a soluției. Astfel, atât dimensiunea vecinătății cât și complexitatea euristicii sunt , unde este numărul de clustere. $O(m^{2})$ $m$
3-opt este similar cu 2-opt, cu toate acestea, nu două, ci trei margini sunt eliminate pe fiecare. În cazul cu 3 optiuni, există opt moduri non-triviale de a insera noi margini pentru a restabili corectitudinea turului. Una dintre aceste moduri păstrează direcția fiecăruia dintre fragmentele de tur, care este o proprietate importantă pentru problemele asimetrice. Dimensiunea cartierului și complexitatea euristicii sunt . $O(m^{3})$
Există modificări naturale ale algoritmilor cu 2 și 3 optiuni, care includ, în plus, căutarea nodurilor optime în grupurile în schimbare.
„Inserție” este un caz special de 3 opt. La fiecare iterație, algoritmul îndepărtează vârful și încearcă să găsească o poziție mai favorabilă pentru acesta. Complexitatea algoritmului este . Este utilizată pe scară largă o modificare care ia în considerare inserarea nu numai a unui vârf îndepărtat, ci și a oricărui alt vârf al clusterului corespunzător. $O(m^{2})$
Optimizarea clusterului este o căutare locală specifică problemei generalizate ale vânzătorului ambulant. Esența algoritmului este de a găsi calea cea mai scurtă printr-o anumită secvență de clustere. Cu alte cuvinte, vecinătatea algoritmului include toate tururile care diferă de originalul prin nu mai mult decât alegerea nodurilor din cadrul fiecărui cluster. Mărimea cartierului investigat este:

$\prod _{i=1}^{m}|C_{i}|\,,$ unde este numerotat clusterul . Aplicând căutarea celei mai scurte căi într-un grafic special construit, algoritmul găsește un minim local pentru , unde . Astfel, Cluster Optimization aparține clasei de căutări locale cu o vecinătate foarte mare , adică explorează o vecinătate exponențială în timp polinomial. $C_{i}$ $i$ $O(ms^{3})$ $s=\max _{i}|C_{i}|$

Metaeuristica

Domeniul algoritmilor genetici, care și-au demonstrat eficiența pentru această sarcină, a fost bine studiat. Prima lucrare în acest domeniu aparține lui Snyder și Duskin [4] , ulterior rezultate importante au fost obținute de Silbergoltz și Golden [5] , Gyuten și Karapetyan [6] .

Note

↑ M. Fischetti, J. J. Salazar-Gonzalez și P. Toth. Un algoritm Branch-and-Cut pentru problema generalizată simetrică a vânzătorului ambulant. Operations Research 45(3) (1997), 378-394.
↑ D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo și A. Zverovitch. Transformations of generalized ATSP into ATSP, Operations Research Letters 31 (2003), 357-365.
↑ 6. Arash Behzad, Mohammad Modarres (2002). O nouă transformare eficientă a problemei generalizate a vânzătorului ambulant în problema vânzătorului călători
↑ LV Snyder și MS Daskin. Un algoritm genetic cu cheie aleatorie pentru problema generalizată a vânzătorului ambulant. Jurnalul European de Cercetare Operațională 174 (2006), 38−53.
↑ J. Silberholz și B. Golden. Problema generalizată a vânzătorului ambulant: o nouă abordare a algoritmului genetic. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, 2007, 165-181.
↑ G. Gutin și D. Karapetyan. Gregory Gutin și Daniel Karapetyan. Un algoritm memetic pentru problema generalizată a vânzătorului ambulant. Natural Computing 9(1), paginile 47-60, Springer 2010. (link indisponibil)

Probleme NP-complete
Problema de maximizare a stivuirii (ambalării)	Ambalare in containere ambalare bidimensională ambalare liniară ambalare după greutate ambalare după valoare Problema rucsacului
teoria grafurilor teoria multimelor	Problemă de acoperire a vârfurilor Faceți clic pe problemă Problema unei multimi (multimi) independente Setați problema acoperirii Problema lui Steiner Problema vânzătorului ambulant Problemă generalizată a vânzătorului ambulant
Probleme algoritmice	Problemă de satisfacție pentru formulele booleene (în formă normală conjunctivă)
Jocuri de logică și puzzle-uri	Etichete generalizate (joc în N 2 -1) cea mai scurta solutie problema Probleme ale căror soluții sunt aplicate în Tetris Problemă generalizată de Sudoku Problemă de umplere a pătratului latin Sarcina lui Kakuro
Clasele de dificultate Cercetare operațională Optimizare Optimizare combinatorie Matematică aplicată Teoria algoritmilor Programare dinamică 21 Problemă Karp NP-completă