AUTOMATICĂ, CALCULATOARE, INGINERIE ELECTRICĂ ȘI [608164]

UNIVERSITATEA „DUNĂREA DE JOS” DIN GALAȚI FACULTATEA DE
AUTOMATICĂ, CALCULATOARE, INGINERIE ELECTRICĂ ȘI
ELECTRONICĂ
Str. Științei Nr. 2, cod poștal 800146, Galați, România, tel/fax: +0236 470 905, e -mail: [anonimizat], web: www.aciee.ugal.ro

PROIECT DE DIPLOMĂ

Îndrumător proiect,
Ș.l. Dr .Ing. Iulian Nicușor ARAMĂ

Absolvent: [anonimizat]
2019

UNIVERSITATEA „DUNĂREA DE JOS” DIN GALAȚI FACULTATEA DE
AUTOMATICĂ, CALCULATOARE, INGINERIE ELECTRICĂ ȘI
ELECTRONICĂ
Str. Științei Nr. 2, cod poștal 800146, Galați, România, tel/fax: +0236 470 905, e -mail: [anonimizat], web: www.aciee.ugal.ro

SPECIALIZAREA: Automatică și informatică aplicată

Rutarea vehiculelor cu variabila
NEIGHBORHOOD SEARCH

Îndrumător proiect,
Ș.l. Dr .Ing. Iulian Nicușor ARAMĂ

Absolvent: [anonimizat]
2019

Rezumat

În domeniul informaticii și optimizării matematice, o metaheuristică este o procedură de nivel
superior sau euristică concepută pentru a găsi, genera sau selecta un algoritm euristic (parțial de
căutare) care poate oferi o soluție suficient de bună pentru o problemă de optimizare, în special
cu informații incomplete sau imperfecte sau o capacitate de calcul limitată .
Metaheuristicile sunt strategii care ghidează procesul de căutare.
Scopul este de a explora eficient spațiul de căutare pentru a găsi soluții aproape optime.
Tehnicile care constituie algoritmi metaheuristice variază de la proceduri simple de căutare
locală la procese complexe de învățare.Algoritmele metaheuristice sunt aproximative și de
obicei, non -deterministe. Metaheuristicile nu sun t specifice problemelor.
Metaheuristicile sunt folosite pentru optimizarea combinatorica in care se cauta o solutie
optima pe un spatiu de cautare discret. Exiztă două mari tipuri de rutare care stau la baza
tuturor celorlalte tipuri de rutare: rutarea sta tică și rutarea dinamică .Rutarea statică
descrie un sistem care rutează într -o rețea de date in funcție de căi fixe. Rutarea dinamică
construiește dinamic tabelele de rutare, bazându -se pe informațiile purtate de protocoale,
permițand rețelei să acționeze în mod aproape automat pentru a evita erori și blocaje în
rețea. Datorită proprietăților sale, rutarea dinamică domină în momentul actual internetul.
Variable Neighborhood Search (VNS) , propus de Mladenović , Hansen , 1997 este o metodă
metaheuristic pe ntru rezolvarea unui set de optimizare combinatorică și probleme de
optimizare la nivel mondial . Acesta explorează cartiere îndepărtate ale soluției curente , și
se mută de acolo la o solutie nouă dacă și numai daca în cazul în care s -a făcut o
îmbunătăți re. Metoda de căutare locală este aplicată în mod repetat, pentru a obține soluții
în vecinătate la valori maxime locale . VNS a fost proiectat pentru soluții de aproximare a
problemelor de optimizare discrete și continue și în funcție de acestea , se are în vedere
pentru rezolvarea problemelor liniare ale programului , probleme de program întreg ,
probleme de program întreg mixte , probleme de programe neliniare , etc.
VNS se bazează pe o schimbare sistematică a cartierelor pentru a scăpa de optima locală și
pentru a oferi o explorare largă a spațiului de căutare. După proiectarea unui set de cartiere
agitare și construirea unei soluții inițiale, aceasta constă în iterativ (i) agitând o soluție
actuală, (ii) efectuarea unei căutări locale pe ea și (iii) deci zia de a o accepta ca o nouă
companie care o ocupă sau nu. Numele metodei provine de la faptul că vecinul folosit pentru
faza de agitare se schimbă sistematic în timpul procesului de căutare.

CUPRINS

Introducere…………………………………………………………………………………………………… ………………………………….1
Capitolul 1. Algoritmi Metaeuristici…………………………………………….. ……………………………………………..2
1.2 Clasificarea metaeuristicelor ………………………………………………………………………………. …3
1.3 Aplicatii …………………………………………….. ………………………………………………………………………..4
1.4 Structura unui algoritm metaeuristic generic …………………………………………………….6
Capitolul 2. Rutarea vehiculelor……………………. ……………………………………………………………………………..7
2.2 Utilizarea protocoalelor de rutare ………………………………………………………………………….8
2.3 Clase de protocoale de rutare . ……………………………………………………………………………….10
2.4 Alegerea protocolului ……………………………………………………………………………………… ………16
2.5 Vehicle routing p roblems ……………………………………………………………………………………….18
Capitolul 3. Variabila neighborhood search ………………………………………………………………………. …….21
3.2 Meto de de solutie exacte………………………………………………………………………………………….22
3.3 Formularea fluxului vehiculului …………………………………………………………………………….2 3
3.5 Structura variabilei neighborhood search……………………………………………………………26
3.6 Prezentarea algoritmului …………………………………………………………………………………… …..28
Capi tolul 4 . Prezentarea programului ………………………………………………………………………………. ……..32
4.1 Algoritmul NialgVrp………………………………………………………………………………….. ……………..33
4.2 Evaluatorul ………………………………………………………………………………………………. ………………..38
4.3 Problema cererii ……………………………………………………… ……………………………………………….39
4.4 Afisarea rezultatelor ……………………………………………………………………………………… ………..40

INTRODUCERE

Metaheuristica probează un set de soluții care este prea mare pentru a fi
eșantionat complet. Metaheuristica poate face puține ipoteze cu privire la rezolvarea
problemei de optimizare și, astfel, poate fi utilizabilă pentru o varietate de probleme.
În comparație cu algoritmii de optimizare și metodele iterative, metaheuristica nu
garantează că se poate găsi o soluție optimă la nivel global pe o anumită clasă de
probleme. Multe metaheurisme implementează o formă de optimizare stocastică, astfel
încât sol uția găsită este dependentă de setul de variabile aleatoare generate. În
optimizarea combinatorică, prin căutarea unui set mare de soluții fezabile,
metaheuristica poate găsi adesea soluții bune cu un efort mai mic de calcul decât
algoritmi de optimizare, metode iterative sau simple heuristici. Ca atare, acestea sunt
abordări utile pentru problemele de optimizare. Câteva cărți și articole de anchetă au
fost publicate pe această temă.
Rutarea directează drumul pachetelor ce conțin adrese logice dinspre sursă spre
destinația finală prin noduri intermediare (numite rutere ). Procesul de rutare
directează de obicei pe baza unor tabele de rutare pe care le gestionează ruterele,
care mentin o înregistrare a celor mai bune rute către diferite destinații din rețea.
Ruterele utilizează protocoale cu rutare dinamică pentru a realiza trei funcții
elementare: descoperirea de noi rute, comunicarea informațiilor despre noua rută
descoperită altor rutere și expedierea pachetelor utilizând acele rute.Protocoalele cu
rutare dinamică se împart în trei mari categorii: cu vectori distanță, cu starea
legăturilor și hibride. Principalele diferențe dintre ele constau în modul în care
realizeză primele două dintre cele trei funcții amintite anterior. Singura variantă la
rutarea dinamică este rutarea statică . Variable Neighborhood Search (VNS) , propus de
Mladenović , Hansen , 1997 este o metodă metaheuristic pentru rezolvarea unui set de
optimizare combinatorică și probleme de optimizare la nivel mondial . Acesta
explore ază cartiere îndepărtate ale soluției curente , și se mută de acolo la o solutie
nouă dacă și numai daca în cazul în care s -a făcut o îmbunătățire. Metoda de căutare
locală este aplicată în mod repetat, pentru a obține soluții în vecinătate la valori
maxim e locale . VNS a fost proiectat pentru soluții de aproximare a problemelor de
optimizare discrete și continue și în funcție de acestea , se are în vedere pentru
rezolvarea problemelor liniare ale programului , probleme de program întreg ,
probleme de progr am întreg mixte , probleme de programe neliniare , etc.

CAPITOLUL 1. Algoritmi Metaeuristici

În domeniul informaticii și optimizării matematice, o metaheuristică este o
procedură de nivel superior sau euristică concepută pentru a găsi, genera sau selecta un
algoritm euristic (parțial de căutare) care poate oferi o soluție suficient de bună pentru
o problemă de optimizare, în special cu informații incomplete sau imperfecte sau o
capacitate de calcul limitată.
Metaheuristica probează un set de soluții care este prea mare pentru a fi
eșantionat complet. Metaheuristica poate face puține ipoteze cu privire la rezolvarea
problemei de optimizare și, astfel, poate fi utilizabilă pen tru o varietate de probleme.
În comparație cu algoritmii de optimizare și metodele iterative, metaheuristica nu
garantează că se poate găsi o soluție optimă la nivel global pe o anumită clasă de
probleme. Multe meta heurisme implement ează o formă de optimizare stoc astică, astfel
încât soluția găsită este dependentă de setul de v ariabile aleatoare generate. În
optimizarea combinatorică, prin căutarea unui set mare de soluții fe zabile,
metaheuristica poate găsi adesea soluții bune cu un efort mai mic de calcul decât
algoritmi de optimizare, metode ite rative sau simple heuristici . Ca atare, acestea sunt
abordări utile pent ru problemele de optimizare. Câteva cărți și articole de an chetă au
fost publicate pe această temă.
Majoritatea literaturii despre metaheuristice sunt experimentale în natură,
descriind rezultate empirice bazate pe experimente pe calculator cu algoritmi. Dar sunt
disponibile și câteva rezultate teoretice formale, adesea în ceea ce privește convergența
și posibilitat ea de a găsi optimul global. Au fost publicate multe metode metaeuristice
cu pretenții de noutate și eficacitate practică. Deși domeniul deține și o cercetare de
înaltă calitate, multe dintre publicații au fost de slabă calitat e; deficiențe includ vagul ,
lipsă de elaborare conceptuală, experimente slabe și ignoranță a literaturii anterioare .

1.1. Proprietățile metaeuristicelor

Acestea sunt proprietăți care caracterizează cele mai multe metaheuristici:

Metaheuristicile sunt strategii care ghidează procesul de căutare.
Scopul este de a explora eficient spațiul de căutare pentru a găsi soluții aproape optime.
Tehnicile care constituie algoritmi metaheuristice variază de la proceduri simple
de căutare local ă la procese complexe de învățare.
Algoritmele metaheuristice sunt aproximative și de obicei, non -deterministe.
Metaheuristicile nu sunt specifice problemelor.

1.2. Clasificarea metaeuristicelor

Există o mare varietate de metaheuristice și o serie de proprietăți în privința
cărora să le clasificăm .

Căutare locală vs. căutare globală

O abordare este aceea de a caracteriza tipul de strategie de căutare.Un tip de
strategie de căutare reprezintă o îmbunătățire a algoritmilor de căutare locală simpli.
Un algoritm de căutare locală bine cunoscut este metoda de alpinism care se utilizează
pentru a găsi optimi locali. Cu toate acestea, alpinismul nu garantează găsirea unor
soluții optime globale.

Au fost propuse numeroase idei metaheuristice pentru a îmbună tăți euristica
căutării locale pentru a găsi soluții mai bune. Astfel de metaeheuristice includ
recoacerea simulată, căutarea tabu, căutarea locală iterativă, căutarea de cartier variabil
și GRASP. Aceste metaeheuristice pot fi clasificate ca metaeheurist ice de căutare locale
sau globale.

Alte metaheuristice de căutare globală care nu sunt bazate pe căutare locală sunt
de obicei metaheuristice bazate pe populație. Astfel de metaheuristici includ
optimizarea coloniilor de furnici, calculul evolutiv, optimi zarea roiului de particule si
algoritmii genetici .

Soluție unică vs. Populație

O altă dimensiune de clasificare este căutarea singulară în funcție de populație.
Soluțiile unice se concentrează pe modificarea și îmbunătățirea unei singure soluții
candid ate; metaheuristica singulară a soluției include recoacerea simulată, căutarea
locală iterativă, căutarea în vecinătatea variabilă și căutarea locală ghidată. Abordările
pe bază de populație mențin și îmbunătățesc mai multe soluții candidate, adesea
utiliz ând caracteristicile populației pentru ghidarea căutării; metaheuristica bazată pe
populație include calculul evolutiv, algoritmii genetici și optimizarea roiurilor de
particule. O altă categorie de metaheuristică este inteligența Swarm, care este un
compo rtament colectiv al agenților descentralizați, autoorganizați într -o populație sau
roi. Optimizarea coloniilor de mistreți, optimizarea roților particulelor, optimizarea
cognitivă socială, optimizarea șoimului Harris, algoritmul de optimizare a căutării
pinguinilor și algoritmii de colonii de albine artificiale sunt exemple din această
categorie.

Hibridizare și algoritmi memetici

Un metaheuristic hibrid este unul care combină o metaheuristică cu alte abordări
de optimizare, cum ar fi algoritmii de pro gramare matematică, programarea
constrângerilor și învățarea în mașină. Ambele componente ale unui metaheuristic
hibrid pot rula simultan și pot schimba informații pentru a ghida căutarea.

Pe de altă parte, algoritmii memetici [12] reprezintă sinergia abordării evolutive
sau a oricărei populații bazată pe învățarea individuală individuală sau pe procedurile
locale de îmbunătățire a căutării în probleme. Un exemplu de algoritm memetic este
utilizarea unui algoritm de căutare locală în locul unui operator de mutație de bază în
algoritmi evolutivi.

Metaeuristică paralelă

O metaheuristică paralelă este aceea care utilizează tehnicile de programare
paralelă pentru a executa mai multe căutări metaheuristice în paralel; acestea pot varia
de la scheme simple d istribuite la runde de căutare concurente care interacționează
pentru a îmbunătăți soluția globală.

Natură -inspirat metaheuristics

Principalele articole: Inteligența roiurilor și lista metaheuristică inspirată de
metaforă.O arie de cercetare foarte activ ă este designul metaheuristicilor inspirate de
natură. Multe metaheurisme recente, în special algoritmi bazați pe calculul evolutiv,
sunt inspirați de sistemele naturale. Natura acționează ca o sursă de concepte,
mecanisme și principii pentru proiectarea s istemelor de calcul artificială pentru a
rezolva problemele computaționale complexe [13]. Astfel de metaeheuristice includ
recoacerea simulată, algoritmi evolutivi, optimizarea coloniilor furnicilor și optimizarea
parcelelor de particule. Un număr mare de metaheurisme mai recente în metaforă au
început să atragă critici în comunitatea de cercetare pentru a ascunde lipsa lor de
noutate în spatele unei metafore elaborate.

1.3 Aplicații

Metaheuristicile sunt folosite pentru optimizarea combinatorica in care se c auta o
solutie optima pe un spatiu de cautare discret. O problemă de exemplu este problema
vânzătorului care călătorește în care spațiul de căutare al soluțiilor candidate avansează
mai repede decât exponențial, pe măsură ce mărimea problemei crește, ceea ce face ca o
căutare exhaustivă a soluției optime să fie imposibilă. În plus, problemele
combinatoriale multidimensionale, inclusiv cele mai multe probleme de proiectare în
inginerie cum ar fi găsirea formelor și comportamentul, suferă din blestemul
dimens ionalității, ceea ce le face imposibilă și pentru căutări exhaustive sau metode

analitice. Metaheuristicile sunt, de asemenea, utilizate pe scară largă pentru planificarea
locurilor de muncă și probleme de selecție a locurilor de muncă. Metheheurismele
pop ulare pentru problemele combinatoriale includ recoacerea simulată de către
Kirkpatrick et al., algoritmi genetici de Holland et al., căutări scatter și tabu search de
Glover. Revizuirea literaturii privind optimizarea metaheuristică a sugerat că Fred
Glove r a inventat cuvântul metaheuristic.

Fig. 1 Schema echivalentă clasificarii metaeuristicelor

1.4 Structura unui algoritm metaeuristic generic

S=soluție candidat inițială
Repeat
R=modificare(S)
if calitate(R)>calitate(S) then R=S
Until <conditie de oprire>
Componente:
Inițializare
Modificare (asigură explorarea spațiului soluțiilor)
Selecție (asigură exploatarea de calitate bună)
Element cheie: asigurarea echilibrului între explorare și expl oatare

1.5 Structura unui algoritm evolutiv

Metaeuristică bazata pe populatii = proces iterativ const ând în aplicarea
succesiv ă a unor operatori asupra unei popula ții inițializat e aleator .
– de explorare
– de exploatare (selecție)

Fig. 2 Schema echivalentă a structurii unui algoritm evolutiv

Initializare
populatie
Evaluare
Operatori
de explorare Conditie
de oprire
Selectie
Solutie

CAPITOLUL 2. Rutarea vehiculelor

2.1 Noțiuni generale despre rutare

In rețelele de calculatoare, termenul rutare
se referă la selectarea căilor într -o rețea, pe care să se trimită anumite date.

Rutarea directează drumul pachetelor ce conțin adrese logice dinspre sursă spre
destinația finală prin noduri intermediare (numite rutere ). Procesul de rutare
directează de obicei pe baza unor tabele de rutare pe care le gestionează ruterele,
care mentin o înregistrare a celor mai bune rute către diferite destinații din rețea.

Rețelele mici pot gestiona tabele de rutare configurate manual. Rețelele mari
implică topologii mari care se schimbă constant, facând utilizarea manuală a tabelelor
de rutare foarte dificilă.

Exiztă două mari tipuri de rutare care stau la baza tuturor celorlalte tipuri de
rutare: rutarea statică și rutarea dinamică .Rutarea statică descrie un sistem care
rutează într -o rețea de date in funcție de căi fixe. Rutarea dinamică construieșt e
dinamic tabelele de rutare, bazându -se pe informațiile purtate de protocoale,
permițand rețelei să acționeze în mod aproape automat pentru a evita erori și blocaje
în rețea. Datorită proprietăților sale, rutarea dinamică domină în momentul actual
interne tul.

Avantajele rutării dinamice fața de cea statică sunt scalabilitatea si
adaptibilitatea. O rețea rutată dinamică poate crește mult mai repede și este capabilă
să se adapteze schimbărilor din topologia rețelei aduse tocmai de această creștere sau
de er orile din una sau mai multe componente ale rețelei. Într -o rețea dinamică,
ruterele îinvață despre topologia rețelei comunicând cu alte rutere. Rutarea dinamică
are însă și dezavantaje, cum ar fi creșterea complexitătii.

Datorită diferentelor pe care le au atât rutarea statică cât și cea dinamică,
probabil vă întrebați care dintre ele ar fi cea mai bună alegere pentru dumneavoastră.
Doar dumneavoastră puteți spune cu sigurantă ce este mai util pentru rețeaua de care
dispuneți. Dar există o limită neutră d e complexitate a rutării dinamice, fara a -i
sacrifica scalabilitatea. Aceasta limită neutră este o schemă hibridă, în care o parte din
rețea folosește rutarea statică, iar cealaltă parte, rutarea dinamică.

2.2 Utilizarea protocoalelor de rutare

Rutarea dinamică și rutarea statică Bazele rutării dinamice

Ruterele utilizează protocoale cu rutare dinamică pentru a realiza trei funcții
elementare: descoperirea de noi rute, comunicarea informațiilor despre noua rută
descoperită altor rutere și expedi erea pachetelor utilizând acele rute.
Protocoalele cu rutare dinamică se împart în trei mari categorii: cu vectori
distanță, cu starea legăturilor și hibride. Principalele diferențe dintre ele constau în
modul în care realizeză primele două dintre cele tre i funcții amintite anterior.
Singura variantă la rutarea dinamică este rutarea statică .

Rutarea cu vectori -distanță

Rutarea se poate baza pe algoritmi cu vectori -distanță (numiți și algoritmi
Bellman -Ford ), care car ca ruterele să paseze periodic copii ale tabelelor de rutare
vecinilor cei mai apropiați din rețea. Fiecare destinatar adaugă la tabelă un vector –
distanță (propria "valoare" distanță) și o expediază vecionilor săi cei mai apropiați.
Acest proces se desfășoară în toate direcțiile între routere le aflate în imediată
vecinătate.
Acest proces pas -cu-pas face ca fiecare router sa afle informații despre celelalte
routere și să -și dezvolte o perspectivă cumulativă asupra "distațelor" rețelei. De
exemplu, un protocol timpuriu de rutare este Routing Information Protocol (protocol
de rutare a informațiilor), sau RIP . Acesta utilizează două unități de măsură pentru
distanțe ca să determine cea mai bună cale următoare pentru orice pachet. Aceste
unități de măsură pentru distanță, tacturile și ho purile, sunt dependente de timp.

Tabela cumulativă este apoi utilizată pentru actualizarea tabelelor de rutare ale
fiecărui router. La finalul procesului, fiecare router a aflat niste informații vagi despre
distanțele până la resursele din rețea. El nu a aflat nimic specific despre alte routere
sau despre topologia reală a rețelei.

Această abordare poate, în anumite circumstanțe, să creeze probleme de rutare
pentru protocoalele bazate pe vectori -distanță. De exemplu, în urma unei căderi în
rețea eset nece sar ceva timp pentru ca routerele să conveargă spre o nouă înțelegere
a topologiei rețelei. În timpul acestui proces, rețeaua ar putea fi vulnerabilă la rutări
contradictorii și chiar la bucle infinite.

Anumite măsuri de siguranță ar putea să micșoreze ac este riscuri, dar rămâne
faptul că performanța rețelei este expusă riscurilor în timpul procesului de
convergență. Prin urmare, este posibil ca protocoalele mai vechi care converg lent să
nu fie potrivite pentru WAN -urile extinse, complexe.

Rutarea cu s tarea legăturilor

Algoritmii de rutare folosind starea legăturilor (link -state routing algorithm),
cunoscuți collectiv ca protocoale cu preferarea drumului minim (SPF), mențin o bază
de date complexă a topologiei rețelei. Spre deosebire de protocoalele cu vectori –
distanță, cele folosind starea legăturilor dezvoltă și întrețin o cunoaștere completă a
routerelor de rețea, ca și a felului cum sunt interconectate acestea.

Această cunoștere este realizată prin schimbarea de pachete cu starea
legăturilor ( LSP) cu alte routere conectate direct. Fiecare router care a schimbat LSP –
uri construiește apoi o bază de date logicș utilizănd toate LSP -urile primite. Este
utilizat apoi un algoritm "cu preferarea drumului liber", pentru a calcula cât de
accesibile sunt desti națiile legate de rețea. Această informație este utilizată pentru a
actualiza tabela de rutare. Acvest proces este capabil să descopere modificările
topologiei rețelei, care ar putea fi cauzate de căderea unei componente sau de
mărirea rețelei. De fapt, sc himbul de LSP -uri este declanșat de un eveniment din
rețea, nu este realizat periodic.

Rutarea cu starea legăturilor are două zone parțiale de risc. Mai înâi, în timpul
procesului inițial de descoperire, rutarea cu starea legăturilor poate acapara mediile
de transmisie ale rețelei, reducând astfel în mod semnificativ capacitatea rețelei de a
transporta date. Acveastă degradare a performanței este temporară, dar foarte
evidentă.

A doua problemă potențială etse că rutarea cu starea legăturilor solicită inte ns
memoria și procesorul. Din această cauză, routerele configurate pentru rutare cu
starea legătulilor sunt în general mai scumpe.

Rutarea hibridă

Ultima formă de rutare dinamică este hibridizarea . Deși există prtocoale hibride
deshise, echilibrate, această formă este asociată aproape exclusiv creației brevetate a
unei singure companii, Cisco Systems Inc. Acest protocol, EIGRP , a fost proiectat
combinând cele ami bune aspecte ale protocoalelor cu v ectori -distanță și cu starea
legăturilor, fără limitările de performanță sau dezavantajele lor.

Protocoalele de rutare hibride echilibrate, utilizează unități de măsură vectori –
ditanță, dar realizează măsurători mult mai precise decât protocoalele cu vectori –
distanță convenționale. De asemenea, ele converg mult mai rapid decât acestea din
urmă, dar evită suprasarcinile și actualizările cu starea legăturilor. Hibrizii echilibrați
nu sunt periodici, ci conduși de evenimente, conservând astfel lărgimea de bandă
pentru aplicații reale.

Bazele rutării statice

Un router care este programat pentru rutare statică expediază pachetele prin
porturi predeterminate. După ce routerele statice sunt configurate, ele nu mai trebuie
să incerce descoperirea rutelor, nici măcar să comunice informații despre rute. Rolul
lor este redus la simpla expediere a pachetelor.

Rutarea statcă este bună doar pentru rețele foarte mici, care au o singură cale
către orice destinație dată. În astfel de cazuri, rutarea statică poate f i cel mai eficient
mecanism de rutare, pentru că nu consumă lărgime de bandă, încercând să descopere
rute și să comunice cu alte routere.

Pe măsură ce rețelele cresc și apar căi redundante către destinații, rutarea
statică devine o sarcină care necesită p rea mult efort. Orice modificări în
disponibilitatea routerelor sau a echipamentelor de transmisie din WAN trebuie să fie
descoperite si programate manual. WAN -urile caracterizate prin tipologii mai
complexe, care pot oferi mai multe căi posibile, necesită categoric rutare dinamică.
Încercările de a utiliza rutarea statică în WAN -uri complexe, cu mai multe căi,
anulează rolul rutelor redundante.

2.3 Clase de protocoale de rutare

Există mai multe clase de protocoale de rutare: protocoalele de rutare pent ru
rețele ad -hoc care apar in rețele cu puțină sau chiar fără infrastructură, protocoale de
rutare internă utilizate în interiorul sistemelor autonome și protocoale de rutare
externă , acestea din urmă utilzându -se între sistemel autonome.

Protocoale cu rutare internă (Interior Gateway Protocols – IGP )

RIP (Routing Information Protocol) este un protocol mai vechi de rutare cu vectori –
distanță IGRP
(Interior Gateway Routing Protocol) este un protocol de rutare cu starea
legăturilor, utili zat pe scară largă, dezvoltat de Cisco Systems. Este brevetat și
acceptat doar pe routere Cisco.
EIGRP (Enhanced Interior Gateway Routing Protocol) este un protocol de rutare
bazat pe protocolul IGRP , predecesorul său. Este proprietate Cisco.
OSPF (Open Shortest Path First) este un protocol cu starea lgăturilor, cu un
standard deschis. IS-IS (Intermediate System to Intermediate System) este un
protocol bazat pe OSI

Protocoale cu rutare externă (Exterior Gateway Protocols – EGP ) EGP
(Exterior Gateway Protocol)
BGP
(Border Gateway Protocol: in versiunea curenta, BGPv4, dateaza din anii 1995)
este un protocol de rutare modern, utilizat între sisteme autonome.

Vectori distanță
Vectori distanță

Starea legăturilor Starea legăturilor

hibrid

Fig. 3 Schema ce ilustrează clase de protocoale de rutare

Un protocol extern transportă informațiile de rutare între entități
administrative independente, cum ar fi două corporații sau două universități. Fiecare
dintre aceste entități menține o infrastructură de rețea independentă și folosește EGP
pentru a putea comunica cu cealaltă entitate. Astăzi, cel mai popular protocol extern
este BGP . Este protocolul extern primar folosit între rețelele conectate la Internet și a
fost proiectat special pentru acest lucru.

Un protocol intern este folosit în interiorul unui singur domeniu administrativ,
sau între grupuri apropiate care cooperează. Spre deosebire de protocoalele externe,
IGP tinde să fie mai simplu rezolvă suprasolicitările venite din partea unui ruter.
Aceste protocoale nu pot fi utilizate în rețelele mari.

Comparatie intre clasele de rutare

RIP
Routing Information Protocol ( RIP ) este protocolul intern cel mai des folosit in
sistemele UNIX. RIP este integrat în cele mai utilizate sisteme UNIX. RIP
selectează ruta cu cel mai mic "număr de hopuri" (metrică) ca fiind ruta cea mai
bună. Numărul de hopuri reprezentat de acest protocol este numărul de porți prin
care trrebuie să treacă datele pentru a ajunge la destinație. RIP
consideră cea mai bună rută ca fiind cea care folosește cele mai puține porți. EGP
BGP IGP
RIP
OSPF IS-IS IGRP
EIGR
P

Această alegere de rute se face cu ajutorul unor algoritmilor vector -ditanța.

RIP
este usor de implementat si de configurat. Perfect! Totusi, lucrurile stau altfel.
Acesta următoarele impedimente:

Diametrul rețelei este limitat : cea mai lungă rută RIP este de 15 hopuri;o rută
RIP nu poate menține o tabelă de rutare completă pentru o rețea care are destinații
mai departe de 15 hopuri; numărul hopurilor nu poate fi incrementat din cauza
următorului imped iment.

Convergența lentă : pentru a șterge o rută proastă este uneori nevoie de
schimbul de multiple
pachete -de-revizuire (update packets) pană ce costul (lungimea) rutei devine
16. Aceasta se mai numește și "numărarea la infinit" pentru că RIP
continuă să incrementeze costul rutei pană ce devine mai mare decat cea mai
mare metrică RIP validă. RIP poate aștepta 180 secunde înainte de a șterge rutele
invalide. În termenii tehnici , aceasta se mai numețte și întarzierea "convergenței de
rutare"; i. e, îi ia mult timp tabelei să reflecte starea curentă a rețelei. Rutarea de clasă
RIP interpretează toate adresele în funcție de niște reguli de clasă. Pentru acest
protocol, toate adresele sunt de clasă A, B, sau C, ceea ce face ca RIP să fie
incompatibil cu rețelele CIDR .

În multe rețele, RIP nu ar fi alegerea potrivită pentru rutare, deoarece timpul
său de convergența și sclabilitatea sunt mai slabe? în comparație cu EIGRP , OSPF , sau
IS-IS (ultimele două fiind cu stare a legăturilor), și limita de ho puri reduce sever
dimensiunea rețelei. Pe de altă parte, este ușor de utilizat și de configurat.

RIP
este unul dintre cele mai longevive protocoale. Acesta este și unul dintre cele
mai usor de confundat protocoale, din cauza varietății de protocoale de rutare care au
aceleși nume. RIP și multe alte protocoale asemănătoare s -au bazat pe același set de
algoritmi care folosesc vectori de distanță comparînd matematic rutele pentru a
indentifica cea mai bună cale spre orice a dresă -destinație dată. Acești algoritmi au
fost creați dupa o cercetare academica riguroasă care a început in anul 1957

În ciuda vîrstei protocolului RIP și a apariției mai multor protocoale de rutare
mai sofisticate, acesta este departe de a fi învechit . Acest protocol etse matur, stabil,
in mare măsură suportat, și ușor de configurat. Simplitatea lui se potrivește foarte
bine la rețelele stub și în sisteme autonome mici care nu au destule căi redundante
pentru a suporta suprasolicitările protocoalelor s ofisticate.

EIGRP

EIGRP a fost dezvoltat de către Cisco (eliberat în 1988) cu scopul de a
îmbunătăți protocolul RIP pe vremea cînd IETF încă lucra la dezvoltarea OSPF -ului.
EIGRP

este un protocol brevetat. Acest protocol elimină unele dintre defectele
protocolului RIP , și are îmbunătățiri ca folorirea de metrici compuse, rutarea pe căi
multiple, și mînuirea rutelor implicite.

Evoluția protocolului EIGRP furnizează compatibilitate și operații precise cu
rutere EIGRP . Capacități cheie care dinting EIGRP
de alte protocoale de rutare includ convergența rapidă, support pentru mască
de subrețea variable -length , suport pentru update, și support pentru multiple
network layer protocols.

EIGRP
are toate avantajele flexibilității și ale configurării simple în timp ce
îmbunătățește viteza și consumarea resurselor. Dealtfel, este capabil a fi un protocol
unic atît pentru IP cît și pentru protocoale non – IP , eliminînd nevoia de a folosi
mult iple protocoale de rutare într -o rețea multi -protocol.

Acest protocol de rutare este unul dintre cele mai diversificate și robuste
protocoale de rutare. Combinația sa unic[ de caracteristici îmbină cele mai bune
atribute ale protocoalelor de vector -distan ță cu cele mai bune atribute ale
protocoalelor cu starea legăturilor. Rezulatul este un protocol de rutare hibrid care
sfidează împărțirea pe categorii a protocoalelor convenționale.

Poate fi folosit împreunpă cu IPv4, AppleTalk, și IPX. Mai important, arhitectura
sa modulara va permite ca Cisco să adauge suport pentru alte protocoale de rutare
importante care vor apărea în viitor.

Spre deosebire de alte protocoale de rutare bazate pe vectori -distanta, EIGRP nu
mandatează o revizuire periodică al tabele lor de rutare între rutere vecine. În schimb,
folosește un mechanism de descoperire/recuperare pentru a asigura că vecinii sunt
conștienți de accesibilatea fiecaruia in parte.

OSPF

Open Shortest Path First ( OSPF ) este alt protocol cu starea legăturilor
dezvoltat pentru TCP/IP . Se folosește in rețele foarte mari și dispune de de cîteva
avantaje față de RIP . Similar cu Interior Gateway Routing Protocol (IGRP), OSPF a fost
creat deoarece la mijlocul anilor _80, Routing Information Protocol ( RIP ) a deve nit
incapabil să servească inter -rețele mari, eterogene. OSPF
are două mari caracteristici. Prima este ca protocolul este deschis, ceea ce
înseamnă ca specificațiile sale sunt de domeniu public. A doua caracteristică
principală este că se bazează pe algoritmul SPF (Shortest Path First).

Deoarece dimensiunea și viteza Internetului au crescut, limitările protocolului
RIP i-au diminuat popularitatea. În schimb, OSPF este considerat acum a fi protocolul
de rutare intern preferat de rețeua Internet.

Idee a principală: în loc de a schimba informații despre distanțele pîna la

destinații (ca în cazul protocolului RIP
),toate nodurile vor menține hărți specifice ale rețelei care sunt revizuite după
fiecare schimbare din topologie; aceste hărți sunt mai apoi fo losite pentru a
determina rute care sunt mai fiabile decat cele în cazul protocoalelor cu vectori –
distanță; rutele determinate de OSPF par a fi la fel de precise ca și cele determinate
central, totuși această determinare fiind distribuită.Astfel, spre deos ebire de RIP ,
OSPF împarte informații despre vecinii săi cu întreaga rețea (cel mult un singur
system autonom). RIP nu încearcă să învețe despre întreaga rețea Internet, iar OSPF
nu încearcă să se promoveze in intregul Internet. Nu aceasta este menirea lo r. Ele
sunt protocoale de rutare interne; astfel, slujba lor este de a construi rutarea in cadrul
unui sistem autonom.

Cele mai importante avantajeale protocolului OSPF sunt facilitățile de securitate ,
facilități de căi multiple , facilități in ceea ce privește utilzarea metricilor de costuri
diferite , suport integrat atît pentru rutarea unicast, cît și pentru cea multicast ,
convergență rapidă .

În mod clar, OSPF
dispune de multă flexibilitate pentru a subdiviza un sistem autonom. Dar este
oare necesar? O problemă a protocolului cu legare de stare este cantitatea mare de
date care poate fi colectată în baza de date cu și de timpul prea lung care este necesar
pentru a calcula rutele pentru acele date.

OSPF este probabil cel mai folosit protocol IGP în ret ele de dimensiuni mari. În
contrast cu RIP sau BGP , OSPF nu folosește TCP sau UDP dar folosește direct
protocolul IP 89.

OSPF domină protocoalele de rutare IGP , mai ales în rețele Enterprise.

IS-IS

Intermediate System to Intermediate System ( IS-IS ) este un protocol de rutare
intern din familia protocoalelor OSI
. Implementează algoritmul folosind starea legăturilor (link -state), după
principiul Shortest Path First (SPF). A fost protocolul folosit pentru T1 NSFNET și este
încă folosit de anumiți pro videri mari de servicii.
IS-IS
rămâne un protocol necunoscut pentru majoritatea administratorilor de rețea și
a fost preponderent folosit de providerii de servici care aveau de gestionat o rețea
mare de calculatoare. IS-IS a devenit mai cunoscut în ultimii ani și a devenit o
alternativă viabilă a protocolului OSPF .

Dacă dorim să realizăm o comparație între IS-IS și OSPF trebuie să avem în

vedere anumite aspecte. Ambele protocoale utilizează rutarea folosind starea
legăturilor, având implementat algoritmul lui Dijkstra de aflare a rutei optime în
cadrul unei rețele. Ca și concept, protocoalele sunt similare. Amândouă au suport
pentru lungimi variabile ale măștilor de subrețea (subnet masks), pot folosi rute
multiple de descoperire a vecinilor folosind pache te ecou și au suport pentru
autentificare în cazul update -urilor.

Dacă OSPF este creat nativ de a ruta IP , IS-IS este un protocol ISO CLNS . IS-IS
nu folosește IP pentru a transporta mesajele cu informații. Routerele IS-IS construiesc
o reprezentare topo logică a rețelei. Această hartă indică IP -ul subrețelelor în care
poate fiecare router IS-IS să ajungă, cunoscând și calea de cost redus. O altă diferență
ar fi metoda prin care topologia IS-IS transferă informațiile prin rețea.

Deoarece OSPF este mai popular, protocolul are un set bogat de extensii și
funcții adăugate. Mulți susțin însă ca IS-IS poate satisface rețele de dimensiuni mai
mari.

Adițional, IS-IS este mult mai neutru din punct de vedere al tipurilor de adrese
de rețea pe care le poate ruta. OSPF
, de cealaltă parte a fost creat având în vedere numai Ipv4 . Astfel IS-IS a fost
mult mai ușor de adaptat să suporte Ipv6 , în timp ce OSPF a avut nevoie de o revizie
majoră ( OSPF v3).

IS-IS diferă de OSPF prin felul in care "zonele" sunt definite și prin felul în care
are loc rutarea între aceste zone. Routerele IS-IS pot fi de Nivel 1 (intra -area), Nivel 2
(interarea) sau Nivel 1 -2 (ambele). Un router d e Nivel 2 poate fi aflat în relație doar
cu un alt router de același nivel. Schimbul de informații se poate realiza doar între
routere de același nivel (fie ele de Nivel 1 sau Nivel 2). Din această cauză a fost
implementat routerul de Nivel 1 -2 care realiz ează schimbul de informații între
routerele intra -area și cele interarea.

In OSPF
, zonele sunt delimitate astfel încât Area border router (ABR) se află de fapt în
două sau mai multe zone. Deasemenea este delimitată o zonă Area 0, prin care trebuie
să tre acă tot traficul inter -area.

Din punct de vedere logic, OSPF
se aseamănă cu o pânză de păianjen sau o topologie stea de mai multe zone
conectate cu Area 0, în timp ce IS-IS creează o topologie logică asemănătoare unei
vertebre, în care routerele de Nivel 2 au ramuri care se separă in routere de Nivel 1 -2
si Nivel 1.

BGP

The Border Gateway Protocol ( BGP
) este protocolul de bază al Internetului. Funcționează prin menținerea unei
tabele de retele IP care stabilește modul de conectare între sisteme autonome.

BGP
este un protocol de rutare între sisteme autonome. Un sistem autonom este o

rețea sau un grup de rețele sub o administrare unică cu aceleași reguli de routare în
toată rețeaua. BGP este folosit pentru a comunica informații despre rute pentru
Internet și este protocolul folosit între providerii de servicii Internet.

BGP este cel mai folosit protocol extern de rutare. Este robust și scalabil și se
bazează pe IDRP . BGP moștenește abilitatea sistemelor autonome de a putea alege
rutele și de a -și implementa regulile de rutare fără a trebui să depindă de o autoritate
centrală.
Și cel mai important lucru despre un protocol extern este acela ca majoritatea
sistemelor nici nu îl folosesc, deoarece nu sunt nevoite să furnizeze servicii externe.
BGP are și câteva neajunsuri. În primul rând necesită configurație manuală
excesivă. BGP 4 are suport numai pentru Ipv4
, o versiune "multiprotocol" fiind în dezvoltare. Fiind necesară o politică de
rutare se implementează soluții ca: BGP tunnelling, Source De mand Routing, IDPR și
MPLS .

2.4 Alegerea protocolului

Este posibil să folosim un protocol intern în locul unuia extern, și vice -versa, dar
acest lucru nu este indicat. Protocoalele externe sunt proiectate pentru rețele mari,
astfel încât complexitatea lor ș i fenomenul de suprasolicitare a ruterului, pot copleși o
rețea mică –medie. De cealaltă parte, protocoalele interne nu se pot mula pe rețelele
mari.

În momentul alegerii unui protocol am putea avea preferințe fie pentru rutarea
folosind starea legăturilor (link -state) sau rutarea cu vectori distanță (distance –
vector), dar alegerea doar în funcție de algoritmul folosit nu este recomandată. Vom
prezenta și alte criterii de alegere care ne vor ajuta să selectăm protocolul care se
potrivește cel mai bine rețelei pe care o gestionăm.

Ar trebui să avem în vedere cât de repede protocolul se va adapta schimbărilor
intervenite în rețea. Aici intervine timpul de convergență, care este cantitatea de timp
scursă de la întâlnirea unei schimbări în rețea până la restabilirea consistenței și
modificarea tabelei de rutare. În mod ideal ne dorim ca acest timp să fie suficient de
mic astfel încât să nu poată fi detectat de utilizatori.

Un alt criteriu important este consumul de resurse, astfel protocolul de rutar e
trebuie să aibă suport pentru lungimi variabile de măști de subrețea. Trebuie să
considerăm nu numai consumul de bandă realizat de mesajele protocolului, ci și câtă
putere de procesare și memorie folosește ruterul. Un protocol cu starea legăturii va
gest iona mai bine consumul de bandă, iar un protocol cu vectori distanță va gestiona
consumul memoriei și al procesorului.

Trebuie avut în vedere și felul în care se iau în vedere rutele multiple către o
destinație. Acest lucru poate să fie critic sau nu în rețeau gestionată. În cazul în care

nu există căi redundante în rețea atunci acest aspect ar putea să nu intereseze. Dar
există pericolul adăugării acestor căi în rețea în viitor, fiind astfel necesar schimbarea
protocolului pentru a putea satisface noile cerințe.

Putem considera și modul în care protocolul este scalabil în funcție de
dimensiunile pe care le poate atinge rețeaua. Protocoalele care folosesc starea
legăturilor scalează mai bine, dar câteva protocoale cu vectori distanță, cum ar fi
EIGRP , au putut fi folosite și în rețele cu mai mult de 1000 de rutere

Un aspect final este dacă protocolul este standard deschis sau este un protocol
brevetat. Acest lucru este relevant din cauza politicii de care este constrânsă
organizația care deține rețe aua sau de faptul că ruterele din rețea trebuie să fie
compatibile. Tabelul de mai jos identifică criteriile prezentate mai sus

Protocol RIP OSPF IGRP EIGRP
Timp
convergenta Vector
distanta Starea
legaturilor Vectori
distanta Vectori
distanta
Timp de
convergenta incet rapid incet Rapid
VLSM Nu Da Nu Da
Consum de
banda Ridicat Scazut Ridicat scazut
Consum de
resurse Scazut Ridicat Scazut Scazut
Suport cai
multiple Nu da da Da
Scalabilitate Nu da da Da
Brevetat Nu nu da Da
Protocol
Non -ip Nu nu nu da

Fig. 4 Tabelul ce ilustrează proprietățile protocoalelor de rutare

2.5 Vehicle routing problems

Problema de rutare a vehiculelor (VRP) este o problemă de optimizare
combinatorică și de programare integrată, care întreabă "Care este setul optim de
rute pentru o flotă de vehicule care urmează să traverseze pentru a livra unui anumit
set de clienți?". Ea generalizează bine -cunoscuta problemă a vânzătorilor care
călătoresc (TSP). A apărut pentru prima oară în lucrarea lui George Dantzig și John
Ramser în 1959, în care a fost scrisă prima abordare algoritmică și a fost aplicată
livrărilor de benzină. Adesea, contextul este acela de livrare a bunurilor situate într –
un depozit central către clienții care au comandat astfel de bunuri. Obiect ivul VRP
este de a minimiza costul total al traseului. În 1964, Clarke și Wright au îmbunătățit
abordarea lui Dantzig și Ramser folosind o abordare eficientă lacomă numită
algoritmul de economii.

Determinarea soluției optime pentru VRP este NP -hard, astfe l încât mărimea
problemelor care pot fi rezolvate, în mod optim, folosind programarea matematică
sau optimizarea combinatorică, poate fi limitată. Prin urmare, solverii comerciali tind
să utilizeze euristicile datorită mărimii și frecvenței VRP -urilor din lumea reală pe
care trebuie să le rezolve. (Pentru o explicație non -tehnică a motivului pentru care
VRP este atât de provocator, vă rugăm să consultați link -urile externe de mai jos.)

VRP are multe aplicații evidente în industrie. De fapt, utilizarea programelor de
optimizare a computerului poate oferi economii de 5% unei companii, deoarece
transportul este de obicei o componentă semnificativă a costului unui produs (10%)
– într-adevăr, sectorul transporturilor reprezintă 10 % din PIB -ul UE. În conseci nță,
orice economie creată de VRP, chiar mai mică de 5%, este semnificativă.

Fig. 5 Schema ce ilustrează optimizarea unui traseu folosind VRP

2.5 Configurarea problemei

VRP se referă la serviciul unei companii de livrare. Cum se livrează lucrurile
dintr -unul sau mai multe depozite care au un anumit set de vehicule de uz casnic și
sunt operate de un set de șoferi care se pot deplasa într -o anumită rețea de drumuri
unui număr de clienți. Solicită o determ inare a unui set de rute S (o rută pentru
fiecare vehicul care trebuie să înceapă și să se termine în depozitul propriu) astfel
încât să fie satisfăcute toate cerințele clienților și constrângerile operaționale, iar
costul global al transportului să fie re dus la minimum. Acest cost poate fi monetar, la
distanță sau în alt mod.

Rețeaua de drumuri poate fi descrisă folosind un grafic în care arcele sunt
drumuri și nodurile sunt noduri între ele. Arcurile pot fi direcționate sau
nedirecționate din cauza preze nței posibile a străzilor cu o singură cale sau a
costurilor diferite în fiecare direcție. Fiecare arc are un cost asociat, care este, în
general, lungimea sau timpul de deplasare care poate depinde de tipul de vehicul.

Pentru a cunoaște costul global al fiecărei rute, trebuie să fie cunoscute costul de
călătorie și timpul de călătorie între fiecare client și depozit. Pentru a face acest lucru,
graficul nostru original este transformat într -unul în care vârfurile sunt clienții și
depozitul, iar arcele sun t drumurile dintre ele.
Costul fiecărui arc este cel mai mic cost între cele două puncte din rețeaua de
drumuri originale. Acest lucru este ușor de făcut deoarece cele mai scurte probleme
ale căii sunt relativ ușor de rezolvat.
Aceasta transformă graficu l inițial slab într -un grafic complet. Pentru fiecare
pereche de noduri i și j, există un arc (i, j) al graficului complet al cărui cost este scris
ca C ij și este definit a fi costul celei mai scurte căi de la i la j. Timpul de călătorie t ij
este suma du ratelor de deplasare a arcurilor pe calea cea mai scurtă de la i la j pe
graficul de drum inițial.

Uneori este imposibil să satisfacem toate cerințele clientului, iar în astfel de
cazuri, solverii pot reduce cererile unor clienți sau pot lăsa unii clienți
nesupravegheați. Pentru a face față acestor situații, poate fi introdusă o variabilă
prioritară pentru fiecare client sau penalități asociate pentru parțial sau lipsit de
servicii pentru fiecare client dat .

Funcția obiectivă a unei VRP poate fi foarte d iferită în funcție de aplicarea
particulară a rezultatului, dar câteva dintre obiectivele mai comune sunt:

Reduceți la minim costurile globale de transport bazate pe distanța globală
parcursă, precum și costurile fixe asociate vehiculelor și șoferilor folosiți
Reducerea numărului de vehicule necesare pentru a servi toți clienții
Cea mai mică variație a timpului de deplasare și a încărcăturii vehiculului

Reduceți penalitățile pentru servicii de calitate scăzută.

Vehicle Routing Problem:

– Determinarea unui drum de cost minim care parcurge un set de locații și
satisface anumite restricții
Caz particular: problema comis voiajorului
TSP= determinarea unui ciclu hamiltonian de cost minim într -un graf complet

Reprezentarea soluțiilor:
1. Matrice binara de alocare (nxn):
Aij = 1 dacă nodul j e vizitat la etapa i
= 0 altfel
Restricții:
Fiecare linie conține exact un 1
Fiecare coloană conține exact un 1
Dimensiune spatiu: 2n*n
2. Permutare de ordin n:
pi = indicele nodului vizitat la etapa i
Restricții:
elementele lui p sunt distincte
Dimensiune spatiu: n! (de fapt (n -1)!/2

a.TSP b.VRP

traseu 3

traseu 2

un singur traseu traseu 1

:depozit
:client

Fig. 6 Schema ce ilustrează diferența dintre un program TSP si VRP

CAPITOLUL 3. Variabila Neighborhood Search

Variable Neighborhood Search (VNS) , propus de Mladenović , Hansen , 1997
este o metodă metaheuristic pentru rezolvarea unui set de optimizare combinatorică
și probleme de optimizare la nivel mondial . Acesta explorează cartiere îndepărtate
ale soluției curente , și se mută de acolo la o solutie nouă dacă și numai daca în cazul
în care s -a făcut o îmbunătățire. Metoda de căutare locală este aplicată în mod repetat,
pentru a obține soluții în vecinătate la valori maxime locale . VNS a fost proiectat
pentru soluții de aproximare a problemelor de optimiza re discrete și continue și în
funcție de acestea , se are în vedere pentru rezolvarea problemelor liniare ale
programului , probleme de program întreg , probleme de program întreg mixte ,
probleme de programe neliniare , etc.

VNS se schimbă în mod sistematic cartier în două etape :
– descendent pentru a găsi un loc optim și în cele din urmă ,
-o fază de perturbație pentru a iesi din valea corespunzătoare .

Solicitările sunt în creștere rapidă în număr și se referă la mai multe domenii :
teoria locației , analiza cluster , programare , rutare vehicul , de proiectare de rețea ,
lot – dimensionare , inteligenta artificiala, inginerie , punerea în comun a problemelor
, biologie , filogenia , fiabilitate , geometrie , proiectare de telecomunicații , etc. .

Heuristica VNS (căutare în vecinătăți variabile) este o metodă care aplică
explicit o strategie de schimbare dinamică a structurilor de vecinătate. Algoritmul are
un grad de generalitate ridicat și dispune de numeroase grade de libertate, fapt
pentru care există numeroase variante pentru diferite probleme tratate.

3.1 Variabila VRP

Există mai multe variante și specializări ale problemei de rutare a vehiculului:
Problema de rutare a vehiculului cu livrare și livrare (VRPPD): un anumit număr
de mărfuri trebuie mutat de la anumite locații de preluare la alte locații de livrare.
Obiectivul este de a găsi rute optime pentru o flotă de vehicule pentru a vizita locațiile
de preluare și decolare.
Problema de rutare a vehiculului cu LIFO: similar cu VRP PD, cu excepția faptului că se
aplică o restricție suplimentară la încărcarea vehiculelor: în orice locație de livrare,
elementul livrat trebuie să fie elementul cel mai recent preluat. Această schemă
reduce timpul de încărcare și descărcare la locurile de livrare, deoarece nu este

nevoie să descărcați temporar alte articole decât cele care ar trebui eliminate.
Problema de rutare a vehiculului cu timpul Windows (VRPTW): Locațiile de
livrare au ferestre de timp în care trebuie efectuate livrările (sau vizite le).
Capacitatea problemelor de rutare a vehiculelor: CVRP sau CVRPTW. Vehiculele au o
capacitate limitată de transport a mărfurilor care trebuie livrate.
Problema de rutare a vehiculului cu multiple călătorii (VRPMT): Vehiculele pot face
mai multe trasee.
Problema de rutare a vehiculelor deschise (OVRP): vehiculele nu trebuie să se
întoarcă la depozit.
Mai mulți furnizori de software au construit produse software pentru a rezolva
diferite probleme VRP. Numeroase articole sunt disponibile pentru mai multe d etalii
despre cercetarea și rezultatele lor.
Deși VRP este legat de problema de planificare a locurilor de muncă, cele două
probleme sunt de obicei rezolvate folosind diferite tehnici.

Lungimea traseului

backhauting
Serviciu mixt
Ferestre
de timp

Fig. 7 Schema ce ilustreaza problema de rutarea vehiculelor

3.2 Metode de soluție exacte

Există trei abordări principale diferite pentru modelarea VRP
Formularea fluxului vehiculului – aceasta folosește variabilele întregi asociate fiecărui
arc care numără de câte ori marginea este traversată de un vehicul. Acesta este, în
general, utilizat pentru VRP de bază. Acest lucru este bun pentru cazurile în care
costul soluției poate fi exprimat ca suma tuturor costurilor asociate arcurilor. Cu toate
acestea, nu poate fi folosit pentru a trata multe aplicații practice.
Comportamentul fluxului de mărfuri – variabi lele întregi adiționale sunt asociate
cu arce sau margini care reprezintă fluxul de mărfuri de -a lungul căilor trase de
vehicule. Acest lucru a fost folosit recent pentru a găsi o soluție exactă. CVRP DCVRP
VRPPD VRPT
W VRPB
VRPP
DTW VRPB
TW

Setarea problemei de partiționare – Acestea au un număr exp onențial de
variabile binare care sunt fiecare asociate cu un circuit fezabil diferit. VRP este apoi
formulat ca o problemă de partiționare setată care întreabă ce este colecția de circuite
cu cost minim care să satisfacă constrângerile VRP. Acest lucru pe rmite costuri foarte
generale de traseu.

3.3 Formularea fluxului vehiculului

Formularea TSP de către Dantzig, Fulkerson și Johnson a fost extinsă pentru a
crea cele două formulări ale fluxului vehiculului index pentru VRP

min ∑ ∑ 𝓬ij 𝔁ij
iϵV jϵV

∑ 𝔁ij = 1 ∀ j ∈ V \ {0}
iϵV

∑ 𝔁ij = 1 ∀ i ∈ V \ {0}
jϵV

∑ 𝔁i0 = K
iϵV

∑ 𝔁0j = K
jϵV

∑ ∑ 𝔁ij ≥ r(S) , ∀ S ⊆ V \ {0} ,S ≠∅
i∉S jϵS

𝔁ij ∈ {0, 1} ∀ i, j ∈ V

Constrângerile 1 și 2 indică faptul că exact un singur arc intră și exact unul
părăsește fiecare vârf asociat unui client, respectiv. Constrângerile 3 și 4 indică faptul
că numărul de vehicule care părăsesc depozitul este același cu nu mărul care intră în
depozit. Constrângerile 5 sunt constrângerile de reducere a capacității, care impun
conectarea rutelor și că cererea pe fiecare traseu nu trebuie să depășească
capacitatea vehiculului. În cele din urmă, constrângerile 6 sunt constrânger ile
integrității.

O constrângere arbitrară între constrângerile 2|V| este implicită de celelalte 2
|V| – 1 poate fi eliminat. Fiecare tăietură definită de un set de clienți S este traversată
de un număr de arce nu mai mic de r (s) (numărul minim de vehic ule necesare pentru
a servi setul S)

O formulă alternativă poate fi obținută prin transformarea constrângerilor de

reducere a capacității în constrângeri de eliminare subterană generalizată (GSEC).
∑ ∑ 𝔁ij ≤ |S| ̶ r(s)
iϵS jϵS

care impune ca cel putin r (s) arce sa paraseasca fiecare set de clienti S.

GCEC și CCC au un număr exponențial de constrângeri, astfel încât este practic
imposibil să se rezolve relaxarea liniară. O posibilă modalitate de a rezolva acest lucru
este de a lua în considerare un subgrup limitat al acestor constrângeri și de a adăuga
restul dacă este necesar.

O altă metodă este din nou utilizarea unei familii de constrângeri care au o
cardinalitate polinomială, cunoscute sub numele de constrângerile MTZ, ace stea fiind
inițial propuse pentru TSP și ulterior extinse de Christofides, Mingozzi și Toth.
ui ̶ uj ≥ dj ̶ C(1 ̶ xij ) ∀ i, j ∈ V \{0}, i ≠ j a.i. d i + d j ≤ C
0 ≤ u i ≤ C ̶ di ∀ i ∈ V \{0}

unde u i , i ∈ V \{0} este o variabilă continuă supli mentară care reprezintă
sarcina rămasă în vehicul după vizitarea clientului i și di este cererea clientului i.
Acestea impun atât conectivitatea, cât și cerințele de capacitate. Când 𝔁ij = 0
constrângere atunci i nu este obligatorie deoarece :
ui ≤ C s i uj ≥ dj intrucat 𝔁ij = 1 si impun u j ≥ ui + dj

Acestea au fost utilizate în mod extensiv pentru a modela VRP de bază (CVRP) și
VRPB. Cu toate acestea, puterea lor este limitată la aceste probleme simple. Ele pot fi
utilizate numai atunci când cost ul soluției poate fi exprimat ca suma costurilor pentru
costurile arcului. De asemenea, nu putem ști care vehicul traversează fiecare arc. Prin
urmare, nu putem folosi acest lucru pentru modele mai complexe, în cazul în care
costul sau fezabilitatea depind e de ordinea clienților sau a vehiculelor utilizate.

3.4 Manuală versus rutare automată optimă

Există multe metode de rezolvare manuală a problemei de rutare a vehiculelor.
De exemplu, rutarea optimă este o problemă de mare eficiență pentru stivuitoarele
din depozitele mari. Unele dintre metodele manuale de a decide asupra celei mai
eficiente rute sunt: cel mai mare decalaj, forma S, culoarul -culoar, combinat și
combinat +. În timp ce metoda combinată + este cea mai complexă, deci cea mai g reu
de utilizat de operatorii de camioane, aceasta este cea mai eficientă metodă de rutare.
Totuși, diferența procentuală dintre metoda manuală de rutare optimă și traseul
optim optim a fost în medie de 13%.

Y

N

N

N

Y

Fig. 7 Diagramă variabila neightborhood search Gaseste o solutie initiala x
Conditia de
oprire (timp
sau numarul
maxim de
iteratie) exit
K ⃪ 1
k ≤
kmax
Amestecare: generare un
punct x ’ at diferit de Nk(x) of
x
Cautare locala pentru VND:
gaseste cel mai bun vecin xⁱʲ
of x’ in Ni(x’) for i=1 ,….. imax
f(xⁱʲ)
<f(x)
x ⃪ xⁱʲ
k ⃪ 1 k ⃪ k+1

3.5 Structura variabilei neighborhood searh

Orice problemă combinatorică de optimizare necesită utilizarea unor tehnici
care permit o mai bună exploatare a spațiului soluției pentru a ajunge la soluții
aproape optime. Tehnicile de căutare locală utilizează o structură de vecinătate
pentru definirea unui set N de soluții candidate.
Prin urmare, orice soluție s0 este direct accesibilă de la s printr -o mișcare, deci
s0 2 N (s). Această structură de vecinătate este implementată într -o tehnică iterativă,
în scopul îmbunătăți rii calității soluțiilor, în funcție de funcția obiectivă a problemei.
Un aspect critic al proiectării unor algoritmi de optimizare este alegerea unei
structuri apropiate.
În patru structuri de cartier diferite au fost aplicate pentru căutarea unei soluții
aproape optimale a unei instanțe TSP:

O pereche adiacentă [21, 22, 23]: Un element din poziția i a unei soluții s este
selectat aleatoriu și este permutat cu elementul din poziția i + 1 a aceleiași soluții.

O pereche aleatoare [22, 24, 25]: Această stru ctură efectuează o singură
permutare între două elemente neadiacente ale lui s plasate în poziții aleatoare i și j.

O pereche adiacentă [21, 22, 23]: Un element din poziția i a unei soluții s este
selectat aleatoriu și este permutat cu elementul din poziț ia i + 1 a aceleiași soluții.

O pereche aleatoare [22, 24, 25]: Această structură efectuează o singură
permutare între două elemente neadiacente ale lui s plasate în poziții aleatoare i și j.

Două perechi adiacente [26]: Două elemente ale lui s în poziți i aleatoare i și j
sunt selectate și ele sunt schimbate cu elementele adiacente: Elementul în poziția i se
permutează cu elementul în poziția i + 1 și elementul în poziția j permută cu
elementul în poziția j + 1.

Două perechi aleatoare [25, 27, 28]: Această structură efectuează două
permutări între patru elemente neadiacente ale lui s plasate în poziții aleatorii i a; ib; ja
și j b. Elementul în poziția ia permut cu elementul în poziția i b și elementul în poziția j a
permută cu elementul în poziția j b.

VNS este un cadru pentru construirea euristicii pe baza schimbărilor sistematice
ale cartierelor, atât in faza de coborare, cât si pentru a găsi un minim local, iar intr -o
faza de perturbare să scape din valea corespunzătoare . VNS este capabil să se ocup e
de dimensiunile variabile ale vecinătății, datorită interacțiunii aleatorii a lui structuri
în timpul execuției, ceea ce îmbunătățește exploatarea spațiului soluției. În cele patru
structuri diferite de vecinătate descrise anterior au fost puse în aplica re pentru a
căuta soluții aproape optime ale instanțelor TSP utilizând o metodă VNS. Figura
prezintă structura acestei metode VNS :

Selecția VNS

NU

DA

NU

DA

Fig. 8 Schema de evoluție a metodei VNS propuse

Start
VNS
Generarea
matricei de cost
s <- soluție initială
Alegerea aleatorie
a tipului N(s)
O pereche
adiacentă O pereche
aleatorie Două perechi
adiacente Două perechi
aleatorii
s’ <- soluția
candidatului
f(s’)<f(
s)
s<- s’ Criteri
ul de
stop
atins
Sfârsit
VNS

3.6 Prezentarea algoritmului

Se alege un set de vecinătăți Nk, k = 1,…, kmax
s ← GenereazăSoluțieInițială()
while nu sunt îndeplinite condițiile de oprire do
k ← 1
while k < kmax do
s’ ← AlegeLaÎntâmplare( Nk(s))
s’’ ← LocalSearch( s’)
if (f(s’’) < f(s)) then
s ← s’’
k ← 1
else
k ← k + 1
endif
endwhile
endwhile

Algoritmul Variable Neighborhood Search

În faza de inițializare trebuie definită o mulțime de vecinătăți. Aceste
structuri pot fi alese arbitrar, dar de obicei se respectă relația între cardinale: |N 1| <
|N2| < … < |N kmax|. Apoi se generează o soluție inițială, se inițializează indexul
vecinătăților și algoritmul rulează până când condiția de oprire este îndeplinită. Mai
întâi se alege o soluție s’ din vecinătatea k a soluției curente s. Apoi are loc un proces
de căutare l ocală cu punctul inițial de căutare s’. Căutarea nu este restricționată de
setul de vecinătăți N k. Soluția returnată s’’ este comparată cu s și, dacă este mai
performantă, o va înlocui, iar algoritmul va porni din nou cu k = 1. În caz contrar, k se
increme ntează și se alege o nouă soluție s’.

VNS se bazează pe o schimbare sistematică a cartierelor pentru a scăpa de
optima locală și pentru a oferi o explorare largă a spațiului de căutare. După
proiectarea unui set de cartiere agitare și construirea unei sol uții inițiale, aceasta
constă în iterativ(i) agitând o soluție actuală, (ii) efectuarea unei căutări locale pe ea
și (iii) decizia de a o accepta ca o nouă companie care o ocupă sau nu. Numele
metodei provine de la faptul că vecinul folosit pentru faza de agitare se schimbă
sistematic în timpul procesului de căutare.

Presupunând cartiere numite N1; ….; N sunt proiectate, apoi căutarea începe cu
N1. Dacă nu se găsește nicio îmbunătățire atunci când se utilizează Nk (k 2 1;…),
atunci următorul carti er folosit pentru agitare va fi Nk + 1; pe de altă parte, de fiecare
dată când se constată o îmbunătățire, cartierul agitat este resetat la N1. VNS este
prezentată în Algoritmul 3.

După ce soluția inițială x este construită și parametrii sunt inițializați (linia 1 -3),
se generează un vecin aleator al lui x folosind cartierul Nk (linia 5). Folosim notația
suplimentară Nkr (x). Căutarea locală este efectuată pentru a îmbunătăți soluția la
x00 (linia 6). Dacă x00 trece decizia de acceptare, acesta devine noul titular (linia 7 –
8) și vecinul agitat este resetat la N1 (linia 9). Dacă noul titular îmbunătățește cea mai
bună soluție găsită x, atunci x este actualizat în consecință (linia 10 –11). În caz
contrar, dacă x00 nu reușește decizia de acceptare, căutarea co ntinuă cu următorul
cartier Nk + 1 (linia 12).

Pentru o introducere bună în VNS, consultați Hansen și Mladenovic ”[31]. O
practică obișnuită este utilizarea așa -numitelor cartiere cuiburi N1 N2; …; Nk. În acest
fel, cercetarea este părtinitoare către ca rtierele mai mici, iar cartierele mari sunt
utilizate numai atunci când cele mici nu reușesc să ofere o nouă soluție acceptabilă.

În ultimii ani, au fost dezvoltate o serie de metode VNS care integrează aspecte
adaptive. În majoritatea cazurilor, aspectul adaptiv privește faza de agitare: agitarea
se realizează diferit în funcție de context. De exemplu, în Pillac și colab. [60] și în
Stenger și colab. [74], metoda de agitare este selectată folosind o roată de ruletă în
care greutatea pentru fiecare cartier se bazează pe rata sa de succes în iterațiile
anterioare. În Polacek și colab. [63], dimensiunea cartierului, precum și rata de
acceptare a mișcărilor ascendente sunt adaptate automat prin căutare. Cu toate
acestea, există și alte posibilități. În Hsiao ș i colab. [38], de exemplu, bugetul CPU
alocat căutării locale este adaptat dinamic.

Nu există o abordare unificată pentru AVNS, prin urmare, vă sugerăm o schemă
generică în Algoritmul 4, care acoperă toate contribuțiile pe care le cunoaștem. Ea
implică me canisme de adaptare potențiale la toate cele trei etape ale oricărei iterații,
și anume agitarea (linia 4), căutarea locală (linia 6) și decizia de acceptare (linia 7).

Algorithm (Adaptive variable neighborhood search).

constructieHeuristică () x
while criteriu de oprire nu a fost indeplinit do
N selectShakin 1(history )
x0 Nr(x)
x00 localSearch (x0; history )
if acceptanceDecision (x; x00; history ) then
x x00
if z(x) < z(x ) then
xx
end if
end if
end while
return x

AVNS prezentat de Polacek și Colab are capacitatea de a se auto -adapta
parametrii cei mai influenți ai unui algoritm VNS: selectarea structurilor de vecinătate
și a parametrului de prag utilizat în decizia de acceptare. Pentru ambii parametri
auto-adaptați, un contor xi este utilizat pentru a obține succesul parametrului i. Dacă
se poate realiza o îmbunătățire, contorul special este mărit cu 1. Metoda roții de
ruletă selectează valorile parametrilor pentru fiecare parte definită a procesului de
soluție. Probabilitatea P (i) pentru fiecare valoare a parametrului i este calculată prin
următoarea funcție:

P(i) = P ln(xi)
8 j 2 j2 ln(xj)

unde descrie setul tuturor valorilor de parametri posibile ale fiecărui parametru
auto -adaptabil. Pentru a evita dominarea unei setări specifice de parametri, se aplică
logaritmul natural. În comparație cu versiunea anterioară VNS, Polacek și colab. [64]
fără parametrii de auto -adaptare, se poate obține o îmbunătățire medie de 0: 28%.

Hosny și Colab utilizează , de asemenea, o strategie simplă de adaptare pentru
dimensiunea cartierului. Autorii execută rulări VNS în mod repetat, în timp ce soluția
inițială este soluția finală a rulării anterioare VNS. Ei află că la începutul întregului
proces de soluție, care cu prinde mai multe rulaje, dimensiunile mai mari de cartier
oferă rapid îmbunătățiri, în timp ce mai târziu cartierele mai mici par să fie mai
benefice.

După fiecare rulare VNS, dimensiunea cartierului este redusă cu un sfert din
dimensiunea maximă inițial ă a vecinătății, până când se atinge limita inferioară
predefinită a unui sfert din dimensiunea inițială a vecinătății. Dimensiunea inițială a
vecinătății este setată la 2 pn, unde n este numărul total de noduri. O execuție AVNS
se oprește după un număr fi x de iterații sau un număr dat de iterații care nu
îmbunătățesc.

Cu alte cuvinte, mai multe rulaje VNS pot fi interpretate ca o rulare VNS cu
reducerea dimensiunii maxime de vecinătate după un număr dat de iterații sau un
număr fix de iterații care nu îm bunătățesc. Se obțin îmbunătățiri de până la 3% în
comparație cu algoritmul genetic din Zhao și colab.

Recent, Stenger și colab. prezintă un algoritm AVNS obținut prin încorporarea
unui mecanism adaptativ inspirat din metoda roții de ruletă în ALNS din P isinger și
Ropke [62], care este descris în secțiunea 3. Datorită metodei de selecție a roților,
AVNS ghidează agitare pas spre zonele în care se așteaptă soluții de înaltă calitate
prin părtinirea pasului de agitare aleatorie a VNS În special, autorii def inesc două
decizii de selecție care sunt independent formate în mod independent: (i) o selecție a
rutei alege rutele care urmează să fie implicate și (ii) o selecție a clienților alege
clienții care vor fi schimbați. În total, sunt utilizate 51 de structur i de cartier diferite.

După aplicarea unei metode în faza de agitare, un sistem de notare evaluează
succesul fiecărui cartier i într -un segment de 30 de iterații și adaugă scoruri la
contorul xi: (i) se adaugă un scor de nouă ori de câte ori se găsește o nouă soluție
generală. , (ii) se adaugă un scor de trei, dacă soluția actuală este îmbunătățită și (iii)
se adaugă un scor al unuia dacă soluția este mai slabă decât cea curentă, dar este
acceptată de criteriul de recoacere simulat.

Capitolul 4 .Prezentarea Programului

Orientare:

1. Extras și Copiați toate fișierele ( 4 fișiere) din arhiva.rar în dosarul implicit
Matlab
2. O problema VRP , de exemplu, aici ( 10 clienti ) , de exemplu, în cazul în care
aveți capacitate de 50kg in vehicul , astfel încât încercați să ruleze la ferestre de
comandă :NIAlgVRP ( Problem25,100 )
3. Desigur, puteți modifica capacitatea adica 75 , 150 , etc , și U poate
crea o nouă problemă VRP , explicația problemei este în Problem25 .m
4 Puteți modifica , de asemenea, imaginea , u poate regla limita
coordonate , aici am folosit
coordonate x = 0 până la x = 100 , y = 0 până la y = 100 .
Setarea este în configurație NIAlgVRP.m
5. Descrierea fișierelor :
==================================
1. NIAlgVRP : Cel mai apropiat de inserție Algoritmul de rezolvare a
problemelor de rutare a vehiculelor
2. ConstEvalVRP : Constrângere Evaluarea VRP
3. Problem25 : problema VRP este format din 20 de noduri , cereri și
poziția de coordonate
4. Hartă : harta

4.1 Algoritmul NIAlgVRP

function []=NIAlgVRP(Problem,Capacity)

%Matricea distanta de formulare
xy=[Problem(:,2) Problem(:,3)];
[n m]=size (Problem);
a = meshgrid(1:n);
d = reshape(sqrt(sum((xy(a,:) -xy(a',:)).^2,2)),n,n);

%Detalii algoritm Cel mai apropiat vecin
%Pas 1 : Incepeti cu [1 1] ,1 este depozitul
%Pas 2 :Examinati toate livrarile care nu au fost servite ,acestea vor fi
%disponibile si cele indisponibile
%Pas 3 :Pentru livrarile disponibile ,alege cea mai buna livrare,pentru
%distanta minima ,inserati ruta si pozitia dupa ultima livrare .
%Step 4 :Repetati pasul 2 si 3 daca nu sunt livrari disponibile.
%Step 5 :in cazul in care nu sunt livrari posibile se creaza o noua ruta[1
%1] si se repeta pasii 1 -4.
%Step 6 :faceti toate etapele pana cand toate magazinele sunt servite.
Demand=Problem(:,4);

if Capacity<max(Demand)
fprintf('Capacitatea vehiculului nu e disponibila \n')
return
end

%algoritmul de cautare a celui mai apropiat vecin de insertie
RouteNow=[1 1]; %inceputul constructiei de rute
UnservedOutlet=2:length(d);
Routes={[]};
while length(UnservedOutlet)>0
FeasibleOutletToInsert=[];

%set format din livrari ce pot fi inserate care sunt deja existente
Distance=[];
for NumberOfOutletNotYetInserted=1:length(UnservedOutlet);
CandidateToInsert=UnservedOutlet(1,NumberOfOutletNotYetInserted);
Route=[RouteNow(1:end -1) CandidateT oInsert 1];
[NumberOfVehicles, TotalDistance, RouteSets]=ConstEvalVRP(Problem,Route,Capacity);

%problema rutarii vehiculelor/ConstEvalVRP
if NumberOfVehicles>1
FeasibleOutletToInsert=FeasibleOutletToInsert;
Distance=Distance;
Else

%Seturile livrarilor posibile pentru insertie
FeasibleOutletToInsert=[FeasibleOutletToInsert CandidateToInsert];
Distance=[Distance TotalDistance];
End

%Informatii despre distanțele după ce examinăm toate livrarile posibile
End

%Alege o livrare care are distanta minima intercalata
if length(FeasibleOutletToInsert)>=1;
[ShortestDistance idx]=min(Distance);
best_FeasibleOutletToInsert=FeasibleOutletToInsert(idx);
g=find(UnservedOutlet(:)==best_FeasibleOutletToInsert);
UnservedOutlet(g)=[];
RouteNow=[RouteNow(1:end -1) best_FeasibleOutletToInsert 1];
End

%Dac a nu exista mai multe livrari posibile , se creeaza o noua ruta [1 1]
if length(FeasibleOutletToInsert)==0 | length(UnservedOutlet)==0;
RouteFixed=RouteNow;
Routes{end+1}=[RouteFixed];
RouteNow=[1 1];
end
end

NumberOfRoutes=length(Routes);
SetsOfNumberOfOutletsInRoute=[];
for RoutesIndex=1:NumberOfRoutes
NumberOfOutletsInRoute=length(Routes{1,RoutesIndex});
SetsOfNumberOfOutletsInRoute=[SetsOfNumberOfOutletsInRoute NumberOfOutletsInRoute];
end
ttt=find(SetsOfNumberOfOutletsInRoute(:)<=2);
Routes(ttt)=[];
n=length(Routes);
for RouteIndex=1:n
Route_VRP=Routes{1,RouteIndex}
r=length(Route_VRP);
jum=0;
for t=1:r -1,
subrute=jum+(d(Route_VRP(t),Route_VRP(t+1)));
jum= subrute;
end
DistanceSets(RouteIndex,:)=[jum];
TotalDistance=sum(DistanceSets);
end
NumberOfRoutes=n
TotalDistance=TotalDistance
img = imread ('map.jpg'); %<==Numele fișierului hărții dvs.
min_x = 0;
max_x = 100;
min_y = 0;
max_y = 100;
x=Problem(:,2);
y=Problem(:,3);
figure
x_min = min_x;
x_max = max_x;
y_min = min_y;
y_max = max_y;
imagesc ([x_min x_max ], [y_min y_max], img);

%Colorarea Liniilor
for tyt=1:n
hold on
shortestPath=Routes{1,tyt};
colour=mod(tyt,6);
xd=[x(shortestPath)];
yd=[y(shortestPath)];
for i=2:length(shortestPath) -1
text(xd(i),yd(i),[' Livrare ',num2str(shortestPath(i))]);
end

text(xd(1),yd(1),[' Depozit ']);
if colour==1
plot(xd,yd,' -cs','LineWidth',2 ,'MarkerEdgeColor','k',…
'MarkerFaceColor','g',…
'MarkerSize',10)
plot(x(1),y(1),'MarkerEdgeColor','k',…
'MarkerFaceColor','k',…
'MarkerSize',10)
hold on
elseif colour==2
plot(xd,yd,' -rs','LineWidth',2,'MarkerEdgeColor','k',…
'MarkerFaceColor','r',…
'MarkerSize',10)
plot(xd(1),yd(1),'MarkerEdgeColor','k',…
'MarkerFaceColor','k',…
'MarkerSize',10)
hold on
elseif colour==3
plot(xd,yd,' -ys','LineWidth',2,'MarkerEdgeColor','k',…
'MarkerFaceColor','y',…
'MarkerSize',10)
plot(xd(1),yd(1),'MarkerEdgeColor','k',.. .
'MarkerFaceColor','k',…
'MarkerSize',10)
hold on

elseif colour==4
plot(xd,yd,' -ks','LineWidth',2,'MarkerEdgeColor','k',…
'MarkerFaceColor','w',…
'MarkerSize',10)
plot(xd(1),yd(1),'MarkerEdgeColor','k',…
'MarkerFaceColor','k',…
'MarkerSize',10)
hold on
elseif colour==5
plot(xd,yd,' -bs','LineWidth',2,'MarkerEdgeColor','k',…
'MarkerFaceColo r','b',…
'MarkerSize',10)
plot(xd(1),yd(1),'MarkerEdgeColor','k',…
'MarkerFaceColor','k',…
'MarkerSize',10)
hold on
elseif colour==0
plot(xd,yd,' -ms','LineWidth',2,'MarkerEdgeCo lor','k',…
'MarkerFaceColor','m',…
'MarkerSize',10)
plot(xd(1),yd(1),'MarkerEdgeColor','k',…
'MarkerFaceColor','k',…
'MarkerSize',10)
hold on

end
end
title([' Distanta Totala = ',num2str(TotalDistance),'
%Numarul de rute = ',num2str(NumberOfRoutes)])

4.2Evaluatorul

function [NumberOfVehicles, TotalDistance, RouteSets]=ConstEvalVRP(Problem,Route,Capacity);
%formularea matricei de distanta

xy=[Problem(:,2) Problem(:,3)];
[n m]=size (Problem);
a = meshgrid(1:n);
d = reshape(sqrt(sum((xy(a,:) -xy(a',:)).^2,2)),n,n);

Demand=Problem(:,4);
[aa,bb]=size(Route);
for hh=1:aa
ee=1;
cc=2;
while hh<=aa && cc<bb
ff=2;
Routes{hh,ee}(1)=1;
Load(hh,ee)=0;
while Load(hh,ee)<=Capacity && cc<bb
if (Load(hh,ee)+Demand(Route(hh,cc)))>Capacity
break
end
Routes{hh,ee}( ff)=Route(hh,cc);
Load(hh,ee)=Load(hh,ee)+Demand(Route(hh,cc));
cc=cc+1;
ff=ff+1;
end
Routes{hh,ee}(ff)=1;
ee=ee+1;
end
hh=hh+1;
end

NumberOfVehicles=length( Routes);
RouteSets=Routes;
n=length(Routes);
for RouteNumber=1:n
Route_VRP=Routes{1,RouteNumber};
r=length(Route_VRP);
jum=0;
for t=1:r -1,

subrute=jum+(d(Route_VRP(t),Route_VRP(t+1)));
jum=subrute;
end
DistanceSets(RouteNumber,:)=[jum];
TotalDistance=sum(DistanceSets);
end
TotalDistance=TotalDistance;

4.3. Problema cereri ,livrari,noduri:

function [Problem]=Problem25()
%Coloana 1 = numarul de livrari,Numarul 1 este depozitul
%Coloana 2 = coordona tele x ale livrarii
%Coloana 3 = coordonatele y ale livrarii
%Coloana 4 = incarcatura coletului/cererea(greutatea) ,depozitul=0

Problem=…
[ 1 20.00 50.00 0.00
2 15.00 68.00 10.00
3 47.00 79.00 15.00
4 32.00 33.00 10.00
5 22.00 45.00 20.00
6 57.00 35.00 10.00
7 30.00 14.00 10.00
8 45.00 19.00 2 0.00
9 28.00 54.00 30.00
10 14.00 58.00 20.00
11 25.00 28.00 25.00
12 25.00 77.00 25.00
13 36.00 65.00 15.00
14 28.00 33.00 15.00
15 19.00 16.00 15.00 ];
%16 85.00 20.00 20.00
%17 90.00 54.00 30.00
%18 78.00 98.00 20.00
%19 65.00 26.00 20.00
%20 55. 00 10.00 20.00 ];

4.Se alege harta pentru traseu.

Prezentarea rezultatelor :
1.Coordonate alese in functie de harta:

Fig.5

Fig.6

Concluzii

O problema VRP cu 15 clienti , de exemplu, în cazul în care
aveți capacitate de 50kg in vehicul , astfel încât încercați să ruleze la ferestre de
comandă :NIAlgVRP ( Problem25,100 )
Desigur, puteți modifica capacitatea adica 75 , 150 , etc , și U poate
crea o nouă problemă VRP , explicația problemei este în Problem25.m
aici am folosit coordonate x = 0 până la x = 100 , y = 0 până la y = 100 .
Setarea este în configurație NIAlgVRP.m
NIAlgVRP : Cel mai apropiat de inserție Algoritmul de rezolvare a problemelor
de rutare a vehiculelor
ConstEvalVRP : Constrângere Evaluarea VRP
Problem25 : problema VRP este format din 20 de noduri din care 10 folosite ,
cereri și poziția de coordonate
Hartă : harta

Bibliografie

[1] https://ro.wikipedia.org/wiki/Tranzistor ,
[2] https://books.google.ro/books?id=sDXvCQAAQBAJ&pg=PR6&dq=routing+vehicle+wi
th+neighborhood+search&hl=ro&sa=X&ved=0ahUKEwiM65rRovXiAhVKIlAKHaDhCvI
Q6AEILzAB#v=onepage&q=routing%20vehicle%20with%20neighborhood%20searc
h&f=false
[3] https://books.googl e.ro/books?id=P –
HpBwAAQBAJ&printsec=frontcover&dq=metaheuristic+neighborhood+search&hl=ro
&sa=X&ved=0ahUKEwjh75vpofXiAhULJ1AKHajPCcEQ6AEIZzAJ#v=onepage&q=meta
heuristic%20neighborhood%20search&f=false
[4] http://staff.fmi.uvt.ro/~daniela.zaharie/am2016/curs/curs1/metaeuristici2016_slid
es1.pdf
[5] https://pdfs.semanticsch olar.org/5373/1072b47dcdd7d2be4419e90304c35cdc5349
.pdf
[6] https://ieeexplore.ieee.org/document/6996867
[7] https://link.spri nger.com/chapter/10.1007/978 -3-319 -07617 -1_2
[8] https://www.researchgate.net/publication/328870263_A_ composite_very -large –
scale_neighborhood_search_algorithm_for_the_vehicle_routing_problem
[9] https://www.wiley.com/en -ro/Metaheuristics+for+Vehicle+Routing+ Problems -p-
9781848218116
[10] https://books.google.ro/books?id=sDX vCQAAQBAJ&pg=PR6&dq=routing+veh
icle+with+neighborhood+search&hl=ro&sa=X&ved=0ahUKEwiM65rRovXiAhVKIlAKH
aDhCvIQ6AEILzAB#v=onepage&q&f=false
[11] https://books.google.ro/books?id=sEN4DQAAQBAJ&printsec=frontcover&dq=
metaheuristic&hl=ro&sa=X&ved=0ahUKEwi9jOK7ofXiAhVNL1AKHcNNCvYQ6AEIXTA
G#v=onepage&q=metaheuristic&f=false