Pregled evolucijskih algoritama pogodnih za rješavanje odabranih optimizacijskih problema

Problem Rutiranja Vozila (VRP)

Vehicle Routing Problem (VRP) je klasični problem optimizacije koji uključuje određivanje najefikasnijih putnih ruta za flotu vozila s ciljem isporuke do više odredišta. Ovaj problem ima širok spektar primjena u logistici, distribuciji i transportu.

S obzirom na veličinu logističke industrije, prirodno se pojavio problem zasićenja prometnica, no i problem optimizacije. Planiranje transportnih ruta postaje sve važnije kako bi se smanjili logistički troškovi i svaki postotak izrazito je vrijedan. Dakle, u posljednjim stoljećima postoji velika potražnja i ulaganja u optimizaciju planiranja efektivnih ruta ovisno o raznim čimbenicima. Inherentno VRP razvrstava se prema svojim karakteristikama i praktičnoj primjeni. Generalno govoreći, VRP određen je uvjetima ograničenja (npr. veličina flote), brojem početnih točaka, brojem ciljnih točaka...

Faktori koji utječu na razvoj iste su:

• težina puta (distanca između odredišta)
• početna točka
• flota vozila
• kakvoća robe

Ciljevi provođenja algoritama i optimizacije istih je minimizacija troškova transporta (i resursa generalno ovisno o zadanim ograničenjima). Resurs može predstavljati broj vozila, potrošnja goriva, broj aktivnih ljudi odnosno prijevoznika, potencijalni penali zbog neizvršavanja usluge unutar traženih parametara… Učestalije analize provode se na VRP sa sljedećim ograničenjima: s ograničenim kapacitetom, sa specifičnim vremenskim prozorima, s podjelom potražnje i dinamičkim VRP. Odredit će se kako se problemi grupiraju te pokušati naći sličnosti u srodnima te simultano razjasniti algoritam za svaki od navedenih.

Matematička formulacija

CVRP se može formulirati kao linearni cijelobrojni programski model. Ukupna udaljenost rute, gdje su zadovoljeni zahtjevi svih kupaca, treba biti minimizirana.

Binarna varijabla \( x_{ijk} \) ima vrijednost 1 ako je luk od čvora \( i \) do čvora \( j \) u optimalnoj ruti i vozi ga vozilo \( k \).

Pri čemu nema putovanja od čvora do samog sebe: \( x_{iik} = 0 \) za sve \( k \in \{1,...,p\} \) i \( i \in \{1,...,n\} \).

Parametar \( d_{ij} \) opisuje udaljenost od čvora \( i \) do čvora \( j \). Postoji \( n \) čvorova (depo = 1) i \( p \) vozila. Ciljna funkcija može biti formulirana kako slijedi:

\( \min \sum_{k=1}^{p} \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij} x_{ijk} \)

Svaki čvor treba biti unesen i napušten jednom (osim za depo) i to istim vozilom. Depo treba biti napušten i unesen jednom od strane svakog vozila. \( q_i \) opisuje zahtjev svakog kupca i \( Q \) je kapacitet vozila. Zbroj zahtjeva svih kupaca koje vozilo \( k \) treba poslužiti, ne smije premašiti kapacitet vozila \( k \).