problema comis-voiajor (drum aerian) prin metode euristice

Temă Curs – Huluba Florin

Problema comis-voiajorului prin metode euristice de rezolvareÎn ceea ce urmează o să rezolv problema comis-voiajorului prin cele 4 metode euristice

de rezolvare. Am să prezint câteva noțiuni teoretice legate de euristicele 1, 2, 3 și 4, după care rezolvăm o problemă prin care să respectăm restricțiile și cerințele.

Aspecte teoretice

De obicei, soluția optimă a unei TSP este foarte greu de găsit (dacă nu chiar imposibil de găsit) atunci când numărul orașelor de vizitat este mare (peste 50). Pentru determinarea unei soluții măcar acceptabile au fost elaborate mai multe procedee euristice. Aceste procedee merită atenție din două puncte de vedere:

• se poate da un "certificat de garanție" pentru soluția obținută în sensul că este posibilă evaluarea "depărtării" maxime de soluția optimă;

• soluția aproximativă este găsită cu un efort de calcul relativ moderat şi într-un timp rezonabil, aceasta însemnând că cei doi parametri depind polinomial de dimensiunea problemei (adică numărul de orașe);

In multe situații practice, procedeele euristice au condus chiar la soluția optimă dar acest lucru a fost confirmat numai prin aplicarea unui algoritm exact. In principiu, o metodă euristică construiește o soluție prin tatonare, din aproape în aproape, făcând la fiecare pas, cea mai bună alegere posibilă. Din nefericire, această "schemă" nu conduce, de regulă, la cea mai bună alegere globală. In continuare, vom prezenta mai multe euristici pentru rezolvarea problemei euclidiene a comis-voiajorului, adică a problemei în care cij sunt distanțe ce satisfac:

• condiția de simetrie: cij = cji:

• inegalitatea triunghiului cik ≤ cij + cjk;

(Nica, 2001)

Problemă

O companie aeriană din Statele Unite, cu sediul în Atlanta, încheie un contract cu un producător de armament în vederea distribuirii către clienți. Armamentul v-a fi distribuit în 9 mari orașe din State (Atlanta, Chicago, Dallas, Detroit, Houston, Los Angeles, New York, Philadelphia, Washington D.C.).

Pentru a respecta contractul compania are la dispoziție un avion special cu o capacitate suficient de mare încât să livreze tot armamentul în orașele menținute mai sus. Un angajat al companiei a calculat distanțele dintre oricare două orașe pentru a găsi un tur astfel încât distanța să fie cât mai mică . Care este metoda euristică este mai avantajoasă ?


Orașe Atlanta Chicago Dallas

Detroit

Houston

Los Angeles New York Philadelphia

Washington DC

Atlanta ꝏ 589 720 598 702 1935 747 666 543Chicago 589 ꝏ 806 237 943 1744 712 664 594Dallas 720 806 ꝏ 1000 225 1239 1372 1299 1183Detroit 598 237 1000 ꝏ 1107 1982 481 442 394Houston 702 943 225 1107 ꝏ 1372 1419 1341 1220Los Angeles 1935 1744 1239 1982 1372 ꝏ 2448 2391 2297New York 747 712 1372 481 1419 2448 ꝏ 81 204Philadelphia 666 664 1299 442 1341 2391 81 ꝏ 123Washington DC 543 594 1183 394 1220 2297 204 123 ꝏ

Tabel 1 – Tabel cu distanțele euclidiene dintre orașe

Euristica E1 (mergi la cel mai apropiat vecin)

• se pleacă din orașul Atlanta către orașul cel mai apropiat;

• din ultimul oraș vizitat avionul pleacă către cel mai apropiat oraș nevizitat; în caz că nu mai există orașe nevizitate se revine în locul de plecare; (Nica, 2001)

Fig. 1 - Harta inițială orașelor e trebuie parcursă


Rezolvare E1 (mergi la cel mai apropiat vecin)

- orașul din care pleacă trenul cu autoturisme este Atlanta;- cel mai apropriat oraș este Washington DC (543 de mile)- din Washington DC cel mai apropriat oraș nevizitat este Philadelphia (123 de mile)- din Philadelphia cel mai apropriat oraș nevizitat este New York (81 de mile)- din New York cel mai apropriat oraș nevizitat este Detroit (481 de mile)- din Detroit cel mai apropriat oraș nevizitat este Chicago (237 de mile)- din Chicago cel mai apropriat oraș nevizitat este Dallas (806 de mile)- din Dallas cel mai apropriat oraș nevizitat este Houston (225 de mile)- din Houston cel mai apropriat oraș nevizitat este Los Angeles (1372 de mile)- din Los Angeles nu mai sunt orașe nevizitate și trenul se întoarce în Atlanta (1935 de

mile)

Inegalitatea triunghiului este respectată și se poate vedea in tabelul Excel din Arhiva.

Aplicând această euristică se obține un tur de o distanța de 543 +123 + 81 +481 + 237 + 806 + 225 + 1372 + 1935 = 5803 de mile. Turul fiind Atlanta – Washington – Philadelphia – New York – Detroit – Chicago – Dallas – Houston – Los Angeles – Atlanta.

Fig. 2 - Turul orașelor parcurse conform E1


Euristica E2 (Ajustare locală)

• se pleacă de la un traseu complet, determinat fie "la întâmplare" fie printr-o altă euristică;

• se caută două arce (u,v) şi (x,y) ale traseului care se încrucişează şi se compară distanţele cuv + cxy cu cux + cvy. Dacă cuv + cxy > cux + cvy se înlocuiesc arcele (u,v) şi (x,y)

cu (u,x) şi (v,y) obţinându-se un traseu de lungime mai mică;

• procedura se opreşte în momentul în care nu mai există situaţii similare cu cea descrisă; (Nica, 2001)

Rezolvare E2

Pentru a ilustra metoda folosim luăm graficul obținut la E1 Se observă în fig. 2 că se intersectează arcele (Chicago-Dallas) și (Los Angeles - Atlanta) dar avem grijă sa nu izola orașul Houston așa că luăm arcele (Chicago-(Dallas+Houston)) și (Los Angeles - Atlanta)

c Chicago, Dallas + Houston + c Los Angeles ,Atlanta = (806 +225) + 1935 = 2966 de mile

c Chicago, Los Angeles + c Houston+ Dallar, Atlanta = 1744 + 225+ 720 = 2689 de mile

2966 > 2689 rezultă că se obține un traseu mai scurt folosind arcele (Chicago - Los Angeles) și (Dallas - Atlanta)


Fig. 3 - Turul orașelor parcurse conform E2

Lungimea noului traseu este va fi 5803 - ( 2966 – 2689 ) = 5526 de mile

Euristica E3

Se determină un arbore H de lungime minimă (aceasta este o problemă "uşoară" rezolvabilă de exemplu cu algoritmul lui Kruskal);

fiecare muchie a arborelui H şe înlocuiește cu două muchii de aceeaşi lungime. Se obţine un multigraf H' în care fiecare nod are grad par. Conform teoremei lui Euler în H' există un ciclu eulerian; cu alte cuvinte, este posibil să se viziteze oraşele astfel încât fiecare muchie a multigrafului H' să fie parcursă o singură dată.

Fie: 0 → x → y → … → u → v → 0

Succesiunea în care muchiile multigrafului H' au fost parcurse. Lungimea acestui "traseu" este de două ori mai mare decât lungimea arborelui minimal H. In această secvenţă, unul sau mai multe oraşe apar de mai multe ori. Se va proceda la urmatoarea operație de scurtcircuitare:

în succesiunea (0 → x → y → … → u → v → 0) se determină prima tripletă de oraşe succesiv vizitate cu proprietatea că oraşul j "din mijloc" mai apare ulterior în succesiune. Se înlocuieşte secvenţa i j → k cu arcul i → k. Prin această scurtcircuitare:

fiecare oraş continuă să fie vizitat cel puţin o dată; noul traseu este mai scurt pentru că cij + cjk ≥ cik; operaţia de scurtcircuitare se repetă până

când în secvenţa "actualizată" fiecare oraş, cu excepţia orașului 0 care apare o singură dată. (Nica, 2001)

Rezolvare E3

Stabilim minimul din fiecare rând din tabelul cu distanta. Conform algoritmului lui Kruskal pe distantele din tabelul distanțelor avem: Atlanta – Washington, Washington – Philadelphia, Philadelphia – New York, Detroit – Chicago, Dallas – Houston, Washington - Detroit, Los Angeles – Dallas, Houston – Atlanta .


Fig. 4 - Distanțele minime pentru H

Un ciclu eulerian în multigraful H', dedus din H prin "dublarea" muchiilor acestuia, arată astfel:

Atlanta => Washington => Philadelphia => New York => Philadelphia => Washington => Detroit => Chicago => Detroit => Washington => Atlanta => Houston => Dallas => Houston => Los Angeles => Dallas => Atlanta

1 Succesiunea Atlanta => Washington => Philadelphia vom înlocui aceasta succesiune direct Atlanta => Philadelphia pentru o distanța cu condiția ca distanta sa fie mai mică sau egal. Adică distanța Atlanta => Washington => Philadelphia = 666 pe cat distanța Atlanta => Philadelphia = 666 este la fel, deci înlocuim succesiunea

2 Succesiunea Atlanta => Philadelphia => New York vom înlocui aceasta succesiune direct Atlanta => Philadelphia pentru o distanța cu condiția ca distanta sa fie mai mică sau egal. Adică distanța Atlanta => Philadelphia => New York = 747 pe cat distanța Atlanta => New York =747 este la fel, deci înlocuim succesiunea

3 Succesiunea Philadelphia => Washington => Detroit vom înlocui aceasta succesiune direct Philadelphia => Detroit pentru o distanța cu condiția ca distanta sa fie mai mică sau egal. Adică distanța Philadelphia => Washington => Detroit = 517 pe cat distanța Philadelphia => Detroit = 442 mai mica decât 517

4 Succesiunea Philadelphia => Detroit => Chicago vom înlocui aceasta succesiune direct Philadelphia => Chicago pentru o distanța cu condiția ca distanta sa fie mai mică sau egal. Adică distanța Philadelphia => Detroit => Chicago = 679 pe cat distanța Philadelphia => Chicago = 664 mai mica decât 679

5 Succesiunea Washington => Atlanta => Houston vom înlocui aceasta succesiune direct Washington => Houston pentru o distanța cu condiția ca distanta sa fie mai mică sau egal. Adică distanța Washington => Atlanta => Houston = 1245 pe cat distanța Washington => Houston = 1220 mai mica decât 1245

6 Succesiunea Washington => Houston => Dallas vom înlocui aceasta succesiune direct Washington => Houston pentru o distanța cu condiția ca distanta sa fie mai mică sau egal. Adică distanța Washington => Houston => Dallas = 1445 pe cat distanța Washington => Houston = 1183 mai mica decât 1445

7 Succesiunea Washington => Dallas => Los Angeles vom înlocui aceasta succesiune direct Houston => Los Angeles pentru o distanța cu condiția ca distanta sa fie mai mică sau egal. Adică distanța Washington => Dallas => Los Angeles = 2422 pe cat distanța Washington => Los Angeles = 2297 mai mica decât 2422

Continuând procesul de scurtcircuitare se obține în final traseul complet: Atlanta => New York => Philadelphia => Chicago => Detroit => Washington => Los Angeles => Dallas => Houston => Atlanta cu un tur de 6586 mile dar se încrucișează în arcele (Atlanta-


NYC,Washington-Detroit)(Atlanta-NYC,Philadelhia-Chicago)(Washington-Detroit,Chicago-Philadelphia)

Fig. 5 - Tur inițial prin E3

Urmează să rezolvăm încrucișările create așadar, pentru a ilustra se observă în fig. 5 că se intersectează arcele (Washington-Detroit) și (Chicago-Philadelphia)

c Washington, Detroit + c Chicago, Philadelphia = 394 + 664 = 1058 de mile

c Washington, Chicago + c Detroit, Philadelphia = 594 + 442 = 1036 de mile

1058 > 1036 rezultă că se obține un traseu mai scurt folosind arcele (Washington-Detroit) și (Chicago-Philadelphia)

Distanța turului a scăzut, dar mai sunt 3 încrucișări și anume (Atlanta-NYC, Washington- Chicago)(Atlanta-NYC, Philadelphia- Detroit) (Atlanta-NYC, Washington- Los Angeles)

c Atlanta-NYC + c Washington, Chicago = 747+ 594 = 1341 de mile

c Atlanta, Chicago + c Washington, NYC = 589 + 204 = 802 de mile

1341 > 802 rezultă că se obține un traseu mai scurt folosind arcele (Atlanta- Los Angeles) și (Washington -NYC)

Distanța turului a scăzut, mai avem de rezolvat încrucișările (Washington-NYC, Philadelphia- Detroit) și (Atlanta- Chicago, Washington- Los Angeles)


c Washington, NYC + c Philadelphia, Detroit = 204+ 442= 646 de mile

c Washington, Philadelphia + c Detroit, NYC = 123 + 614 = 604 de mile

646 > 604 rezultă că se obține un traseu mai scurt folosind arcele (Washington- Philadelphia) și (Detroit - NYC)

Rezolvarea ultimei intersecții între muchiile (Atlanta- Chicago, Washington- Los Angeles)

c Atlanta, Chicago + c Washington, Los Angeles = 589 + 2297= 2886 de mile

c Atlanta, Washington + c Chicago, Los Angeles = 543 + 1935 = 2478 de mile

2886 > 2478 rezultă că se obține un traseu mai scurt folosind arcele (Atlanta-Washington) și (Chicago - Angeles)

În final distanța turului după rezolvarea tuturor încrucișărilor este = 6586 – (1058 – 1036) – (1341 – 802) – (646 – 604) – (2886 – 2478) = 5566 mile

Fig. 5 - Tur final prin E3

Euristica E4

Această procedură, datorată lui Cristofides, este o rafinare a euristicii precedente. Deoarece suma gradelor nodurilor din arborele H este pară, numărul nodurilor de grad impar este par! Folosind numai aceste noduri şi muchiile dintre ele vom determina cuplajul C de pondere minimă, ponderile muchiilor luate în calcul fiind distanțele dintre extremități. Fie H' graful rezultat din H prin adăugarea muchiilor cuplajului C, cu mențiunea că dacă între două noduri


avem o muchie în H şi o alta în C, graful H' va avea între nodurile respective două muchii. Prin construcție în H’ fiecare nod are grad par, astfel că H’ are un ciclu eulerian. Plecând de aici și utilizând tehnica scurtcircuitării se ajunge la un traseu complet

Se poate arăta că lungimea acestui traseu nu depășește 3/2 din lungimea traseului optim(Nica, 2001)

Rezolvare E4

Se reia fig. 4, unde am stabilim minimul din fiecare rând din tabelul cu distanta. Conform algoritmului lui Kruskal pe distantele din tabelul distanțelor avem: Atlanta – Washington, Washington – Philadelphia, Philadelphia – New York, Detroit – Chicago, Dallas – Houston, Los Angeles – Dallas, Dallas – Washington, Washington – Detroit (vezi fig. 4 )

Stabilim gradul unui nod. Gradul este dat de numărul de muchii incidente în nodul respectiv. Astfel nodurile cu grad impar sunt: Chicago, Dallas, Houston, Los Angeles, New York, Washington D.C.

Numărul nodurilor impare din graful din fig.4 este par. Se determina cuplajul minim între nodurile cu grad impar după cum se vede în tabelul de mai jos. Cuplajul se determină aplicând algoritmul ungar.

Orașe Chicago Los Angeles New York Washington DC minim linieChicago ꝏ 1744 712 594 594

Los Angeles 1744 ꝏ 2448 2297 1744New York 712 2448 ꝏ 204 204

Washington DC 594 2297 204 ꝏ 204Tabel 2 - Tabel noduri impare minim linii

Din tabelul de mai sus se scade minimul din fiecare linie și se obține:

Orașe Chicago Los Angeles New York Washington DCChicago ꝏ 1150 118 0

Los Angeles 0 ꝏ 704 553New York 508 2244 ꝏ 0

Washington DC 390 2093 0 ꝏminim coloană 0 1150 0 0

Tabel 3 - Tabel noduri impare minim coloane


La fel ca și mai sus se scade minimul de pe fiecare coloană și vom obține

Orașe Chicago Los Angeles New York Washington DC minim linieChicago ꝏ 0 118 0 594

Los Angeles 0 ꝏ 704 553 1744New York 508 1094 ꝏ 0 204

Washington DC 390 943 0 ꝏ 204Tabel 4 - Tabel încadrare zero-uri

Cu galben sunt 0-uri încadrate, iar cu roșu 0-uri în plus, legăturile noi create sunt între Chicago – Los Angeles și Washington – New York. Distanțele sunt euclidiene, și legăturile pe graf vor arăta că în fig. 6

Fig. 6 - Tur inițial prin E4

Turul este Atlanta => Washington => New York => Philadelphia => Washington => Detroit => Chicago => Los Angeles => Dallas => Houston => Atlanta cu un tur de 5492

1 Succesiunea Atlanta => Washington => New York vom înlocui aceasta succesiune direct Atlanta => New York pentru o distanța cu condiția ca distanta sa fie mai mică sau egal.


Adică distanța Atlanta => Washington => New York = 747 pe cat distanța Atlanta => New York= 747 este la fel, deci înlocuim succesiunea.

Așadar turul devine format din succesiunea orașelor Atlanta => New York => Philadelphia => Washington => Detroit => Chicago => Los Angeles => Dallas => Houston => Atlanta

Rezolvarea ultimei intersecții între muchiile (Atlanta- NYC, Washington- Detroit)

c Atlanta, NYC + c Washington, Detroit = 747 + 394 = 1141 de mile

c Atlanta, Washington + c Detroit, NYC = 543 + 481 = 1024 de mile

1141 > 1024 rezultă că se obține un traseu mai scurt folosind arcele (Atlanta-Washington) și (NYC - Detroit)

Ordinea este Atlanta => Washington => Philadelphia => New York => Detroit => Chicago => Los Angeles => Dallas => Houston => Atlanta are distanța turului de 5375 mile

Fig. 6 - Tur final prin E4

Concluzie


După calcul, cea mai avantajoasă metodă euristica a fost E4 distanța fiind de 5375 de mile. În timp ce prin metodele E1, E2 și E3 rezultatele obținute cu privire la distanța au fost de 5803, 5526, respectiv 5566 mile. Așadar, compania livra armamentul în orașele menținute mai sus, în ordinea ce urmează: Atlanta => Washington => Philadelphia => New York => Detroit => Chicago => Los Angeles => Dallas => Houston => Atlanta.

BibliographyNica, V. (2001). Capitole speciale ale Cercetări operaționale. București: Editura ASE .

Cursuri și seminarii Cercetări operaționale

Calcul distante euclidiene - http://tjpeiffer.com/crowflies.html

Calcul distante euclidiene - http://www.distancefromto.net/distance-from/New+York/to/Los+Angeles

problema comis-voiajor (drum aerian) prin metode euristice

Documents