1
1. UVOD:
U poslovnom svijetu zahtjevi za povećanom brzinom i učinkovitošću prezentirani su
izravno u djelokrugu transporta i logistike. Tomu postoje mnogi razlozi, a najočitiji je sve veća
prisutnost transporta i logistike. Ne postoji djelatnost, a ni ljudska aktivnost koja nije u
direktnom ili indirektnom odnosu s transportnim aktivnostima i potrebama. Ekonomski rast,
promjene u fiskalnoj politici, elektroničko poslovanje, zaštita korisnika, zaštita okoliša i mnoge
druge stvari, faktori su koji potiču potrebe za robama i uslugama. Gdje god postoje logističke
potrebe pronaći ćemo i odgovarajuće prometne zahtjeve, a gdje su zahtjevi počinju i problemi.
Problem usmjeravanja vozila se u posljednje vrijeme počeo sve više razmatrati zbog sve većih
zahtjeva gospodarstva za uštedama u transportu. Budući da se radi o složenim kombinatornim
problemima, informatizacija je neizbježna. Racionalizacijom prijevoznih procesa moguće je
ostvariti znatne uštede. Cilj racionalizacije je poboljšati plan prijevoza odnosno pronaći skup
ruta koje će smanjiti ukupne troškove prijevoznog procesa, pri čemu se troškovi reflektiraju u
ukupnoj duljini puta, broju upotrijebljenih vozila ili vremenu potrebnom da se cijeli posao
obavi.
Zato ćemo ovdje vidjeti kako se planiraju i određuju rute transporta, a da se pri tom
zadovolje svi današnji strogi kriteriji.
2. IZLAGANJE TEMATIKE:
3
Određivanje najpovoljnijeg puta, kojeg koristi grupa vozila prilikom posluživanja
skupa korisnika predstavlja problem na operativnoj razini tehnologije transporta. Promjenama
planova ruta vozila pri distribuciji dobara i usluga moguće je smanjiti transportne troškove.
Zbog velikog broja mogućih ruta, optimalnu rutu (osim za manji broj ruta) nije moguće pronaći
egzaktnim metodama. Korištenjem heurističkih metoda moguće se je približiti optimalnom
planu ruta. U praktičnoj upotrebi, metode optimizacije je potrebno često modificirati i
provjeravati njihovu uspješnost. U radu je predložen programski jezik i razvojna okolina za
izradu konstruktivnih heurističkih algoritama. Heurističke metode raspravljene su sa stanovišta
njihove upotrebljivosti u praktičnoj primjeni i testirane na standardnim ispitnim zadacima u
novo razvijenom programskom okruženju za konstrukciju, ispitivanje i parametrizaciju
heurističkih algoritama. Metode su uspoređene s vodećim heurističkim metodama i
upotrebljene za rješavanje problema rutiranja grupe vozila u realnom transportnom okruženju.
Programsko razvojno okruženje, povezano je s geoinformacijskim sustavom. Izrađen je i
programski sustav koji u realnom transportnom okruženju predlaže nove planove ruta. Analiza
rezultata optimizacije izvedena je na temelju usporedbe ruta koje se obavljaju prema radnim
nalozima u postojećem sustavu vožnje i ruta dobivenih heurističkim algoritmom. Rezultati
ukazuju na opravdanost upotrebe predloženog sustava za optimizaciju ruta grupe vozila u cilju
predlaganja novih ruta koje obavljaju isti posao uz vidne uštede. Planiranje ruta mora sadržavati
informacije o svim logističkim parametrima transportnog procesa, od vremena početka
dostavljanja, vremena vožnje do svake prodajne lokacije, vremena iskrcavanja robe i popratnih
vozačevih aktivnosti, planiranja „praznog hoda“ i detaljne evidencije planiranog i realiziranog
radnog vremena. Tijekom planiranja transporta dispečer mora imati tablični, kartografski i
kronološki pregled uvjeta skladišta u okviru kojih djeluje, brzine prijevoznih sredstava te
pregled mjesta dostave – kapaciteta tereta i radnog vremena skladišta i vozača – raspoloživosti
vozila i vozača, točne lokacije skladišta i mjesta dostave, obujam i prioritet dostave i konačno
raspored dostave. Na taj način proces planiranja je značajno brži i kvaliteta transporta prelazi na
puno višu razinu.
3.1. OPIS PROBLEMA USMJERAVANJA VOZILA (VRP)
4
Određivanje najpovoljnijeg puta, kojeg koristi grupa vozila prilikom posluživanja
skupa korisnika predstavlja problem usmjeravanja vozila, u daljnjem tekstu VRP (Vehicle
Routing Problem)
2
. Prvo spominjanje ovog prometnog problema zabilježeno je 1959. godine.
Povod proučavanja ovog kombinatoričko-optimizacijskog problema bio je unapređenje
organizacije dostave goriva benzinskim crpkama. Tada su Dantzig i Ramser prvi put predložili
matematičku interpretaciju problema i algoritamski pristup rješavanju [20]. Clark i Wright su
1964. g. predložili poboljšanje Dantzig-Ramserovog
3
pristupa kroz heuristička rješenja koja
koriste "pohlepne" (greedy)
4
algoritme. Na tragu ovih pristupa razvijeno je više od stotinu
modela i algoritama za dobivanje optimalnih i aproksimativnih rješenja. Sa današnjim stanjem
tehnologije i s trenutno najdjelotvornijim egzaktnim algoritmima moguće je riješiti problem
usmjeravanja vozila samo u slučajevima gdje imamo manje od 50 korisnika, i to na način da se
do optimuma kod najvećih problema može doći samo za pojedine slučajeve. Realni problemi
koje je potrebno rješavati imaju znatno više korisnika, pa se pomoću egzaktnog pristupa ne
mogu riješiti u prihvatljivom vremenu. Zato se za rješavanje koristi heuristički pristup koji
dovodi do približno optimalnog rješenja u realnom vremenu. Da bi definirali VRP za
distribuciju ili prikupljanje dobara, potrebno je dati osnovna ograničenja problema. U zadanom
vremenu, skup vozila poslužuje skup korisnika. Vozila kreću iz skladišta i pri transportu koriste
mrežu prometnica. Rješenje problema predstavlja skup ruta. Svaka ruta ima polaznu i završnu
točku u skladištu vozila koje koristi rutu. Svi zahtjevi korisnika moraju biti ispunjeni, a sva
nametnuta ograničenja poštovana. Cilj je da ukupni transportni trošak bude minimalan. Moguće
je uvoditi različita ograničenja i ciljeve koji mogu izravno utjecati na konstrukciju ruta prilikom
optimizacijskog procesa. Mreža prometnica koja se koristi za transport dobara najčešće se
opisuje grafom čiji lukovi predstavljaju prometnice, a točke raskrižja, skladišta ili korisnike.
Lukovi mogu biti jednosmjerni ili dvosmjerni, a uz svaki luk postoji cijena koja najčešće
korespondira sa udaljenošću i vremenom putovanja koje je ovisno o tipu vozila. Informacije
potrebne za dobar opis korisnika pri rješavanju VRP su:
- polazna točka koja predstavlja skladište,
- količina dobara, moguće je da postoji više tipova dobara, koje je potrebno prikupiti ili
dostaviti,
2
Toth P., Vigo D.: The Vehicle Routing Problem, SIAM, Philadelphia, 2002.
3
Toth P., Vigo D.: The Vehicle Routing Problem, SIAM, Philadelphia, 2002.
4
Toth P., Vigo D.: The Vehicle Routing Problem, SIAM, Philadelphia, 2002.
