Problema vânzătorului călător

Problema vânzătorului călător este cea mai simplă dintre problemele de rutare și gestionare a proceselor . Este adesea menționat prin numele său în limba engleză , problema vânzătorului ambulant sau problema vânzătorului de călători , în acronimul TSP .

Descriere

Definiție

Problema vânzătorului călător este unul dintre studiile de caz tipice ale informaticii teoretice și ale teoriei complexității computaționale . Numele provine din cea mai tipică reprezentare: având în vedere un set de orașe și cunoscute distanțele dintre fiecare pereche de ele, găsiți ruta minimă pe care un vânzător călător trebuie să o urmeze pentru a vizita toate orașele o singură dată și pentru a reveni la orașul de plecare .

Model matematic

Un grafic G = (V, A) poate fi asociat cu problema TSP, unde V este setul de n noduri (sau orașe) și A este setul de arce (sau drumuri). Este indicat cu $c_{ij}$ ${\ displaystyle c_ {ij}}$ $c _ {{ij}}$ costul arcului pentru a merge de la nodul i la nodul j (vezi Calea minimă ). TSP este simetric totuși $c_{ij}=c_{ji}\forall (i,j)$ ${\ displaystyle c_ {ij} = c_ {ji} \ forall (i, j)}$ $c_ {ij} = c_ {ji} \ forall (i, j)$ , altfel se numește asimetric. În funcție de dacă problema este simetrică sau asimetrică, poate fi descrisă cu diferite modele matematice. Spus $x_{ij}$ ${\ displaystyle x_ {ij}}$ $x_ {ij}$ variabila binară generică astfel încât $x_{ij}=1$ ${\ displaystyle x_ {ij} = 1}$ $x_ {ij} = 1$ dacă arc (i, j) aparține circuitului e $x_{ij}=0$ ${\ displaystyle x_ {ij} = 0}$ $x_ {ij} = 0$ în caz contrar, în cazul mai general al unei probleme asimetrice, o posibilă formulare matematică a problemei este:

z=\min \sum _{i=1}^{n}\sum _{j=1}^{n}c_{ij}x_{ij}\quad (1)

{\ displaystyle z = \ min \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {n} c_ {ij} x_ {ij} \ quad (1)}

{\ displaystyle z = \ min \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {n} c_ {ij} x_ {ij} \ quad (1)}

supus la

{\begin{aligned}&\sum _{i=1}^{n}x_{ij}=1&&j=1,...,n&&(2)\\&\sum _{j=1}^{n}x_{ij}=1&&i=1,...,n&&(3)\\&\sum _{i\in Q}\sum _{j\in V\setminus Q}x_{ij}\geq 1&&\forall Q\subset V,|Q|\geq 1&&(4)\\&x_{ij}\in \{0,1\}&&i,j=1,...,n\end{aligned}}

{\ displaystyle {\ begin {align} & \ sum _ {i = 1} ^ {n} x_ {ij} = 1 && j = 1, ..., n && (2) \\ & \ sum _ {j = 1} ^ {n} x_ {ij} = 1 && i = 1, ..., n && (3) \\ & \ sum _ {i \ in Q} \ sum _ {j \ in V \ setminus Q } x_ {ij} \ geq 1 && \ forall Q \ subset V, | Q | \ geq 1 && (4) \\ & x_ {ij} \ in \ {0,1 \} && i, j = 1,. .., n \ end {align}}}

{\ displaystyle {\ begin {align} & \ sum _ {i = 1} ^ {n} x_ {ij} = 1 && j = 1, ..., n && (2) \\ & \ sum _ {j = 1} ^ {n} x_ {ij} = 1 && i = 1, ..., n && (3) \\ & \ sum _ {i \ in Q} \ sum _ {j \ in V \ setminus Q } x_ {ij} \ geq 1 && \ forall Q \ subset V, | Q | \ geq 1 && (4) \\ & x_ {ij} \ in \ {0,1 \} && i, j = 1,. .., n \ end {align}}}

Relația (1) este funcția obiectivă care reprezintă minimizarea costului călătoriei. Constrângerile (2) și (3) indică faptul că în fiecare nod i intră și iese doar un arc și sunt numite constrângeri de atribuire. Deoarece aceste constrângeri nu asigură o soluție constând dintr-un singur circuit, sunt inserate și constrângerile (4) care asigură absența subcircuitelor. În special, ei definesc că, oricum se alege un subset corespunzător de noduri Q în V, trebuie să existe cel puțin un arc care conectează un nod al lui Q cu un nod care nu aparține lui Q.

Complexitatea computațională

Nu există algoritmi eficienți pentru rezoluția TSP, singura metodă de rezoluție este reprezentată de enumerarea totală, adică în elaborarea tuturor căilor posibile pe grafic pentru alegerea ulterioară a celei mai bune. Cu toate acestea, complexitatea operației îl face impracticabil pentru grafice cu dimensiuni comune în probleme reale: într-un grafic de n noduri, va fi necesar să se calculeze, în cel mai rău caz în care fiecare nod este conectat cu toți ceilalți, n ! ( n factoriale ) căi posibile, ceea ce implică o complexitate exponențială (bazată pe aproximarea Stirling ). TSP reprezintă, de asemenea, un exemplu de problemă liniară de programare întreagă în care este aproape imposibil de obținut evaluări aproximative prin tehnica de relaxare continuă , deoarece problema LP rezultată ar avea o serie de constrângeri care cresc exponențial cu nodurile, făcând matricile atât de intratabile. asociat cu acesta. În scopuri practice, metoda de recoacere simulată ( recoacere simulată ) a rezolvat în mod eficient TSP.
O rețea de o mie de noduri, mult mai comună decât s-ar putea crede, ar începe deja să creeze probleme de calcul serioase.

NP-completitudine

S-a arătat că TSP este o problemă dificilă pentru NP (mai exact, este NP-completă pentru clasa de complexitate FP ^NP ; vezi problema funcției ) și versiunea de decizie a problemei („având în vedere greutățile și un număr x , a decide dacă există o soluție mai bună decât x ") este NP-complet.

Problema rămâne NP-dificilă chiar și în multe dintre versiunile sale mai mici, ca în cazul în care orașele se află într-un avion cu distanțe euclidiene . În plus, omiterea condiției de a vizita un oraș „o singură dată” nu elimină dificultatea NP, deoarece este ușor de observat că, în cazul plat, o cale optimă ar vizita orașele o singură dată.

Problema vânzătorului care călătorește cu gâtuire este, de asemenea, NP-hard.

Algoritmi

Strategiile tradiționale de soluționare a problemelor dificile din PN sunt:

găsiți un caz specific al problemei (subproblemă) pentru care este posibilă fie o soluție exactă, fie o euristică mai bună.
proiectați algoritmi euristici , adică algoritmi care produc soluții care sunt probabil bune, dar imposibil de dovedit a fi optime
proiectarea algoritmilor pentru a găsi soluția exactă, destul de rapidă doar pentru problemele cu un număr relativ mic de orașe

Pentru a efectua teste pe algoritmi TSP, a fost dezvoltată biblioteca TSPLIB, care conține exemple de exemple ale problemei TSP și variantele conexe (a se vedea secțiunea de articole corelate). Multe dintre aceste exemple sunt liste de orașe și diagrame cu circuite imprimate.

Algoritmi exacți

Algoritmi ramificați și legați care pot fi utilizați pentru probleme TSP cu 50-60 de orașe.
Algoritmi care se desfășoară prin rafinări succesive folosind tehnici derivate din programarea liniară , potrivite pentru probleme de până la 120-200 de orașe.
Implementări recente de ramură și legătură și ramură și tăiere bazate pe programare liniară, potrivite pentru probleme care conțin până la 5.000 de orașe. Această abordare a fost, de asemenea, urmată pentru a rezolva situații cu 33.810 orașe.

În 2001, de exemplu, a fost găsită soluția exactă la o problemă de aproximativ 15.000 de orașe cuprinsă în TSPLIB, folosind metoda planului de tăiere , bazată pe programare dinamică și propusă inițial în 1954 de George Dantzig , Delbert Ray Fulkerson și Selmer Johnson .
Calculul a fost efectuat la Universitatea Rice și la Universitatea Princeton , de către o rețea de 110 procesoare . Timpul total de procesare a fost echivalent cu aproximativ 23 de ani pe un singur procesor Alpha de 500 MHz . În mai 2004, TSP a fost rezolvat pentru toate cele aproximativ 25.000 de orașe din Suedia , rezultând o distanță de aproximativ 72.500 de kilometri . Remarcabil este că această cale s-a dovedit mai târziu a fi cea mai bună.

În martie 2005 , TSP privind vizita tuturor celor 34.000 de puncte dintr-o placă de circuit a fost rezolvată folosind CONCORDE: a fost găsită o cale de aproximativ 66 de milioane de unități și a dovedit că nu ar putea exista una mai bună. Executarea a durat aproximativ 16 ani CPU .

Euristică

Până în prezent, au fost proiectați diferiți algoritmi aproximativi , care au o probabilitate „mare” de a produce „rapid” o soluție „bună”. Metodele moderne pot găsi soluții în timp rezonabil acceptabil pentru probleme extrem de mari (milioane de orașe), cu o mare probabilitate ca acestea să fie 2-3% diferite de soluția exactă.

Există diferite tipuri de euristică.

Euristică constructivă

Cel mai apropiat algoritm vecin , care este de obicei destul de aproape de soluția optimă, și nu durează prea mult. Din păcate, este posibil să se demonstreze bunătatea soluției numai în cazuri particulare ale TSP. În cazul general, există întotdeauna un exemplu în care cel mai apropiat vecin produce o soluție foarte proastă.

Perfecționări ulterioare

Euristică de schimb în perechi sau euristică Lin-Kernighan .
Euristică k-opt

Cazuri speciale

Locații particulare

Un caz particular al unei soluții banale apare atunci când orașele sunt dispuse pe perimetrul unui poligon convex.
Un exercițiu bun asupra algoritmilor combinatori se referă la soluția TSP pentru un set de orașe situate de-a lungul a două cercuri concentrice.

Inegalitatea triunghiulară și algoritmul Christofides

O restricție naturală a TSP este inegalitatea triunghiulară . Adică pentru oricare trei orașe $LA$ ${\ displaystyle A}$ $LA$ , $B.$ ${\ displaystyle B}$ $B.$ Și $C.$ ${\ displaystyle C}$ $C.$ , distanța dintre $LA$ ${\ displaystyle A}$ $LA$ Și $C.$ ${\ displaystyle C}$ $C.$ trebuie să fie cel mult la distanță de $LA$ ${\ displaystyle A}$ $LA$ la $B.$ ${\ displaystyle B}$ $B.$ cu cât distanța de la $B.$ ${\ displaystyle B}$ $B.$ la $C.$ ${\ displaystyle C}$ $C.$ . Multe cazuri reale de probleme TSP satisfac această constrângere.

În acest caz, avem un algoritm de aproximare cu factor de aproximare constant (grație lui Christofides , 1975 ), care produce întotdeauna o cale de-a lungul a cel mult 2 ori calea optimă.

Lungimea arborelui minim care se întinde pe rețea este o limită inferioară naturală pentru lungimea optimă a căii. În TSP cu inegalitate triunghiulară este posibil să se determine o limită superioară în termenii arborelui minim de întindere și să se proiecteze un algoritm care are o limită superioară demonstrabilă pe lungimea soluției.

Primul și cel mai simplu algoritm este:

construiți arborele minim de întindere (1 copac)
Luați în considerare numai nodurile de grad impar și construiți „potrivirea perfectă”
adăugați potrivire în grafic: acum toate nodurile vor avea un nivel egal. Aceasta produce un grafic eulerian .
găsiți un circuit eulerian în interiorul său. Evident, lungimea sa este de două ori lungimea arborelui.
convertiți circuitul eulerian într-un ciclu hamiltonian în felul următor: urmând ciclul eulerian, de fiecare dată când sunteți pe punctul de a atinge un vârf deja vizitat, săriți-l și încercați să ajungeți la următorul (urmând întotdeauna calea euleriană).

Este ușor să demonstrezi că ultimul pas funcționează. Mai mult, datorită inegalității triunghiulare, de fiecare dată când săriți un vârf la pasul 4, sunteți de fapt o comandă rapidă, asigurându-vă că lungimea ciclului nu crește. Acest lucru ne permite să avem o soluție care cu siguranță nu depășește dublul celei optime.

Algoritmul lui Christofides urmează o abordare similară, dar combină arborele minim care se întinde cu o soluție a unei alte probleme, potrivirea perfectă a greutății minime . Acest lucru garantează o soluție de cel mult 2 ori cea optimă. Încercarea de a reduce constanta 2 a fost o problemă deschisă din 1975 .

TSP euclidian

TSP euclidian sau TSP plan, este cazul particular în care sunt utilizate distanțe euclidiene obișnuite. În timp ce problema rămâne NP-hard, multe euristici funcționează mai bine.

TSP euclidian este un caz special al TSP cu inegalitate triunghiulară, deoarece distanțele din plan respectă această constrângere; cu toate acestea, pare a fi mai simplu decât cazul general cu inegalitate triunghiulară. De exemplu, arborele minim de întindere al graficului asociat cu un caz TSP euclidian este un arbore minim de întindere euclidian și ca atare poate fi calculat în timp $O(n\log {n})$ ${\ displaystyle O (n \ log {n})}$ $O (n \ log {n})$ pentru $n$ ${\ displaystyle n}$ $n$ puncte. Aceasta permite algoritmului prezentat mai sus să calculeze mai repede.

În general, pentru fiecare $c>0$ ${\ displaystyle c> 0}$ $c> 0$ există un algoritm polinom care identifică, pe orice grafic, o cale de-a lungul cel mult $(1+c)$ ${\ displaystyle (1 + c)}$ $(1 + c)$ ori cel optim ( Arora , 1997 ); aceasta se numește schemă de aproximare polinomială . Cu toate acestea, acest algoritm este prea lent în practică pentru a fi folosit; în schimb, se utilizează euristicile care oferă garanții mai slabe, dar care funcționează mai bine în cazurile TSP euclidiene decât în cazurile generale.

TSP asimetric

De cele mai multe ori, distanța dintre două noduri de rețea TSP este aceeași în ambele direcții. Cazul general în care distanța de la $LA$ ${\ displaystyle A}$ $LA$ la $B.$ ${\ displaystyle B}$ $B.$ nu este egal cu distanța de la $B.$ ${\ displaystyle B}$ $B.$ la $LA$ ${\ displaystyle A}$ $LA$ se numește TSP asimetric. Un exemplu practic ar putea fi căutarea unui traseu pe străzile unui oraș, unde există străzi cu sens unic.

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre problema vânzătorului călător

linkuri externe

( EN ) The Traveling Salesman Problem , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
(EN) TSPLIB , pe iwr.uni-heidelberg.de. Adus la 4 ianuarie 2006 (arhivat din original la 25 martie 2017) .
( RO ) Pagină dedicată TSP , pe tsp.gatech.edu .
Rețeaua Kohonen aplicată problemei vânzătorului călător (în 3 dimensiuni)

Controlul autorității	Tezaur BNCF 7977 · LCCN (EN) sh85137179 · GND (DE) 4185966-2

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică