Generaliseret rejsende sælger problem

Det generaliserede rejsende sælgerproblem er et kombinatorisk optimeringsproblem, der er en generalisering af det velkendte rejsende sælgerproblem . De indledende data for problemet er et sæt toppunkter, en opdeling af dette sæt i såkaldte klynger, samt en matrix af overgangsomkostninger fra et toppunkt til et andet. Problemet er at finde den korteste lukkede sti, der ville besøge et toppunkt i hver klynge (der er også en ændring, når stien skal besøge mindst et vertex i hver klynge).

Afhængigt af omkostningsmatrixens egenskaber kan problemet være symmetrisk, hvis matricen er symmetrisk eller asymmetrisk på anden måde. Et af de hyppigst betragtede specialtilfælde af et symmetrisk problem er det euklidiske eller plane problem, når hvert toppunkt har sine egne koordinater i rummet, og omkostningerne ved at bevæge sig mellem hjørner svarer til den euklidiske afstand mellem de tilsvarende punkter i rummet.

Ligesom problemet med rejsende sælger, hører det generaliserede rejsende sælgerproblem til klassen af NP-hårde problemer . For at bevise det, er det tilstrækkeligt at overveje et særligt tilfælde af problemet, når hver klynge indeholder præcis et toppunkt, og problemet reduceres til et simpelt rejsende sælgerproblem, som er NP-hårdt.

Løsningsmetoder

Præcise metoder

Der er to effektive metoder til den nøjagtige løsning af det generaliserede rejsende sælgerproblem: Brunch-and-Cut [1] , samt en metode til at reducere det generaliserede problem til det sædvanlige rejsende sælgerproblem, metoderne til at løse som er velstuderede [2] .

I 2002 blev det vist [3] at det generaliserede rejsende sælgerproblem kan reduceres til et almindeligt rejsende sælgerproblem af samme dimension ved at erstatte vægtmatricen .

Heuristiske metoder

Simple heuristiske metoder

De enkleste heuristiske metoder til at løse det generaliserede rejsende sælgerproblem inkluderer den grådige algoritme , som ved hvert trin vælger kanten af de mindste omkostninger fra det sæt af kanter, der ikke krænker korrektheden af løsningen, samt den mere effektive Nearest Neighbor metode, som starter fra et vilkårligt vertex og ved hvert trin tilføjer til løsningen, det toppunkt, der er tættest på det sidst tilføjede. Der er også andre heuristika, der er modifikationer af velkendte heuristika for det almindelige rejsende sælgerproblem.

Især følgende typer lokal søgning bruges ofte :

2-opt , som er meget brugt i mange kombinatoriske optimeringsproblemer, reducerer til at fjerne to kanter fra turen og indsætte to nye kanter, der ikke krænker korrektheden af løsningen (i tilfælde af 2-opt, de kanter, der skal indsættes er entydigt bestemt). En tur betragtes som et lokalt minimum, hvis der ikke er par kanter i den, hvis udskiftning ville føre til en forbedring af løsningen. Således er både størrelsen af kvarteret og kompleksiteten af heuristikken , hvor er antallet af klynger. $O(m^{2})$ $m$
3-opt ligner 2-opt, dog fjernes ikke to, men tre kanter på hver. I tilfældet med 3 valgmuligheder er der otte ikke-trivielle måder at indsætte nye kanter på for at genoprette korrektheden af turen. En af disse måder bevarer retningen af hvert af turfragmenterne, hvilket er en vigtig egenskab for asymmetriske problemer. Størrelsen af kvarteret og kompleksiteten af heuristikken er . $O(m^{3})$
Der er naturlige modifikationer af 2-opt og 3-opt algoritmer, som desuden inkluderer søgningen efter optimale toppunkter inden for skiftende klynger.
"Indsættelse" er et særligt tilfælde af 3-opt. Ved hver iteration fjerner algoritmen toppunktet og forsøger at finde en mere gunstig position for det. Kompleksiteten af algoritmen er . En modifikation er meget udbredt, der tager hensyn til indsættelsen ikke kun af et fjerntliggende vertex, men også af et hvilket som helst andet vertex af den tilsvarende klynge. $O(m^{2})$
Klyngeoptimering er en lokal søgning, der er specifik for det generelle problem med rejsende sælger. Essensen af algoritmen er at finde den korteste vej gennem en given sekvens af klynger. Med andre ord inkluderer algoritmens nabolag alle ture, der ikke adskiller sig fra originalen med mere end valget af hjørner inden for hver af klyngerne. Størrelsen af det undersøgte kvarter er:

$\prod _{i=1}^{m}|C_{i}|\,,$ hvor er klyngen nummereret . Ved at anvende søgningen efter den korteste vej i en specielt konstrueret graf, finder algoritmen et lokalt minimum for , hvor . Klyngeoptimering hører således til klassen af lokale søgninger med et meget stort kvarter , det vil sige, det udforsker et eksponentielt kvarter i polynomisk tid. $C_{i}$ $jeg$ $O(ms^{3})$ $s=\max _{i}|C_{i}|$

Metaheuristics

Området for genetiske algoritmer, som har vist deres effektivitet til denne opgave, er blevet grundigt undersøgt. Det første arbejde på dette område tilhører Snyder og Duskin [4] , senere blev vigtige resultater opnået af Silbergoltz og Golden [5] , Gyuten og Karapetyan [6] .

Noter

↑ M. Fischetti, J. J. Salazar-Gonzalez og P. Toth. En Branch-and-Cut-algoritme til det symmetriske generaliserede rejsende sælgerproblem. Operations Research 45(3) (1997), 378-394.
↑ D. Ben-Arieh, G. Gutin, M. Penn, A. Yeo og A. Zverovitch. Transformationer af generaliseret ATSP til ATSP, Operations Research Letters 31 (2003), 357-365.
↑ 6. Arash Behzad, Mohammad Modarres (2002). En ny effektiv transformation af generaliseret rejsende sælgerproblem til rejsende sælgerproblem
↑ LV Snyder og MS Daskin. En tilfældig nøgle genetisk algoritme til det generaliserede rejsende sælgerproblem. European Journal of Operational Research 174 (2006), 38−53.
↑ J. Silberholz og B. Golden. The Generalized Travelling Salesman Problem: en ny genetisk algoritme-tilgang. Extend the Horizons: Advances in Computing, Optimization, and Decision Technologies, 2007, 165-181.
↑ G. Gutin og D. Karapetyan. Gregory Gutin og Daniel Karapetyan. En memetisk algoritme for det generaliserede rejsende sælgerproblem. Natural Computing 9(1), side 47-60, Springer 2010. (ikke tilgængeligt link)

NP-komplette problemer
Maksimeringsproblem ved stabling (pakning)	Emballering i containere todimensionel pakning lineær pakning pakning efter vægt emballage efter værdi Rygsækproblemet
grafteori mængdeteori	Vertex Cover Problem Klik problem Problemet med et uafhængigt sæt (sæt) Sæt dækningsproblem Steiners problem Problemet med den rejsende sælger Generaliseret rejsende sælger problem
Algoritmiske problemer	Tilfredshedsproblem for booleske formler (i konjunktiv normal form)
Logiske spil og puslespil	Generaliserede tags (spil i N 2 -1) korteste løsningsproblem Problemer, hvis løsninger anvendes i Tetris Generaliseret Sudoku problem Latinsk kvadratisk påfyldningsproblem Kakuros opgave
Sværhedsklasser Operationsforskning Optimering Kombinatorisk optimering Anvendt matematik Teori om algoritmer Dynamisk programmering 21 NP-komplet Karp problem